К. Поляков, Программирование на алгоритмическом языке Тема 4. Циклы

Программирование на алгоритмическом языке К. Поляков, Циклы 2 Задача. Вывести на экран 5 раз слово «Привет». Особенность: одинаковые действия выполняются 5 раз. Можно ли решить известными методами? ? Цикл – это многократное выполнение одинаковых действий. Цикл цикл с известным числом шагов цикл с неизвестным числом шагов (цикл с условием)

Программирование на алгоритмическом языке К. Поляков, Циклы 3 алг Привет нач вывод "Привет", нс кон алг Привет нач вывод "Привет", нс кон Что плохо? ?

Программирование на алгоритмическом языке К. Поляков, Циклы 4 алг Привет нач нц 5 раз вывод "Привет!", нс кц кон алг Привет нач нц 5 раз вывод "Привет!", нс кц кон Как выглядит блок-схема? ? конец цикла начало цикла вывод "Привет!", нс тело цикла

Программирование на алгоритмическом языке К. Поляков, Циклы 5 начало конец Блок-схема: да нет тело цикла сделали 5 раз? вывод "Привет!"

Программирование на алгоритмическом языке К. Поляков, Число шагов – переменная 6 алг Привет нач цел N вывод "Сколько раз?", нс ввод N нц N раз вывод "Привет!", нс кц кон алг Привет нач цел N вывод "Сколько раз?", нс ввод N нц N раз вывод "Привет!", нс кц кон Задача: ввести количество повторения с клавиатуры.

Программирование на алгоритмическом языке К. Поляков, Задания 7 «3»: Ввести натуральное число и вывести в строчку все числа от 1 до этого числа. Пример: Введите натуральное число: 4 Ответ: «4»: Ввести два целых числа, найти их произведение, не используя операцию умножения. Пример: Введите два числа: *15=60

Программирование на алгоритмическом языке К. Поляков, Задания 8 «5»: Ввести натуральное число N и найти сумму всех чисел от 1 до N (1+2+3+…+N). Пример: Введите число слагаемых: 100 Сумма чисел от 1 до 100 равна 5050

Программирование на алгоритмическом языке К. Поляков, Циклы 9 алг Привет нач нц 5 раз вывод "Привет!", нс кц кон алг Привет нач нц 5 раз вывод "Привет!", нс кц кон Как отсчитать ровно 5 раз? ? Как запоминать, сколько раз уже сделали? ? N := N + 1

Программирование на алгоритмическом языке К. Поляков, Блок-схема алгоритма 10 начало конец да нет N = 5?N = 5? N := 0 N := N + 1 еще не сделали ни одного раза проверить, все ли сделали считаем очередной шаг вывод "Привет!" цикл

Программирование на алгоритмическом языке К. Поляков, Цикл с условием 11 алг Привет 2 нач цел N N:= 0 нц пока N 5 вывод "Привет!", нс N:= N + 1 кц кон алг Привет 2 нач цел N N:= 0 нц пока N 5 вывод "Привет!", нс N:= N + 1 кц кон

Программирование на алгоритмическом языке К. Поляков, Цикл с условием 12 алг Привет 3 нач цел N N:= 5 нц пока N ??? вывод "Привет!", нс ??? кц кон алг Привет 3 нач цел N N:= 5 нц пока N ??? вывод "Привет!", нс ??? кц кон Вместо знаков вопроса добавьте числа и операторы так, чтобы цикл выполнился ровно 5 раз: 0 N:= N - 1

Программирование на алгоритмическом языке К. Поляков, Что получим? 13 алг Пример 1 нач цел N N:= 1 нц пока N

Программирование на алгоритмическом языке К. Поляков, Что получим? 14 алг Пример 2 нач цел N N:= 1 нц пока N

Программирование на алгоритмическом языке К. Поляков, Что получим? 15 алг Пример 3 нач цел N N:= 2 нц пока N 5 вывод N, нс N:= N + 2 кц кон алг Пример 3 нач цел N N:= 2 нц пока N 5 вывод N, нс N:= N + 2 кц кон Условие цикла никогда не станет ложным – это зацикливание! !

Программирование на алгоритмическом языке К. Поляков, Что получим? 16 алг Пример 4 нач цел N N:= 1 нц пока N

Программирование на алгоритмическом языке К. Поляков, Что получим? 17 алг Пример 5 нач цел N N:= 5 нц пока N >= 1 вывод N*N*N, нс N:= N - 1 кц кон алг Пример 5 нач цел N N:= 5 нц пока N >= 1 вывод N*N*N, нс N:= N - 1 кц кон

Программирование на алгоритмическом языке К. Поляков, Задания 18 «3»: Ввести натуральное число вывести квадраты и кубы всех чисел от 1 до этого числа. Пример: Введите натуральное число: 3 1: 1 1 2: 4 8 3: 9 27 «4»: Ввести два целых числа a и b ( a b ) и вывести квадраты все чисел от a до b. Пример: Введите два числа: 4 5 4*4=16 5*5=25

Программирование на алгоритмическом языке К. Поляков, Задания 19 «5»: Ввести два целых числа a и b ( a b ) и вывести сумму квадратов всех чисел от a до b. Пример: Введите два числа: 4 10 Сумма квадратов 371

Программирование на алгоритмическом языке К. Поляков, Циклы с условием 20 Пример: Распилить бревно на поленья. Сколько поленьев получится? Задача: Ввести целое число (

Программирование на алгоритмическом языке К. Поляков, Блок-схема алгоритма 21 начало конец нет да n 0? count := 0 count := count + 1 n := div(n, 10) обнулить счетчик цифр ввод n выполнять «пока n 0» вывод count

Программирование на алгоритмическом языке К. Поляков, Программа 22 алг Число цифр нач цел n, count вывод "Введите целое число", нс ввод n count:= 0 вывод "В числе ", n, " нашли ", count, " цифр" кон алг Число цифр нач цел n, count вывод "Введите целое число", нс ввод n count:= 0 вывод "В числе ", n, " нашли ", count, " цифр" кон нц пока n0 count:= count + 1 n:= div(n,10) кц нц пока n0 count:= count + 1 n:= div(n,10) кц, n1 ; n1:= n n1, Что плохо? ?

Программирование на алгоритмическом языке К. Поляков, Цикл с условием 23 Особенности: можно использовать сложные условия: можно записывать в одну строчку, разделяя команды точкой с запятой: нц пока a < b b:= b - 2 кц ; нц пока a 5 a:= a + 5; b:= b - 2 кц нц пока a 5 a:= a + 5; b:= b - 2 кц a 5

Программирование на алгоритмическом языке К. Поляков, Цикл с условием 24 Особенности: условие проверяется при каждом входе в цикл если условие на входе в цикл ложно, цикл не выполняется ни разу если условие никогда не станет ложным, программа зацикливается a := 4; b := 6 нц пока a > b; a:= a – b кц a := 4; b := 6 нц пока a > b; a:= a – b кц a:= 4; b:= 6 нц пока a < b; d:= a + b кц a:= 4; b:= 6 нц пока a < b; d:= a + b кц

Программирование на алгоритмическом языке К. Поляков, Сколько раз выполняется цикл? 25 a:= 4; b:= 6 нц пока a < b; a:= a + 1 кц a:= 4; b:= 6 нц пока a < b; a:= a + 1 кц 2 раза a = 6 2 раза a = 6 a:= 4; b:= 6 нц пока a < b; a:= a + b кц a:= 4; b:= 6 нц пока a < b; a:= a + b кц 1 раз a = 10 1 раз a = 10 a:= 4; b:= 6 нц пока a > b; a:= a + 1 кц a:= 4; b:= 6 нц пока a > b; a:= a + 1 кц 0 раз a = 4 0 раз a = 4 a:= 4; b:= 6 нц пока a < b; b:= a – b кц a:= 4; b:= 6 нц пока a < b; b:= a – b кц 1 раз b = -2 1 раз b = -2 a:= 4; b:= 6 нц пока a < b; a:= a – 1 кц a:= 4; b:= 6 нц пока a < b; a:= a – 1 кц зацикливание

Программирование на алгоритмическом языке К. Поляков, Задания 26 «3»: Ввести целое число и определить, верно ли, что в нём ровно 3 цифры. Пример:Введите число: Да.Нет. «4»: Ввести целое число и найти сумму его цифр. Пример: Введите целое число: 1234 Сумма цифр числа 1234 равна 10.

Программирование на алгоритмическом языке К. Поляков, Задания 27 «5»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример: Введите целое число: Введите целое число: Нет. Да. «6»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, НЕ обязательно стоящие рядом. Пример: Введите целое число: Введите целое число: Нет. Да.

Программирование на алгоритмическом языке К. Поляков, Задания-2 28 «3»: Ввести целое число и определить, верно ли, что в нём ровно 1 цифра «9». Пример:Введите число: Да.Нет. «4»: Ввести целое число и определить, верно ли, что все его цифры четные. Пример:Введите число: Да.Нет.

Программирование на алгоритмическом языке К. Поляков, Задания-2 29 «5»: Ввести целое число и определить, верно ли, что все его цифры расположены в порядке возрастания. Пример: Введите целое число: Введите целое число: Да. Нет. «6»: Ввести целое число и «перевернуть» его, так чтобы первая цифра стала последней и т.д. Пример: Введите целое число: Введите целое число:

Программирование на алгоритмическом языке К. Поляков, Вычисление НОД 30 НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. Перебор: 1.Записать в переменную k минимальное из двух чисел. 2.Если a и b без остатка делятся на k, то стоп. 3.Уменьшить k на 1. 4.Перейти к шагу 2. 1.Записать в переменную k минимальное из двух чисел. 2.Если a и b без остатка делятся на k, то стоп. 3.Уменьшить k на 1. 4.Перейти к шагу 2. Где будет НОД? ? Почему алгоритм обязательно закончится? ? это цикл с условием!

Программирование на алгоритмическом языке К. Поляков, Алгоритм Евклида 31 Евклид ( до. н. э.) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7) НОД (1998, 2) = НОД (1996, 2) = … = 2 Пример: много шагов при большой разнице чисел: = НОД (7, 7) = 7 Надо: вычислить наибольший общий делитель (НОД) чисел a и b.

