Электронное обучение (Информатика - 9 класс). § 15. Программирование циклов.

Программирование циклов (§ 15. Программирование циклов)

Вы научились составлять линейные и ветвящиеся программы на Паскале. Теперь нужно освоить программирование циклов. Снова будем учиться на примере конкретной задачи. Но, в отличие от предыдущих примеров, подход к ее решению будет несколько другим.

Этапы решения расчетной задачи на компьютере

Часто задача, которую требуется решить, сформулирована не на математическом языке. Для решения на компьютере ее сначала нужно привести к форме математической задачи, а потом уже программировать.

Работа по решению таких задач с использованием компьютера проходит через следующие этапы:

1. Постановка задачи.
2. Математическая формализация.
3. Построение алгоритма.
4. Составление программы на языке программирования.
5. Отладка и тестирование программы.
6. Проведение расчетов и анализ полученных результатов.

Эту последовательность называют технологией решения задачи на компьютере.

В чистом виде программированием, т. е. разработкой алгоритма и программы, здесь являются лишь 3-й, 4-й и 5-й этапы.

На этапе постановки задачи должно быть четко определено, что дано и что требуется найти.

Второй этап - математическая формализация. Здесь задача переводится на язык математических формул, уравнений, отношений. Далеко не всегда эти формулы очевидны. Нередко их приходится выводить самому или отыскивать в специальной литературе. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели.

Третий этап - построение алгоритма. Вы знаете два способа описания алгоритмов: блок-схемы и Алгоритмический язык (АЯ).

Первые три этапа - это работа без компьютера. Дальше следует собственно программирование на определенном языке в определенной системе программирования. Последний (шестой) этап - это использование уже разработанной программы в практических целях.

Задача о перестановке букв. Программирование цикла на Паскале

Проследим все этапы технологии на примере конкретной задачи.

1. Постановка задачи. Дано N кубиков, на которых написаны разные буквы. Сколько различных N-буквенных слов можно составить из этих кубиков (слова не обязательно должны иметь смысл)?

Искомую целочисленную величину обозначим буквой F. Тогда постановка задачи выглядит так:

2. Математическая формализация. Получим расчетную формулу. Сначала рассмотрим несколько конкретных примеров. Имеются два кубика с буквами "И" и "К". Ясно, что из них можно составить два слова:

Добавим к ним третью букву С. Теперь число разных слов будет в три раза больше предыдущего, т. е. равно 6:

Если добавить четвертую букву, например "А", то число слов возрастет в четыре раза и станет равным 24:

Попробуйте записать все варианты слов из пяти букв: И, К, С, А, У. Сделать это непросто. Ясно лишь, что количество таких слов будет в пять раз больше 24, т. е. равно 120. Из шести букв можно составить 720 различных слов. С ростом числа букв число слов быстро растет. Например, для 10 букв получается 3 628 800 слов.

Подобные задачи решает раздел математики, который называется комбинаторикой.

Количество различных комбинаций из N предметов, получаемых изменением их порядка, называется числом перестановок. Это число выражается функцией от N, которая называется факториалом и записывается так:

Читается: "N факториал". Для любого натурального значение N! вычисляется как произведение последовательности натуральных чисел от 1 до N. Например:

1! = 1;
2! = 1-2 = 2;
3! - 1-2-3 - 6;
4! - 1-2-3-4 = 24;
5! = 1-2-3-4-5 = 120
и т. д.

Теперь вернемся к формулировке задачи. Если N обозначает количество букв, a F - количество слов из этих букв, то расчетная формула такова:

3. Построение алгоритма. Поскольку алгоритм должен быть независимым от данного значения N, то его нельзя сделать линейным. Дело в том, что для разных N надо выполнить разное число умножений. В таком случае с изменением N линейная программа должна была бы менять длину.

Алгоритм решения данной задачи будет циклическим. С циклическими алгоритмами вы уже познакомились, работая с графическим исполнителем.

Цикл - это команда исполнителю многократно повторить указанную последовательность команд.

Рассмотрим блок-схему на рис. 3.11 и алгоритм на АЯ.

