Информатика, 10 класс К. Ю. Поляков, Е. А. Еремин
 Скачать 0.95 Mb.
|
|
§ 60. Функции Пример функции С функциями вы уже знакомы, потому что наверняка применяли стандартные функции языка программирования (например, abs, sin, cos). Функция, как и процедура – это вспомогательный алгоритм, который может принимать аргументы. Нов отличие от процедуры, функция всегда возвращает значение-результат. Результатом может быть число, символ, или объект другого типа. Составим функцию, которая вычисляет сумму цифр числа. Будем использовать следующий алгоритм (предполагается, что число записано в переменной n): сумма = пока n != 0 { сумма = сумма + n % 10 n = n / 10 ; } Чтобы получить последнюю цифру числа (которая добавляется к сумме) нужно взять остаток отделения числа на 10. Затем последняя цифра отсекается, и мы переходим к следующей цифре. Цикл продолжается до тех пор, пока значение n не становится равно нулю. Пока остается неясно, как указать в программе, чему равно значение функции Для этого в языках C и С+ используют специальный оператор return (от англ. вернуть, после которого записывают значение-результат: int sumDigits ( int n ) { int sum = 0 ; while ( n != 0 ) { sum += n % 10 ; n /= 10 ; } return sum; } main() { printf ( "%d" , sumDigits( 12345 ) ); } Обратим внимание на особенности записи тип возвращаемого значения ( int) указывается в заголовке функции перед именем функции. Также как ив процедурах, в функциях можно объявлять и использовать локальные переменные. Они входят в зону видимости только этой функции, для всех остальных функций и процедур они недоступны. В функции может быть несколько операторов return, после выполнения любого из них работа функции заканчивается. Функции, созданные в программе таким образом, применяются точно также, как и стандартные функции. Их можно вызывать везде, где может использоваться выражение того типа, который возвращает функция. Приведем несколько примеров на языке C: x = 2 *sumDigits(n+ 5 ); z = sumDigits(k) + sumDigits(m); if ( sumDigits(n) % 2 == 0 ) { printf ( Сумма цифр чётная\n" ); Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 27 22.10.2015 printf ( Она равна %d" , sumDigits(n) ); } Логические функции Достаточно часто применяют специальный тип функций, которые возвращают логическое значение (да или нет, true или false). Иначе говоря, такая логическая функция отвечает на вопрос да или нет и возвращает 1 бит информации. Вернёмся к задаче, которую мы уже рассматривали вывести на экран все простые числа в диапазоне от 2 до 1000. Алгоритм определения простоты числа оформим в виде функции. При этом его можно будет легко вызвать из любой точки программы. Запишем основную программу на псевдокоде для i от 2 до 100 если i - простое то вывод i Предположим, что у нас уже есть логическая функция isPrime, которая определяет простоту числа, переданного ей как параметр, и возвращает true (истинно, если число простое, и false (ложно) в противном случае. Такую функцию можно использовать вместо выделенного блока алгоритма if ( isPrime(i) ) printf ( "%d\n" , i ); if ( isPrime(i) ) cout << i << endl; Остается написать саму функцию isPrime. Будем использовать уже известный алгоритм если число n в интервале от 2 доне имеет ни одного делителя, то оно простое bool isPrime ( int n ) { int k = 2 ; while ( k*k <= n && n % k != 0 ) k ++; return ( k*k > n ); } Эта функция возвращает логическое значение, на это указывает ключевое слово bool (от boolean – булевский, логический, в честь Дж. Буля). Значение функции определяется оператором return ( k*k > n ); Это оператор возвращает результат логического выражения k*k > n. Если это выражение истинно значение счётчика равно 0), то возвращается значение true, иначе – значение false. Для того, чтобы использовать переменные типа bool в языке C, вначале программы нужно подключить файл stdbool.h с помощью директивы #include: В этом файле константе true присваивается значение 1, а константе false – значение 0. Дело в том, что в языке C любое значение, отличное от нуля, соответствует истинному условию, а нулевое значение – ложному. Поэтому логическая функция может возвращать и целое значение – 1 как ответ да и 0 как ответ нет. Форма вызова такой функции не меняется. Логические функции можно использовать также, как и любые условия в условных операторах и циклах с условием. Например, такой цикл останавливается на первом введённом составном числе scanf ( "%d" , &n ); while ( isPrime(n) ) { printf ( "%d - простое число scanf ( "%d" , &n ); } cin >> n; while ( isPrime(n) ) { cout << n << " - простое число << endl; cin >> n; } 8 Эту программу можно еще немного усовершенствовать после числа 2 имеет смысл проверять только не- чётные делители, увеличивая на каждом шаге значение k сразу на 2. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 28 22.10.2015 1. Что такое функция Чем она отличается от процедуры 2. Как оформляются функции в тексте программы 3. Как по тексту программы определить, какое значение возвращает функция 4. Какие функции называются логическими Зачем они нужны 5. Обязательно ли логическая функция должна возвращать значение типа bool? 1. Напишите функцию, которая вычисляет максимальное из трёх чисел. 2. На соревнованиях выступление спортсмена оценивают 5 экспертов, каждый ихних выставляет оценку в баллах (целое число. Для получения итоговой оценки лучшая и худшая из оценок экспертов отбрасываются, а для оставшихся трёх находится среднее арифметическое. Напишите функцию, которая вводит 5 оценок экспертов и возвращает итоговую оценку выступления спортсмена. 3. Напишите функцию, которая вычисляет количество цифр числа. 4. Напишите функцию, которая вычисляет наибольший общий делитель двух чисел. 5. Напишите функцию, которая вычисляет наименьшее общее кратное двух чисел. 6. Напишите функцию, которая разворачивает десятичную запись числа наоборот, например, из 123 получается 321, и из 3210 – 0123. 7. Напишите функцию, которая моделирует бросание двух игральных кубиков (на каждом может выпасть от 1 до 6 очков. (Используйте генератор псевдослучайных чисел) 8. Напишите функцию, которая вычисляет факториал натурального числа N. 9. Напишите функцию, которая вычисляет N-ое число Фибоначчи. 10. Дружественные числа – это два натуральных числа, таких, что сумма всех делителей одного числа (меньших самого этого числа) равна другому числу, и наоборот. Найдите все пары дружественных чисел, каждое из которых меньше 10000. Используйте функцию, которая вычисляет сумму делителей числа. 11. Напишите программу, которая вводит натуральное число N и находит все числа в диапазоне [0,N], сумма цифр которых не меняется приумножении на 2, 3, 4, 5, 6, 7, 8 и 9 (например, число 9). Используйте функцию для вычисления суммы цифр числа. 12. Напишите логическую функцию, которая определяет, верно ли, что число N – совершенное, то есть равно сумме своих делителей, меньших его самого. 13. Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр с конца, тоже является простым. Например, число 733 – гиперпро- стое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что число N – гиперпростое. Используйте уже готовую функцию isPrime. § 61. Рекурсия Что такое рекурсия Вспомним определение натуральных чисел. Оно состоит из двух частей 1) 1 – натуральное число 2) если n – натуральное число, то 1 + n – тоже натуральное число. Вторая часть этого определения в математике называется индуктивным натуральное число определяется через другое натуральное число, и таким образом определяется всё множество натуральных чисел. В программировании этот приём называют рекурсией. Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев. Задачи и задания ? Контрольные вопросы Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 29 Первая часть в определении натуральных чисел – это и есть тот самый базовый случай. Если убрать первую часть из определения, оно будет неполно вторая часть даёт только метод перехода к следующему значению, ноне даёт никакой зацепки, не отвечает на вопрос откуда начать. Похожим образом задаются числа Фибоначчи первые два числа равны 1, а каждое из следующих чисел равно сумме двух предыдущих 1) 1 2 1 = = F F , 2) 2 1 − − + = n n n F F F для Популярные примеры рекурсивных объектов – фракталы. Так в математике называют геометрические фигуры, обладающие самоподобием. Это значит, что они составлены из фигур меньшего размера, каждая из которых подобна целой фигуре. На рисунке показан треугольник Серпинского – один из первых фракталов, который предложил в 1915 году польский математик В. Серпинский. Равносторонний треугольник делится на 4 равных треугольника меньшего размера (левый рисунок, затем каждый из полученных треугольников, кроме центрального, снова делится на 4 ещё более мелких треугольника и т.д. На правом рисунке показан треугольник Серпинского стремя уровнями деления. Ханойские башни Согласно легенде, конец света наступит тогда, когда монахи Великого храма города Бенарас смогут переложить 64 диска разного диаметра с одного стержня на другой. Вначале все диски нанизаны на первый стержень. За один раз можно перекладывать только один диск, причем разрешается класть только меньший диск на больший, ноне наоборот. Есть также и третий стержень, который можно использовать в качестве вспомогательного. Решить задачу для 2, 3 и даже х дисков довольно просто. Проблема в том, чтобы составить алгоритм для любого числа дисков. Пусть нужно перенести n дисков со стержня 1 на стержень 3. Представим себе, что мы как- то смогли перемести n-1 дисков на вспомогательный стержень 2. Тогда остается перенести самый большой диск на стержень 3, а затем n-1 меньших диска со вспомогательного стержня 2 на стержень 3, и задача будет решена. Получается такой псевдокод перенести ( n- 1 , 1 , 2 ) 1 -> перенести ( n- 1 , 2 , 3 ) Здесь запись 1 –> 3 обозначает перенести один диск со стержня 1 на стержень 3». Процедура перенести (которую нам предстоит написать) принимает 3 параметра число дисков, начальный и конечный стержни. Таким образом, мы свели задачу переноса n дисков к двум задача переноса n-1 дисков и одному элементарному действию – переносу 1 диска. Заметим, что при известных номерах начального и конечного стержней легко рассчитать номер вспомогательного, так как сумма номеров равна 1 + 2 + 3 = 6. Получается такая (пока не совсем верная) процедура 1 2 3 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 30 22.10.2015 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 ); } Эта процедура вызывает сама себя, нос другими параметрами. Такая процедура называется рекурсивной. Рекурсивная процедура (функция — это процедура (функция, которая вызывает сама себя напрямую или через другие процедуры и функции. Основная программа для решения задачи, например, с четырьмя дисками, будет содержать всего одну строку (перенести 4 диска со стержня 1 на стержень 3): Hanoi( 4 , 1 , 3 ); Если вы попробуете запустить эту программу, она зациклится, то есть будет работать бесконечно долго. В чем же дело Вспомните, что определение рекурсивного объекта состоит из двух частей. Впервой части определяются базовые объекты (например, первое натуральное число, именно эта часть отвечает за остановку рекурсии в программе. Пока мы не определили такое условие остановки, и процедура бесконечно вызывает сама себя (это можно проверить, выполняя программу по шагам. Когда же остановить рекурсию Очевидно, что если нужно переложить 0 дисков, задача уже решена, ничего перекладывать не надо. Это и есть условие окончания рекурсии если значение параметра n, переданное процедуре, равно 0, нужно выйти из процедуры без каких-либо действий (с помощью оператора return). Правильная версия процедуры выглядит так void Hanoi ( int n, int k, int m ) { int p; if ( n == 0 ) return ; p = 6 - k - m; Hanoi ( n - 1 , k, p ); printf ( "%d -> %d\n" , k, m); Hanoi ( n - 1 , p, m ); } void Hanoi ( int n, int k, int m ) { int p; if ( n == 0 ) return ; p = 6 - k - m; Hanoi ( n - 1 , k, p ); cout << k << " -> " << m << endl; Hanoi ( n - 1 , p, m ); } Чтобы переложить N дисков, нужно выполнить 2 N – 1 перекладываний. Для N=64 это число равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, каждую секунду перемещали один диск, им бы потребовалось 580 миллиардов лет. Примеры Пример 1. Составим процедуру, которая переводит натуральное число в двоичную систему. Мы уже занимались вариантом этой задачи, где требовалось вывести 8-битную запись числа из диапазона 0..255, сохранив лидирующие нули. Теперь усложним задачу лидирующие нули выводить ненужно, а натуральное число может быть любым (в пределах допустимого диапазона для выбранного типа данных. Стандартный алгоритм перевода числа в двоичную систему можно записать, например, так пока n != 0 { вывод n % 2 n = n / 2 } Проблема в том, что двоичное число выводится задом наперёд», то есть первым будет выведен последний разряд. Как перевернуть число Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 31 Есть разные способы решения этой задачи, которые сводятся к тому, чтобы запоминать остатки отделения (например, в символьной строке) и затем, когда результат полностью получен, вывести его на экран. Однако можно применить красивый подход использующий рекурсию. Идея такова чтобы вывести двоичную запись числа n, нужно сначала вывести двоичную запись числа n/2, а затем – последнюю цифру, то есть n % 2. Если полученное число-параметр равно нулю, нужно выйти из процедуры. Такой алгоритм очень просто программируется void printBin ( int n ) { if ( n == 0 ) return ; printBin( n / 2 ); printf ( "%d" , n % 2 ); } void printBin ( int n ) { if ( n == 0 ) return ; printBin( n / 2 ); cout << n % 2 ; } Конечно, тоже самое можно было сделать и с помощью цикла. Поэтому можно сделать важный вывод рекурсия заменяет цикл. При этом программа во многих случаях становится более понятной. Пример 2. Составим функцию, которая вычисляет сумму цифр числа. Будем рассуждать так сумма цифр числа n равна значению последней цифры плюс сумма цифр числа n/10. Сумма цифр однозначного числа равна самому этому числу, это условие окончания рекурсии. Получаем следующую функцию int sumDig ( int n ) { int sum; sum = n % 10 ; if ( n >= 10 ) sum += sumDig ( n / 10 ); return sum; } Пример 3. Алгоритм Евклида, один из древнейших известных алгоритмов, предназначен для поиска наибольшего общего делителя (НОД) двух натуральных чисел. Формулируется он так Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел. Этот алгоритм может быть сформулировать в рекурсивном виде. Во-первых, в нём для перехода к следующему шагу используется равенство НОД( a , b ) = НОД( b a − , b ) при b a ≥ . Кроме того, задано условие останова если одно из чисел равно нулю, то НОД совпадает со вторым числом. Поэтому можно написать такую рекурсивную функцию int NOD ( int a, int b ) { if ( a == 0 || b == 0 ) return a + b; if ( a > b ) return NOD ( a - b, b ); else return NOD ( a, b – a ); } Заметим, что при равенстве одного из чисел нулю второе число совпадает с суммой двух, поэтому в качестве результата функции принимается a+b. Существует и более быстрый вариант алгоритма Евклида (модифицированный алгоритм, в котором большее число заменяется на остаток отделения большего на меньшее int NOD ( int a, int b ) { if ( a == 0 || b == 0 ) return a + b; if ( a > b ) return NOD ( a % b, b ); Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 32 22.10.2015 else return NOD ( a, b % a ); } Эту функцию можно еще значительно упростить. Дело в том, что остаток отделения навсегда меньше делителя b, поэтому при очередном рекурсивном вызове модно передавать функции NOD сначала большее число, а потом – меньшее это позволит избавиться от условного оператора int NOD ( int a, int b ) { if ( b == 0 ) return a; return NOD ( b, a % b ); } Заметьте, что условие окончания рекурсии тоже упростилось достаточно проверить, что на очередном шаге остаток отделения (второй параметр) стал равен нулю, тогда результат – это значение первого параметра a. Как работает рекурсия Рассмотрим вычисление факториала ! N : так называют произведение всех натуральных чисел от 1 до заданного числа N N ⋅ ⋅ ⋅ ⋅ = K 3 2 1 ! . Факториал может быть также введён с помощью рекуррентной формулы, которая связывает факториал данного числа с факториалом предыдущего Здесь первая часть описывает базовый случай (условие окончания рекурсии, а вторая – переход к следующему шагу. Запишем соответствующую функцию на языке C, добавив вначале ив конце операторы вывода 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 Справа от программы показан протокол ее работы при вызове для наглядности сделаны отступы, показывающие вложенность вызовов. Из протокола видно, что вызов Fact(2) происходит раньше, чем заканчивается вызов Fact(3). Это значит, что компьютеру нужно где-то без помощи программиста) запомнить состояние программы (в том числе значения всех локальных переменных) и адрес, по которому нужно вернуться после завершения вызова Fact(2). Для этой цели используется стек. Стек (англ. stack – кипа, стопка) – особая область памяти, в которой хранятся локальные переменные и адреса возврата из процедур и функций. Один из регистров процессора называется указателем стека (англ. stack pointer = SP) – в нём записан адрес последней занятой ячейки стека. При вызове процедуры в стек помещаются значения всех ее параметров, адрес возврата и выделяется место под локальные переменные. На рисунке а показано начальное состояние стека, серым цветом выделены занятые ячейки. Когда функция Fact вызывается из основной программы с параметром 3, в стек записывается значение параметра, затем – адрес возврата Аи выделяется место для результата R 9 (рисунок б. При втором и третьем вложенных вызовах в стек добавляются аналогичные блоки данных (рисун- 9 Результат может передаваться вызывающей программе также через регистры процессора, без использования стека. Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 33 киви г. Заметьте, что в нашем случае адрес возврата A F (точка после вызова в рекурсивной функции) в последних двух блоках будет один и тот же. Когда выполняется возврат из процедуры, состояние стека изменяется в обратную сторону г – в б – а. Что же следует из этой схемы Во-первых, с каждым новым вызовом расходуется дополнительная стековая память. Если вложенных вызовов будет очень много (или если процедура создает много локальных переменных, эта память закончится, и программа завершится аварийно. Во-вторых, при каждом вызове процедуры некоторое время затрачивается на выполнение служебных операций (занесение данных в стеки т.п.), поэтому, как правило, рекурсивные программы выполняются несколько дольше, чем аналогичные нерекурсивные. А всегда ли можно написать нерекурсивную программу Оказывается всегда. Доказано, что любой рекурсивный алгоритм может быть записан без использования рекурсии (хотя часто при этом программа усложняется и становится менее понятной. Например, для вычисления факториала можно использовать обычный цикл F = 1 ; for ( i = 2 ; i <= N; i++ ) F = F * i; В данном случае такой итерационный (то есть повторяющийся, циклический) алгоритм значительно лучше, чем рекурсивный он не расходует стековую память и выполняется быстрее. Поэтому здесь нет никакой необходимости использовать рекурсию. Итак, рекурсия – это мощный инструмент, заменяющий циклы в задачах, которые можно свести к более простым задачам того же типа. В сложных случаях использование рекурсии позволяет значительно упростить программу, сократить ее текст и сделать более понятной. С другой стороны, если существует простое решение задачи без использования рекурсии, лучше применить именно его. Нужно стараться обходиться без рекурсии, если вложенность вызовов получается очень большой, или процедура использует много локальных данных. 1. Что такое рекурсия Приведите примеры. 2. Как выдумаете, почему любое рекурсивное определение состоит из двух частей 3. Что такое рекурсивная процедура (функция 4. Расскажите о задаче Ханойские башни. Попытайтесь придумать алгоритм ее решения, не использующий рекурсию. 5. Процедура А вызывает процедуру Б, а процедура Б – процедуру Аи сама себя. Какую из них можно назвать рекурсивной 6. В каком случае рекурсия никогда не остановится Докажите, что в рассмотренных задачах этого не случится. 7. Что такое стек Как он используется при выполнении программ 8. Почему при использовании рекурсии может случиться переполнение стека ? Контрольные вопросы 3 А 3 А А б) a) в) 3 А А R 1 А г) SP SP SP SP Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 34 22.10.2015 9. Назовите достоинства и недостатки рекурсии. Когда ее следует использовать, а когда – нет 1. Найдите в Интернете информацию об использовании рекурсии в искусстве и рекламе. Сделайте сообщение в классе. 2. Найдите в Интернете информацию о фракталах. Сделайте сообщение в классе. 3. Используя материалы Интернета, ответьте на вопрос Как связаны числа Фибоначчи с кроликами. Придумайте свою рекурсивную фигуру и опишите е. 5. Используя графические возможности модуля turtle, постройте на экране треугольник Серпинского и другие фракталы. 6. Напишите рекурсивную процедуру для перевода числа в двоичную систему, которая правильно работала бы для нуля (выводила 0). 7. Напишите рекурсивную процедуру для перевода числа в шестнадцатеричную систему счисления. 8. Напишите рекурсивную процедуру для перевода числа в троичную уравновешенную систему счисления (см. § 14). Вместо цифры 1 используйте символ «#». 9. Дано натуральное число N. Требуется получить и вывести на экран всевозможные различные способы представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры 10. Напишите рекурсивную процедуру для перевода числа из двоичной системы счисления в десятичную. 11. Напишите рекурсивную процедуру для перевода числа из шестнадцатеричной системы счисления в десятичную. 12. Напишите рекурсивную процедуру для перевода числа из троичной уравновешенной системы счисления (см. § 14) в десятичную. Вместо цифры 1 используйте символ «#». 13. Напишите рекурсивную и нерекурсивную функции, вычисляющие НОД двух натуральных чисел с помощью модифицированного алгоритма Евклида. Какой вариант вы предпочтете |