К. Поляков, 2010-2011 http://kpolyakov.narod.ru 1 Программирование на алгоритмическом языке Тема 4. Циклы. - презентация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17 Программирование на алгоритмическом языке К. Поляков, Что получим? 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 Программирование на алгоритмическом языке К. Поляков, Задания 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 Программирование на алгоритмическом языке К. Поляков, Задания 19 «5»: Ввести два целых числа a и b ( a b ) и вывести сумму квадратов всех чисел от a до b. Пример: Введите два числа: 4 10 Сумма квадратов 371

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

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

22 Программирование на алгоритмическом языке К. Поляков, Программа 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 Программирование на алгоритмическом языке К. Поляков, Цикл с условием 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 Программирование на алгоритмическом языке К. Поляков, Цикл с условием 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 Программирование на алгоритмическом языке К. Поляков, Сколько раз выполняется цикл? 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 Программирование на алгоритмическом языке К. Поляков, Задания 26 «3»: Ввести целое число и определить, верно ли, что в нём ровно 3 цифры. Пример:Введите число: Да.Нет. «4»: Ввести целое число и найти сумму его цифр. Пример: Введите целое число: 1234 Сумма цифр числа 1234 равна 10.

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

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

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

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

31 Программирование на алгоритмическом языке К. Поляков, Алгоритм Евклида 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 Программирование на алгоритмическом языке К. Поляков, Блок-схема алгоритма 32 a = b? да нет a > b? да a:=a-b нет b:=b-a начало конец

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

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

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

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

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

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

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

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

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

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

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