Знакомство с указателями в Паскале
Всем читателям habr.com, привет! Мы студенты Технического ВУЗа- Мария и Екатерина, и хотим рассказать о своем опыте работы с указателями на языке программирования Паскаль.
Знакомство с указателями произошло еще на первом курсе, когда нам читали предмет по языку программирования Паскаль. Данная тема нас заинтересовала, поэтому мы изучили множество статей и учебной литературы. Отметим, не нашли ни одной, в которой довольно подробно, понятно и, главное, доступно для людей любого уровня знаний было бы рассказано об использование указателей в Паскале. Безусловно, информация по этой теме имеется в интернете, но она разрознена и большинство авторов сложно доносят информацию для неподготовленного читателя, который только начинает путь программиста.
Как показывает практика, тема указателей сложна для понимания, именно поэтому у нас родилась идея — написать публикацию о работе с динамической памятью и указателями, чтобы любому, увидевшему данную статью, подобная тема стала ясна.
Виды памяти в языке программирования Паскаль
Оперативная память ПК представляет собой совокупность элементарных ячеек для хранения информации — байтов, каждый из которых имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти.
Существует много различных видов оперативной памяти. Все эти виды можно разделить на две подгруппы — статическая память (Static RAM) и динамическая память (Dynamic RAM). Когда говорится о видах памяти, имеются в виду способы организации работы с ней, включая выделение, освобождение памяти и методы доступа.
Статическая память
Статическая память — это память, которая выделяется до начала работы программы, на стадии компиляции и сборки.
Компиляция — это преобразование программы, составленной на исходном языке высокого уровня (одним из которых является Паскаль — процедурно-ориентированный язык программирования высокого уровня), в эквивалентную программу на низкоуровневом языке или машинном коде (Машинный код — это двоичные числа, выражающие команды процессора и данные, которые нужно обработать. Его трудно понять и проводить в нем какие-то корректировки).
Сборка — процесс получения информационного продукта из исходного кода. Чаще всего сборка — исполняемый файл — двоичный файл, содержащий исполняемый код (машинные инструкции) программы или библиотеки.
- статические переменные имеют фиксированный адрес, известный до запуска программы и не изменяющийся в процессе ее работы.
- доступ к статическим переменным осуществляется через их имена.
- статические программные объекты порождаются автоматически перед выполнением программы или подпрограммы, в которой они описаны, и существуют, пока выполнение этой программы или подпрограммы не завершится. Размер статических объектовне изменяется на протяжении всего времени их существования.
Примером статического объекта в языке Паскаль является переменная, описанная в блоке программы или подпрограммы (процедуры, функции).
Приведем пример статического объекта:
var n: integer; begin n:=32; end.Такое объявление порождает статическую переменную целого типа.
Динамическая память
Динамическая память — это оперативная память, которая выделяется в процессе компиляции программы. При динамическом размещении заранее не известны ни тип, ни количество размещаемых данных, к ним нельзя обращаться по именам, как к статическим переменным. Программа может захватывать участки динамической памяти нужного размера. После использования ранее захваченный участок динамической памяти следует освободить.
Под динамическую память отводится пространство между статической памятью и стеком. Обычно стек располагается в старших адресах виртуальной памяти и растет в сторону уменьшения адресов. Программа и константные данные размещаются в младших адресах, выше располагаются статические переменные. Пространство выше статических переменных и ниже стека занимает динамическая память:
Динамическую память обычно используют при:
- обработке больших массивов данных
- разработке САПР (Система Автоматизации Проектных Работ)
- временном сохранение данных при работе с графическими и звуковыми средствами ЭВМ
К таким объектам относят:
- файлы (текстовые, типизированные, нетипизированные)
- линейные структуры
- односвязные (очередь, стек, список и т.д.)
- многосвязные (многосвязный список)
Управление динамической памятью связано с использованием ссылочного типа данных. Величины, имеющие ссылочный тип, называют указателями.
Указатели простейшие действия с ними
Указатель — это переменная, которая содержит адрес другой переменной (байта памяти).
Объявление указателей
var p:^integer;Где «^» означает, что задаётся указательный тип, а затем идет имя любого стандартного или ранее описанного типа.
Операции над указателями
Для работы с указателем объявим еще одну переменную, но уже не указательного типа (строка 3).
var p:^integer; n:integer; k:^integer; k1:integer; y1:^integer; y2:^integer; y3:^integer; begin n:=5; p:=@n; writeln('адрес n:',@n); writeln('значение n:',n); writeln('адрес p:',@p); writeln('значение p:',p); writeln('Разыменование или получения значения по адресу,который содержит p в качестве значения:',p^); k:=@k1; k^:=9; writeln('Разыменование или получения значения по адресу,который содержит k в качестве значения:',k^); writeln(); If k^=p^ then begin writeln('значения переменных, расположенных по разным адресам, одинаковое'); writeln('значение p:',p); writeln('значение k:',k); end; If k^<>p^ then begin writeln('значения переменных, расположенных по разным адресам, разные'); writeln('Разыменование k:',k^); writeln('Разыменование p:',p^); end; writeln(); y2:=@n; y1:=y2; writeln('Разыменование y1:',y1^); writeln('Разыменование y2:',y2^); writeln(); y3:=nil; writeln('Значение y3:',y3); end.- В строках 11, 12, 14, 17, 36: мы получаем адрес переменной, используя символ «@».
- В строках 16, 19, 21, 28 и т.д.: мы получаем значение переменной по её адресу, используя символ «^». Данная операция называется «разыменование». (Разыменование это операция получения значения объекта, адрес которого хранится в указателе). Добавим в нашу программу две переменные: типа указатель — k и целое k1 (строки 4,5).
- В строках 10, 11, 17 и т.д.: мы используем операцию «присваивания».Присвоить можно:
- значение того же типа, что и указатель (строка 36, 37)
- адрес другой переменной (строка 11, 17)
- специальное значение, которое называется пустой указатель и обозначается служебным словом nil (Оно не связано ни с каким объектом, т.е. ни на что фактически не указывает, строка 41)
- значение типа, на который указывает указатель (строка 18)
- В строке 21: мы сравниваем указатели на «равенство».
- В строке 28: мы сравниваем указатели на «неравенство».
Процедуры для работы с указателями
Первым шагом после объявления переменной типа указатель (строка 2) является процедура выделения памяти, которая обозначается new(указатель). Данная процедура имеет один параметр (строка 4).
var p:^integer; begin new(p); end.После применения процедуры new под переменную p выделилась память.
*Для более лучшего усвоения материала будем графически изображать указатели. На схеме точка будет ставиться точка у указателя и рисоваться стрелка для связывания его с соответствующим объектом.
Объект, созданный с помощью new в процессе выполнения программы или подпрограммы, существует вплоть до завершения основной программы, или до тех пор, пока он не будет уничтожен явно. При создании объекта указатель на него помещается в переменную, являющуюся фактическим параметром оператора вызова процедуры new.
В начальный момент выполнения программы переменная p не имеет никакого значения:
После создания динамического объекта указатель на него автоматически присваивается переменной p. Схематично результат изображается следующим образом:
Переменная p теперь «указывает» на объект целого типа, поэтому саму указательную переменную тоже называют указателем. Заметим, что параметр процедуры new однозначно определяет, какого типа объект порождается. В данном случае из описания типа переменной p следует, что порождается объект типа integer. Отметим, что порождаемые объекты не имеют никакого начального значения.
Для освобождения динамического памяти, на которую указывает указатель применяется процедура удаления dispose(указатель) (строка 8). Параметр в этой процедуре должен быть указатель на уже существующий динамический объект, иначе возникнет ошибка.
var p:^integer; begin new(p); writeln('Адрес указателя: ',@p); writeln('Значение указателя: ',p); writeln('Разыменование указателя: ',p^); dispose(p); writeln(); writeln('Адрес указателя после удаления: ',@p); writeln('Значение указателя после удаления: ',p); end.
После применения объект, указанный в качестве фактического параметра перестает существовать, a указатель на него удаляется из множества значений указательного типа, в результате чего все переменные, содержащие указатель на уничтоженный объект, становятся неопределёнными.
Следует помнить, что повторное применение процедуры dispose к свободному указателю может привести к ошибке.
Достоинства и недостатки указателей
- Достоинства указателей
- уменьшают объем памяти и сокращает время выполнения программы
- позволяют возвращать несколько значений из функции и могут использоваться для передачи информации между функциями
- дают возможность изменить размер динамически выделенного блока памяти
- позволяют получить доступ к любой ячейки памяти компьютера
- помогают создавать сложные структуры данных, такие как связанный список, стек, очереди, деревья, графики и т.д.
- Недостатки указателей
- выделенный динамически блок памяти необходимо освобождать явно, иначе может произойти утечка памяти
- повышают вероятность возникновения ошибок и проблем с памятью. При этом найти и исправить эти ошибки задача не из легких, особенно в объемных программах
- сложны для понимания и требуют определенного объема знаний. Программист несет ответственность за эффективное и правильное использование указателей
Для чего нужны указатели?
Если нет особой необходимости использовать указатели, лучше выбирать альтернативный вариант, который практически всегда присутствует. Например, использование ссылок.
- Для того, чтобы напрямую работать с памятью Указатели нужны для того, чтобы можно было напрямую работать с оперативной памятью. Например, при передаче указателя в функцию компьютер не создаёт её локальную копию, а обращается к ней напрямую.
- Для динамического управления памятью Если нам нужно выделить в памяти некоторую область для хранения своих данных, но стандартные переменные нам не подходят, мы можем использовать указатель. В этом случае мы помещаем в него стартовый адрес ячейки и говорим, сколько байтов после него нужно использовать и что в них положить.
Задачи с применением указателей
- Через указатели на указатели посчитать сумму двух чисел и записать в третье.
var num_1, num_2:integer; //два числа, значения которых будут использоваться в сложении sum:integer; //переменная для сохранения рез-та сложения x, y:^integer; //переменные для хранения адресов двух чисел x1:^^integer; //первое слагаемое y1:^^integer; //второе слагаемое begin //занесение в переменные числовых значений num_1:=1; num_2:=2; //присваивание переменным типа указатель в кач-ве значения адресов переменных целевого типа x:=@num_1; y:=@num_2; //присваивание переменным типа указатель на указатель в кач-ве значения адресов переменных типа указатель x1:=@x; y1:=@y; //суммирование двух чисел, это получается за счет двойного разыменования переменной типа указатель на указатель на тип integer sum:=x1^^+y1^^; writeln('сумма:',sum); end.- Напишите функцию swap, которая меняет значения переданных аргументов. В Pascal существуют два типа подпрограмм: процедуры и функции (служебные слова: procedure, function). Процедуры после выполнения не возвращают никакое значение из подпрограммы, а функция возвращает результат. При написании подпрограмм важным этапом выступает передача параметров. Выделяют параметры-значения и параметры-переменные.
- Параметры-значения При этом в формальные параметры подпрограммы передаются копии фактических. Перед формальными параметрами нет слова Var. С такими параметрами удобно работать, так как при вызове подпрограммы на их место можно подставить не только переменную, но и константу или выражение. Даже если внутри подпрограммы значение такого параметра меняется, при выходе из нее оно восстанавливается (так как меняется значение не самого параметра, а его копии).
- Параметры-переменные При этом в формальные параметры подпрограммы передаются адреса фактических. Фактические значения по указанному адресу меняются. Перед формальными параметрами указывается слово Var. Пример передача значений в подпрограмму со словом var есть в задаче 2.
//Создаем два указателя на целое число и две переменные типа целое число var p1:^integer; p2:^integer; x:integer; y:integer; procedure Swap(var a,b:integer); //Создаем временную переменную типа целое var temp:integer; begin //Присваиваем temp значение первой переменной temp:=a; //Присваиваем первой переменной значение второй a:=b; //Присваиваем второй переменной значение temp b:=temp; end; begin //Присваиваем целое значение переменным x:=5; y:=8; //Инициализируем указатели p1:=@x; p2:=@y; //Вызываем процедуру, которая меняет местами значения двух переменных, используя операцию разыменовывание Swap(p1^, p2^); writeln (p1^); writeln(p2^); end.Заключение
В данной статье мы попытались на собственном опыте изучения указателей в Паскале поделиться полученными знаниями и простым языком объяснить базовые понятия, подкрепив их примерами и схемами. Если вы разобрались в теме указателей: получили новые знания или освежили в памяти ранее изученное, значит, цель статьи достигнута
Конечно, мы рассказали не все об указателях и их возможностях. Надеемся, что данная статья помогла Вам найти ответы на интересующие вопросы по рассматриваемой теме и побудила к дальнейшему, более глубокому, изучению указателей не только на языке Паскаль, но и применению их в любых своих программах. До встречи в будущих статьях 🙂
- указатели
- статическая память
- динамическая память
- адресация
- Программирование
- Научно-популярное
Помогите с дз по информатике. Паскаль. 9 класс.
Задание 1
Составить блок-схему алгоритма и программу на языке Паскаль для решения задачи.
Найдите количество положительных элементов одномерного массива, которые без остатка делятся на 4 и принадлежат промежутку от 10 до 30. Количество элементов массива и их значения задайте самостоятельно путём ввода с клавиатуры.Задание 2
Составить программу на языке Паскаль для решения задачи.
Дан одномерный массив из 15 элементов, заполненный случайным образом в диапазоне от –40 до 40. Замените на ноль значения всех элементов, расположенных на нечётных позициях в массиве. Выведите на экран весь полученный ряд значений.( P.S я из ИнтернетУрок. Кто тоже, то напишите если хотите в чат с домашкой в тг)
Лучший ответ
Программы обозначаю как P1 (Program P1) и P2 — соответственно P1 — к 1-ому заданию, P2 — ко 2-ому.
Кстати, в 1-ом: какой именно промежуток (границы строгие или включая эти числа)?
1)
Program P1;
uses crt;
const n=10;
type massiv=array [1..n] of integer;
var m: massiv;
i, k: integer;
begin
clrscr;
k:=0;
for i:=1 to n do begin
write (‘Введите ‘, i, ‘-й элемент массива, после чего нажмите клавишу Enter: ‘);
readln (m[i]);
end;
for i:=1 to n do begin
if (m[i]>0) and (m[i] mod 4=0) and (m[i]>=10) and (m[i]<=30) then k:=k+1;
end;
writeln (‘Количество положительных элементов одномерного массива, которые без остатка делятся на 4 и принадлежат промежутку от 10 до 30 составляет: ‘, k);
write (‘Программа завершена. Для выхода нажмите клавишу Enter.’);
readkey;
end.2)
Program P2;
uses crt;
const n=15;
type massiv=array [1..n] of integer;
var m: massiv;
i: integer;
begin
clrscr;
for i:=1 to n do begin
m[i]:=random (81)-40;
end;
write (‘Был сгенерирован массив:’);
for i:=1 to n do begin
write (‘ ‘, m[i]);
end;
writeln (»);
for i:=1 to n do begin
if i mod 2<>0 then m[i]:=0;
end;
write (‘Этот массив после изменения: ‘);
for i:=1 to n do begin
write (‘ ‘, m[i]);
end;
writeln (‘ ‘);
write (‘Программа завершена. Для выхода нажмите клавишу Enter.’);
readkey;
end.Остальные ответы
я хочу в тг
Загрузка… █████[][][][] 49%Знаток (456) 2 года назад
Загрузка… █████[][][][] 49%Знаток (456) 2 года назадэто бот с гдз, тоже может помочь
Покупаче ПокупачеУченик (115) 1 год назад
Если вам нужны ответы в домашней школе ИнтернетУрок — в телеграмме есть группа с ответами: https://t.me/dostup10class
Там есть ответы в интернет уроке на домашние задания/аттестации и другого для всех классов)
Программы обозначаю как P1 (Program P1) и P2 — соответственно P1 — к 1-ому заданию, P2 — ко 2-ому.
Кстати, в 1-ом: какой именно промежуток (границы строгие или включая эти числа)?
1)
Program P1;
uses crt;
const n=10;
type massiv=array [1..n] of integer;
var m: massiv;
i, k: integer;
begin
clrscr;
k:=0;
for i:=1 to n do begin
write (‘Введите ‘, i, ‘-й элемент массива, после чего нажмите клавишу Enter: ‘);
readln (m[i]);
end;
for i:=1 to n do begin
if (m[i]>0) and (m[i] mod 4=0) and (m[i]>=10) and (m[i]<=30) then k:=k+1;
end;
writeln (‘Количество положительных элементов одномерного массива, которые без остатка делятся на 4 и принадлежат промежутку от 10 до 30 составляет: ‘, k);
write (‘Программа завершена. Для выхода нажмите клавишу Enter.’);
readkey;
end.2)
Program P2;
uses crt;
const n=15;
type massiv=array [1..n] of integer;
var m: massiv;
i: integer;
begin
clrscr;
for i:=1 to n do begin
m[i]:=random (81)-40;
end;
write (‘Был сгенерирован массив:’);
for i:=1 to n do begin
write (‘ ‘, m[i]);
end;
writeln (»);
for i:=1 to n do begin
if i mod 2<>0 then m[i]:=0;
end;
write (‘Этот массив после изменения: ‘);
for i:=1 to n do begin
write (‘ ‘, m[i]);
end;
writeln (‘ ‘);
write (‘Программа завершена. Для выхода нажмите клавишу Enter.’);
readkey;
end.Загрузка… █████[][][][] 49%Знаток (456) 2 месяца назад
чел, просто копировать ответы, что бы заработать баллы, не хорошо.program task1; const n = 10; <количество элементов массива>var a: array[1…n] of integer; i, k: integer; begin writeln(‘Введите элементы массива:’); for i:= 1 to n do read(a[i]); k := 0; for i:= 1 to n do if (a[i] > 0) and (a[i] mod 4 = 0) and (a[i] < 30) and (a[i] >= 10) then k := k + 1; writeln(‘Количество положительных чисел, кратных 4 и принадлежащих промежутку [10,30): ‘, k); end. program task2; const m = 15; var A: array [1…m] of integer; i: integer; begin randomize; writeln(‘Исходный массив:’);
PascalABC.NET и ЕГЭ по информатике 2024
Мы рекомендуем всем, кто готовит и готовится к сдаче ЕГЭ, пользоваться возможностями PascalABC.NET версии 3.9.0. Эта версия вышла 10.07.2023 года. Использование более ранних версий лишит школьника некоторых имеющихся в языке возможностей и потребует самостоятельно искать для них эквивалентные замены.
Мы призываем также тех работников образования, от которых зависит состояние программных средств на станциях ЕГЭ, заблаговременно установить любую доступную сборку версии 3.9.0 или выше. Версия PascalABC.NET 3.8.3 считается устаревшей.
Просим руководство учебных заведений принять к сведению, что многие школьники, занимаясь самостоятельно или с репетиторами, используют именно эту версию и, обнаружив на экзамене версию более старую, могут показать результат гораздо ниже своих возможностей.
Об этом документе
Здесь представлены решения некоторых задач демонстрационных вариантов ЕГЭ по информатике прошлых лет. Решения даются с кратким описанием алгоритма и концентрируются в основном на демонстрации возможностей языка.
Решения сбалансированы по простоте записи и восприятия в балансе с новыми возможностями.
В сети можно встретить либо более длинные и непонятные решения на старом языке Паскаль либо переусложнённые и малопонятные для школьника решения с использованием всех возможностей языка. Ни тот ни другой стиль записи программ нами не рекомендуется.
Великолепный разбор задач типа 8, 13 и 22 ЕГЭ по информатике 2023-24 на чистом PascalABC.NET дан К.Ю.Поляковым в данной презентации. Здесь представлены наиболее эффективные и неочевидные решения.
О PascalABC.NET
PascalABC.NET – современный диалект языка программирования Паскаль, позволяющий записывать код компактно и понятно, используя современные языковые возможности. Это делает программу яснее и как следствие сокращает число возможных ошибок на ЕГЭ по информатике, связанных с волнением и другими субъективными причинами.
Данный текст составлен разработчиками языка и рассматривает ряд вопросов, связанных с использованием PascalABC.NET при сдаче ЕГЭ по информатике. Он ориентирован:
- на школьников, использующих при сдаче ЕГЭ PascalABC.NET как язык реализации программ
- на преподавателей, которые при подготовке школьников к сдаче ЕГЭ по информатике используют PascalABC.NET
Важно! Данный текст не рассматривает вопросы, связанные с методикой решения задач. Он лишь описывает то, как на PascalABC.NET сделать запись алгоритмов лучше, сохранив при этом эффективность.
PascalABC.NET имеет множество языковых возможностей и множество стилей программирования, поскольку обобщает современные языковые и библиотечные возможности сразу нескольких современных языков программирования (C#, Python, Kotlin).
При решении задач ЕГЭ по информатике мы рекомендуем использовать лишь ограниченный набор возможностей PascalABC.NET, которые делают текст программы яснее и короче, позволяя концентрироваться на сути алгоритма, а не на технических деталях.
К базовым возможностям языка, рекомендуемым нами при решении задач ЕГЭ, относятся:
- Описания переменных внутри блока в том месте, где они впервые потребовались. Это ликвидирует длинные перечни описания переменных до beginа основной программы, ухудшающие читаемость и лёгкость написания программы.
- Автовывод типа переменной при описании с инициализацией ( var a := 1 ).
- Использование описания счётчика цикла for в заголовке цикла ( for var i ).
- Функции ввода вида ReadInteger , ReadReal , ReadInteger2 и т.д., позволяющие одной строкой описывать и вводить переменную в любом месте операторного блока программы ( var a := ReadInteger ).
- Процедуры вывода Print , Println , автоматически разделяющие элементы вывода пробелами.
- Цикл loop – аналог цикла for, использующийся когда счётчик цикла не нужен.
- Кортежи и распаковка кортежей в переменные, называемая также множественным присваиванием: (a,b) := (1,1) .
Кроме того, в некоторых задачах уместно использование лямбда-выражений как параметров стандартных методов.
Все представленные здесь решения сбалансированно сочетают простоту и понятность записи и использование новых возможностей.
Задача 17
Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число.
Решение 1. Минимум новых возможностей; длинная запись условия, уводящая от сути
begin var count := 0; var max := -MaxInt; for var x := 1016 to 7937 do if (x mod 3 = 0) and (x mod 7 <> 0) and (x mod 17 <> 0) and (x mod 19 <> 0) and (x mod 27 <> 0) then begin count += 1; if x > max then max := x; end; Print(count,max); end.Ответ. 1568 7935
Решение 2. Использование методов Divs и DivsAny
begin var count := 0; var max := -MaxInt; for var x := 1016 to 7937 do if x.Divs(3) and not x.DivsAny(7, 17, 19, 27) then begin count += 1; if x > max then max := x; end; Print(count,max); end.Решение 2а. Заметим, что максимальный элемент является последним удовлетворяющим условию
begin var count := 0; var last := 0; for var x := 1016 to 7937 do if x.Divs(3) and not x.DivsAny(7, 17, 19, 27) then begin count += 1; last := x; end; Print(count,last); end.Решение 3. Использование последовательностей
begin // Рассмотрим последовательность целых от 1016 до 7937, делящихся на 3 и не делящихся ни на одно из 7, 17, 19, 27 var seq := (1016..7937).Where(x -> x.Divs(3) and not x.DivsAny(7, 17, 19, 27)); // Выведем количество элементов этой последовательности и ее максимальный элемент Print(seq.Count,seq.Max); end.Замечание. Аналогично предыдущему вместо seq.Max можно использовать seq.Last
Задача 25
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
Решение 1
Для получения всех делителей составим функцию, которая будет помещать все получаемые делители в список. Это неэффективно (нужны только числа с ровно двумя делителями), но для приводимых на ЕГЭ значений программа выполняется мгновенно, поэтому писать более оптимальный алгоритм не следует.
function Divisors(N: integer): Listinteger>; begin Result := new Listinteger>; for var i:=2 to N-1 do if N.Divs(i) then Result.Add(i); end; begin for var N := 174457 to 174505 do begin var d := Divisors(N); if d.Count = 2 then Println(d[0],'|',d[1]); end; end.Ответ.
3 | 58153 7 | 24923 59 | 2957 13 | 13421 149 | 1171 5 | 34897 211 | 827 2 | 87251Решение 2
Без использования функции
begin for var N := 174457 to 174505 do begin var d := new Listinteger>; for var i:=2 to N-1 do if N mod i = 0 then d.Add(i); if d.Count = 2 then Println(d[0],'|',d[1]); end; end.Решение 3
Более эффективное, в котором список делителей не пополняется если уже содержит более двух делителей. Это решение — на случай достаточно больших значений N, что трудно представить на ЕГЭ
begin for var N := 174457 to 174505 do begin var d := new Listinteger>; for var i:=2 to N-1 do begin if N mod i = 0 then d.Add(i); if d.Count > 2 then // Это условие даёт более эффективное решение break; end; if d.Count = 2 then Println(d[0],'|',d[1]); end; end.Данное решение тем не менее будет медленно работать при очень больших N, однако подобное усложнение невозможно на ЕГЭ — оно делает задачу олимпиадной. Однако, решение есть и в этом случае. Оптимизации решения задачи 25 рассмотрены в презентации К.Ю. Полякова.
Задача 26
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4 80 30 50 40При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
2 50Решение 1
begin Assign(input, '26.txt'); var (S,N) := ReadInteger2; var data := ReadArrInteger(N); Sort(data); var (total,count) := (0,0); while (count N) and (total + data[count] S) do begin total += data[count]; count += 1; end; var delta := S - total; Println(count, data.Last(x -> x - data[count-1] delta)); end.Решение скорее всего позаимствовано с сайта К. Полякова с косметическими правками в стиле PascalABC.NET.
Решения аналогичных задач на чистом PascalABC.NET содержатся в презентации К.Ю. Полякова.
Ответ.
568 50Задача 27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6 1 3 5 12 6 9 5 4 3 3 1 1Для указанных входных данных значением искомой суммы должно быть число 32. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение 1
begin Assign(input,'27-b.txt'); var (s, d) := (0, MaxInt); var n := ReadInteger; loop n do begin var (a,b) := ReadInteger2; s += Max(a,b); var diff := Abs(a-b); if diff mod 3 <> 0 then d := Min(d, diff) end; if s mod 3 <> 0 then Print(s) else Print(s-d) end.Решение скорее всего позаимствовано с сайта К. Полякова с косметическими правками в стиле PascalABC.NET.
Ответ.
127127 399762080Далее рассматриваются задачи, которые не требуют решения в виде программы, однако с помощью программы можно проверить ответ.
Задача 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Пояснение
Для решения используется функция Bin модуля School, содержащего ряд базовых математических алгоритмов:
uses School; begin for var NN := 1 to 100 do begin var N := NN; var rem := Bin(N).Count(d->d='1') mod 2; N := 2*N + rem; rem := Bin(N).Count(d->d='1') mod 2; N := 2*N + rem; Println(NN,N); end; end.Задача 12
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
ПОКА условие последовательность команд КОНЕЦ ПОКАвыполняется, пока условие истинно.
ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИвыполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО ПОКА нашлось (2222) ИЛИ нашлось (8888) ЕСЛИ нашлось (2222) ТО заменить (2222, 88) ИНАЧЕ заменить (8888, 22) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦРешение. Условие — слишком длинное ))
begin var s := 70 * '8'; while ('2222' in s) or ('8888' in s) do if '2222' in s then s := s.Replace('2222', '88', 1) else s := s.Replace('8888', '22', 1); Print(s); end.Ответ
Задача 14
Значение арифметического выражения: 49 7 + 7 21 – 7 – записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?
Решение.
begin var bb := 49bi ** 7 + 7bi ** 21 - 7; var count := 0; repeat if bb mod 7 = 6 then count += 1; bb := bb div 7; until bb = 0; Count.Print; end.Пояснение 49bi , 7bi — это константы типа BigInteger
Ответ
Решение 2. Используем стандартный метод ToBase модуля School и стандартный метод последовательностей CountOf:
uses School; begin (49bi ** 7 + 7bi ** 21 - 7).ToBase(7).CountOf('6').Print end.Задача 15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение.
begin // Возьмём большой диапазон a: от 1 до 10000 for var a := 10000 downto 1 do // Если для всех натуральных x (возьмём некоторый большой диапазон) // выполняется условие задачи, то мы нашли a if (1..100000).All(x -> not x.Divs(a) (x.Divs(6) not x.Divs(9))) then begin Print(a); break; end; end.Пояснение Импликация → в PascalABC.NET описывается операцией
Пояснение
Тип BigInteger указан “на всякий случай” — если будут возникать очень большие целые. В задачах ЕГЭ — вряд ли
Задача 16
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n – чётно, F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.Чему равно значение функции F(26)?
Решение.
function F(n: integer): BigInteger; begin if n = 1 then Result := 1 else if n.IsEven then Result := n + F(n - 1) else Result := 2 * F(n - 2); end; begin F(26).Print end.Ответ
4122©2024 PascalABCNET Team. All rights reserved.
Page last updated: 20.12.2023
Site last generated: Mar 19, 2024Методика быстрого обучения программированию на основе изучения классов задач (11-15) Текст научной статьи по специальности «Математика»
АЛГОРИТМ / ALGORITHM / ПРОГРАММА / PROGRAM / ЯЗЫК ПРОГРАММИРОВАНИЯ ПАСКАЛЬ / PROGRAMMING LANGUAGE PASCAL / МАССИВ / ARRAY / ПРОЦЕДУРЫ И ФУНКЦИИ / PROCEDURES AND FUNCTIONS / РЕКУРСИЯ / RECURSION / МНОЖЕСТВО / SET / ЗАПИСЬ / RECORD
Аннотация научной статьи по математике, автор научной работы — Аляев Юрий Александрович
Предлагается методика быстрого обучения программированию на основе изучения классов задач, разработанная и применяющаяся на практике в процессе обучения программированию студентов вузов
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Аляев Юрий Александрович
Методика быстрого обучения программированию на основе изучения классов задач (16-17)
Методика быстрого обучения программированию на основе изучения классов задач (6-7)
Методика быстрого обучения программированию на основе изучения классов задач (18-19)
Методика быстрого обучения программированию на основе изучения классов задач (8-10)
Методика быстрого обучения программированию на основе изучения классов задач
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.Methods of the quick education to programming on base of the study of the classes of the problems (11-15)
Is offered methods of the quick education to programming on base of the study of the classes of the problems, designed and using in practice in process of the education to programming student high school
Текст научной работы на тему «Методика быстрого обучения программированию на основе изучения классов задач (11-15)»
1. Дорошенко Е.Г., Пак Н.И., Рукосуева Н.В., Хегай Л.Б. О технологии разработки ментальных учебников // Вестник Томского государственного педагогического университета (Tomsk State Pedagogical University Bulletin). 2013. Вып. 12 (140). С. 145-151.
2. Новак Д., Канас А. Теория построения и практика применения карт понятий. URL: http://cmap.ihmc.us/Publications/ResearchPapers/TheoryCmaps/TheoryUnderl
3. Шенк Ф.Б. Ментальные карты: конструирование географического пространства в Европе / пер. с нем. А. Жоровой // Политическая наука. Политический дискурс: История и современные исследования. 2001. Вып. 4. С. 4-17.
4. Шаталов В.Ф. Эксперимент продолжается. М.: Педагогика, 1989. 334 с.
5. Калитина В.В. Электронная энциклопедия как средство повышения уровня запоминания учебного материала // Вестник КГПУ. 2013. № 1 (23). С. 111-114.
6. Мюллер Х. Составление ментальных карт: метод генерации и структурирования идей / пер. с нем. В.В. Мартыновой, М.М. Демина. М.: Омега-Л, 2007. 126 с.
7. Пак Н.И. Гипермозг как основа становления ментальной дидактики. Интернет — свободный, безопасный, образовательный // Межрегион. науч.-практ. конф. (18-19 октября, 2013 г., г. Омск): сб. матер. / под общ. ред. М.П. Лапчика. Омск: Полиграфический центр КАН, 2013. 278 с.
8. Пак Н.И. Информационное моделирование: учебное пособие. // КГПУ им. В.П. Астафьева. Красноярск, 2010. 152 с.
9. Колесник В. Ментальные карты. URL: http://kolesnik.ru/2005/mindmapping
10. Петрова И.А., Ракова Е.П. Использование структурированных графических схем в изучении информатики // Успехи современного естествознания. 2013. № 10. С. 35-36.
11. Найссер У. Познание и реальность. М.: Прогресс, 1981. 252 с.
12. Бруннер Е.Ю. Применение технологии mind map в учебном процессе // Развитие международного сотрудничества в области образования в контексте Болонского процесса: материалы международной науч.-практ. конф. г. Ялта (5-6 марта 2008 г.). Ялта: РИО КГУ, 2008. Вып. 19. Ч. 1. С. 50-53.
13. Бабич А.В. Эффективная обработка информации (Mind mapping). URL: http://www.intuit.ru/studies/courses/647/503/lecture/11414?page=8
Use in educational process mental map
Damir Rashitovich Khakimov, Master SibGTU, Siberian State Technological University,
In this paper, the technique used in the training process of mental maps, the technology development which is based on the information model of thinking. Using this technique significantly affects the intensification of training and intensifying training activities due to higher than traditional teaching methods, the degree of visualization of the material presented.
Keywords: mental map, image, information model of thinking, structuring the learning process
МЕТОДИКА БЫСТРОГО ОБУЧЕНИЯ ПРОГРАММИРОВАНИЮ НА ОСНОВЕ ИЗУЧЕНИЯ КЛАССОВ ЗАДАЧ (11-15)
Юрий Александрович Аляев, доц., доц. кафедры программного обеспечения вычислительной техники и автоматизированных систем,
e-mail: alyr1@yandex.ru, Пермский военный институт внутренних войск МВД России,
Предлагается методика быстрого обучения программированию на основе изучения классов задач, разработанная и применяющаяся на практике в процессе обучения программированию студентов вузов.
Ключевые слова: алгоритм, программа, язык программирования Паскаль, массив, процедуры и функции, рекурсия, множество, запись
Разделы курса «Информатика» — алгоритмизация и программирование — остаются наиболее важными для формирования алгоритмического мышления. Поскольку в школах данные разделы преподаются в недостаточном объеме, в вузе возникает необходимость начинать обучение с нуля и достичь хорошего уровня программирования при ограниченном количестве часов преподавания.
Этого удается добиться за счет применения рациональных методов обучения, прежде всего, последовательно проводя идеи обучения на основе выделения элементарных операций деятельности по построению алгоритмов и программ; выявления структуры алгоритма и форм ее записи на алгоритмическом языке; одинаковой формы алгоритма для решения задач с одинаковой структурой исходных данных [1-2]. Благодаря этим идеям, задачи по программированию удается разбить на ряд классов и типизировать методы решения задач каждого класса.
Предлагаемая методика быстрого обучения программированию на основе изучения классов задач, появилась и применяется на протяжении многих лет в процессе обучения программированию студентов пермских вузов благодаря В.П. Гладкову [2]. В статье рассматриваются методики решения по пяти (11-15) из девятнадцати выделенных классов задач (1-10 классы задач рассмотрены в [3-6]).
11. Данные типа string
Задача 1. Подсчитать, сколько раз в заданной строке встречается указанная буква. Решение 1. Пусть исходная строка хранится в переменной s, а искомая буква в переменной а. Для решения задачи будем просматривать строку s посимвольно и каждый символ сравнивать с заданной буквой. k:=0; for i:=1 to length(s) do
if copy(s,i,1)=a then k:=k+1;. Решение 2. Будем искать положение указанной буквы в строке до тех пор, пока ее удастся найти. Затем отбрасываем ту часть строки, где была найдена указанная буква, и повторяем поиск.
s:=copy(s,j+1 ,length(s)-j); j:=pos(a,s); end.
Задача 2. Проверить, входят ли в строку s две буквы а.
Решение. Для двух букв а, стоящих подряд: if pos(‘aa’,s)>0 then write(‘входят’) else write(‘HE входят’). Здесь требуется проверить наличие двух букв а, стоящих в любом месте строки. Эта задача является поисковой. Если строка закончится и две буквы а не будут найдены, то ответ на вопрос задачи отрицательный. Если при поиске будут найдены две буквы а, то ответ на вопрос задачи положительный. Для подсчета найденных букв а использовать счетчик. k:=0; f:=false; i:=1; while (i<=length(s)) and not f do if copy(s,i,1)='a' then begin k:=k+1;
if k=2 then f:=true;
then write(‘в строке есть две буквы а’) else write^ строке нет двух букв а’);. Другое решение этой задачи можно получить, основываясь на втором решении задачи 10.1.1.
then begin s:=copy(s,j+1,length(s)-j); j:=pos(‘a’,s); if j>0
then write(‘в строке есть две буквы а’) else write^ строке нет двух букв а’);
else write^ строке нет двух букв а’);.
Задача 3. В строке s заменить символы а на символы я.
Решение 1. Просматриваем строку посимвольно, удаляем найденный символ а, вставляем на его место я. for i:=1 to length(s) do if copy(s,i,1)=’a’ then begin delete(s,i,1) insert(V,s,i);
Решение 2. Просматриваем исходную строку посимвольно и переписываем в выходную строку символы, отличные от а. Вместо символа а переписываем символ я. s1:=»; < выходная строка >for i:=1 to length(s) do if copy(s,i,1)=’a’ then s1:=s1+V else s1:=s1+copy(s,i,1);. Решение 3. Оно основывается на решении 2 задачи 10.1.1. j:=pos(‘a’,s); while j<>0 do
Задача 4. Будем считать словом любую последовательность букв и цифр. Строка состоит из слов, разделенных одним или несколькими пробелами. Удалить лишние пробелы, оставив между словами по одному пробелу.
Решение. Лишними пробелами называются второй, третий и т.д., следующие за первым пробелом. Следовательно, чтобы найти лишний пробел, нужно искать два пробела, стоящие рядом, и удалять второй пробел в каждой найденной паре. j:=pos(‘ ‘,s); while j<>0 do begin delete(s,j,1);
Задача 5. Строка символов — это любая последовательность символов, заключенная в апострофы. Задана строка символов, состоящая из слов и строк,
разделенных одним или несколькими пробелами. Удалить из строки все незначащие пробелы. Незначащими пробелами называются пробелы, не стоящие в апострофах.
Решение. Запишем формально определение незначащего пробела. Текущий пробел незначащий, если предыдущий символ является пробелом и этот пробел не стоит в апострофах. Введем логическую переменную p, которая принимает значение false, если предыдущий символ не является пробелом, и значение true, если предыдущий символ — пробел. Введем логическую переменную q, которая принимает значение false, если пробел находится не в апострофах, и значение true, если пробел в апострофах. Тогда формальное определение незначащего пробела запишется так: (copy(s,i,1)=’ ‘) and p and not q.
Составляем программу: p:=false; q:=false; s1:=»;
for i:=1 to length(s) do begin if not((copy(s,i,1)=’ ‘) and p and not q) then s1:=s1+copy(s,i,1); if copy(s,i,1)=’ ‘ then p:=true else p:=false; if copy(s,i,1)=»» then q:=not q; end;.
Задача 6. Подсчитать количество гласных букв русского алфавита в строке. Решение. Гласная буква — это такая буква, которая принадлежит множеству гласных букв. Для решения задачи просматриваем строку посимвольно и проверяем каждый символ на принадлежность гласным буквам: k:=0; for i:=1 to length(s) do if pos(copy(s,i,1),’аоуэыяёюеи’)>0 then k:=k+1;.
Задача 7. Задано предложение, состоящее из слов, разделенных одним или несколькими пробелами. Определить самое длинное слово предложения.
Решение. Для того чтобы выделить окончание слова, нужно анализировать два символа: первый символ должен быть отличен от пробела, а второй должен быть пробелом. Для одинаковой обработки всех символов добавим к концу предложения дополнительный символ — пробел. Как только обнаружится конец слова, вычислим его длину и проверим на максимум:
то запоминаем его>
else if copy(s,i,1)<>‘ ‘ then ss:=ss+copy(s,i,1);
Задача 8. Задано предложение, состоящее из слов, разделенных одним или несколькими пробелами. Расположить слова предложения в алфавитном порядке.
Решение. Перепишем слова предложения по одному в элементы одномерного массива. Отсортируем массив по возрастанию и перепишем слова из массива в строку. const nn=100; type mas=array[1..nn]of string; var a:mas; i,j , k:integer; s,
write(‘Введите строку ‘); readln(s);
if a[i]>a[j] then begin
for i:=1 to k do s:=s+a[i]+’ ‘; write(s); end.
12. Процедуры и функции
Задача 1. Написать программы для вычисления числа сочетаний из n по m, оформив вычисления факториала процедурой без параметров, процедурой с параметрами, функцией. Сравнить решения.
Решение 1. Воспользуемся известной формулой: n!
procedure fact1; var i:longint; begin p:=1;
for i:=1 to q do p:=p*i;
begin write(‘Введите n и m ‘); readln(n,m);
write(‘Число сочетаний из ‘,n,’ по ‘,m,’ равно ‘,c); end.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
procedure fact2(q:longint;var p:longint); var i:longint; begin p:=1;
for i:=1 to q do p:=p*i;
begin write(‘Введите n и m ‘); readln(n,m); fact2(n,fn); fact2(m,fm); fact2(n-m,fnm); c:=fn div (fm*fnm);
write(‘Число сочетаний из ‘,n,’ по ‘,m,’ равно ‘,c); end.
c:longint; function fact3 (q: longint): longint; var i:longint; begin p:=1;
for i:=1 to q do p:=p*i; fact3:=p;
begin write(‘Введите n и m ‘); readln(n,m);
write(‘Число сочетаний из ‘,n,’ по ‘,m,’ равно ‘, fact3(n) div (fact3(m)*fact3(n-m))); end.
Задача 2. Даны два числа a и b. Разработать алгоритм и написать программу для определения наибольшего общего делителя (НОД) трех величин: a+b, I a-b I , a-b. Расчет НОД двух чисел оформить в виде пользовательской процедуры.
Математическая модель данной задачи имеет вид:
Расчет: x=a+b; y=| a-b I ; z=a-b.
Для расчета наибольшего общего делителя используем следующее выражение: нод^у^^нодснод^у)^). Для расчета НОД двух чисел используем алгоритм Евклида.
Фрагмент алгоритма для расчета наибольшего общего делителя k двух чисел n и m имеет вид:
Цикл-ПОКА (m*n); Если m>n То;
n:=n-m; Конец-Если; Конец-Цикла; k:=m;
В Паскаль-программе пользовательская процедура размещается в разделе описания процедур и функций.
procedure evklid(m,n:integer; var k:integer);
while m<>n do if m>n then m:=m-n else n:=n-m; k:=m; end;
writeln(‘a=’,a,’ b=’,b); evklid(a+b,abs(a-b),c); evklid(c,a*b,c); writeln(‘нод=’,c);
В данной программе обращение к пользовательской процедуре осуществляется дважды: первый раз — для расчета НОД суммы и модуля разности чисел a и b, второй раз — для расчета НОД числа, полученного от первого обращения к процедуре и произведения чисел a и b.
Пользовательская процедура имеет три формальных параметра: параметры-значения — m и n, а также параметр-переменную — k. Формальному параметру k соответствует фактический параметр с, с помощью которого выводится на печать искомый результат.
Задача 3. Решить задачу 11.2.2, используя для нахождения НОД пользовательскую функцию. Программа на языке Паскаль для решения этой задачи имеет следующий вид:
function evklid(m,n:integer) : integer; begin
while m<>n do if m>n then m:=m-n
evklid:=m; end; begin read(a,b);
writeln(‘a=’,a,’ b=’,b); c:=evklid(evklid(a+b,abs(a-b)),a*b); writeln(‘нод=’,c);
Для вызова пользовательской функции применяется оператор присваивания, в котором в качестве операнда используется обращение к функции, содержащее имя функции и список фактических параметров. В соответствии с правилами приоритета первым выполняется обращение evklid(a+b,abs(a-b)). Для возвращения результата решения пользовательская функция должна содержать оператор присваивания, у которого в левой части должно стоять имя функции, а в правой — возвращаемый в основную программу результат.
Задача 1. Известно рекурсивное определение факториала:
fi, если n = 0 или n = 1, n =\
Здесь n — неотрицательно. Записать эту функцию на языке Паскаль. Решение. В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (п-1)! и умножить его на n. Уменьшающееся значение гарантирует, что, в конце концов, возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно. program task5;
function fact(i: integer) :integer; begin if (i=1) or (i=0) then fact:=1 else fact:=fact(i-1)*i;
begin write(‘Введите нужное значение n ‘); readln(n);
writeln(‘Факториал ‘,n,’ равен ‘,fact(n)); end.
Вспомним, что на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех переменных, объявляемых в нем, причем переменные других копий будут недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и все его переменные. Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4!. Основной алгоритм: вводится n=4, вызов fact(4). Основной алгоритм
приостанавливается, вызывается и работает fact(4): 4<>1 и 4<>0, поэтому fact:=fact(3)*4. Работа функции приостанавливается, вызывается и работает fact(3): 3<>1 и 3<>0, поэтому fact:=fact(2)*3. В данный момент в памяти компьютера две копии функции fact. Вызывается и работает fact(2): 2<>1 и 2<>0, поэтому fact:=fact(1)*2. В памяти компьютера уже три копии функции fact и вызывается четвертая. Вызывается и работает fact(1): 1=1, поэтому fact(1)=1. Работа этой функции завершена, продолжает работу fact(2). fact(2):=fact(1)*2=1*2=2. Работа этой функции также завершена, и продолжает работу функция fact(3). fact(3):=fact(2)*3=2*3=6. Завершается работа и этой функции, и продолжает работу функция fact(4). fact(4):=fact(3)*4=6*4=24. Сейчас управление передается в основную программу и печатается ответ: «Факториал 4 равен 24».
14. Тип данных множество
Задача 1. Задать множество целых чисел от заданного числа до числа в три раза большего, чем заданное.
Решение. Используем описание множеств на языке Паскаль и операторы для работы с множествами.
Если количество элементов n в множестве известно заранее, то задача решается
type setnum=set of byte; const mn:setnum=[n..3*n];
. Если начальное значение задается пользователем, то задача решается так: type setnum=set of byte; var mn:setnum; n,i:byte;
begin write(‘задайте первый элемент множества ‘);
else write(‘заданное количество элементов не поместится в множестве ‘); end.
Задача 2. Вывести элементы множества, содержащего прописные и строчные буквы латинского алфавита, на экран.
Решение. В цикле проверим вхождение всех элементов базового типа и выводим те, которые входят в множество. var zn:set of ‘A’..’z’; i:char;
begin for i:=’A’ to ‘Z’ do
if i in zn then write(i,’ ‘); for i:=’a’ to ‘z’ do
if i in zn then write(i,’ ‘);
Задача 3. Написать программу, которая в заданном слове, состоящем из строчных букв, определяет составляющие его буквы, глухие и звонкие согласные, затем все согласные и все гласные буквы. Решение.
type setchar = set of char;
ALF:string=’абвгдеёжзийклмнопрстуфхцчшщъыьэюя’; var s:string;
for i:=1 to length(ALF) do if ALF[i] in mn then write(ALF[i],’ ‘); writeln; end;
begin write(‘Введите русское слово ‘); readln(s);
gla:=buk-(sog+[V,V]); print(‘слово состоит из букв; ‘,buk); print(‘гласные буквы: ‘,gla); print(‘согласные буквы: ‘,sog); print(‘глухие согласные: ‘,mgl); print(‘звонкие согласные; ‘,mzv); end.
Задача 4. Заданы два слова. Определить буквы, которые не являются общими для обоих слов.
Решение. Образуем множества, содержащие буквы первого и второго слова. Затем найдем разности первого и второго, второго и первого множеств. Их объединение даст ответ.
type setchar=set of char;
begin for i:=1 to length(ALF) do
if ALF[i] in mn then write(ALF[i],’ ‘); writeln; end;
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
begin write(‘Введите два русских слова, разделив их нажатием клавиши Enter ‘); readln(s 1);readln(s2); ms1:=[]; ms2:=[]; for i:=1 to length(sl) do ms1:=ms1+[s1[i]]; < множество букв второго слова>for i:=1 to length(s2) do ms2:=ms2+[s2[i]]; g1:=ms1-ms2; g2:=ms2-ms1; print(g1+g2); end.
Задача 5. Написать программу для нахождения простых чисел с помощью «решета Эратосфена». Решение.
1. Поместим все числа между 2 и n (n<=255) в решето.
2. Выберем из решета наименьшее из чисел.
3. Поместим это число среди простых.
4. Переберем и вынем из решета все числа, кратные данному.
5. Если решето не пустое, то повторим шаги 2 — 5. const n=255; var interval,
begin interval:=[2..n]; prost:=[]; next:=2;
repeat while not (next in interval) do next:=succ(next); prost: =pro st+[next]; c:=2*next-1; j:=next; while j
begin interval:=interval-[j]; j:=j=c; end; until interval=[]; end.
Задача 6. Натуральные числа вводятся с клавиатуры до тех пор, пока не будет введено число нуль (признак окончания ввода). Написать программу для определения цифры, которая встречается во всех введенных числах.
Решение. Для каждого введенного числа образуем множество его цифр и найдем его пересечение с множествами цифр других чисел. Для первого числа не существует множества цифр предыдущих чисел, поэтому в ответе следует записать все множество цифр первого числа. Эта ситуация контролируется в программе с помощью переменной — признака р.
if p=1 then begin s:=s1;p:=0; end else s:=s*s1; read(a);
for a:=0 to 9 do if a in s then write(a,’ ‘);
15. Тип данных запись
Задача 1. Создайте массив автовладельцев. Для каждого автовладельца известен номер, марка автомобиля, фамилия и адрес. Нужно подсчитать количество владельцев автомобиля определенной марки и вывести все сведения о них.
Решение. Сведения об автовладельцах представим массивом записей. Исходные данные вводятся с клавиатуры. Работа с массивом записей аналогична работе с одномерным массивом.
writeln(‘Введите ‘,n,’ автовладельцев’); for i:=1 to n do begin v[i].nomer:=i;
writeln(‘автовладелец номер ‘,v[i].nomer); write(‘Фамилия? ‘);readln(v[i].fio); write(‘марка ? ‘);readln(v[i].marka); write(‘адрес? ‘);readln(v[i].adres);
write(‘Какая марка вас интересует? ‘);
for i:=1 to n do if v[i].marka=s
then begin with v[i] do writeln(nomer,’ ‘,marka,’ ‘,fio,’ ‘,adres); k:=k+1;
write(‘Количество владельцев марки ‘,s,’=’,k);
Таким образом, представлены методики решения по пяти из девятнадцати выделенных классов задач:
11. Данные типа string.
12. Процедуры и функции.
14. Тип данных множество.
15. Тип данных запись.
В следующей статье мы продолжим знакомство с методикой быстрого обучения программированию на основе изучения классов задач. Будут рассмотрены методики по следующим двум из девятнадцати выделенных классов задач:
17. Организация работы с модулями.
1. Аляев Ю.А. Алгоритмизация и языки программирования Pascal, C++, Visual Basic / Ю.А. Аляев, О.А. Козлов. М.: Финансы и статистика, 2002, 2004, 2007. 320 с.
2. Аляев Ю.А. Практикум по алгоритмизации и программированию на языке Паскаль / Ю.А. Аляев, В.П. Гладков, О.А. Козлов. М.: Финансы и статистика, 2004, 2007. 528 с.
3. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (1-3) // Образовательные ресурсы и технологии. 2015’1(9). С. 3-14. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_1_3-14.pdf
4. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (4-5) // Образовательные ресурсы и технологии. 2015’2(10). С. 3-16. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_2_3 — 16.pdf
5. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (6-7) // Образовательные ресурсы и технологии. 2015’3(11). С. 3-20. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_003_020.pdf
6. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (8-10) // Образовательные ресурсы и технологии. 2015’4(12). С. 26-43. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_4_026-043.pdf
Methods of the quick education to programming on base of the study of the classes of the problems (11-15)
Yuri Alexandrovich Alyaev, assistant professor, assistant professor of the pulpit of software of the computing machinery and automated systems, Perm military institute of internal troops of the MIA of Russia,
Is offered methods of the quick education to programming on base of the study of the classes of the problems, designed and using in practice in process of the education to programming student high school.
The Keywords: algorithm, program, programming language Pascal, array, procedures and functions, recursion, set, record