Практикум ргппу 2017 3 Аннотация
 Скачать 3.14 Mb.
|
|
Тема 4 Вспомогательные алгоритмы Процесс решения сложной задачи часть сводится к решению нескольких более простых подзадач. Соответственно процесс разработки сложного алгоритма разбивается на этапы составления отдельных алгоритмов, которые называются вспомогательными. Каждый вспомогательный алгоритм описывает решение какой- либо подзадачи. При разработке сложных алгоритмов используется метод последовательной детализации, который состоит в следующем.Сначала алгоритм формулируется в крупных блоках, которые еще нельзя перевести на язык операторов и записываются как вызовы вспомогательных алгоритмов. Затем происходит детализации, и все вспомогательные алгоритмы подробно расписываются для перевода на язык команд. Вспомогательные алгоритмы на языке программирования реализуются через подпрограммы. Программы, которые неразделимы на отдельные структурные элементы, называются монолитными. Большие монолитные программы сложны для разработки, отладки и сопровождения. Минимальным автономным элементом монолитной программы является оператор. Естественно стремление разбить программу на более крупные, чем оператор, компоненты. Роль таких компонентов выполняют подпрограммы. Программы, содержащие подпрограммы, называются модульными. Подпрограммы, в свою очередь, могут вызывать подпрограммы более низкого уровня и т.д. Таким образом, каждая модульная программа имеет иерархическую структуру. Использование аппарата подпрограмм позволяет сократить объем и улучшить структуру программы с точки зрения наглядности и читаемости, уменьшить вероятность ошибок и облегчить процесс отладки программы. Разложение программы на взаимосвязанные, но замкнутые и логически завершенные компоненты дает возможность выполнять разработку отдельных подпрограмм разным программистам и более или менее независимо друг от друга. Кроме того, подпрограмма может быть рассмотрена как отдельная единица (со своими входными и выходными данными), что позволяет использовать ее в общем иерархическом подходе при конструировании алгоритма и программы по принципам нисходящего проектирования. В языке C++ подпрограммы реализуются в виде функций и void функций. Существуют встроенные (стандартные) функции, которые являются частью языка и могут вызываться по имени без предварительного описания. Программист имеет возможность определять свои собственные функции. Это можно делать либо в том же файле, в котором хранится основная часть программы, либо в отдельном файле, с тем чтобы эту функцию можно было использовать и в других программах. И в том и в другом случае определение будет одним и тем же, но пока предположим, что функция определяется в том же файле, в котором содержится функция main программы. Описание функции состоит из двух частей, которые называются прототипом функции (function prototype) иопределением функции (function 84 definition). Прототип функции описывает, как эта функция должна вызываться. В C++ перед вызовом функции в коде должно быть помешено либо полное определение функции, либо ее прототип. Прототип функции предоставляет всю информацию, необходимую для того, чтобы вызвать эту функцию. В коде прототип должен располагаться до вызова функции, если только она не была определена до этого. Обычно прототипы функций размещают перед функцией main программы. В определении функции описано, как именно эта функция должна вычислять возвращаемое значение. Если представить себе функцию как маленькую программу внутри вашей большой программы, то определение функции — это ее код. Синтаксис определения функции очень похож на синтаксис основной части программы. Определение функции состоит из заголовка функции, вслед за которым следует тело функции. Заголовок функции записывается гак же, как и ее прототип, но в конце заголовка, в отличие от прототипа, не ставится точка с запятой. Это приводит к тому, что заголовок повторяется, но в этом нет ничего страшного. Хотя прототип функции и сообщает всю информацию, необходимую при ее вызове, он не сообщает, какое именно значение эта функция возвращает. Возвращаемое функцией значение определяется инструкциями тела функции. Тело функции следует после ее заголовка и завершает определение функции, состоящее из объявлений и выполняемых инструкций, заключенных в фигурные скобки. Таким образом, тело функции выглядит точно так же, как и та часть программы, которая следует после слова main. При вызове функции вместо ее формальных параметров подставляются реальные аргументы, после чего выполняются инструкции тела этой функции. Возвращаемое функцией значение определяется в момент вычисления инструкции return. Инструкция return состоит из ключевого слова return, за которым следует выражение. Чтобы лучше разобраться в использовании функций, запомните три положения.. Определение функции похоже на небольшую программу, а ее вызов подобен запуску этой "маленькой" программы. В функции вместо ввода, поступающего в программу с помощью потока cin, используются формальные параметры. Аргументы функции (фактические параметры), которые подставляются вместо формальных параметров, служат для нее входной информацией. Функция ничего не выводит на экран, однако возвращает некоторую информацию вызвавшей ее программе. Для этого она использует инструкцию return.. Размещение определения функции Мы обсудили, где, как правило, размешаются прототипы и определения функций. В обычной ситуации указанное место является для них самым лучшим. Однако компилятор будет воспринимать и такие программы, в которых эти элементы кода размешаются в некоторых других местах. Сформулируем эти правила более точно: до вызова каждой функции компилятор должен встретить либо ее прототип, либо определение. Например, если в программе все определения 85 функций разместить перед основной частью программы, то прототипы функций уже не нужны. Знание этого общего правила поможет понять программы на C++, приведенные в других книгах, но все же лучше придерживаться образца, по которому написаны программы, представленные в этих работах. Используемого нами стиля придерживается большая часть программистов, которые работают на C++. Процедурная абстракция Применительно к определению функции принцип процедурной абстракции означает, что функцию нужно писать так, чтобы ее можно было использовать подобно черному ящику.Это значит, что программисту, который захочет использовать эту функцию, не нужно будет заглядывать в ее тело, чтобы понять, как она работает. Прототип функции и прилагающийся к ней комментарий должны предоставлять всю необходимую для использования этой функции информацию. Чтобы определение функции удовлетворяло этому требованию, нужно строго придерживаться приведенных ниже правил. Как писать определение функции в виде черного ящика Комментарии к прототипу должны сообщать программисту все, что необходимо знать об аргументах функции, и описывать значение, возвращаемое функцией при ее вызове с этими аргументами. Все переменные, используемые в теле функции, должны быть объявлены в теле функции (формальные параметры объявлять не нужно, потому что они перечислены в ее прототипе). Принцип процедурной абстракции гласит, что функция должна быть оформлена в виде самодостаточного модуля, который разрабатывается отдельно от остальной программы. При работе над большими программными проектами функции могут разрабатываться разными программистами, которые должны подбирать для формальных параметров имена, наиболее подходящие по смыслу. Аргументам (фактическим параметрам), которые подставляются вместо формальных параметров (и зачастую не тем программистом, который писал определение функции), тоже следует давать имена со смыслом. При этом может оказаться, что некоторые аргументы имеют одинаковые имена с формальными параметрами. Это был бы идеальный вариант. Однако независимо от того, какие имена выбраны для переменных, которые будут использованы в качестве аргументов, эти имена не перепутаются с именами формальных параметров. Ведь функции используют только значения аргументов, не обращая внимания на их имена. Лабораторная 5 Функции Теория Функция – это подпрограмма, вычисляющая и возвращающая некоторое значение. 86 Функция пользователя используется только тогда, когда требуется вычислить единственное значение. Функция возвращает результат в точку своего вызова. Поэтому функция является частью какого-нибудь выражения. Синтаксис функции, которая возвращает значение: Прототип функции: Возвратаемый_тип Имя_функции {Список_параметров); Комментарии_к_прототипу Определение функции: //Следующая строка представляет собой заголовок функции Возвращаемый_тип Имя_функции(Список_параметров) { // Начало тела функции Объявление_1 Объявление_2 Объявление_N Исполняемая_инструкция_1 // Одна из этих Исполняемая_инструкция_2 // инструкций . . . // должна быть Исполняемая_инструкция_N // инструкцией return } // Конец тела функции Поскольку функция не возвращает значения, пока не выполнит инструкцию return, в ее теле должна находиться по крайней мере одна такая инструкция (в теле функции может находиться и несколько инструкций return). Для определения функции допустим любой образец размещения с помощью пробелов и символов новой строки. Однако лучше придерживаться тех же правил использования отступов от начала строки и размещения элементов кода, которые приняты для основной части программы. В частности открывающая ({) и закрываю- щая (}) скобки, которыми обозначаются границы тела функции, размещаются на от- дельных строках. Тем самым тело функции отделяется от остального кода. Данные, описанные в подпрограмме, действительны только в пределах данной пользовательской подпрограммы. Они называются локальные параметры. Данные, описанные в основной программе, называются глобальными и их можно так же использовать в подпрограмме. Если имя глобальной переменной совпадает с именем локальной, внутри подпрограммы эта переменная интерпретируется как локальная. Параметры функции позволяют вычислять функцию с различными начальными данными. Параметры указываются в заголовке функции и называются формальными параметрами. По сути, они являются переменными, локальными для определения данной функции; их можно рассматривать как локальные переменные, которые объявляются при определении функции. Описание формальных параметров имеет вид: тип имя параметра. Описание параметров разделяются запятой. При вызове функции список формальных параметров заменяется фактическими параметрами. Между формальными и фактическими параметрами должны выполняться следующие правила соответствия: по количеству (количество формальных и фактических параметров одинаково); 87 по последовательности (первому формальному параметру соответствует первый фактический параметр, второй – второму и т.д.); по типам ( типы соответствующих формальных и фактических параметров должны совпадать). Фактические параметры-аргументы могут бать выражениями соответствующего типа. При разработке блок-схемы вспомогательный алгоритм разрабатывается как отдельная блок-схема, но в блоке «Начало» указывается заголовок подпрограммы. Примеры Пример 1. Вычислить с заданной точностью Этот пример рассматривался в предыдущей лабораторной работе. Возведение в степень в нем выполнялось с помощью функции pow, но результат функции – это вещественное число, хотя в степень возводятся целые числа и результат тоже будет целым. В этом случае модно создать функцию возводящую целые числа в целую степень. p=1 i=1,k,1 p=p*x p power(x,k) int power( int x, int k) { int p=1; for ( int i=1;i<=k;i++) p*=x; return p; } Исходные данные: точность eps вещественный тип, член последовательности а – вещественный тип. Результат: сумма S – вещественный тип. Тестовый пример: при eps=10 -4 , S=0.0097. 0 2 5 4 1 i i i 88 Пример 2. Д аны натур альны е числа n, m, целые числа a 1 , …, a n , b 1 , …, b m , c 1 , …, c 10 Получ ить w=x 2 + y 2 +z 2 , где x= min(a 1 , …, a n ), y= min(b 1 , …, b m ), z= min(c 1 , …, c 10 ). Исходные данные: n, m – целого типа, элемент последовательности a – целого типа, элемент последовательности b целого типа, элемент последовательности c– целого типа, Результат: w целого типа Приведен пример блок-схемы вычисления функции нахождения минимального значения. Тестовый пример: при n=7, m=8, последовательность а: 5, 2, 7, 0, 6, 1, 4; последовательность b: -1, -3, -5, -3, -6, -2, -2, -7; последовательность с -2, 4, 6, -8, 3, 5, -3, -5, -2, 1 w=65. a=1/(1+25) s=0 i=0 Ввод eps a>eps a=1/(power(4,i)+power(5,i+2) s=s+a i=i+1 Вывод s да нет # include # include using namespace std; int power( int x, int k); void main() { int i=0; double eps,a,s=0; cout<< "eps=" ; cin>>eps; a=1.0/(1+25); while (a>eps) {s=s+a; i++; a=1.0/ (power(4,i)+power(5,i+2)); } cout<< "s= " < } int power( int x, int k) { int p=1; for ( int i=1;i<=k;i++) p*=x; return p; } 89 Ввод n,m Вычисление x - минимального значения в последовательности a Вычисление y - минимального значения в последовательности b Вычисление z - минимального значения в последовательности c w=x 2 +y 2 +z 2 Вывод w minimum(k) Ввод t min=a i=2,k,1 Ввод t t y=minimum(m) z=minimum(10) w=x 2 +y 2 +z 2 Вывод w 90 Пример 3. Составить программу нахождения всех простых чисел не превосходящих n. Исходные данные: n – целый тип. Результат: вывод i числа, количество делителей у которого равно 0. Ввод n i=1,n,1 Найти k - количество делителей i k=0 Вывод i да нет При построении укрупненной блок схемы не выявлены повторяющиеся задачи, но подсчет количества делителей у числа можно рассматривать как самостоятельную задачу. Для этой задачи можно написать отдельную функцию. Тестовый пример: при n=15, вывод 1, 2, 3, 5, 7, 11, 13. Ввод n i=1,n,1 k=kol_d(i) k=0 Вывод i да нет kol_d(n) k=0 i=2,k/2,1 n mod n=0 k=k+1 k да нет 91 Пример 4. Написать программу, которая проверяет, являются ли во введенном четырехзначном числе вида abcd , все цифры разные. Исходные данные: четырехзначное число m. Результаты: цифры числа m - a,b,c,d целый тип, k=0, если есть совпадение цифр, k=1 если совпадения цифр нет. Следует создать функцию, которая выделяет заданную цифру из данного числа. Эта функция работает только с 4-значным числом, поэтому в начале программу следует проверить количество цифр в числе. Тестовый пример: при 2467 – все цифры разные; при 1233 –цифры совпадают. tcif(n,k) i=1,p,1 n=n / 10 a=n % 10 p=5-k a a=tcif(m,1) b=tcif(m,2) k=0 Ввод m m>999 и m<10000 да нет A c=tcif(m,3) d=tcif(m,4) не совпадают a<>b c<>a и c<>b d<>c и d<>b и d<>a k=1 k=1 совпадают да да да нет нет нет да нет A 92 Пример 5. Найти наибольший общий делитель 3 чисел. Исходные данные: A, B, C – целого типа. Результат: наибольший общий делитель чисел A, B, C – D целого типа. NOD(A,B) A<>B A>B A=A-B B=B-A NOD=A да да нет нет Нахождение наибольшего общего делителя (НОД) двух чисел выполняется в функции NOD. Сначала находится НОД для чисел A, B, а затем для полученного значения и D. Ввод A, B, C D=NOD(NOD(A,B),C) Вывод D Задание 1 Написать и отладить программу для примера 4. Контрольные вопросы 1. Может ли функция не иметь параметров. 2. Могут ли в качестве фактических параметров использоваться выражения. 3. Какие правила соответствия должны выполняться для формальных и фактических параметров. 4. Что будет, если имя формального параметра совпадает с глобальным параметром. 5. В Примере № 3 в основной программе используется цикл с параметром i и в подпрограмме используется цикл с параметром i. Не запутается ли программа с такими совпадениями. 93 6. Можно ли в теле функции использовать несколько операторов return. 7. Можно ли из одной функции вызывать другую функцию. Индивидуальные задания 1. Даны действительные числа s, t. Получить: h(s,t)+max(h 2 (s-t, st), h 4 (s-t, s+t)) + h(1,1), где 3 2 2 ) ( 1 1 ) , ( b a a b b a b a h 2. Даны действительные числа a, b, натуральное число n (b>a). Получить (f 1 + … + f n )h, где , 2 , 1 , 2 1 1 2 1 , 2 n i h i a h i a f n a b h i 3. Даны натуральные числа k, l, m целые числа x 1 , …, x k , y 1 , …, y l , z 1 , …, z m. Получить (max(y 1 , …, y l ) + max(z 1 , …, z m ))/2 при max(x 1 , …, x k )>=0, l= 1+( max(x 1 , …, x k )) 3 в противном случае. 4. Дано натуральное n. Вычислить сумму n k k S k 1 ! где 1 1 3 1 2 1 k S k 5. Даны натуральные u, v и n. Найти n k k k k b a 1 )! 1 ( , где a 1 =u, b 1 =v, a k =2b k-1 +a k-1 ; b k =2a 2 k-1 +b k-1 , k=2,3,… Вычисление a k и b k и факториала выполнять с помощью функции. 6. Даны действительные числа x и ε (x≠0, ε > 0). Вычислить с точностью ε и указать количество учтенных слагаемых 0 1 2 1 )! 1 2 ( )! 1 2 ( ) 1 ( k k k k k x Возведение в степень и факториал вычислять с помощью функций 7. Дано действительное число y. Получить ) 1 ( 6 ) 1 ( 2 ) 25 0 ( 7 1 2 y t y t t , где 10 0 2 10 0 1 2 )! 2 ( )! 1 2 ( ) ( k k k k k x k x x t 94 8. Составить программу для нахождения чисел из интервала [M, N], имеющих наибольшее количество делителей. 9. Составить программу, определяющую, в каком из данных двух чисел больше цифр. 10. Два натуральных числа называются «дружественными», если каждое из них равно сумме всех делителей (кроме его самого) другого числа (например 220 и 284). Найти все пары «дружественных» чисел, которые не больше данного числа N. 11. Натуральное число, в записи которого n цифр, называется числом Амстронга, если сумма его цифр, возведенная в степень n, равна самому числу. Найти все числа Амстронга от 1 до k. 12. Найти все натуральные числа, не превосходящие n, которые делятся на каждую из своих цифр. Процедуры (void-функции) Теория В C++ подзадачи реализуются в виде функций. Функции, которые рассматривались выше, всегда возвращают одно значение. Однако бывают и другие виды подзадач, например, когда требуется возвратить из функции несколько значений либо не возвращать вовсе ничего. Функции, которые не возвращают ни одного значения, называются процедурами (в C - void-функциями). Например, одной из типичных подзадач программы является вывод результатов вычислений. В этой подзадаче осуществляется вывод на экран, но она не вычисляет никаких значений, которые бы использовались в остальной части программы. Такую разновидность подзадач можно реализовать в виде void-функций. Процедура (void-функция) – это независимая именованная часть программы, которую после однократного описания можно многократно вызывать по имени из последующих частей программы для выполнения определенных действий. В C++ эти void-функции определяются аналогично функциям, возвращающим значение. Между определением void-функции и определениями функций, есть только два различия. Одно из них заключается в том, что вместо указания типа возвращаемого значения в определении void-функции используется ключевое слово void. Тем самым компилятору сообщается, что эта функция не возвращает никаких значений. Само имя void говорит: "эта функция не возвращает никаких значений". Второе различие состоит в том, что в инструкции return не содержится выражения, 95 по которому должно вычисляться возвращаемое значение, потому что никакого возвращаемого значения не существует. Синтаксис определения void-функции Прототип void-функции: void Имя_функции{Список_параметров); / /Комментарий_к_прототипу Определение void-функции: void Имя_функции(Список_параметров) //Заголовок функции { //Начало тела функции 0бъявление_1 // Объявления можно чередовать 0бъявление_2 // с исполняемыми инструкциями Объявление_N Выполняемая инструкция_1 // Можно включить одну или Выполняемая инструкция_2 // несколько (необязательных) Выполняемая инструкция_3 // инструкций return Выполняемая инструкция_N } //Конец тела функции Вызов процедуры (void-функции) является выполняемой инструкцией. Она состоит из имени функции и списка фактических параметров отделенных друг от друга запятыми и заключенными в круглыми скобками. Иногда нужны функции без аргументов, что вполне корректно. В этом случае в прототипе функции список формальных параметров просто отсутствует и при ее вызове не передается ни одного аргумента. Процедуры имеют более широкий спектр применения, чем функции: с помощью процедур можно одновременно вычислять несколько значений; в процедурах можно изменять входные параметры; результатом процедур не обязательно является вычисление значений, это может быть выполнение каких-нибудь действий, например ввод или вывод данных. В процедурах (void-функциях), как и в функциях, возвращающих значение, могут присутствовать инструкции return. Если функция возвращает значение, оно определяется инструкцией return. В void-функциях эта инструкция просто завершает вызов функции, т.е.означает досрочный выход из функции. При вызове функции ее аргументы подставляются вместо формальных параметров из определения этой функции; иными словами, аргументы "подключаются" к формальным параметрам. Есть несколько механизмов реализации такого процесса подстановки. Механизм, использовавшийся в предыдущем разделе, называется механизмом передачи параметров по значению (call-by-value). Второй важный механизм подстановки аргументов известен под названием передачи параметров по ссылке (call-by-reference). При выполнении некоторых подзадач оказывается, что механизма передачи параметров по значению недостаточно. Например, довольно распространенной задачей является вычисление в функции одной или нескольких величин. Аргументы функции, которые использовались до сих пор, могут быть переменными, но вместо формального параметра вызова по значению подставляется только значение аргумента. Для функции вычисляющей несколько значений нужно, чтобы вместо вычисляемого формального параметра подставлялась сама перемен- 96 ная, а не только ее значение. Механизм передачи параметров по ссылке работает следующим образом. Для формального параметра, передаваемого по ссылке, соответствующий аргумент вызова функции должен быть переменной, и эта переменная подставляется в тело функции вместо формального параметра. Все происходит так, как если бы переменная-аргумент (а не ее значение!) буквально копировалась в тело определения функции вместо формального параметра. После этого при выполнении тела функции значение переменной-аргумента может изменяться. Чтобы компилятор мог отличить параметр, передаваемый по ссылке, от параметра, передаваемого по значению, необходимо явно указать способ передачи по ссылке. Для этого используется знак амнерсанда (&), который располагается после имени типа формального параметра, передаваемого по ссылке, как в прототипе функции, так и в заголовке ее определения. В блок-схеме программы блок-схема процедуры, как и блок-схема функции, изображается отдельно. В блок-схеме основной программы оператор вызова подпрограммы изображается в виде блока: Примеры Пример 6. Дана дробь в виде В А (А, В – натуральные числа). Представить эту дробь в виде несократимой дроби. Исходные данные: A – числитель, целый тип и B – знаменатель, целый тип. Результат: A – числитель после сокращения, В – знаменатель после сокращения. Для сокращения дроби надо найти наибольший общий делитель (НОД) для числителя и знаменателя, а затем разделить числитель и знаменатель на это число. Сокращение дроби запишем в отдельной viod-функции SOKR. Эта viod- функция в дальнейшем может быть использована в других задачах. Данную задачу можно решить только с использованием viod-функции, т.к. в результате этой подпрограммы изменяются входные параметры. Обратите внимание, что функция NOD, которая была рассмотрена в предыдущей лабораторной работе, в данном примере представлена как viod- функция. Любая функция может быть представлена как void-функция. В этом случае, полученный результат является еще одним параметром void-функции, причем параметром, передаваемым по ссылке. В данном примере используется две void-функции: void-функция NOD, для нахождения наибольшего общего делителя и void-функция SOKR для сокращения числителя и знаменателя. Void-функция SOKR вызывает процедуру NOD, поэтому в описании прототипов void-функция NOD должна предшествовать void-функции SOKR Тестовый пример: 97 При А=7, В=56, после сокращения получаем А=1, В=8. NOD(A, B, C) A ≠B A>B A=A-B B=B-A Да Нет Да Нет С=A SOKR(A,B) NOD(A,B,C) A=A/C B=B/C Ввод A, B SOKR(A, B) Вывод A, B # include # include using namespace std; //Нахождение наибольшего общего делителя - c void nod( int a, int b, int & c); // сокращение дроби a/b void socr( int & a, int & b); void main() { int a,b; cout<< "a=" ; cin>>a; cout<< "b=" ; cin>>b; socr(a,b); cout<< "a= " < < } void nod( int a, int b, int & c) { while (a!=b) { if (a>b) a=a-b; else b=b-a; } c=a; } void socr( int & a, int & b) { int c; nod(a,b,c); a=a/c; b=b/c; } 98 Пример 7. Дана последовательность из n натуральных чисел. Для каждого числа указать его наименьший и наибольший делитель. Для простого числа – 1 и само число, для остальных это должны быть числа отличные от 1 и самого числа. Исходные данные: n- количество элементов последовательности. а – элемент последовательности. Результат: Max – наибольший делитель, Min – наименьший делитель каждого элемента последовательности. Нахождение наибольшего и наименьшего делителя выполняется в процедуре DELIT. Void- функция в этом случае используется потому, что в результате получается не одно значение, а два. Тестовый пример: при n=5 и a=6, Max=3, Min-2 a=7, Max=7, Min=1 a=24, Max=12, Min=2 a=15, Max=5, Min=3 a=63, Max=7, Min=3 DELIT(M,Max, Min) Min=0 Max=0 i=2, M/2,1 M % i=0 Max=i Min=0 Min=i Max=0 Min=1 Max=M да нет да нет да нет Обнуление начального минимального делителя Обнуление начального максимального делителя Перебор возможных делителей Если это делитель Запоминаем делитель в Max Если это первый найденный делитель Запоминаем делитель в Min Если делителей нет A A # include # include # include using namespace std; Ввод n i=1,n,1 Ввод а DELIT(a, Max, Min) Вывод Max, Min 99 void delit( int m, int & min, int & max); void main() { int n,a,min,max; setlocale(0, "" ); cout<< "n=" ;cin>>n; for ( int i=1;i<=n;i++) {cout<<"Введите число "; cin>>a; delit(a,min,max); cout<<"мимальный делитель "< _getch(); } void delit( int m, int & min, int & max) {min=0; max=0; for ( int i=2; i<=m/2;i++) { if (m % i==0) {max=i; if (min==0) min=i; } } if (max==0) {min=1; max=m; } } Пример 8. Найти все натуральные числа, не превосходящие заданное N, которые делятся на каждую из своих цифр. Исходные данные: N – целый тип. Результат: Вывод чисел, которые делятся на каждую из своих цифр. В процедуре Prov проверяется делится ли число на все свои цифры, если делится - данное число выводится на экран. Результатом процедуры является печать чисел, удовлетворяющих заданному условию. Тестовый пример: При N=20 выводятся числа: 1,2,3,4,5,6,7,8,9,10,11,12,15,20 Приведен пример блок-схемы процедуры Prov, которая проверяет деление числа на свои цифры. 100 Задание 2 Написать и отладить программу для примера 8. Контрольные вопросы 1. Можно ли в Примере 6 при вычислении NOD параметры A и B описать как параметры, передаваемые по ссылке. 2. Можно ли в Примере 6 поменять местами описание void-функции NOD и SOKR. 3. Перечислите преимущества void-функций перед функциями. 4. Чем параметры передаваемые по ссылке отличаются от параметров передаваемых по значению. 5. Можно ли в Примере 6 использовать не viod-функцию, а функцию. 6. В каких случаях viod-функцию можно заменить на функцию. 7. Можно ли в качестве фактических параметров по ссылке использовать выражения. 8. В каких ситуациях удобнее использовать функцию вместо viod-функции. Индивидуальные задания 1. Даны две дроби D C B A и (A, B, C, D – натуральные числа). Составить программу вычитания этих дробей. Результат должен быть несократимой дробью. 2. Даны две дроби (A, B, C, D – натуральные числа). Составить программу для деления этих дробей. Результат должен быть несократимой дробью. D C B A и Prov(n) k=0 n / 10>0 n=n / 10 k=0 m=n Вывод k a=n% 10 m % a!=0 k=1 m % n!=0 k=1 Сохранение первоначального числа Признак деления числа на его цифру Выделение цифры из числа Проверка деления числа на его цифру Сокращение числа на разряд Признак, что число не делится на цифру Проверка последней цифры Если число делится на все свои цифры да нет да нет нет да нет да A A 101 3. Даны натуральные n, m и последовательности вещественных чисел х 1 , х 2 , …, х n , y 1 , y 2 , …, y m . Найти разности максимумов и минимумов каждой последовательности. 4. Два простых числа называются «близнецами», если они отличаются друг от друга на 2 (например, 41 и 43). Напечатать все пары «близнецов» из отрезка [n, 2n], где n – заданное натуральное число. 5. Дано натуральное n-значное число. Оставить в этом числе только первую цифру, а остальные заменить нулями. 6. Дано натуральное число N. Вывести все совершенные числа, которые <=N. Совершенным называется число равное, сумме своих делителей. 7. Дана последовательность из n натуральных чисел и натуральное число А. Найти в данной последовательности число, которое имеет самый большой наибольший общий делитель с числом А. 8. Дано натуральное число N. Найти и вывести все числа в интервале от 1 до N-1, у которых сумма всех цифр совпадает с суммой цифр данного числа. 9. Найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую последовательность (например, 1234). 10. Из заданного числа вычли сумму его цифр. Из результата вновь вычли сумму его цифр и т.д. сколько таких действий надо произвести, чтобы получить нуль? 11. Для последовательности а 1 =1, составить программу печати k-того члена в виде обыкновенной несократимой дроби. 12. Дано четное число n>2. Проверить для него гипотезу Гольдбаха: каждое четное n представляется в виде суммы двух простых чисел. Рекурсия* Теория Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе. В рекурсивной процедуре или функции обязательно должно содержаться условие окончания рекурсии. При выполнении рекурсии, когда подпрограмма доходит до рекурсивного вызова, процесс приостанавливается и новый процесс запускается с начала , но уже на новом уровне. Прерванный же процесс запоминается. Новый процесс тоже может n n n a a a 1 1 1 102 быть приостановлен и т.д. Образуется последовательность прерванных процессов. Последовательность рекурсивных обращений должна обязательно выходить на определенное значение. При каждом очередном входе в подпрограмму ее локальные параметры и адреса возврата размещаются в специальной области памяти – стеке. После выхода на определенной значение выполняется обратный ход- цепочка вычислений по обратному маршруту, сохраненному с стеке. Пример 9. Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=n*(n-1)!. Но как вычислить (n-1)!? Если бы мы вычислили (n-2)!, то мы сможем вычислить и (n-1)!=(n-1)*(n-2)!. А как вычислить (n-2)!? Если бы... В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Блок-схема этого алгоритма выглядит следующим образом: fact(n) n=0 fact=1 да нет условие ограничивающее рекурсивный процесс fact=fact(n-1)*n Программа соответствующего алгоритма имеет вид: int factorial (int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } } Программа вызова рекурсивной функции вычисления факториала будет иметь вид: 103 Ввод n f=fact(n) Вывод f program recurc1; var n: integer; f: real; function fact(n: integer): real; begin if n=0 then fact:=0 else fact:=fact(n-1)*n; end; begin write( „n=‟); readln(n); f:=fact(n); writeln( „n!=‟, n:5:0); end. Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны. Также часто использование рекурсии приводит к ошибкам, наиболее распространенная из таких ошибок – бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается, пока не кончится свободная память в компьютере. Две наиболее распространенные причины для бесконечной рекурсии: 1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if (n == 0), то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т.д. 2. Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получится бесконечная цепочка. Поэтому при разработке рекурсивной функции необходимо прежде всего оформлять условия завершения рекурсии и думать, почему рекурсия когда-либо завершит работу. Общее требование к задачам с рекурсией: когда вы сдаѐте задачу, использующую рекурсию, вы устно обосновываете, почему рекурсия всегда когда- нибудь закончится. Еще один пример рекурсивной void-функции: viod Rec(int a) { if (a>0) Rec(a-1); cout< Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов. 104 Void-функция Rec вызывается с параметром a = 3. В ней содержится вызов void-функции Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна void-функция и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра void-функции. Количество одновременно выполняемых void-функций называют глубиной рекурсии. Четвертая вызванная void-функция (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к void-функции, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все void- функции. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3. Еще один визуальный образ происходящего представлен на рисунке. Выполнение void-функции Rec с параметром 3 состоит из выполнения void- функции Rec с параметром 2 и печати числа 3. В свою очередь выполнение void- функции Rec с параметром 2 состоит из выполнения void-функции Rec с параметром 1 и печати числа 2. И т. д. 105 Использование рекурсивных подпрограмм – красивый прием с точки зрения программирования. Программа выглядит более компактно. Но у рекурсии есть недостатки: рекурсия выполняется более медленно и глубина рекурсии ограничена. Примеры Пример 1. Даны действительные числа x и ε (x≠0, ε > 0). Вычислить сумму с точностью ε. 0 2 )! 2 ( k k k x Исходные данные: x – вещественный тип, точность eps – вещественный тип. Результат: сумма summa – вещественный тип. Вычисление суммы выполняем в функции sum. Рекуррентная формула, которая используется при вычислении суммы: a k =a k-1 (x 2 )/((2k-1)(2k)). Вызов функции заканчивается при abs(a) =1. Это значение суммируется в основной программе. Тестовый пример: при x=4, eps=0.0001, summa=27.3082 sum(k,x,eps,a,s) abs(a) да нет Ввод eps,x k=1 a=1 s=a summa=sum(k,x,eps,a,s) Вывод summa s namespace Сумма { class Program { static double summ( int k, double x, double eps, ref double a, ref double s) { if ( Math .Abs(a) < eps) return s; else { a = a * x * x / ((2 * k - 1) * 2 * k); s = s + a; return summ(k + 1, x, eps, ref a, ref s); } } 106 static void Main( string [] args) { double summa; double eps = 0.0001f; double x = 4f; int k = 1; double a = 1f; double s = a; summa = summ(k,x,eps, ref a, ref s); Console .WriteLine( "summa={0}" , summa); Console .ReadKey(); } } } Пример 2. Подсчитать количество цифр в заданном натуральном числе. Исходные данные: заданное число N – целый тип. Результат: количество цифр k – целый тип. В рекурсивной функции заданное число делится на 10, для уменьшения количества цифр. Деление прекращается, когда результатом деления будет ноль. Это граничное условие для рекурсии. Тестовый пример: при N=5674, k=4. kol(n) n=0 kol=1 kol=kol(n-1)+1 n=n div 10 Ввод N k=kol((N) Вывод k да нет Приведем пример с рекурсивной процедурой. Пример 3. Вычислить сумму n членов ряда: n i i 1 1 Исходные данные: количество слагаемых n – целый тип. Результат: сумма ряда summa – целый тип. Тестовый пример: при n=5 summa=2.2833 107 sumrec(n,sum) n=1 sum=sum+1/n sumrec(n-1,sum) sum=1+sum Ввод n summa=0 sumrec(n,summa) Вывод summa нет да namespace Рекурсия { class Program { static void sumrec( int n, ref double sum) { if (n==1) sum=1+sum; else {sum=sum+1.0/n; sumrec(n-1, ref sum); } } static void Main( string [] args) { int n; double summa = 0; Console .WriteLine( "n" ); n = Convert .ToInt32( Console .ReadLine()); sumrec(n, ref summa); Console .WriteLine( "summa={0}" , summa); Console .ReadKey(); } } } Задание Написать и отладить программу для примера 2. Контрольные вопросы 1. Какая подпрограмма называется рекурсивной. 2. Почему в рекурсивной подпрограмме отсутствуют операторы цикла. 3. Может ли в рекурсивной подпрограмме отсутствовать развилка. 4. Почему в Примере 10 отсутствует операция k=k+1. 5. Как будет работать рекурсивная подпрограмма в Примере 10 при eps=0.1 и x=1. 6. Как будет работать рекурсивная подпрограмма в Примере 11 при k=333. 7. В Примере 12 укажите параметры по ссылке и параметры по значению в процедуре sumrec. 108 Индивидуальные задания 1. Найти сумму цифр заданного натурального числа. 2. Написать программу вычисления целой степени любого вещественного числа. 3. Составить программу для нахождения числа, которое образуется из данного натурального числа при записи его цифр в обратном порядке 4. Даны неотрицательные целые числа n, m; вычислить A(n,m), где 0 m 0, n если 1)), - m A(, 1, - A(n 0, m 0, n если 1,1), - A(n 0, n если , 1 ) , ( m m n A 5. Создать программу вычисляющую k a Для этого надо вычислить элементы числовой последовательности: , 2 , 1 , 1 : 1 1 1 0 i x k a x k k x a x k i i i Найти первое значение x n , для которого |x n k -a|<10 -4 6. Создать логическую функцию, которая возвращает True, если ее аргумент - простое число. 7. Даны действительные числа x и ε (x≠0, ε > 0). Вычислить с точностью ε и указать количество учтенных слагаемых ) 1 ( 2 0 2 2 ) )! 1 (( ) 1 ( k k k x k Вычисление выражения под знаком суммы выполнить через рекурсию. 8. Даны действительные числа x и ε (x≠0, ε > 0). Вычислить с точностью ε и указать количество учтенных слагаемых 0 1 2 1 )! 1 2 ( )! 1 2 ( ) 1 ( k k k k k x Вычисление выражения под знаком суммы выполнить через рекурсию. 9. Дано действительное число ε (ε > 0). Последовательность a1, a2, … образована по следующему закону: 1 1 1 3 1 1 2 1 1 n a n С помощью рекурсии найти первый член a n (n≥2), для которого выполнено условие: |a n – a n-1 |< ε. 109 10. Дано действительное число ε (ε > 0). Последовательность a1, a2, … образована по следующему закону: )! 1 ( ) 1 ( 1 ! 3 1 1 ! 2 1 1 n a n n С помощью рекурсии найти первый член a n (n≥2), для которого выполнено условие: |a n – a n-1 |< ε. 11. Даны действительные числа x и ε (ε > 0). Последовательность a1, a2, … образована по следующему закону: a1= x; далее, для n=2, 3, … выполнено: 2 1 1 4 2 n n n a x a a С помощью рекурсии найти первый член a n (n≥2), для которого выполнено условие: |a n – a n-1 |< ε (ограничиться рассмотрением первых 10 4 членов). 12. Даны действительные числа x и ε (ε > 0). Последовательность a 1 , a 2 , … образована по следующему закону: a 1 = x; далее, для n=2, 3, … выполнено: 1 2 4 1 2 1 x a a n n С помощью рекурсии найти первый член a n (n≥2), для которого выполнено условие: |a n – a n-1 |< ε (ограничиться рассмотрением первых 10 4 членов). |