Сёмов Основы разработки алгоритмов и программ. Учебное пособие для студентов факультета дистанционных форм обучения миигаик москва 2020 2 Рецензенты
 Скачать 391.34 Kb.
|
|
begin и end. А теперь, запишем тот же алгоритм с помощью индексного цикла Паскаля (цикла с параметром). Цикл с параметром обеспечивает повторное выполнение тела цикла, пока целочисленный параметр пробегает множество всех значений от начального (In) до конечного (Ik) шагом 1.Он имеет формат: 49 for i := In to Ik do begin <операторы тела цикла> end; Обратите внимание на необходимость отступов от вертикали For и от вертикали begin – end при записи операторов тела цикла. В Паскале используется еще и индексный цикл, в котором целочисленный параметр пробегает множество всех значений от начального (In) до конечного (Ik), при In большем Ik, шагом --1. Он имеет формат: for i := In downto Ik do begin <операторы тела цикла> end; Алгоритм показан в таблице 14. Таблица 14 С оператором for – to - do С оператором for – downto - do Program Words1 Var F, N, R: integer; begin write('Bведите число букв: '); readln(N); F := l; for i := 1 to N do begin F := F * i; end; writeln('Количество слов = ', F); end. Program Words1; Var F, N, R: integer; begin write('Bведите число букв: '); readln(N); F := l; for i := N downto 1 do begin F := F * i; end; writeln('Количество слов = ', F); end. Отладка и тестирование. Под отладкой программы понимается процесс испытания работы программы и исправления обнаруженных при этом ошибок. Обнаружить ошибки, связанные с нарушением правил записи программы на Паскале (синтаксические и 50 семантические ошибки) помогает используемая система программирования. Пользователь получает сообщение об ошибке, исправляет ее и снова повторяет попытку исполнить программу. Проверка на компьютере правильности алгоритма производится с помощью тестов. Тест — это конкретный вариант значений исходных данных, для которого известен ожидаемый результат. Прохождение теста — необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного сценария. Нашу программу, например, можно протестировать на значении N=6. На экране должно получиться: Введите число букв: 6 Количество слов = 720 Проведение расчетов и анализ полученных результатов — этот этап технологической цепочки реализуется при разработке практически полезных (не учебных) программ. Например, «Программа расчета прогноза погоды». Ясно, что ею будут пользоваться длительное время, и правильность ее работы очень важна для практики. А поэтому в процессе эксплуатации эта программа может дорабатываться и совершенствоваться. 4.13. Алгоритм Евклида Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел. Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натурально число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так: НОД(12,18)=6. Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом: ДАНО: M, N НАЙТИ НОД(М, N). В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М,N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида, 51 Идея этого алгоритма основана на том свойстве, что если M>N, то НОД(М,N) = НОД(М - N,N). Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа. Легко доказать это свойство. Пусть К — общий делитель М и N (M>N). Это значит, что M=mK, N=nK, где m, n — натуральные числа, причем m>n. Тогда M-N=K(m-n), откуда следует, что К — делитель числа М—N. Значит, все общие делители чисел М и N являются делителями их разности M-N, в том числе и наибольший общий делитель. Отсюда: НОД(М,N)= НОД(М - N,N). Второе очевидное свойство: НОД(М,М) = М. Для «ручного» счета алгоритм Евклида выглядит так: 1. если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма; 2. заменить большее число разностью большего и меньшего из чисел; 3. вернуться к выполнению пункта 1. Запишем алгоритм на АЯ и на Паскале (Табл. 15). Таблица 15 алг Евклид цел М, N нач вывод 'Введите М и N' ввод М, N пока М не = N, повторять нц если M>N то M:=M-N иначе N:=N-M кв кц вывод 'НОД=', М кон Program Evklid; var M, N: integer; begin writeln ('Введите М и N'); readln (M,N); while M<>N do begin if M>N then M:=M-N else N:=N – M: end; writeln ('НОД=', М) end. 52 Структура алгоритма — цикл-пока с вложенным ветвлением. Цикл повторяет выполнение, пока значения М и N не равны друг другу. Ветвление заменяет большее из двух значений на их разность. А теперь посмотрите на трассировочную таблицу (Табл.16) алгоритма для исходных значений М=32, N=24. Таблица 16 Шаг Операция M N Условие 1 ввод М 32 2 ввод N 24 3 M не =N 32≠24, да 4 M>N 32>24, да 5 M:=M-N 8 6 M не =N 8≠24, да 7 M>N 8>24. нет 8 N:=N - M 16 9 M не =M 8≠16, да 10 M>N 8>16, нет 11 N:=N-M 8 12 M не =N 8≠8, нет 13 вывод М 8 14 конец В итоге получился верный результат. Коротко о главном Последовательность этапов работы программиста при решении задачи на ЭВМ называется технологической цепочкой. Таких этапов шесть: 1. постановка задачи; 2. математическая формализация; 3. построение алгоритма; 4. составление программы на языке программирования; 53 5. отладка и тестирование программы; 6. проведение расчетов и анализ полученных результатов. Любой циклический алгоритм может быть построен с помощью команды «цикл-пока» (цикл с предусловием). Оператор цикла с предусловием в Паскале имеет вид: while <логическое выражение> do <оператор> Оператор, составляющий тело цикла, может быть простым или составным. Алгоритм Евклида предназначен для получения наибольшего общего делителя двух натуральных чисел. Структура алгоритма Евклида — цикл с вложенным ветвлением. Ручная трассировка может использоваться для проверки правильности лишь сравнительно простых алгоритмов. Правильность программ проверяется путем тестирования на компьютере. 4.14. Оператор цикла с постусловием Так называется оператор который имеет формат: REPEAT <тело цикла > UNTIL < условие выхода из цикла >. Здесь REPEAT, UNTIL- кодовые слова (англ.: повторять, до тех пор [,пока не будет выполнено]); < тело цикла > - произвольная последовательность операторов ТП; < условие выхода из цикла > - выражение логического типа. Операторы <тело цикла > выполняются хотя бы один раз, после чего проверяется < условие выхода из цикла >: если его значение есть FALSE, операторы <тело цикла > повторяются, в противном случае оператор REPEAT ... UNTIL завершает свою работу. Обратите внимание: пара REPEAT ... UNTIL подобна операторным скобкам BEGIN ... END, поэтому перед UNTIL ставить точку с запятой необязательно. Рассмотрим блок-схему алгоритма с оператором повторения Repeat…Until на примере следующей задачи: 54 Для х, таких, что 1 < x < M, вычислять и выводить члены ряда: x, x 2 , x 3 , … ,до тех пор, пока очередной член ряда меньше M и последним вывести первый член ряда превысивший или равный М . Блок-схема программы приведена на рис. 5. Tru e Выв. Y Y : = Y * X Y : = 1 Ввод X , M Вывод ' Введите X , M ' Y > = M False Рис.5 Блок-схема программы Запишем программу, для приведенной на Рис.5 блок-схемы Program Test_Repeat; Var x, y, M : real; Begin 55 ReadLn(x, M); y := x; Repeat {В цикле два оператора, но использовать операторные скобки не надо, т.к. слова – Repeat, Until ограничивают тело цикла.} Write ( y ); y := y * x Until y >= M; End. 4.15. Вопросы и упражнения 1. Как блок-схемой и на Алгоритмическом языке представляется команда цикла с предусловием? 2. Как программируется цикл с предусловием на Паскале? 3. Почему алгоритм вычисления N! должен быть циклическим? 4. Из каких этапов состоит работа программиста по решению задачи на ЭВМ? 5. Что такое «математическая формализация задачи»? 6. Что такое отладка программы? Что называется тестом? 7. Составить блок-схему алгоритма вычисления суммы всех положительный целых чисел, не превышающих данного натурального числа N. Проверить алгоритм трассировкой. Написать программу на Паскале. 8. Дано целое число X и натуральное N. Составить блок-схему алгоритма вычисления X в степени N. Проверить алгоритм трассировкой. Написать программу на Паскале. 9. Выполнить на компьютере программу «Evklid» . Протестируйте ее на значениях М=32, N=24; М=696, N=234. 10. Составить блок-схему алгоритма и программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу: НОД(А,В,С) = НОД( НОД(А,В), С). 11. Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: А х В = НОД(А, В) х НОК(А, В} 56 5. Работа с массивами в паскале 5.1. Понятие массива Массив (array) - это конечный набор элементов одного (базового) типа, которые сохраняются в последовательно размещённых ячейках оперативной памяти и имеют общее имя. В математике понятию массив соответствуют понятия вектора и матрицы. Различают одно- и многомерные массивы. Двумерный массив данных - это таблица, которая состоит из нескольких строк. Общий вид конструкции описания типа массив такой: <имя типа> = array [<размер>] of <имя базового типа>; Размер (количество элементов) массива чаще всего задают в виде диапазона целых чисел (например 1 . . 100 ) или именем некоторого перечислимого типа данных. Описать массив с помощью введенного имени типа можно в разделе объявления переменных var. Имена типов массивов и переменных-массивов указывает пользователь. 5.2. Одномерные массивы. Пример. Опишем тип массива mas – одномерный массив из 100 дробных чисел. Объявим массивы A и B типа mas и массив C — из 100 элементов-символов. type mas = array [1 . . 100] of real; var A, B: mas; C : array [1..100] of char; В этом примере продемонстрированы два способа объявления массивов в программе. Способ, которым введенs массивы А и B является наиболее распространенным. Над массивами в целом определена единственная команда присваивания. Например, команда A:= B все значения элементов массива B присваивает элементам массива A (делает значениями элементов массива A) при этом массивы должны иметь одинаковый тип. В большинстве случаев работа ведется с каждым элементом массива отдельно, например: A [ i ] := B [ j ] ; при этом переменные i и j должны получить конкретные числовые значения в предыдущих операторах программы. Для обработки элементов массива как правило используются индексные циклы for. Приведем пример простейшей программы, вычисляющей элементы массивов А и В и суммирующей элементы массивов A и B в массив C и выводящей массив С на экран. Program summa; const n = 10; 57 var А, B, C : array [ l . . n ] of integer; i : integer; begin for i := 1 to n do begin A[ i ] := i * i ; B [ i ] := 5 * i ; C [ i ] := A [ i ] + B [ i ]; writeln (C [ i ] : 6); {выводит С[i] в строку консоли и переводит курсор в начало следующей строки консоли} end; readln ; {этот оператор без списка ввода будет ожидать нажатия любой клавиши на клавиатуре, а человек - оператор в это время может разбираться с результатами, выданными на экран (консоль). Для возвращения к просмотру текста программы достаточно нажать любую клавишу} end. 5.3. Двумерные массивы Двумерные массивы предназначены для работы с табличными данными. В двумерном массиве элементы определяются именем массива и двумя индексами: первый индекс указывает номер строки, а второй — номер столбца, на пересечении которых находится элемент. Например, р [1, 2] - второй элемент первой строки массива р. Задача. Составить программу для построения таблицы умножения двух чисел (таблицы Пифагора) и занесения её в двумерный массив р. Вывести массив на экран в виде таблицы (матрицы). program Pifagor; const n = 9; type matr = array [ l . . n , l . . n ] of integer; var p : matr; i, j : integer; begin for i := 1 to n do begin 58 for j := 1 to n do {выводит все элементы i-ой строки матрицы в одну строку консоли} begin p [ i , j ] := i * j; write (p [ i , j] : 6); {выводит p [ i , j] в строку консоли } end; writeln; {переводит курсор в начало следующей строки консоли для вывода новой строки таблицы умножения} end; Readln; end. Для доступа к элементам массива необходимо после идентификатора массива в квадратных скобках указать индекс нужного элемента или список индексов, определяющий элемент многомерного массива. В качестве индексов могут выступать произвольные выражения, тип которых должен соответствовать типу индексов в описании массива. Например: m [1], m [(I + 1)*2]. Для двумерного массива доступ к элементам можно записать, например, так: V[3, 7], V[ i, j ]. Элемент массива считается переменной. Он может получать значения, например, в операторе присваивания, а также участвовать в выражениях. Для иллюстрации работы с массивами данных составим программу, проверяющую качество работы встроенного генератора псевдослучайных чисел Random. Поскольку этот генератор должен давать последовательность случайных целых чисел, равномерно распределенных на промежутке [ 0...d ) , где d > 0 - параметр обращения к Random, то количество выпадения каждого из чисел: 0,1,2,3, … (d-1) должно быть приблизительно одинаковым для достаточно большой последовательности из N случайных чисел. Program TestOfRandomGenerator; const N = 10000; {количество обращений к Random} d = 10; {диапазон изменения чисел} var measure : array [0..d-l] of word; i, j : integer; 59 Begin for i := 0 to d-1 do measure [ i ] := 0; for i := 1 to N do begin j := random(d) measure [j] := measure [j] +1 ; end; for i := 0 to d-1 do write(measure [ i ] :5); Readln; End. 5.4. Примеры алгоритмов и программ обработки одномерных массивов Рассмотрим несколько базовых алгоритмов обработки одномерных массивов. 1. Найти сумму значений элементов одномерного массива А=(1.1, -2.2, 6, 4, -5); Блок-схема алгоритма представлена на Рис. 6. 60 S : = S+A [ k ] S : = 0 K : = 1 , M 'Сумма = ' , S A [ k ] Вывод ' Введите M <= 100 ' Ввод M Рис.6 Блок-схема алгоритма 61 Ниже приведена программа, составленная для рассматриваемого алгоритма. Program Test_Summa; Var k, M : integer; S : real; A : array[1..100] of real; { тип массива real, т.к. среди заданных значений массива есть числа с десятичной точкой} Begin Write('Введите М <= 100 –количество элементов в вашем массиве'); ReadLn(M); S := 0; for k := 1 to M do Begin Write('Введите очередной элемент вашего массива '); ReadLn(a[k]);{программа считывает введенное число и переводит курсор в новую строку консоли} S := S + a[k]; End; WriteLn('Сумма элементов массива А= ', S); End. 62 2. Найти наибольшее значение элементов одномерного массива А=(1.1, -2.2, 6, 4, - 5); Блок-схема алгоритма представлена на Рис. 7. A [ k ] Вывод ' Введите M <= 100 ' Ввод M 'Наибольший элемент = ' , S К = 1 ИЛИ A [ k ] > S false k : = 1 , M tru e S : = A [ k ] Рис.7 Блок-схема алгоритма |