Сложные циклы
NEXT I
Характерные моменты циклического алгоритма
Циклические алгоритмы
Алгоритм называется циклическим, если все или отдельные его этапы в процессе решения задачи неоднократно повторяются.
Цикл обеспечивает повторное выполнение, или, иначе говоря, циклическую работу операторов. Оператор или группа операторов, повторяющаяся в цикле, называется «телом цикла».
Далее рассмотрим два типа циклических задач:
а) задачи, в которых вычисления многократно ведутся по одним и тем же формулам с различными значениями входящих в нее величин. Такие задачи иногда называются задачами на табулирование.
б) задачи, где значение некоторой величины вычисляется через значение этой же величины, полученное в предыдущем цикле (рекурсии). Примерами таких задач являются задачи вычисления сумм и произведений рядов, а также вычисление значений факториала.
- первоначальный вход в цикл выполняется через блок подготовки;
- цикл всегда характеризуется некоторой переменной, называемой параметром цикла. Начальное значение параметра задается перед циклом в блоке подготовки, а при каждом повторении цикла выполняются операторы тела цикла и параметр изменяется на определенную величину - шаг;
- число повторений цикла должно быть конечным, однако, не всегда число повторений известно или может быть вычислено заранее. Выход из цикла осуществляется при выполнении некоторых условий. Когда число повторений известно или может быть определено заранее, выход из цикла осуществляется при достижении параметром некоторой заранее заданной величины. Для такого рода задач используется оператор цикла «FOR … NEXT». В общем виде этот оператор цикла записывается следующим образом:
FOR I = I0 TO IN STEP DN ' начало цикла
операторы «тела цикла»
Здесь:
I - параметр цикла (переменная),
I0 - начальное значение параметра цикла (переменная или число),
IN - конечное значение параметра цикла (переменная или число),
DN - шаг изменения параметра (переменная или число), если шаг равен единице, то его можно опустить.
Этот оператор многократно выполняет операторы «тела цикла», находящиеся между FOR и NEXT для всех значений параметра I от I0 до IN. Структура самого оператора включает и подготовку цикла, и изменение параметра, и проверку условия выхода из цикла.
ПРИМЕР 11.1(задача типа а) Составить схему алгоритма и программу вычисления всех значений функции F(x) для всех значений аргумента х: F(x) = SIN(x)+COS(x), при -p £ х £p, шаг изменения аргумента Dх=0. | |
Рисунок 3. Схема алгоритма к примеру 11.1 | REM Циклический алгоритм CLS CONST PI=3.14 PRINT " X ", " Y " FOR X= - PI TO PI STEP 0.1 Y= SIN(x)+COS(x) PRINT X ,Y NEXT X END |
Результат выполнения программы на экране будет иметь вид:
Х Y -3.14 -1.001591 -3.04 -1.096262 -2.94 -1.179979 -2.84 -1.251906 …………………………………. 2.859999 -.6827266 2.959999 -.8029594 3.059999 -.9151694 Press any key to continue Чтобы продолжить, нажмите любую клавишу |
Пояснения к программе:
- в цикле FOR многократно вычисляются значения функции для всех значений аргумента. Значения аргумента и проверка условия выхода из цикла осуществляется самим оператором FOR.
ПРИМЕР 11.2(задача типа б) Вычислить сумму n слагаемых ряда: | ||
Рисунок 4. Схема алгоритма к примеру 11.2 | REM Цикл с известным числом REM повторений INPUT "Число слагаемых:", N S = 1 FOR I=1 TO N S=S+1/(3*I) NEXT I PRINT "Сумма ряда:"; S END Результат выполнения на экране: Сумма ряда: <число> | |
ПРИМЕР 11.3(задача типа б) Вычислить факториал n чисел: P= n!=1*2*3*….*n | ||
Рис. 5. Схема алгоритма к примеру 11.3 | REM Цикл с известным числом REM повторений INPUT "Число сомножителей:", N P = 1 FOR I=1 TO N P=P*I NEXT I PRINT N; "-факториал:"; P END Результат выполнения на экране: N-факториал : <число> | |
Пояснения к программам:
- с помощью циклов в этих программах последовательно вычисляется значение суммы и факториала (произведения). При этом каждое следующее значение вычисляется через предыдущее. Результатом многократных вычислений является одна величина - сумма ряда заданного числа слагаемых (11.2) или произведение заданного числа сомножителей (11.3);
- в приведенных примерах 11.1 - 11.3 число повторений легко определяется заранее. В примере 11.1 параметром цикла является переменная «х», а в 11.2 и 11.3 - переменная «I».
Когда условие задачи не позволяет определить заранее число повторений цикла, выход из цикла часто осуществляется по достижении заданной точности вычислений или по какому-либо другому условию, оговоренному в задании. В этих случаях удобно использовать следующие операторы цикла:
а)DO WHILE L <операторы "тела цикла"> LOOP | б)DO UNTIL L <операторы "тела цикла"> LOOP |
в) DO <операторы "тела цикла"> LOOP WHILE L | г) DО <операторы "тела цикла"> LOOP UNTIL L |
Здесь: L - логическое выражение.
Операторы, находящиеся между DO и LOOP повторяются до тех пор, пока выражение, стоящее после WHILE - истинно или до тех пор, пока выражение, стоящее после UNTIL - ложно.
Циклы типа а) и б) называются циклами с предусловием (проверка условия осуществляется перед началом выполнения тела цикла), а циклы в) и г) – циклами с постусловием (проверка условия осуществляется после каждого выполнения тела цикла). Циклы с постусловием выполнятся в программе хотя бы один раз, тогда как циклы с предусловием могут не выполниться ни разу.
ПРИМЕР 11.4. Вычислить сумму S ряда с заданной точностью е и количество слагаемых N, необходимых для достижения заданной точности: | |
Рисунок 6. Схема алгоритма к примеру 11.4 | REM Цикл с неизвестным числом REM повторений INPUT "Введите точность", e S = 1: I=1 DO A = 1/( 3*I ) ' слагаемое S = S+A : I=I+1 LOOP WHILE A > e PRINT "Сумма ряда:"; S-A,"N="; I-1 END Результат выполнения на экране: Сумма ряда:<число> N=<число> |
Пояснения к программе:
- вычислить сумму ряда с точностью е - это значит производить вычисления до тех пор, пока очередной член последовательности не станет меньше или равен заданной точности;
- в примерах 11.2 и в 11.4, в обоих случаях требуется вычислить сумму ряда. В первом случае количество слагаемых определено условием задачи, а во втором - слагаемое последовательно, в цикле, прибавляется к сумме до тех пор, пока оно (слагаемое) не станет меньше или равно некоторого маленького числа (заданной точности). Такая постановка задачи имеет смысл только для сходящихся рядов, т.е. слагаемое должно стремиться к нулю.
Далее приведено еще несколько примеров циклических программ.
ПРИМЕР 11.5. Дано натуральное число n. Определить количество цифр в этом числе. | ||||
Рисунок 7. Схема алгоритма к примеру 11.5 | CLS REM Ввод числа N REM Проверка: N - натуральное DO INPUT N LOOP N<>INT(N) OR N<=0 I%=0 : X=N DO WHILE X<>0 X = X \ 10 ‘ уменьшаем число на разряд I%=I%+1 LOOP PRINT “В числе”; N; I%; “цифр”» END |
Пояснения к программе:
- при очередном выполнении тела цикла число уменьшается на разряд (операцией целочисленного деления); в счетчике I происходит подсчет, сколько таких уменьшений выполнено;
- цикл завершается, когда число становится равным нулю (т.е. число «закончилось»).
ПРИМЕР 11.6. Дано натуральное число n. Поменять порядок следования цифр в этом числе на обратный. | |
Рисунок 8. Схема алгоритма к примеру 11.6 | CLS REM Ввод числа N REM Проверка: N - натуральное DO INPUT N LOOP N<>INT(N) OR N<=0 I%=0 : X=N DO WHILE X<>0 X = X \ 10 ‘ уменьшаем число на разряд I%=I%+1 LOOP X=N FOR J=I TO 0 STEP -1 REM получаем очередную цифру C=X MOD 10 REM уменьшаем число на разряд X=X \ 10 ‘ REM формируем новое число Z=Z + C * 10^(J-1) NEXT J PRINT Z END |
Пояснения к программе:
- этот пример является продолжением предыдущего;
- после того как мы получили количество цифр в числе I, организуем цикл, начиная с I до 0 с шагом -1, в котором формируется новое число с обратным порядком следования цифр: получаем очередную цифру исходного числа, уменьшаем число на разряд, добавляем к новому числу полученную цифру, умноженную на 10 в соответствующей степени (смотри программу).
ПРИМЕР 11.7. Определить является ли случайное число Х простым.
CLS
REM Задаем целое число с помощью датчика случайных чисел
RANDOMIZE TIMER
X=FIX(RND*100)
REM Определяем делится ли введенное число на какое-либо другое кроме 1 и REM самого себя без остатка
FOR j = 2 TO X\2 'т.к. делители числа образуют пары
REM Если находится делитель, то число не простое, дальше можно не делить
IF X MOD j = 0 THEN PRINT Х, " - это число не простое" : END
NEXT j
REM Если вышли из цикла, значит делителей у числа нет
PRINT USING " простое число: "; Х
END
ПРИМЕР 11.8. Вводится последовательность чисел, 0 – конец последовательности. Определить, содержит ли последовательность хотя бы два равных соседних элемента. | ||||
Рисунок 8. Схема алгоритма к примеру 11.8 | CLS INPUT “X=“, X INPUT “X=“, Y F=0 DO WHILE Y <> 0 IF X = Y THEN F = 1 X = Y INPUT “X=“, Y LOOP IF F = 0 THEN REM Равных соседних элементов нет PRINT “НЕТ” ELSE REM Есть равные соседние элементы PRINT “ДА” ‘ END IF END |
Пояснения к программе:
- вводим два первых элемента последовательности как X и Y, задаем начальное значение переменной F (признак того, что в последовательности нет равных элементов F=0 или есть равные элементы F=1);
- в цикле сравниваем два числа и, если они равны, устанавливаем значение F=1;
- запоминаем значение Y в X и вводим новое Y;
- в зависимости от значения переменной выводим результат.
Цикл называется сложным, если он содержит в себе другой, вложенный в него цикл. Количество вложенных друг в друга циклов (глубина вложений) может быть достаточно большим. Каждому циклу соответствует свой параметр. Типы циклов, из которых образован сложный, могут быть различными, это зависит от конкретной задачи. Первоначальный вход в любой цикл допустим только через блок подготовки соответствующего цикла. В общем виде схема алгоритма сложного цикла приведена на рисунке 9. Тело цикла включает в себя операторы соответствующего цикла. Причем для каждого значения параметра внешнего цикла параметр внутреннего цикла пробегает все свои значения.
Рисунок 9. Схема алгоритма сложного цикла глубиной два
Отметим, что циклы должны быть вложены друг в друга как матрешки, т.е. первым закрывается тот цикл, который был открыт последним. В противном случае будет выдано сообщение об ошибке. Название переменной после оператора NEXT можно не писать, тогда автоматически будет закрываться цикл, который на данный момент открыт последним.
Если несколько усложнить условия примера 11.7, то для его решения придется использовать алгоритм сложного цикла.
ПРИМЕР 11.9: Найти и вывести все простые числа от 1 до 1000.
CLS
n=0
FOR i = 1 TO 1000 'начало внешнего цикла
FOR j = 2 TO i \ 2 'начало внутреннего цикла
IF i MOD j = 0 THEN GOTO 20
NEXT j 'завершение внутреннего цикла
n=n+1 'подсчет количества простых чисел
PRINT i 'вывод простого числа
20 NEXT i 'завершение внешнего цикла
PRINT "КОЛИЧЕСТВО ПРОСТЫХ ЧИСЕЛ НА ИНТЕРВАЛЕ:"; n
END
Лабораторное задание
1. Набрать, отладить и выполнить программы, реализующие циклические алгоритмы Вашего индивидуального задания.
2. Составить блок-схему.
3. Проанализировать работу операторов, пользуясь отладочными режимами.
4. Составить отчет. Защитить работу.
Лабораторная работа состоит из четырех задач. Студент выбирает из списка заданий свой индивидуальный вариант и выполняет его.
Вариант №1
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Приписать по единице перед и после этого числа.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить номер максимального числа в данной последовательности.
Вариант №2
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Переставить первую и последнюю цифры в этом числе.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем Определить, сколько раз в ней меняется знак.
Вариант №3
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Определить произведение цифр этого числа.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить максимальное число в данной последовательности.
Вариант №4
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Определить сумму цифр этого числа.
Задание № 4.
Вводится последовательность ненулевых чисел. Определить два максимальных числа в данной последовательности.
___________________________________________________________________
Вариант №5
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Прибавить по единице к старшему и к младшему разряду этого числа.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить два минимальных числа в данной последовательности.
Вариант №6
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Определить, является ли оно простым.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить максимальное и минимальное числа в данной последовательности.
Вариант №7
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п (n>2). Определить все делители данного числа.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить максимальную сумму двух соседних элементов в данной последовательности.
Вариант №8
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Определить входит ли цифра m в данное число п.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить максимальное произведение двух соседних элементов в данной последовательности.
Вариант №9
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Даны натуральные числа п и m. Вывести все простые числа в диапазоне от п до m.
Задание № 4.
Вычислить число точек с целочисленными координатами, попадающих в круг радиуса R и с центром в начале координат.
Вариант №10
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Вывести все простые делители данного числа.
Задание № 4.
Вычислить число точек с целочисленными координатами, попадающих в квадрат со стороной a, центр пересечения диагоналей которого находится в начале координат.
Вариант №11
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Даны натуральные числа п и m. Вывести сумму всех простых чисел в диапазоне от п до m.
Задание № 4.
Вычислить число точек с целочисленными координатами, попадающих в квадрат со стороной a, центр пересечения диагоналей которого находится в начале координат, но не попадающих во вписанный в него круг.
Вариант №12
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Вывести все совершенные числа, меньшие п (число является совершенным, если оно равно сумме своих делителей, включая 1, но не включая само число).
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить среднее арифметическое чисел данной последовательности.
Вариант №13
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Вывести число, меньшие п с максимальной суммой делителей.
Задание № 4.
Вводится последовательность ненулевых чисел, завершаемая нулем. Определить среднее арифметическое положительных чисел данной последовательности.
Вариант №14
Задание № 1.
Вычислить выражения, используя для организации цикла операторы FOR … NEXT (значения переменной п задавать с клавиатуры):
Задание № 2.
Определить сумму ряда с заданной точностью t ( ) и число слагаемых, необходимое для достижения этой точности.
Задание № 3.
Дано натуральное число п. Вывести число, меньшие п с максимальным произведением делителей.
Задание № 4.
Вычислить число точек с целочисленными координатами, попадающих в прямоугольник со сторонами a и b, центр пересечения диагоналей которого находится в начале координат.
Лабораторная работа № 12
Работа с одномерными массивами
Цель работы:
1. Изучение приемов программирования с использованием массивов.
2. Закрепление навыков работы в отладочных режимах среды QBasic.
Массивом называют совокупность данных одного типа, обозначаемую одним именем. В зависимости от типа данных массивы могут быть числовыми или текстовыми. При работе с массивами, в ЭВМ под каждый элемент массива отводится ячейка памяти, обращение к которой осуществляется с помощью имени массива с индексом, например А(15). Положение элемента в массиве определяется индексами: одним - для одномерных массивов, двумя - для двумерных (матриц) и т.д. В QBasic допускаются массивы размерностью 255. Максимальное значение каждого индекса не должно превышать 32767.
Имя массива образуется так же, как имя простой переменной. Индексы заключаются в круглые скобки и разделяются запятой, если массив не одномерный. В качестве индексов использоваться числа, переменные или арифметические выражения, значения которых автоматически округляются до целого. Если индексы не числовые, то их значения должны быть определены заранее.
Примеры обозначения в QBASIC элементов массивов:
AQ(33), AQ(I), AQ(I + 4/3) - для одномерного массива;
AD(12,3), AD(I,J), AD(I/2,J+3) - для двумерных массивов.
В случае, когда какой-либо из индексов массива превышает 10, массив должен быть заранее объявлен оператором DIM. В операторе DIM указываются имена массивов и в круглых скобках верхние и нижние границы изменения индексов, которые должны быть целыми положительными числами или переменными, значения которых ранее определены в программе.
Если в процессе выполнения программы значение индекса превысит верхнюю границу массива, то система выдаст сообщениеSubscript out of range (Индекс вне диапазона).
Например, оператор DIM ASD12(5 TO 50) AS INTEGER описывает одномерный целочисленный массив, имя которого ASD12, а индексы могут принимать значения от 5 до 50, т.е. под этот массив выделяется 46 ячеек памяти.
Значение нижней границы индексов может быть опущено, и тогда по умолчанию оно принимается равным нулю, например, оператор
DIM MASSIV1(15) описывает одномерный массив MASSIV1, элементы которого принимают вещественные значения обычной точности (тип SINGLE по умолчанию),а индексы могут принимать значения от 0 до 15, т.е. зарезервировано 16 ячеек памяти.
Обработка массивов в QBasic осуществляется поэлементно, в том числе и ввод-вывод массива. Если массив содержит несколько элементов, то задать их значения можно с помощью операторов присваивания: