Алгоритмическая структура ПОВТОРЕНИЕ

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

20.1. ПОКА – цикл с предусловием (WHILE)

 

 

While – оператор цикла. Его принято называть «цикл с предусловием», так как проверка условия выполнения цикла осуществляется до выполнения операторов, входящих в состав тела цикла.

P – логическое выражение (условие выполнения цикла);

S – оператор (простой или составной), который выполняется, если Р истинно; тело цикла.

Например, согласно фрагменту, на экран компьютера при K=3 будет выведено:

 

Делай 3

Делай 4

Тело цикла

Делай 5

 

При K=5 тело цикла будет выполняться один раз, а при K=10 (K>5) – ни одного раза.
Примеры:

Пример 1. Программа вычисления значений функции y=1/x при x=1; 1,1; 1,2; 1,3; …; 2.
Переменной х присваивается значение 1. Так как условие 1 ≤ 2 истинно, выполняется тело цикла: вычисляется и выводится на экран значение y, значение переменной x увеличивается на 0,1. Условие 1,1 ≤ 2 истинно, поэтому выполняется тело цикла для значения x = 1,1; x становится равным 1,2; и т. д. Последний раз тело цикла выполнится при x=2. Затем значение переменной x становится равным 2,1; условие 2,1 ≤ 2 ложно, выполнение цикла завершается.	Найти: y – значения функции y=1/x при x = 1; 1,1; 1,2; 1,3; …; 2. Метод: Будем последовательно подставлять в формулу y=1/x вместо х значения 1; 1,1; …; 2, вычислять соответствующие значения y; каждое полученное значение y выводить на экран.
Программа Функция Описание x, y : вещественный Конец_Описания x:=1 Повторять_Пока x<=2 y:=1/x Вывод(y, '; ') x:=x+0.1 Завершить Конец_Программы
Program FUNCT_1 ; Var x, y : Real ; Begin x:=1; While x<=2 do Begin y:=1/x ; Writeln (y : 0: 5); x:=x+0.1 End End.
После запуска программы обратите внимание на то, что на экран не выводится значение функции в последней точке x=2. Это связано с особенностью представления числовой информации (в частности, вещественных чисел) в памяти компьютера. Рекомендуется для получения требуемого вывода записать в заголовке цикла условие в виде: While x<=b+h/2 do … , где h – дробный шаг изменения значения x (в данном случае, x<=2.05).
Пример 2. Программа нахождения первой (старшей) цифры заданного натурального числа n. Идея алгоритма основана на последовательном делении на 10 числа n и получаемых частных от деления; процесс деления закончится, когда будет получен остаток, меньший 10.
	Program ONE ; Var n : LongInt ; {заданное число} C : LongInt ; {искомая цифра} Begin Write ('n=') ; Readln (n); C:=n; While C>9 do C:=C div 10 ; Writeln ('Первая цифра=',C) End.
Анализируя программу, можно заметить, что тело цикла может выполняться различное количество раз: ни одного (например, при вводе чисел 2, 8 или другого, не большего 9), 1 раз (для двузначных чисел), 2 (трехзначных) и т.д. Использование цикла While в данном случае вполне уместно.
Пример 3. Петя купил в магазине определенное количество конфет и хочет разделить их поровну между своими тремя друзьями. Написать программу проверки, возможен ли такой дележ. Задача осложняется тем, что Петя учится в подготовительном классе и пока еще не умеет ни делить, ни умножать.
Дано: n – количество купленных конфет Надо: можно ли разделить n на 3 Связь: можно, если остаток от деления n на 3 равен нулю, и нельзя – в противном случае При: n>0 (считать, что данные корректны) Метод: Так как Петя не умеет выполнять операцию деления, предложим ему раскладывать конфеты на три кучки, добавляя в каждую по очереди по одной конфете (количество конфет при этом будет уменьшаться на 3). Если после очередного прохода по кучкам не останется ни одной конфеты, значит, дележ возможен. Если кому-то не хватило конфеты, невозможен. Здесь тело цикла содержит единственную команду n:=n-3.	Program VKUSNO; Var n : Integer ; Begin Write ('Число конфет= '); Readln (n); While n>0 do n:=n-3 ; if n=0 then Write ('можно ') Else Write ('нельзя '); Writeln ('разделить') End.
S := 0; n :=1; While n<=10 do S := S + k ; Writeln (S) ; * Пример 4. Имеется фрагмент программы суммирования квадратов двадцати последовательных натуральных чисел, в котором Женя допустил ошибки. При запуске программа зависает, и Евгений вынужден прерывать ее работу принудительно (Ctrl+Break). Поможем автору разобраться в причинах зависания.

Анализ 1. Зависание программы свидетельствует о наличии так называемого “зацикливания”: мы имеем дело с бесконечным циклом, в котором условие выхода из цикла, в данном случае, n>10, не наступает, пока не будет выполнено принудительное завершение работы программы. Проследим изменение значений переменной n в заголовке цикла. Первоначально n=1. Условие 1<=10 истинно, поэтому происходит вхождение в цикл, и выполняется команда присваивания S:=S+k; Значение n не изменяется, и компьютер постоянно проверяет справедливость истинного условия 1<=10. Итак, первая ошибка связана с неправильной организацией работы счетчика n: автор задал начальное и конечное значения, а значение шага не определил.

Устранение ошибки 1. Добавим в тело цикла команду присваивания для увеличения значения n на 1: n:=n+1. Это приведет к необходимости организации составного оператора Begin .. End. После внесения изменений и запуска программы зацикливание не наблюдается, однако на экран выводится неверный результат (число 0).

Анализ 2. Обратим внимание, как осуществляется суммирование. Вначале S=0 и затем в цикле должна накапливаться сумма путем добавления квадратов чисел 1, 2, …, 20. Запись команды S := S + k ; говорит о том, что в переменной S накапливаются значения переменной k, которая ни задается, ни изменяется. Сами суммируемые числа обозначены в программе переменной n, которую и следует записать в теле цикла вместо k.

Устранение ошибки 2. Заменим команду S := S + k; на S := S + n;

Анализ 3. Вы, пожалуй, уже заметили другие ошибки, допущенные автором программы, которые возникли по причине несоответствия алгоритма условию задачи: программа вычисляет сумму десяти последовательных чисел (сравните с условием). Эти ошибки можно обнаружить, если подобрать более простое условие. Подсчитайте, например, устно сумму пяти чисел (1² +2² +3² +4² +5² =55), измените в программе условие n<=10 на n<=5, запустите программу на выполнение и сравните полученные результаты.

Устранение ошибки 3. Окончательный вариант фрагмента программы примет такой вид.

* Пример 5. Фрагмент программы, который выполняется до тех пор, пока не будет введено нужное число: например, А, удовлетворяющее условию 0<A<pi/2: Такую конструкцию удобно использовать, например, для контроля ввода исходных данных.

P:=False; {присвоим логической переменной Р значение False: нужное условие не выполнено} While P=False do {пока не выполнено нужное условие} Begin {будем повторять ввод} Writeln ('Введите число 0<A<pi/2'); Readln (A); If (A>0) and (A<pi/2) Then P:=True {условие выполнено} End;

1. Определите, сколько раз будет выполняться тело цикла:

1) i:=1; While i<=50 do Begin Writeln (i); i:=i+2 End ;

2) k:=12; While k<=356 do Begin H:=k/5; k:=k+3 End;

3) N:=100; While N>=0 do Begin N:=N-3; s:=s+1 End;

* 2. При каких начальных значениях переменной р завершится выполнение оператора цикла:

1) while p>2.5 do p:=sqrt (p) ; 2) while abs (p)>0 do p:=p+1 ;

3) while sqr (p) >=0 then p:=sin (p) ; 4) while p>p/2 do p:=p-0.5 ;

* 3. Найдите ошибки, содержащиеся в приведенном фрагменте программы, предназначенной для получения числа, цифры которого записаны в обратном порядке по отношению к данному натуральному числу (например, если заданное число n=739, то программа должна получить число a=937). После обнаружения ошибок их следует исправить.

x:=n ; a:=0 ; while x>=0 do Begin a:=a+x mod 10 x:=x div 10 End ;

Напишите программы решения следующих задач:

1) найти сумму цифр заданного натурального числа;

2) определить количество цифр заданного натурального числа;

3) проверить, равна ли пяти старшая цифра заданного натурального числа;

4) проверить, равна ли старшая цифра заданного натурального числа младшей;

5) найти сумму чисел, заключенных на отрезке [a, b] и отличающихся друг от друга на величину h (a, b, h вводятся с клавиатуры);

6) найти среди чисел 1, 1+1/2, 1+1/2+1/3, … первое, большее а;

7) вычислить сумму 1+1/2+1/3+ … + 1/n (значение n вводится с клавиатуры);

* 8) найти наибольший делитель заданного натурального числа, отличный от самого числа;

9) Незнайке поручили разделить яблоки, собранные на субботнике по уборке урожая, поровну между участниками субботника. Требуется определить, сколько яблок достанется каждому и сколько яблок останется (количество яблок и участников субботника вводятся с клавиатуры). Получить решение двумя способами: по методу Знайки и Незнайки, который не умеет ни делить, ни умножать;

* 10) вычислить значение π с заданной точностью ε с использованием бесконечного разложения:. Вычисления продолжать до тех пор, пока очередной член ряда не окажется меньше заданной погрешности ε (этот член ряда в сумму уже не включать);

11) вычислить значения функций y=sin x и y=cos x на отрезке [-1; 1] c шагом 0,1. Результат вывести в таблицу (справа приводится «шапка» таблицы);	---------------------------- ! x ! sin x ! cos x ! ----------------------------
12) помогите Незнайке подсчитать количество ковриков квадратной формы, которое понадобится, чтобы покрыть ими пол комнаты прямоугольной формы (размеры комнаты вводятся с клавиатуры). План расположения ковриков см. на рисунке. Например, если размеры комнаты 300(см)х 450(см), то понадобится 3 коврика.

* 13) последовательность чисел формируется путем i-кратного дублирования i-го числа из ряда натуральных чисел: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, … Определить, какое число Nнаходится на k-м месте этой интересной последовательности (kзадано, 1≤k≤2000000000).

20.2. ДЛЯ – цикл с параметром (FOR)

 

Переменная I должна быть порядкового типа; I_нач, I_кон – выражения, совместимые с переменной I.

 

FOR – оператор цикла с параметром (шагом). Здесь тело цикла повторяется для всех значений параметра I, определенного в границах [I_нач ; I_кон] (отсюда и название цикла). Порядок его выполнения: вычисляются значения выражений I_нач и I_кон; параметр цикла принимает последовательно все значения от начального до конечного; для каждого из них выполняется тело цикла.

Служебное слово TO в записи оператора цикла предполагает, что I_нач≤I_кон, при этом значение параметра цикла на каждом шаге увеличивается на 1. Служебное слово DOWNTO предполагает, что I_нач ≥ I_кон, и значение параметра уменьшается на 1. При нарушении этих условий цикл выполняться не будет. После выхода из цикла значение параметра цикла не всегда определено, что следует учитывать при разработке циклических программ.

Пример 1 (экологическая модель). В результате сброса в реку промышленных стоков произошло ее загрязнение свинцом. Какой окажется концентрация свинца в реке через заданное время (n суток), если известны его начальная концентрация и коэффициент суточного уменьшения. Скорректируйте математическую постановку задачи и алгоритм ее решения в соответствии с изменениями в формулировке задачи (задача 2 п. 9.1). Анализ алгоритма свидетельствует о возможности его реализации с помощью цикла FOR (в алгоритме присутствует целочисленная переменная i, для которой известны начальное значение 1, конечное – n, шаг изменения 1).
Программа СБРОС Описание C0, K, Cn : вещественный i, n : целый Конец_Описания Ввод(C0, 'Начальная концентрация=') Ввод(K, 'Коэффициент=') Ввод(n, 'Сколько суток прошло=') Cn:=C0 Повторять_Для i От 1 До n Cn:=Cn/K Завершить Вывод (Cn, 'Cn=') Конец_Программы	Program Sbros ; Var C0, K, Cn : Real ; i, n : Integer ; Begin Write ('Начальная концентрация=') ; Readln (С0) ; Write ('Коэффициент =') ; Readln (K) ; Write ('Сколько суток прошло = ') ; Readln (n) ; {здесь опущен контроль входных данных} Cn:=C0 ; For i:=1 To n do Cn:=Cn/K ; Writeln ('Cn= ', Cn: 0: 4) End.
Пример 2. Смоделировать работу сберегательного банка: написать программу начисления ежегодной денежной суммы вклада, положенной в банк под P% с капитализацией вклада (первоначальная сумма и число лет вводятся с клавиатуры). Считать, что данные корректны.
Дано: S – первоначальная сумма, K - количество лет, P – годовая процентная ставка. Найти: S1, S2, …, Sk – сумма на счете в конце 1-го, 2-го, …, K-го года. Связь: , где n=1, 2, 3, …, K При: K ≥ 1; S > 0; 3 < Р < 50 Метод: Первоначально подставим в правую часть формулы значение S и найдем S1 (новую сумму по истечении одного года). При подстановке S1 в правую часть формулы найдем значение S2 по истечении двух лет и т. д. Такие манипуляции проделаем K раз. Для подсчета количества прошедших лет введем переменную g.	Program Pribyl ; Var S : Real ; P, K, g : Integer ; Begin Write ('Начальная сумма=') ; Readln (S) ; Write ('Ставка P (%)=') ; Readln (P) ; Write ('Количество лет=') ; Readln (K) ; For g := 1 To K do Begin S := S*(1+P/100) ; Writeln (g, ': ', S : 0 : 2) End End.
Пример 3. Составить программу отсчета времени, оставшегося до начала спектакля: программа должна предложить ввести оставшееся время (в с) и выводить на экран отсчет времени в обратном порядке. Когда отсчет окажется равным нулю, требуется вывести текст “Начало спектакля. Вход запрещен!”. Испытайте программу, подберите подходящие цвета фона, выводимого текста, параметр для процедуры Delay, позволяющий выводить на экран посекундное время, близкое к реальному.	Program Nachalo; Uses CRT; Var T, S : Integer; Begin Write ('Время до начала (с)= '); Readln (T); For S:=T downto 0 do Begin ClrScr; GotoXY (40, 10) ; Write (S); Delay (1000) End ; GotoXY (35, 15); TextColor (4); Writeln ('Начало спектакля !!!'); Writeln ('Вход воспрещен !!!'); End.
* Пример 4. Буратино нашел записку, где указан маршрут к кладу. Маршрут задается в виде инструкций, указывающих код направления движения (в соответствии с приведенной схемой) и число шагов в этом направлении. Требуется найти координаты клада, если известно число инструкций и для каждой из них код направления и число шагов. Первоначально Буратино находится в начале координат, откуда и начинается поиск клада. Длина шага всегда постоянна и равна 1. Заметим, что при перемещении в соответствии с данной схемой происходит смещение относительно предыдущей точки вдоль оси OX и OY соответственно на и единиц, где К – код направления. Таким образом, новые координаты Буратино при перемещении на S шагов в направлении К могут быть вычислены по формулам: где первоначально Х= Y= 0.	Program KLAD; Var i, N, K, S : Longint; X, Y : Real; Begin Write ('N=') ; Readln (N); {N - общее число инструкций} X:=0; Y:=0; {Маршрут начинается в начале координат} For i:=1 to N do {Для каждой} Begin {инструкции} Readln (K, S); {вводим код направления и число шагов,} X:=X+S*sin (pi/4*(K-1)); {вычисляем (X,Y) – новые координаты точки} Y:=Y+S*cos (pi/4*(K-1)) End; Writeln (X:0:3,' ',Y:0:3) End.
Пример 5. Известен возраст каждого конкурсанта фестиваля «Славянский базар». Определить средний возраст конкурсантов. Пусть возраст конкурсантов задается как число полных лет. Введем обозначения: K – общее количество конкурсантов, V – возраст очередного конкурсанта, S – суммарный возраст, SV – средний возраст конкурсантов. Тогда SV = S/K. Найдем вначале суммарный возраст, выполняя постепенное суммирование с переменной S значения возраста V очередного конкурсанта. Первоначально S=0. Переменная S играет роль сумматора, куда по очереди добавляются значения V.	Program FEST ; Var K, V, i : Integer; S : LongInt; SV : Real; Begin Write ('Сколько конкурсантов='); Readln (K); S:=0; {Пока S=0} For i:=1 to K do {Для каждого} Begin {конкурсанта} Readln (V);{вводим возраст,} S:=S+V {и суммируем его} End; SV:=S/K; Writeln ('SV= ', SV : 0 : 1); End.
1. Тело цикла может содержать любые операторы (как простые, так и управляющие). При программировании таких алгоритмов следует следить за сохранением вложенности алгоритмических структур (в примерах 6-7 вложенные структуры изображены пунктирными линиями). 2. При программировании порой можно выбрать различные варианты алгоритмических структур. Например, обратите внимание, что вычисление значений функции y=sin x на отрезке [0; 2] с шагом 0,1 можно задать такими вариантами записи операторов: 1) x:=0; while x<=2 do begin y:=sin(x); writeln (x:0:1,y:5:1); x:=x+0.1 end; 2) x:=0; for k:=1 to 21 do begin y:=sin(x); writeln (x:0:1,y:5:1); x:=x+0.1 end; 3) a:=0.1; for k:=0 to 20 do begin x:=a*k; y:=sin(x); writeln (x:0:1,y:5:1) end; Какая запись Вам представляется наиболее подходящей и почему?
Пример 6. Настя выбрала в магазине открытки двух типов: первого по цене M р. для поздравления мальчикам, второго – D р. для поздравления девочкам. Всего у Насти R р. Требуется получить все возможные варианты покупок, где будут истрачены все имеющиеся у Насти деньги. Дано: R (р.) – общая денежная сумма; M (р.), D (р.) – стоимости открыток для мальчиков и девочек. Найти: KM, KD – количество открыток для мальчиков и девочек соответственно. Связь: KM*M+KD*D=R Метод: Будем перебирать значения KM от 0 (наименьшее количество открыток; все деньги тратятся на открытки для девочек) до [R/M] (наибольшее количество открыток; все деньги тратятся на покупку открыток мальчикам). Тогда KD=(R-KM*M)/D. Если KD – целое число, получен вариант покупки. Так как Настя на сумму R может не купить ни одной открытки, введем логическую переменную Yes, которой присвоим значение True, если покупка возможна.	Program New_Year ; Var M, D, R, KM : Integer ; KD : Real ; Yes : Boolean ; Begin Write ('Всего денег=') ; Readln (R) ; Writeln ('Стоимости открыток:') ; Write ('мальчикам ') ; Readln (M) ; Write ('девочкам ') ; Readln (D) ; Yes := False ; For KM := 0 To R div M do Begin KD := (R-KM*M)/D ; If KD=Trunc (KD) Then Begin Yes := True ; Writeln (KM, ', ', Trunc (KD)) End End ; If Yes=False Then Writeln ('Покупка невозможна') End .
Пример 7. Среди трехзначных чисел требуется найти числа, сумма старшей и младшей цифры каждого из которых равна заданному числу, которое вводится с клавиатуры. Пусть X – заданное число. Трехзначное число С удовлетворяет условию 100 ≤ C ≤ 999. Будем перебирать все числа, удовлетворяющие этому условию, искать сумму m+s, где m – младшая цифра, равная остатку от деления C на 10, s – старшая цифра, равная целой части от деления С на 100. Если m+s=X, выведем число С на экран. Логическая переменная Yes предназначена для отслеживания случая отсутствия искомых чисел.	Program _3 ; Var C, X, m, s : Integer ; Yes : Boolean ; Begin Write ('Заданное число = ') ; Readln (X) ; Yes := False ; For C:=100 To 999 do Begin m := C mod 10 ; s := C div 100 ; If m+s = X Then Begin Yes := True ; Writeln (C) End End ; If Yes = False Then Writeln ('Таких чисел нет') End.

1. Какие данные необходимы для организации цикла?

3. Какие типы операторов цикла Вам известны? Каковы их форматы?

4. Что такое параметр цикла? шаг? тело цикла?

По заданному фрагменту программы определите условие задачи:

1) y:=2; for k:=1 to 10 do y:=y*x ; 2) P:=1; for n:=15 downto 1 do P:=P+1/n ;

3) S:=0; For p:=1 to 10 do S:=S+p/(p+1) ;

* 4) For k:=1 to 20 do Begin a:=k*k; b:=sqr ((k+1)); Writeln ('a=', a , ', b=', b) end;

* 5) a:=1; S:=0; For n:=1 to 15 do Begin S:=S+a/n; a:=a*х ; End ;

Напишите программы решения следующих задач:

1. Требуется занумеровать партию лекарств, выводя на экран в столбик текст в виде: Партия № 1

Партия № 2

…

Партия № 20

2. Решить задачу 1) в предположении, что наименьший и наибольший номера партии лекарств вводятся с клавиатуры.

3. Вывести на экран квадраты натуральных чисел от 1 до 50.

4. В качестве призов на новогодний утренник предполагают купить подарки двух видов (их стоимости известны). Получить все варианты покупок на заданную денежную сумму (например, для покупки подарков стоимостью 700 р и 9800 р на общую сумму 28000 р возможны варианты покупок, приведенные в таблице.

5. На соревнованиях по пятиборью принимают участие K спортсменов. Итоги соревнований подводятся по суммарному числу баллов, полученных каждым спортсменом в каждом виде соревнований. Напишите программу, которая для каждого спортсмена вводит баллы по каждому виду соревнований и выводит суммарный балл.

6. Среди двузначных чисел требуется найти все числа, делящиеся на заданное число, которое вводится с клавиатуры.

7. Среди трехзначных чисел требуется найти все числа, средняя цифра которых:

1) равна сумме крайних цифр;

