1 Программирование на языке Паскаль § 54. Алгоритм и его свойства § 55. Простейшие программы § 56. Вычисления § 57. Ветвления § 58. Циклические алгоритмы § 59. Процедуры § 60. Функции § 61. Рекурсия
§ 54. Алгоритм и его свойства 2
3 Мухаммед ал-Хорезми (ок. 783–ок. 850 гг.) Алгоритм — это точное описание порядка действий, которые должен выполнить исполнитель для решения задачи за конечное время. Исполнитель – это устройство или одушёвленное существо (человек), способное понять и выполнить команды, составляющие алгоритм. Формальные исполнители : не понимают (и не могут понять) смысл команд.
4 Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное время. Детерминированность ( определённость ) — при каждом запуске алгоритма с одними и теми же исходными данными получается один и тот же результат. Понятность — алгоритм содержит только команды, входящие в систему команд исполнителя. Конечность (результативность) — для корректного набора данных алгоритм должен завершаться через конечное время. Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату.
5 дискретный объект 1 2 3 4 алгоритм шаг 1 шаг 2 шаг 3 2 3 4 5 5 4 3 2 дискретный объект 25 16 9 4 получает на вход дискретный объект в результате строит другой дискретный объект (или выдаёт сообщение об ошибке) обрабатывает объект по шагам на каждом шаге получается новый дискретный объект
6 естественный язык псевдокод установить соединение пока не принята команда «стоп» принять команду выполнить команду завершить сеанс связи установить соединение нц принять команду выполнить команду кц_при команда = 'stop' завершить сеанс связи
7 блок-схема setConnection ; repeat cmd := getCommand ; executeCommand ( cmd ); until cmd = "stop"; closeConnection ; программа принять команду установить соединение завершить соединение выполнить команду «стоп»? да нет
§ 55. Простейшие программы 8
9 program qq ; begin { начало программы } { тело программы } end. { конец программы } комментарии в скобках {} не обрабатываются Что делает эта программа ? ? название алгоритма
10 program qq ; begin write('2+'); { без перехода } write ln ('2=?'); { на новую строку } write ln (' Ответ: 4'); end. Протокол: 2+2=? Ответ: 4
11 « B »: Вывести на экран текст «лесенкой» Вася пошел гулять « C »: Вывести на экран рисунок из букв Ж ЖЖЖ ЖЖЖЖЖ ЖЖЖЖЖЖЖ HH HH ZZZZZ
12 Задача. Ввести с клавиатуры два числа и найти их сумму. Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь компьютер считает сам! Как ввести числа в память? Где хранить введенные числа ? Как вычислить? Как вывести результат? ?
13 program qq ; begin { ввести два числа } { вычислить их сумму } { вывести сумму на экран } end. Псевдокод : алгоритм на русском языке с элементами Паскаля. Компьютер не может исполнить псевдокод! !
14 Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы. a Значение Имя Поместится? ? Другой тип данных В переменной хранятся данные определенного типа! !
15 МОЖНО использовать латинские буквы ( A-Z) цифры знак подчеркивания _ заглавные и строчные буквы НЕ различаются НЕЛЬЗЯ использовать русские буквы пробелы скобки, знаки +, =, !, ? и др. имя не может начинаться с цифры Какие имена правильные? AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B
16 Типы переменных: integer { целая } real { вещественная } и другие… Объявление переменных: var a, b, c: integer ; выделение места в памяти variable – переменная тип – целые список имен переменных
17 область допустимых значений допустимые операции объём памяти формат хранения данных для предотвращения случайных ошибок
18 read ( a ); Программа ждет, пока пользователь введет значение и нажмет Enter. Введенное значение записывается в переменную a. ! оператор ввода 5 a
19 через пробел: 25 30 через Enter : 25 30 read ( a, b ); Ввод значений двух переменных (через пробел или Enter ). a 25 b 30 a 25 b 30
20 var a, b: integer ; ... a := 5 ; b := a + 2 ; a := (a + 2 )*(b – 3 ); b := b + 1 ; a ? 5 5 b ? 5+2 7 a 5 7*4 28 b 7 7+1 8
21 { вывод значения переменной a} { вывод значения переменной a и переход на новую строку } { вывод текста } { вывод текста и значения переменной c} write( a ); write ln ( a ); writeln ( ' Привет! ' ); writeln ( ' Ответ: ', c ); writeln ( a, '+', b, '=', c );
22 program Sum ; var a, b, c: integer ; begin read ( a, b ); c := a + b; writeln ( c ); end. Что плохо? ?
23 program Sum ; var a, b, c: integer ; begin writeln ( ' Введите два целых числа ' ); read ( a, b ); c := a + b; writeln ( a, '+', b, '=', c ); end. Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь
24 a:= 123 ; write( a: 5 ); Форматный вывод: Вычисление выражений: writeln ( a, '+', b, '=', a+b ); a+b 123 5 знаков
§ 56. Вычисления 25
26 byte { целые 0..255 } shortint { целые -128.. 1 2 8 } word { целые 0.. 6553 5 } longint { целые –2147483648..2147483647 } single { вещественная, 4 байта } real { вещественная, 6 байта } double { вещественная, 8 байтов } extended { вещественная, 10 байтов } boolean { логическая, 1 байт } char { символ, 1 байт } string { символьная строка } Сколько байт в памяти? ?
27 a:= (c + b * 5 * 3 - 1 ) / 2 * d; Приоритет ( старшинство ): скобки умножение и деление сложение и вычитание 2 1 3 4 5 6
28 Результат деления «/» – вещественное число: a:= 2 / 3; var a: single ; 0.6666… div – деление нацело (остаток отбрасывается) mod – остаток от деления var a, b, d: integer ; ... d := 85 ; b := d div 10 ; { 8 } a := d mod 10 ; { 5 }
29 write(-7 div 2, ',' ); write(-7 mod 2); -3 -1 -7 = ( -3 )*2 + ( -1 ) В математике не так! ! -7 = ( -4 )*2 + 1 остаток 0
30 Целая и дробная части числа разделяются точкой ! ! var x: double ; ... x:= 123.456 ; Форматный вывод : a:= 1 ; write( a/ 3 ); write( a/ 3 :7 :3 ); 3.333333E-001 3,333333 10 -1 = 0,3333333 0.333 всего знаков в дробной части
31 abs (x) — модуль sqrt ( x ) — квадратный корень sin ( x ) — синус угла, заданного в радианах cos ( x ) — косинус угла, заданного в радианах exp ( x ) — экспонента е х ln ( x ) — натуральный логарифм trunc (x) — отсечение дробной части round (x) — округление до ближайшего целого
32 Случайно… встретить друга на улице разбить тарелку найти 10 рублей выиграть в лотерею Случайный выбор : жеребьевка на соревнованиях выигравшие номера в лотерее Как получить случайность?
33 Электронный генератор нужно специальное устройство нельзя воспроизвести результаты 318458191041 564321 209938992481 458191 938992 малый период (последовательность повторяется через 10 6 чисел) Метод середины квадрата (Дж. фон Нейман) в квадрате Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле. зерно
34 X := ( a*X+b) mo d c | интервал от 0 до c-1 X := ( X+ 3 ) mo d 10 | интервал от 0 до 9 X := 0 зерно 3 6 9 2 5 8 0 зацикливание 8 1 4 7 Важен правильный выбор параметров a, b и с ! ! Компилятор GCC : a = 1103515245 b = 12345 c = 2 31
35 Вещественные числа в интервале [0, 1 ) : var X, Y: double ; ... X:= r a ndom ; { интервал от 0 до 1 ( <1 ) } Y:= r a ndom ; { это уже другое число! } англ. random – случайный Целые числа в интервале [0,10) : var K, L: integer ; ... K:= ra ndom ( 1 0 ) { интервал от 0 до 9 ( <10 ) } L := ra ndom ( 1 0 ) { это уже другое число! }
36 Вещественные числа: var X, a, b : double ; ... X:= r a ndom * 10 ; { расширение интервала: [0,10) } X:= r a ndom * 10 + 5 ; { расширение и сдвиг: [ 5,1 5 ) } X:= r a ndom * (b-a) + a ; { расширение и сдвиг: [ a,b ) } var K, a, b : integer ; ... K:= r a ndom ( 10 ) + 5 ; { [ 5,14] } X:= r a ndom (b-a+1) + a ; { [ a,b ] } Целые числа:
37 « A »: Ввести с клавиатуры три целых числа, найти их сумму, произведение и среднее арифметическое. Пример : Введите три целых числа: 5 7 8 5+7+8=20 5*7*8=280 (5+7+8)/3= 6.667 « B »: Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB. Пример : Введите координаты точки A: 5.5 3.5 Введите координаты точки B: 1.5 2 Длина отрезка AB = 4.272
38 « C »: Получить случайное трехзначное число и вывести через запятую его отдельные цифры. Пример : Получено число 123. Его цифры 1, 2, 3.
§ 57. Ветвления 39
40 Задача: изменить порядок действий в зависимости от выполнения некоторого условия. M:= a a > b? M:= b да нет вывод M полная форма ветвления Если a = b? ?
41 if a > b then M:= a else M:= b; if a > b then begin M:= a; end else begin M:= b; end ; операторные скобки Перед else знак « ; » НЕ ставится! !
42 M:= b b > a? да нет вывод M M:= a неполная форма ветвления M:= a; if b > a then M:= b;
43 if a < b then begin с := a; a:= b; b:= c end ; Что делает ? ? 4 6 ? 4 6 4 a b 3 2 1 Можно ли обойтись без переменной c ? ? c
44 > < > = < = = <> больше, меньше больше или равно меньше или равно равно не равно
45 if a > b then writeln ( ' Андрей старше' ) else if a = b then writeln( ' Одного возраста') else writeln( ' Борис старше' ); вложенный условный оператор Зачем нужен ? ? Задача: в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше? Сколько вариантов ? ?
46 if a > b then write( 'А' ) else if a = b then write( '=' ) else write( 'Б' ); if a > b then write( 'А' ) else if a = b then write( '=' ) else write( 'Б' );
47 « A »: Ввести три целых числа, найти максимальное из них. Пример : Введите три целых числа: 1 5 4 Максимальное число 5 « B »: Ввести пять целых чисел, найти максимальное из них. Пример : Введите пять целых чисел: 1 5 4 3 2 Максимальное число 5
48 « C »: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них старше. Пример : Возраст Антона: 15 Возраст Бориса: 17 Возраст Виктора: 16 Ответ: Борис старше всех. Пример : Возраст Антона: 17 Возраст Бориса: 17 Возраст Виктора: 16 Ответ: Антон и Борис старше Виктора.
49 Задача : набор сотрудников в возрасте 25-40 лет (включительно). if then writeln( ' подходит ' ) else writeln( ' не подходит ' ); and or not Приоритет : not and or, xor отношения ( <, >, <=, >=, =, <> ) xor исключающее «ИЛИ» ( v >= 25 ) and ( v <= 40 ) сложное условие Почему скобки обязательны ? ?
50 « A »: Напишите программу, которая получает три числа и выводит количество одинаковых чисел в этой цепочке. Пример : Введите три числа: 5 5 5 Все числа одинаковые. Пример : Введите три числа: 5 7 5 Два числа одинаковые. Пример : Введите три числа: 5 7 8 Нет одинаковых чисел.
51 « B »: Напишите программу, которая получает номер месяца и выводит соответствующее ему время года или сообщение об ошибке. Пример : Введите номер месяца: 5 Весна. Пример : Введите номер месяца: 15 Неверный номер месяца.
52 « C »: Напишите программу, которая получает возраст человека (целое число, не превышающее 120) и выводит этот возраст со словом «год», «года» или «лет». Например, «21 год», «22 года», «25 лет». Пример : Введите возраст: 18 Вам 18 лет. Пример : Введите возраст: 21 Вам 21 год. Пример : Введите возраст: 2 2 Вам 22 года.
53 « A »: Напишите условие, которое определяет заштрихованную область. « B »: Напишите условие, которое определяет заштрихованную область.
54 « C »: Напишите условие, которое определяет заштрихованную область.
55 if m = 1 then write( ' январь ' ); if m = 2 then write( ' февраль ' ); ... if m = 12 then write( ' декабрь ' ); case m of 1 : write( ' январь' ); 2 : write( ' февраль' ); ... 12 : write( ' декабрь' ) else write( ' ошибка' ) end;
56 case m of 2 : d:= 28 ; { невисокосный год } 1, 3, 5, 7, 8, 10, 12 : d:= 31 else d:= 30 end; Число дней в месяце : Социальный статус : case v of 0.. 6 : write( ' дошкольник ' ); 7.. 17 : write( ' школьник ' ) else write( ' взрослый ' ) end;
57 var c: char ; ... case c of ' а ' : begin writeln ( ' антилопа' ); writeln ( ' Анапа' ); end ; ... ' я ' : begin writeln ( ' ягуар' ) ; writeln ( ' Якутск' ) ; end else writeln ( ' ошибка' ) end; несколько операторов в блоке
§ 58. Циклические алгоритмы 58
59 Цикл – это многократное выполнение одинаковых действий. Два вида циклов : цикл с известным числом шагов ( сделать 10 раз ) цикл с неизвестным числом шагов (делать, пока не надоест) Задача. Вывести на экран 10 раз слово «Привет». Можно ли решить известными методами ? ?
60 writeln ( ' Привет ' ); writeln ( ' Привет ' ); writeln ( ' Привет ' ); ... writeln ( ' Привет ' ); Что плохо ? ?
61 начало конец да нет тело цикла сделали 10 раз ? writeln ( ' Привет! ' );
62 счётчик:= 0 пока счётчик < 10 writeln( ' привет' ) ; увеличить счётчик на 1 счётчик:= 10 пока счётчик > 0 writeln( ' привет' ); уменьшить счётчик на 1 Какой способ удобнее для процессора ? ? результат операции автоматически сравнивается с нулём!
63 Задача. Определить количество цифр в десятичной записи целого положительного числа, записанного в переменную n. счётчик:= 0 пока n > 0 отсечь последнюю цифру n увеличить счётчик на 1 n счётчик 1234 0 123 1 12 2 1 3 0 4 Как отсечь последнюю цифру ? ? n:= n div 10 Как увеличить счётчик на 1 ? ? счётчик := счётчик + 1
64 count:= 0 ; while do begin end ; n:= n div 10 ; count:= count + 1 тело цикла начальное значение счётчика n > 0 условие продолжения заголовок цикла Зачем begin-end ? ? Цикл с предусловием – проверка на входе в цикл! !
65 k:= 0 ; while k < 10 do begin writeln ( ' привет ' ); k:= k + 1 end; При известном количестве шагов: k:= 0 ; while k < 10 do writeln ( ' привет ' ); Зацикливание:
66 a:= 4 ; b:= 6 ; while a < b d o a:= a + 1 ; 2 раза a = 6 a:= 4 ; b:= 6 ; while a < b d o a:= a + b ; 1 раз a = 10 a:= 4 ; b:= 6 ; while a > b d o a:= a + 1 ; 0 раз a = 4 a:= 4 ; b:= 6 ; while a < b d o b:= a - b; 1 раз b = -2 a:= 4 ; b:= 6 ; while a < b d o a:= a - 1 ; зацикливание
67 repeat until ; условие окончания заголовок цикла write( 'Введите n > 0: ' ); read(n) n > 0 тело цикла при входе в цикл условие не проверяется цикл всегда выполняется хотя бы один раз в последней строке указывают условие окончания цикла, а не условие его продолжения
68 « A »: Напишите программу, которая получает два целых числа A и B (0 < A < B) и выводит квадраты всех натуральных чисел в интервале от A до B. Пример : Введите два целых числа: 10 12 10*10=100 11*11=121 12*12=144 « B »: Напишите программу, которая получает два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрицательными. Пример : Введите два числа: 10 -15 10*(-15)=-150
69 « C »: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи, меньших N. Предусмотрите защиту от ввода отрицательного числа N. Пример : Введите число N: 10000 Сумма 177 1 0
70 « A »: Ввести натуральное число и найти сумму его цифр. Пример : Введите натуральное число: 12345 Сумма цифр 15. « B »: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример : Введите натуральное число: 12342 Нет. Пример : Введите натуральное число: 12 2 4 5 Да.
71 « C »: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры (не обязательно стоящие рядом). Пример : Введите натуральное число: 12342 Да. Пример : Введите натуральное число: 1234 5 Нет.
72 Задача. Вывести все степени двойки от 2 1 до 2 10. Можно ли сделать с циклом « while » ? ? n := 2 ; while do begin writeln (n); n:= n * 2 ; end; k := 1 ; k <= 10 k:= k + 1 n:= 2 ; for do begin writeln (n); n:= n * 2 end; k := 1 to 10 Переменная k – целая! !
73 for k := 10 1 do writeln (k * k); downto var k: integer ; целое целое шаг «–1» Шаг может быть равен только 1 или «–1» ! ! Как сделать шаг 2? ? for i := 1 to 1 0 do begin writeln (k * k); end; k:= 1; k:= k + 2
74 a := 1 ; for i:= 1 to 3 do a := a+ 1 ; a = 4 a := 1 ; for i:= 3 to 1 do a := a+ 1 ; a = 1 a := 1 ; for i:= 1 down to 3 do a := a+ 1 ; a = 1 a := 1 ; for i:= 3 down to 1 do a := a+ 1 ; a = 4
75 « A »: Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111. « B »: Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 1 3 + 5 3 + 3 3. Найдите все трёхзначные Армстронга.
76 «С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 25 2 = 6 25. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N. Пример : Введите N: 1000 1*1=1 5*5=25 6*6=36 25*25=625 76*76=5776
77 Задача. Вывести все простые числа в диапазоне от 2 до 1000. для n от 2 до 1000 если число n простое то writeln (n); число n простое нет делителей [ 2.. n -1 ] : проверка в цикле! Что значит «простое число» ? ?
78 for n := 2 to 1000 do begin count:= 0 ; if count = 0 then writeln (n) end; for k:= 2 to n- 1 do if n mod k = 0 then count:= count + 1 ; вложенный цикл
79 for i := 1 to 4 do for k:= 1 to i do writeln ( i, ' ', k); Как меняются переменные? ? 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 Переменная внутреннего цикла изменяется быстрее! !
80 count:= 0 ; k:= 2 ; while do begin if n mod k = 0 then count:= count + 1 ; k:= k + 1 end; while k <= sqrt (n) do begin ... end; Что плохо? ? while ( k * k <= n ) and do begin ... end; k*k <= n Как ещё улучшить? ? (count = 0 )
81 « A »: Напишите программу, которая получает натуральные числа A и B (A<B) и выводит все простые числа в интервале от A до B. Пример : Введите границы диапазона: 10 20 11 13 17 19 « B »: В магазине продается мастика в ящиках по 15 кг, 17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?
82 « C »: Ввести натуральное число N и вывести все натуральные числа, не превосходящие N и делящиеся на каждую из своих цифр. Пример : Введите N: 15 1 2 3 4 5 6 7 8 9 11 12 15
§ 59. Процедуры 83
84 writeln ( 'Ошибка программы' ); много раз! program withProc ; var n: integer ; begin read(n); if n < 0 then Error ; ... end. procedure Error ; begin writeln ( ' Ошибка программы' ) end; вызов процедуры
85 Процедура – вспомогательный алгоритм, который выполняет некоторые действия. текст (расшифровка) процедуры записывается до основной программы в программе может быть много процедур чтобы процедура заработала, нужно вызвать её по имени из основной программы или из другой процедуры
86 Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. много раз! Алгоритм: 178 10110010 2 Как вывести первую цифру ? ? 7 6 5 4 3 2 1 0 1 0 1 1 0 0 1 0 2 разряды n := n div 128 n mod 128 Как вывести вторую цифру ? ? n 1 div 64
87 Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. Алгоритм: k := 128 ; while k > 0 do begin write(n div k ) ; n:= n mod k; k:= k div 2 end; n k вывод 178 128 1 50 64 0 50 32 1 18 16 1 2 8 0 2 4 0 2 2 1 0 1 0 0 0 178 10110010 Результат зависит от n ! !
88 program binCode ; begin printBin ( 99 ) end. procedure printBin ( n: integer ) ; var k: integer ; begin k := 128 ; while k > 0 do begin write(n div k ) ; n:= n mod k; k:= k div 2 end end; Параметры – данные, изменяющие работу процедуры. локальная переменная значение параметра ( аргумент )
89 procedure printSred (a: integer ; b: integer ); begin write(( a+b )/ 2 ); end. procedure printSred (a, b: integer ); begin write(( a+b )/ 2 ); end.
90 « A »: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'. Пример : Введите N: 10 ---------- « B »: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой. Пример : Введите натуральное число: 1234 1 2 3 4
91 « C »: Напишите процедуру, которая выводит на экран запись переданного ей числа в римской системе счисления. Пример : Введите натуральное число: 2013 MMXIII
92 Задача. Написать процедуру, которая меняет местами значения двух переменных. program Exchange ; var x, y: integer ; begin x:= 2 ; y:= 3 ; Swap (x, y); write(x, ' ', y) end. procedure Swap (a, b: integer ); var c: integer ; begin c:= a ; a:= b ; b:= c ; end; 2 3 Процедура работает с копиями переданных значений параметров! ! Почему не работает? ? передача по значению
93 procedure Swap ( a, b: integer ); var c: integer ; begin c:= a ; a:= b ; b:= c ; end; var передача по ссылке переменные могут изменяться var a, b: integer ; ... Swap (a, b); { правильно } Swap ( 2, 3 ); { неправильно } Swap (a, b +3 ); { неправильно } Вызов:
94 « A »: Напишите процедуру, которая переставляет три переданные ей числа в порядке возрастания. Пример : Введите три натуральных числа: 10 15 5 5 10 15 « B »: Напишите процедуру, которая сокращает дробь вида M/N. Числитель и знаменатель дроби передаются как изменяемые параметры. Пример : Введите числитель и знаменатель дроби: 25 15 После сокращения: 5/3
95 « C »: Напишите процедуру, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел и возвращает их через изменяемые параметры. Пример : Введите два натуральных числа: 10 15 НОД(10,15)=5 НОК(10,15)=30
§ 60. Функции 96
97 Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа). Задача. Написать функцию, которая вычисляет сумму цифр числа. Алгоритм: сумма:= 0 ; while n <> 0 do begin сумма:= сумма + n mod 10 ; n:= n div 10 end;
98 program Sum ; begin writeln ( s umDigits ( 12345 ) ) end. function sumDigits (n: integer ): ; var sum: integer ; begin sum:= 0 ; while n <> 0 do begin sum:= sum + n mod 10 ; n:= n div 10 ; end; end; sumDigits := sum передача результата integer тип результата
99 x:= 2 * sumDigits (n+ 5 ); z:= sumDigits (k) + sumDigits (m); if sumDigits ( n ) mod 2 = 0 then begin writeln ( 'Сумма цифр чётная' ); writeln ( 'Она равна ', sumDigits ( n ) ) end; Функция, возвращающая целое число, может использоваться везде, где и целая величина! !
100 « A »: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел. Пример : Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574) = 1234. « B »: Напишите функцию, которая определяет сумму цифр переданного ей числа. Пример : Введите натуральное число: 123 Сумма цифр числа 123 равна 6.
101 « C »: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором цифры стоят в обратном порядке. Пример : Введите натуральное число: 1234 После переворота: 4321.
102 Задача. Найти все простые числа в диапазоне от 2 до 100. program PrimeNum ; var i : integer ; begin for i := 2 to 100 do if then writeln ( i ) end. i - простое функция, возвращающая логическое значение ( True / False ) isPrime ( i )
103 Какой алгоритм? ? function isPrime (n: integer ): ; var count, k: integer ; begin count:= 0 ; k:= 2 ; while (k*k <= n) and (count = 0 ) do begin if n mod k = 0 then count:= count + 1 ; k:= k + 1 end; end; boolean логическое значение ( True / False ) is Prime := (count = 0 ) if count = 0 then isPrime := True else isPrime := False
104 read(n); while isPrime (n) do begin writeln ( ' простое число ' ); read(n) end; Функция, возвращающая логическое значение, может использоваться везде, где и логическая величина! !
105 « A »: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого. Пример : Введите натуральное число: 28 Число 28 совершенное. Пример : Введите натуральное число: 2 9 Число 2 9 не совершенное.
106 « B »: Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1. Пример : Введите два натуральных числа: 28 15 Числа 28 и 15 взаимно простые. Пример : Введите два натуральных числа: 28 1 6 Числа 28 и 1 6 не взаимно простые.
107 «С»: Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике. Пример : Введите натуральное число: 733 Число 733 гиперпростое. Пример : Введите натуральное число: 19 Число 19 не гиперпростое.
§ 61. Рекурсия 108
109 У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …
110 Натуральные числа : 1 – натуральное число если – натуральное число, то – натуральное число индуктивное определение Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев. Числа Фибоначчи : при 1, 1, 2, 3, 5, 8, 13, 21, 34, …
111 Фракталы – геометрические фигуры, обладающие самоподобием. Треугольник Серпинского:
112 1 2 3 за один раз переносится один диск класть только меньший диск на больший третий стержень вспомогательный перенести (n- 1, 1, 2 ) 1 -> 3 перенести (n- 1, 2, 3 ) перенести ( n, 1, 3 )
113 proceduer Hanoi ( n, k, m : integer ) ; var p: integer ; begin p := 6 - k – m ; Hanoi (n- 1, k, p ) ; writeln ( k, ' -> ', m ); Hanoi (n- 1, p, m ) end; номер вспомогательного стержня (1+2+3=6!) сколько откуда куда Что плохо? ? Рекурсия никогда не остановится! ! рекурсия рекурсия
114 Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции. proceduer Hanoi ( n, k, m : integer ) ; var p: integer ; begin p := 6 - k – m ; Hanoi (n- 1, k, p ) ; writeln ( k, ' -> ', m ); Hanoi (n- 1, p, m ) end; if n = 0 then exit; условие выхода из рекурсии program HanoiTower ; ... begin Hanoi ( 4, 1, 3 ) end.
115 procedure printBin ( n : integer ) ; begin if n = 0 then exit; printBin ( n div 2 ) ; write( n mod 2 ) end; условие выхода из рекурсии напечатать все цифры, кроме последней вывести последнюю цифру Как без рекурсии? ? 10011 printBin ( 19 ) printBin ( 9 ) printBin ( 4 ) printBin ( 2 ) printBin ( 1 ) printBin ( 0 )
116 function sumDig (n: integer ): integer ; var sum: integer ; нач sum := n mod 10 ; if n >= 10 then sum := sum + sumDig ( n div 10 ); sumDig := sum end; Где условие окончания рекурсии? ? рекурсивный вызов последняя цифра sumDig ( 1234 ) 4 + sumDig ( 123 ) 4 + 3 + sumDig ( 12 ) 4 + 3 + 2 + sumDig ( 1 ) 4 + 3 + 2 + 1
117 Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел. function NOD ( a, b : integer ) : integer ; begin if ( a = 0 ) or ( b = 0 ) then begin exit end; if a > b then NOD := NOD (a - b, b) else NOD := NOD (a, b - a) end; NOD := a + b ; рекурсивные вызовы условие окончания рекурсии
118 « A »: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида. Пример : Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574)=1234. « B »: Напишите рекурсивную функцию, которая раскладывает число на простые сомножители. Пример : Введите натуральное число: 378 378 = 2*3*3*3*7
119 « C »: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры. Пример : Введите натуральное число: 4 Количество разложений: 4.
120 function Fact (N: integer ): integer ; begin writeln ( '-> N = ', N); if N <= 1 then Fact := 1 else Fact := N * Fact (N- 1 ); writeln ( '<- N = ', N) end; -> N = 3 -> N = 2 -> N = 1 <- N = 1 <- N = 2 <- N = 3 Как сохранить состояние функции перед рекурсивным вызовом? ? Факториал:
121 Стек – область памяти, в которой хранятся локальные переменные и адреса возврата. SP SP 3 A знач SP 3 A знач 2 A F знач 3 A знач 2 A F знач 1 A F знач SP Fact(3) Fact( 2 ) Fact(1) значение параметра адрес возврата локальная переменная
122 с каждым новым вызовом расходуется память в стеке (возможно переполнение стека) затраты на выполнение служебных операций при рекурсивном вызове программа становится более короткой и понятной возможно переполнение стека замедление работы Любой рекурсивный алгоритм можно заменить нерекурсивным ! ! function Fact (N: integer ): integer ; var i, F: integer; begin F:= 1 ; for i := 1 to N do F := F * i ; Fact := F end; итерационный алгоритм
123 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
124 old-moneta.ru www.random.org www.allruletka.ru www.lotterypros.com logos.cs.uic.edu ru.wikipedia.org иллюстрации художников издательства «Бином» авторские материалы
