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 блок-схема установитьСоединение начало цикла cmd = получитьКоманду выполнитьКоманду ( cmd ) конец при cmd = 'stop' закрытьСоединение программа принять команду установить соединение завершить соединение выполнить команду «стоп»? да нет
§ 55. Простейшие программы 8
9 main () { // это основная программа /* здесь записывают операторы */ } Что делает эта программа ? ? это основная программа комментарии после // не обрабатываются это тоже комментарий
10 main () { printf ( "2+" ); printf ( "2=?\n" ); printf ( " Ответ : 4" ); } Протокол: 2+2=? Ответ: 4 " \ n" – новая строка
11 #include < stdio.h > main () { printf ( "2+" ); printf ( "2=?\n" ); printf ( " Ответ : 4" ); getchar (); } стандартные функции ввода и вывода ждать нажатия любой клавиши
12 « B »: Вывести на экран текст «лесенкой» Вася пошел гулять « C »: Вывести на экран рисунок из букв Ж ЖЖЖ ЖЖЖЖЖ ЖЖЖЖЖЖЖ HH HH ZZZZZ
13 Задача. Ввести с клавиатуры два числа и найти их сумму. Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь компьютер считает сам! Как ввести числа в память? Где хранить введенные числа ? Как вычислить? Как вывести результат? ?
14 main() { // ввести два числа // вычислить их сумму // вывести сумму на экран } Псевдокод – алгоритм на русском языке с элементами языка программирования. Компьютер не может исполнить псевдокод! !
15 Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы. a Значение Имя Поместится? ? Другой тип данных В переменной хранятся данные определенного типа! !
16 МОЖНО использовать латинские буквы ( A-Z, a-z) цифры знак подчеркивания _ заглавные и строчные буквы различаются НЕЛЬЗЯ использовать рус c кие буквы скобки знаки +, =, !, ? и др. имя не может начинаться с цифры Какие имена правильные? AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B
17 Типы переменных: int // целая float // вещественная и другие… Объявление переменных: int a, b, c; выделение места в памяти тип – целые список имен переменных
18 область допустимых значений допустимые операции объём памяти формат хранения данных для предотвращения случайных ошибок int a, b = 1, c = 55 ; Начальные значения: Что в переменной a ? ?
19 a = 5 ; оператор присваивания При записи нового значения старое стирается! ! 5 Оператор – это команда языка программирования (инструкция). Оператор присваивания – это команда для записи нового значения в переменную. a
20 Программа ждет, пока пользователь введет значение и нажмет Enter. Введенное значение записывается в переменную a. ! 5 a
21 scanf ( "%d", & a ); функция ввода формат ввода %d – целое %f – вещественное адрес переменной a ввести целое число и записать в память по адресу переменной a
22 через пробел: 25 30 через Enter : 25 30 a 25 b 30 a 25 b 30 scanf ( "% d%d ", & a, & b);
23 int a, b; 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
24 // вывод значения // переменной a //... и переход // на новую строку printf ( "% d ", a ); формат вывода printf ( "% d \n ", a ); " \ n" – новая строка
25 // вывод текста // вывод текста и значения переменной c printf ( " Привет! " ); printf ( " Ответ : %d", c ); printf ( "%d+%d=%d", a, b, c );
26 #include < stdio.h > main() { int a, b, c; scanf ( "% d%d ", &a, &b ); c = a + b; printf ( "% d ", c ); getch ar (); } Что плохо? ?
27 main() { int a, b, c; printf ( " Введите два целых числа\ n " ); scanf ( "% d%d ", &a, &b ); c = a + b; printf ( "%d+%d=%d", a, b, c ); } Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь подсказка
28 a = 123 ; printf ( "% 5 d", a); Форматный вывод : Вычисление выражений: printf ( "%d+%d=%d", a, b, a+b ); a+b 5 знаков 123 5
§ 56. Вычисления 29
30 int // целое long int // длинное целое float // вещественное double // веществ. двойной точности bool // логические значения char // символ
31 a = (c + b * 5 * 3 - 1 ) / 2 * d; Приоритет ( старшинство ): скобки умножение и деление сложение и вычитание 1 2 3 4 5 6
32 Результат деления целого на целое – целое число (остаток отбрасывается): int a = 3, b = 4 ; float x; x = 3 / 4 ; // = 0 x = 3. / 4 ; // = 0.75 x = 3 / 4.; // = 0.75 x = a / 4 ; // = 0 x = a / 4.; // = 0.75 x = a / b; // = 0 x = float (a) / 4 ; // = 0.75 x = a / float (b); // = 0.75 Что запишется в x ? ?
33 % – остаток от деления int a, b, d; d = 85 ; b = d / 10 ; // 8 a = d % 10 ; // 5 d = a % b; // 5 d = b % a; // 3 Для отрицательных чисел : int a = -7 ; b = a / 2 ; // -3 d = a % 2 ; // -1 В математике не так! ! -7 = ( -4 )*2 + 1 остаток 0
34 int a, b; ... a ++; // a = a + 1; a --; // a = a – 1; a += b; // a = a + b; a -= b; // a = a - b; a *= b; // a = a * b; a /= b; // a = a / b; a %= b; // a = a % b;
35 Целая и дробная части числа разделяются точкой ! ! Форматы вывода : float x = 123.456 ; printf ( "%f\n", x ); printf ( "%10.2f\n", x ); 123.45600 1 всего знаков 123.46 в дробной части printf ( "%g\n", x ); printf ( "%10.2g\n", x ); значащих цифр 123.456 1.2e+002 6 цифр в дробной части 6 значащих цифр 1,2 10 2
36 Экспоненциальный формат : float x; x = 1. / 30000 ; printf( "%e\n", x); x = 12345678. ; printf( "%e\n", x); 3.333333e - 0 05 1.234568e+007 3,333333 10 –5 float x = 123.456 ; printf ( "%e\n", x ); printf ( "%10.2e\n", x ); 1.234560 e +002 1.23e+002 1,234568 10 7 всего знаков в дробной части
37 abs (x) — модуль целого числа fabs (x) — модуль вещественного числа sqrt ( x ) — квадратный корень sin ( x ) — синус угла, заданного в радианах cos ( x ) — косинус угла, заданного в радианах exp ( x ) — экспонента е х ln ( x ) — натуральный логарифм pow ( x,y ) — x y : возведение числа x в степень y floor ( x ) — округление «вниз» ceil ( x ) — округление «вверх» #include < math.h > подключить математическую библиотеку float x; x = floor( 1.6 ); // 1 x = ceil( 1.6 ); // 2 x = floor(- 1.6 ); //-2 x = ceil(- 1.6 ); //-1
38 Случайно… встретить друга на улице разбить тарелку найти 10 рублей выиграть в лотерею Случайный выбор : жеребьевка на соревнованиях выигравшие номера в лотерее Как получить случайность?
39 Электронный генератор нужно специальное устройство нельзя воспроизвести результаты 318458191041 564321 209938992481 458191 938992 малый период (последовательность повторяется через 10 6 чисел) Метод середины квадрата (Дж. фон Нейман) в квадрате Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле. зерно
40 X = ( a*X+b) % c | интервал от 0 до c-1 X = ( X+ 3 ) % 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
41 Генератор на отрезке [0,RAND_MAX] : int X, Y; X = r a nd () ; // псевдослучайное число Y = r a nd () // это уже другое число! англ. random – случайный Целые числа на отрезке [a,b] : int X, Y; X = a + rand ( ) % ( b - a + 1 ) ; Y = a + rand ( ) % ( b - a + 1 ) ; #include < stdlib.h > Почему так? ? rand ( ) % (b - a + 1 ) ; [0,b-a]
42 « 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
43 « C »: Получить случайное трехзначное число и вывести через запятую его отдельные цифры. Пример : Получено число 123. Его цифры 1, 2, 3.
§ 57. Ветвления 44
45 Задача: изменить порядок действий в зависимости от выполнения некоторого условия. M = a; a > b? M = b; да нет вывод M полная форма ветвления Если a = b? ? if ( a > b ) M = a; else M = b;
46 M = b; b > a? да нет вывод M M = a; неполная форма ветвления M = a; if ( b > a ) M = b;
47 if ( a > b ) { с = a; a = b; b = c; } Что делает ? ? 4 6 ? 4 6 4 a b 3 2 1 Можно ли обойтись без переменной c ? ? c
48 > < > = < = = = != больше, меньше больше или равно меньше или равно равно не равно
49 if ( a > b ) printf ( " Андрей старше " ); else if ( a == b ) printf( " Одного возраста " ); else printf( " Борис старше " ); вложенный условный оператор Зачем нужен ? ? Задача : в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше? Сколько вариантов ? ?
50 « A »: Ввести три целых числа, найти максимальное из них. Пример : Введите три целых числа: 1 5 4 Максимальное число 5 « B »: Ввести пять целых чисел, найти максимальное из них. Пример : Введите пять целых чисел: 1 5 4 3 2 Максимальное число 5
51 « C »: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них старше. Пример : Возраст Антона: 15 Возраст Бориса: 17 Возраст Виктора: 16 Ответ: Борис старше всех. Пример : Возраст Антона: 17 Возраст Бориса: 17 Возраст Виктора: 16 Ответ: Антон и Борис старше Виктора.
52 Задача : набор сотрудников в возрасте 25-40 лет (включительно). if ( ) printf ( " подходит " ); else printf ( "не подходит" ); && || ! Приоритет : отношения ( <, >, <=, >=, ==, != ) ! («НЕ») && («И») || («ИЛИ») v >= 25 && v <= 40 сложное условие «И» «ИЛИ» «НЕ»
53 « A »: Напишите программу, которая получает три числа и выводит количество одинаковых чисел в этой цепочке. Пример : Введите три числа: 5 5 5 Все числа одинаковые. Пример : Введите три числа: 5 7 5 Два числа одинаковые. Пример : Введите три числа: 5 7 8 Нет одинаковых чисел.
54 « B »: Напишите программу, которая получает номер месяца и выводит соответствующее ему время года или сообщение об ошибке. Пример : Введите номер месяца: 5 Весна. Пример : Введите номер месяца: 15 Неверный номер месяца.
55 « C »: Напишите программу, которая получает возраст человека (целое число, не превышающее 120) и выводит этот возраст со словом «год», «года» или «лет». Например, «21 год», «22 года», «25 лет». Пример : Введите возраст: 18 Вам 18 лет. Пример : Введите возраст: 21 Вам 21 год. Пример : Введите возраст: 2 2 Вам 22 года.
56 « A »: Напишите условие, которое определяет заштрихованную область. « B »: Напишите условие, которое определяет заштрихованную область.
57 « C »: Напишите условие, которое определяет заштрихованную область.
58 if (m == 1 ) printf ( " январь " ); if (m == 2 ) printf ( " февраль " ); ... if (m == 12 ) printf ( " декабрь " ); switch ( m ) { case 1 : printf( " январь " ); break ; case 2 : printf( " февраль " ); break ; ... case 12 : printf( " декабрь " ); break ; default : printf( " ошибка " ); }
59 switch ( m ) { case 1 : printf( " январь " ); case 2 : printf( " февраль " ); case 3 : printf( " март " ); default : printf( " ошибка " ); } Если не ставить break : февральмартошибка При m = 2 :
60 char c; c = getchar (); switch (c) { case ' а ' : printf ( " антилопа \n" ); printf ( " Анапа \n" ); break ; ... case ' я ' : printf ( " ягуар \n" ); printf ( " Якутск \n" ); break ; default : printf ( " Ошибка! " ); } несколько операторов в блоке ждать нажатия клавиши, получить её код
§ 58. Циклические алгоритмы 61
62 Цикл – это многократное выполнение одинаковых действий. Два вида циклов : цикл с известным числом шагов ( сделать 10 раз ) цикл с неизвестным числом шагов (делать, пока не надоест) Задача. Вывести на экран 10 раз слово «Привет». Можно ли решить известными методами ? ?
63 printf ( " Привет \n" ); printf ( " Привет \n" ); ... printf ( " Привет \n" ); Что плохо ? ?
64 начало конец да нет тело цикла сделали 10 раз ? вывод "Привет!"
65 счётчик = 0 пока счётчик < 10 printf( " Привет \n" ); увеличить счётчик на 1 счётчик = 10 пока счётчик > 0 printf( " Привет \n" ); уменьшить счётчик на 1 Какой способ удобнее для процессора ? ? результат операции автоматически сравнивается с нулём!
66 Задача. Определить количество цифр в десятичной записи целого положительного числа, записанного в переменную n. счётчик = 0 пока n > 0 отсечь последнюю цифру n увеличить счётчик на 1 n счётчик 1234 0 123 1 12 2 1 3 0 4 Как отсечь последнюю цифру ? ? n = n / 10 ; Как увеличить счётчик на 1 ? ? счётчик = счётчик + 1 ; счётчик ++;
67 count = 0 ; while ( ) { } n = n / 10 ; count ++; тело цикла начальное значение счётчика n > 0 условие продолжения заголовок цикла конец цикла Цикл с предусловием – проверка на входе в цикл! !
68 k = 0 ; while ( k < 10 ) { printf ( "привет\n" ); k ++; } При известном количестве шагов: k = 0 ; while ( k < 10 ) { printf ( "привет\n" ); } Зацикливание:
69 a = 4 ; b = 6 ; while ( a < b ) a = a + 1 ; 2 раза a = 6 a = 4 ; b = 6 ; while ( a < b ) a = a + b ; 1 раз a = 10 a = 4 ; b = 6 ; while ( a > b ) a ++ ; 0 раз a = 4 a = 4 ; b = 6 ; while ( a < b ) b = a - b ; 1 раз b = -2 a = 4 ; b = 6 ; while ( a < b ) a -- ; зацикливание
70 do { } while ( n <= 0 ); условие продолжения заголовок цикла printf( " Введите n > 0: " ); scanf ( "%d", &n ); тело цикла при входе в цикл условие не проверяется цикл всегда выполняется хотя бы один раз
71 « 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
72 « C »: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи, меньших N. Предусмотрите защиту от ввода отрицательного числа N. Пример : Введите число N: 10000 Сумма 177 1 0
73 « A »: Ввести натуральное число и найти сумму его цифр. Пример : Введите натуральное число: 12345 Сумма цифр 15. « B »: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример : Введите натуральное число: 12342 Нет. Пример : Введите натуральное число: 12 2 4 5 Да.
74 « C »: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры (не обязательно стоящие рядом). Пример : Введите натуральное число: 12342 Да. Пример : Введите натуральное число: 1234 5 Нет.
75 Задача. Вывести все степени двойки от 2 1 до 2 10. Можно ли сделать с циклом «пока» ? ? n = 2 ; while ( ) { printf ( "%d\n", n); n *= 2 ; } k = 1 ; k <= 10 k ++; n = 2 ; for ( ) { printf ( "%d\n", n); n *= 2 ; } k = 1 ; k<= 10 ; k++ цикл с переменной
76 for ( k = 10 ; k >= 1 ; k-- ) printf ( "%d\n", k*k ); 10 0 81 64 49 36 25 16 9 4 1 Что получится ? ? for ( k = 1 ; k <= 10 ; k += 2 ) printf ( "%d\n", k*k ); 1 9 25 49 81
77 a = 1 ; for ( i = 1 ; i <= 3 ; i ++ ) a = a + 1 ; a = 4 a = 1 ; for ( i = 3 ; i <= 1 ; i ++ ) a = a + 1 ; a = 1 a = 1 ; for ( i = 1 ; i <= 3 ; i -- ) a = a + 1 ; a = 1 a = 1 ; for ( i = 3 ; i >= 1 ; i -- ) a = a + 1 ; a = 4
78 « A »: Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111. « B »: Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 1 3 + 5 3 + 3 3. Найдите все трёхзначные Армстронга.
79 «С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 25 2 = 6 25. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N. Пример : Введите N: 1000 1*1=1 5*5=25 6*6=36 25*25=625 76*76=5776
80 Задача. Вывести все простые числа в диапазоне от 2 до 1000. сделать для n от 2 до 1000 если число n простое то вывод n число n простое нет делителей [ 2.. n -1 ] : проверка в цикле! Что значит «простое число» ? ?
81 for ( n = 2 ; n <= 1000 ; n ++ ) { count = 0 ; if ( count == 0 ) printf ( "%d\n", n); } for ( k = 2 ; k < n; k ++ ) if ( n % k == 0 ) count ++; вложенный цикл
82 for ( i = 1 ; i <= 4 ; i ++ ) { for ( k = 1 ; k <= i ; k++ ) { ... } } Как меняются переменные? ? 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 Переменная внутреннего цикла изменяется быстрее! !
83 count = 0 ; k = 2 ; while ( ) { if ( n % k == 0 ) count ++; k ++; } while ( k <= sqrt ( n ) ) { ... } Что плохо? ? while ( k*k <= n && count == 0 ) { ... } k*k <= n Как ещё улучшить? ? (count == 0 )
84 « A »: Напишите программу, которая получает натуральные числа A и B (A<B) и выводит все простые числа в интервале от A до B. Пример : Введите границы диапазона: 10 20 11 13 17 19 « B »: В магазине продается мастика в ящиках по 15 кг, 17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?
85 « C »: Ввести натуральное число N и вывести все натуральные числа, не превосходящие N и делящиеся на каждую из своих цифр. Пример : Введите N: 15 1 2 3 4 5 6 7 8 9 11 12 15
§ 59. Процедуры 86
87 printf ( "Ошибка программы" ); много раз! main() { int n; scanf ( "%d", &n ); if ( n < 0 ) Error(); ... } вызов процедуры void Error () { printf( "Ошибка программы" ) ; }
88 Процедура – вспомогательный алгоритм, который выполняет некоторые действия. текст (расшифровка) процедуры записывается после основной программы в программе может быть много процедур чтобы процедура заработала, нужно вызвать её по имени из основной программы или из другой процедуры
89 Задача. Вывести на экран запись целого числа (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 / 128 n % 128 Как вывести вторую цифру ? ? n 1 / 64
90 Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде. Решение: k = 128 ; while ( k > 0 ) { printf ( "%d", n / k ); n = n % k; k = k / 2 ; } 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 ! !
91 main() { printBin ( 99 ); } значение параметра ( аргумент ) void printBin ( int n ) { int k; k = 128 ; while ( k > 0 ) { printf ( "%d", n / k ); n = n % k; k = k / 2 ; } } Параметры – данные, изменяющие работу процедуры. локальные переменные
92 void printSred ( int a, int b ) { printf ( "%f", ( a+b )/ 2. ); }
93 « A »: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'. Пример : Введите N: 10 ---------- « B »: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой. Пример : Введите натуральное число: 1234 1 2 3 4
94 « C »: Напишите процедуру, которая выводит на экран запись переданного ей числа в римской системе счисления. Пример : Введите натуральное число: 2013 MMXIII
95 Задача. Написать процедуру, которая меняет местами значения двух переменных. main() { int x = 2, y = 3 ; Swap ( x, y ); printf ( "%d %d", x, y ); } void Swap ( int a, int b ) { int c; c = a; a = b; b = c; } 2 3 Процедура работает с копиями переданных значений параметров! ! Почему не работает? ? передача по значению
96 void Swap ( int adrA, int adrB ) { int c; c = * adrA ; * adrA = * adrB ; * adrB = c; } * int a, b; Swap ( & a, & b ); // правильно Swap( 2, 3 ); // неправильно Swap( & a, b +3 ); // неправильно Вызов: * передача по адресу передаются адреса переменных значение переменной по адресу
97 void Swap ( int a, int b ) { int c; c = a; a = b; b = c; } & int a, b; Swap (a, b); // правильно Swap( 2, 3 ); // неправильно Swap(a, b +3 ); // неправильно Вызов: & передача по ссылке переменные могут изменяться
98 « A »: Напишите процедуру, которая переставляет три переданные ей числа в порядке возрастания. Пример : Введите три натуральных числа: 10 15 5 5 10 15 « B »: Напишите процедуру, которая сокращает дробь вида M/N. Числитель и знаменатель дроби передаются как изменяемые параметры. Пример : Введите числитель и знаменатель дроби: 25 15 После сокращения: 5/3
99 « C »: Напишите процедуру, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел и возвращает их через изменяемые параметры. Пример : Введите два натуральных числа: 10 15 НОД(10,15)=5 НОК(10,15)=30
§ 60. Функции 100
101 Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа). Задача. Написать функцию, которая вычисляет сумму цифр числа. Алгоритм: сумма = 0 пока n != 0 сумма = сумма + n % 10 n = n / 10
102 main() { printf ( "%d", sumDigits ( 12345 ) ); } int sumDigits ( int n ) { int sum = 0 ; while ( n != 0 ) { sum += n % 10 ; n /= 10 ; } return sum; } return sum; передача результата int тип результата
103 x = 2 *sumDigits(n+ 5 ); z = sumDigits(k) + sumDigits(m); if ( sumDigits(n) % 2 == 0 ) { printf ( " Сумма цифр чётная \n" ); printf ( "Она равна % d ", sumDigits ( n ) ); } Функция, возвращающая целое число, может использоваться везде, где и целая величина! !
104 « A »: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел. Пример : Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574) = 1234. « B »: Напишите функцию, которая определяет сумму цифр переданного ей числа. Пример : Введите натуральное число: 123 Сумма цифр числа 123 равна 6.
105 « C »: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором цифры стоят в обратном порядке. Пример : Введите натуральное число: 1234 После переворота: 4321.
106 Задача. Найти все простые числа в диапазоне от 2 до 100. main() { int i ; for ( i = 2 ; i <= 100 ; i ++) if ( ) printf ( "%d\n", i ); } i - простое isPrime ( i ) функция, возвращающая логическое значение ( да / нет )
107 Какой алгоритм? ? bool isPrime ( int n ) { int count = 0, k = 2 ; while ( k*k <= n && count == 0 ) { if ( n % k == 0 ) count ++; k ++; } return ( count == 0 ); } bool return (count = = 0 ) ; if ( count = = 0 ) return true ; else return false ;
108 scanf ( "%d", &n ); while ( isPrime(n) ) { printf ( "простое число\ n " ); scanf ( "% d ", & n ); } Функция, возвращающая логическое значение, может использоваться везде, где и логическая величина! !
109 « A »: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого. Пример : Введите натуральное число: 28 Число 28 совершенное. Пример : Введите натуральное число: 2 9 Число 2 9 не совершенное.
110 « B »: Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1. Пример : Введите два натуральных числа: 28 15 Числа 28 и 15 взаимно простые. Пример : Введите два натуральных числа: 28 1 6 Числа 28 и 1 6 не взаимно простые.
111 «С»: Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике. Пример : Введите натуральное число: 733 Число 733 гиперпростое. Пример : Введите натуральное число: 19 Число 19 не гиперпростое.
§ 61. Рекурсия 112
113 У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …
114 Натуральные числа : 1 – натуральное число если – натуральное число, то – натуральное число индуктивное определение Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев. Числа Фибоначчи : при 1, 1, 2, 3, 5, 8, 13, 21, 34, …
115 Фракталы – геометрические фигуры, обладающие самоподобием. Треугольник Серпинского:
116 1 2 3 за один раз переносится один диск класть только меньший диск на больший третий стержень вспомогательный перенести (n- 1, 1, 2 ) 1 -> 3 перенести (n- 1, 2, 3 ) перенести ( n, 1, 3 )
117 void Hanoi ( int n, int k, int m ) { int p; p = 6 - k - m; Hanoi ( n- 1, k, p ); printf ( "%d -> %d\n", k, m ); Hanoi ( n- 1, p, m ); } номер вспомогательного стержня (1+2+3=6!) сколько откуда куда Что плохо? ? Рекурсия никогда не остановится! ! рекурсия рекурсия
118 Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции. void Hanoi ( int n, int k, int m ) { int p; p = 6 - k - m; Hanoi ( n - 1, k, p ); printf ( "%d -> %d\n", k, m); Hanoi ( n - 1, p, m ); } if ( n == 0 ) return ; условие выхода из рекурсии main() { Hanoi ( 4, 1, 3 ) ; }
119 void printBin ( int n ) { if ( n == 0 ) return ; printBin ( n / 2 ); printf ( "%d", n % 2 ); } условие выхода из рекурсии напечатать все цифры, кроме последней вывести последнюю цифру 10011 printBin ( 19 ) printBin ( 9 ) printBin ( 4 ) printBin ( 2 ) printBin ( 1 ) printBin ( 0 ) Как без рекурсии? ?
120 int sumDig ( int n ) { int sum; sum = n % 10 ; if ( n >= 10 ) sum += sumDig ( n / 10 ); return sum ; } Где условие окончания рекурсии? ? рекурсивный вызов sumDig ( 1234 ) 4 + sumDig ( 123 ) 4 + 3 + sumDig ( 12 ) 4 + 3 + 2 + sumDig ( 1 ) 4 + 3 + 2 + 1 последняя цифра
121 Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел. int NOD ( int a, int b ) { if ( a == 0 || b == 0 ) if ( a > b ) return NOD( a - b, b ); else return NOD( a, b – a ); } return a + b ; рекурсивные вызовы условие окончания рекурсии
122 « A »: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида. Пример : Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574)=1234. « B »: Напишите рекурсивную функцию, которая раскладывает число на простые сомножители. Пример : Введите натуральное число: 378 378 = 2*3*3*3*7
123 « C »: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры. Пример : Введите натуральное число: 4 Количество разложений: 4.
124 int Fact ( int N ) { int F; printf ( "-> N=%d\n", N ); if ( N <= 1 ) F = 1 ; else F = N * Fact(N - 1 ); printf ( "<- N=%d\n", N ); return F; } -> N = 3 -> N = 2 -> N = 1 <- N = 1 <- N = 2 <- N = 3 Как сохранить состояние функции перед рекурсивным вызовом? ? Факториал:
125 Стек – область памяти, в которой хранятся локальные переменные и адреса возврата. SP SP 3 A F SP 3 A F 2 A F F 3 A F 2 A F F 1 A F F SP Fact(3) Fact( 2 ) Fact(1) значение параметра адрес возврата локальная переменная
126 с каждым новым вызовом расходуется память в стеке (возможно переполнение стека) затраты на выполнение служебных операций при рекурсивном вызове программа становится более короткой и понятной возможно переполнение стека замедление работы Любой рекурсивный алгоритм можно заменить нерекурсивным ! ! int Fact ( int N ) { int F; F = 1 ; for ( i = 2 ;i <= N;i ++) F = F * i ; return F; } итерационный алгоритм
127 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
128 old-moneta.ru www.random.org www.allruletka.ru www.lotterypros.com logos.cs.uic.edu ru.wikipedia.org иллюстрации художников издательства «Бином» авторские материалы