Здесь применена знакомая вам алгоритмическая структура "цикл с предусловием". Выполняется она так: пока истинно условие цикла, повторяется выполнение тела цикла.

алг СЛОВА цел F, N, R нач ввод N      F:=1      R:=1      пока R<=N, повторять      нц           F:=F*R           R:=R+1      кц      вывод F кон
Рис. 3.11. Блок-схема алгоритма вычисления факториала

Тело цикла составляют две команды присваивания, заключенные между служебными словами нц и кц. Условие цикла - это отношение R<=N (R меньше или равно N).

В данном алгоритме переменная R выполняет роль множителя, значение которого меняется от 1 до N через единицу. Произведение накапливается в переменной F, начальное значение которой равно 1. Цикл заканчивается, когда R становится равно N + 1. Это значение в произведение уже не попадет.

Для проверки правильности алгоритма построим трассировочную таблицу (для случая N = 3):

Шаг	Операция	N	F	R	Условие
1	ввод N	3	-	-
2	F:=1		1	-
3	R:=1			1
4	R<=N				1<=3, да
5	F:=F*R		1
6	R:=R+l			2
7	R<=N				2<=3, да
8	F:=F*R		2
9	R:=R+1			3
10	R<=N				3<=3,да
11	F:=F*R		6
12	R=R+l			4
13	R<=N				4<=3, нет
14	вывод F		6
15	конец

Из этой таблицы хорошо видно, как менялись значения переменных. Новое значение, присвоенное переменной, стирает ее старое значение (в данной таблице не повторяется запись значения переменной, если оно не изменяется; в таком виде таблица менее загромождена числами). Последнее значение F равно 6. Оно выводится в качестве результата. Очевидно, что результат верный: 3! = 6.

4. Составление программы. Чтобы составить программу решения нашей задачи, нужно научиться программировать циклы на Паскале. Основной циклической структурой является цикл с предусловием (цикл-пока). С помощью этой структуры можно построить любой циклический алгоритм. Оператор цикла с предусловием в Паскале имеет следующий формат:

Служебное слово while означает "пока", do - "делать", "выполнять".

Оператор, стоящий после слова do, называется телом цикла. Тело цикла может быть простым или составным оператором, т. е. последовательностью операторов между служебными словами begin и end.

А теперь запрограммируем на Паскале алгоритм решения нашей задачи (добавим к нему организацию диалога).

Program Words;
var F, N, R: integer;
begin
     write('Введите число букв');
     readln(N);
     F:=l;
     R:=1;
     while R<=N do
     begin
          F:=F*R;
          R:=R+1
     end;
     write('Из ',N,' букв можно составить ', F,' слов' )
end.

Снова бросается в глаза схожесть алгоритма на АЯ и программы на Паскале. Обратите внимание на то, что в Паскале нет специальных служебных слов для обозначения конца цикла (так же как и конца ветвления). Во всех случаях, где это необходимо, используются слова begin и end.

Что такое отладка и тестирование программы

5. Отладка и тестирование. Под отладкой программы понимается процесс испытания работы программы и исправления обнаруженных при этом ошибок. Обнаружить ошибки, связанные с нарушением правил записи программы на Паскале (синтаксические и семантические ошибки), помогает используемая система программирования. Пользователь получает сообщение об ошибке, исправляет ее и снова повторяет попытку исполнить программу.

Проверка на компьютере правильности алгоритма производится с помощью тестов. Тест - это конкретный вариант значений исходных данных, для которого известен ожидаемый результат. Прохождение теста - необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного сценария.

Нашу программу, например, можно протестировать на значении N = 6. На экране должно получиться:

Введите число букв: 6
Из 6 букв можно составить 720 слов.

6. Проведение расчетов и анализ полученных результатов - этот этап технологической цепочки реализуется при разработке практически полезных (не учебных) программ. Например, программы "Расчет прогноза погоды". Ясно, что ею будут пользоваться длительное время, и правильность ее работы очень важна для практики. А поэтому в процессе эксплуатации эта программа может дорабатываться и совершенствоваться.