Программирование на алгоритмическом языке К. Поляков, Блок-схема алгоритма 32 a = b? да нет a > b? да a:=a-b нет b:=b-a начало конец

Программирование на алгоритмическом языке К. Поляков, Алгоритм Евклида 33 нц пока a b если a > b то a:= a - b иначе b:= b - a все кц нц пока a b если a > b то a:= a - b иначе b:= b - a все кц Где будет НОД? Как его вывести? ? Как вывести НОД в формате НОД(14,21) = 7? ? А без дополнительных переменных? ?

Программирование на алгоритмическом языке К. Поляков, Модифицированный алгоритм Евклида 34 НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Еще один вариант: НОД(2 · a,2 · b)= 2 · НОД(a, b) НОД(2 · a,b)= НОД(a, b) | при нечетном b НОД(2 · a,2 · b)= 2 · НОД(a, b) НОД(2 · a,b)= НОД(a, b) | при нечетном b

Программирование на алгоритмическом языке К. Поляков, Алгоритм Евклида 35 «3»: Составить программу для вычисления НОД с помощью алгоритма Евклида. «4»: Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу: a b НОД(a,b)

Программирование на алгоритмическом языке К. Поляков, Алгоритм Евклида 36 «5»: Выполнить задание на «4» и подсчитать число шагов алгоритма для каждого случая. a b НОД(a,b) шагов

Программирование на алгоритмическом языке К. Поляков, Цикл с переменной 37 Задача: вывести кубы чисел от 1 до 8. Можно ли решить известными способами? ? 1.Нужны ли переменные? Сколько? 2.Как они должны изменяться? 3.Нужен ли цикл?