2) делится без остатка на сумму крайних цифр;

3) отличается от суммы крайних цифр не более чем на единицу.

8. Среди четырехзначных чисел найти все числа, для которых:

1) сумма первых двух цифр равна сумме двух последних цифр;

2) сумма первой и последней цифры равна сумме двух средних цифр.

9. Будем считать, что натуральное число является «счастливым», если оно делится на 7. Получить на заданном числовом промежутке [A; B] все «счастливые» натуральные числа (значения A и B вводятся с клавиатуры).

10. Вывести на экран степени двойки 2ⁿ, где n=1, 2, 3, 4, …, 17.

11. Получить на заданном числовом промежутке в порядке убывания все натуральные числа, сумма цифр которых равна заданному числу, вводимому с клавиатуры.

12. В баскетбольную команду могут принять учеников, рост которых превышает 175 см. Подсчитать количество школьников – кандидатов в баскетбольную команду.

* 13. Смоделируйте работу датчика, фиксирующего координаты судна при его перемещении в соответствии с передаваемыми ему командами: судно перемещается в указанном направлении и ожидает новой команды. Программа должна предложить ввести количество команд; вывести меню для выбора направления; предложить ввести число, соответствующее выбранному направлению; вывести координаты акватории, где окажется судно после выполнения команды. Считать, что судно отправляется в рейс из условного пункта с координатами (0; 0); по одном команде оно перемещается на расстояние в 1 милю. Например, если судно находилось в точке (0, 0) и получена команда 1 (Север), координаты судна окажутся равными (0, 1).

* 14. Известны результаты соревнования по прыжкам в высоту n учеников. Найдите самый лучший результат.

* 15. Итальянский математик Леонардо Фибоначчи (1180-1250) обнаружил интересную числовую последовательность: 1, 1, 2, 3, 5, 8, 13, 21, … Напишите программу определения n-го члена Фибоначчи (значение n вводится с клавиатуры). Программа должна также произвести вычисления по формуле общего члена Фибоначчи. Сравните полученные результаты вычислений по двум методам.

Познакомьтесь с информацией о том, какую роль играют ряды Фибоначчи в математике.