Программирование на алгоритмическом языке К. Поляков, Блок-схема алгоритма 38 начало конец нет да N

Программирование на алгоритмическом языке К. Поляков, Цикл с переменной 39 Задача: вывести кубы натуральных чисел от 1 до 8. алг Кубы нач цел N, кубN N:= 1 нц пока N

Программирование на алгоритмическом языке К. Поляков, Цикл с переменной 40 Задача: вывести кубы натуральных чисел от 1 до 8. алг Кубы нач цел N, кубN кон алг Кубы нач цел N, кубN кон нц для N от 1 до 8 кубN:= N*N*N вывод кубN, нс кц Как обойтись без переменной кубN ? ? для 1,2,3,…,8

Программирование на алгоритмическом языке К. Поляков, Цикл с переменной 41 Задача: вывести кубы чётных чисел от 2 до 8. алг Кубы нач цел N, кубN кон алг Кубы нач цел N, кубN кон нц для N от 2 до 8 шаг 2 кубN:= N*N*N вывод кубN, нс кц для 2,4,6,8 только целые !

Программирование на алгоритмическом языке К. Поляков, Сколько раз выполняется цикл? 42 a := 1 нц для i от 1 до 3; a:=a+1 кц a := 1 нц для i от 1 до 3; a:=a+1 кц a = 4a = 4 a = 4a = 4 a := 1 нц для i от 3 до 1; a:=a+1 кц a := 1 нц для i от 3 до 1; a:=a+1 кц a = 1a = 1 a = 1a = 1 a := 1 нц для i от 1 до 3 шаг -1; a:=a+1 кц a := 1 нц для i от 1 до 3 шаг -1; a:=a+1 кц a = 1a = 1 a = 1a = 1 a := 1 нц для i от 3 до 1 шаг -1; a:=a+1 кц a := 1 нц для i от 3 до 1 шаг -1; a:=a+1 кц a = 4a = 4 a = 4a = 4

Программирование на алгоритмическом языке К. Поляков, Цикл с переменной 43 Особенности: переменная цикла может быть только целой ( цел ) начальное и конечное значения и шаг – целые можно записывать в одну строчку, разделяя команды точкой с запятой: если шаг > 0 и конечное значение < начального, цикл не выполняется ни разу (проверка условия в начале цикла, цикл с предусловием) если шаг начального, цикл не выполняется ни разу нц для n от 1 до 4 вывод n кц ;

Программирование на алгоритмическом языке К. Поляков, Замена одного вида цикла на другой 44 нц для i от 1 до 10 | тело цикла кц нц для i от 1 до 10 | тело цикла кц i:= 1 нц пока i = b | тело цикла i:= i - 1 кц Замена пока на для возможна только тогда, когда можно заранее вычислить число шагов цикла. Замена цикла для на пока возможна всегда.

Программирование на алгоритмическом языке К. Поляков, Задания 45 «3»: Ввести натуральное число N и вывести числа от N до 1 (через одно) в порядке убывания. Пример: Введите натуральное число: 8 Ответ:

Программирование на алгоритмическом языке К. Поляков, Задания 46 «4»: Ввести два целых числа a и b ( a b ) и вывести кубы всех чисел от a до b. Пример: Введите два числа: 4 6 4*4*4=64 5*5*5=125 6*6*6=216 «5»: Ввести целое число a и вывести сумму квадратов всех чисел от 1 до a с шагом 0.1. Пример: Введите последнее число: 3 Сумма …+ a 2

Программирование на алгоритмическом языке К. Поляков, Задания 47 «4»: Ввести a и b и вывести квадраты и кубы чисел от a до b. Пример: Введите границы интервала: 4 6 4: : : «5»: Вывести квадраты и кубы 10 чисел следующей последовательности: 1, 2, 4, 7, 11, 16, … Пример: 1: 1 1 2: 4 8 4: :