3. Рекурсивные функции и процедуры для обсуждения

Три первые функции представляются учащимся на доске или в виде раздаточного материала. Необходимо определить, что выполняет каждая из них.

' Обсуждение

графич

' При изображении схемы па доске целесоображч щ

щий п рямоуголы шк с псе стирать. Это же касается завершения ртСчггы функции Fc другими фактическими параметрами. — Прим. ред.

16

2008 Nt 5 информатика

<.Vr,i.\Miwc п|ЧМ1сдуры и функция Аккерлина p.U]\»- ООюлначнм .чдапное ,и\'ятичи<ч' число — п. Для его «тыкаются п 1ччч|ессе обсуждения (для их записи к периода в/>-нчную систему счисления требуется опре-

лоске кы.!ыв.1е1\-я один hj учеников).

После обсуждения целесообра.шо предложить уча­щимся решить рассмотренные ладами на комт-мтедч*. 1.

Function Кы: 1o:i.t: г.*. *: '......

Begin

If л •. '. .* Then 4 : Else mj Div 101

End

Or.'jvv;. функция вычисляет количество цифр в .ia-данном натурньнач числе.J.

Fc.vh число — параметр функции меньше К\ то ко­личество цифр в нем равно 1. иначе значение функции равно сумме единицы и 4itc.\a, полученного путем "от­брасывания" последней цифры числа-параметра. \'ка-лшное Ч1кло оулет при каждо.ч< вы.*ове функции умень­шаться в 10 раз до тел пор, пока не "с|\1оотает' с\».юв.»я часть рекурсивного описания функции К. 2.

Function Ftk: byte): ler.^ir.t; Begin

If ,\ '.! Or ,4 - ^ Then :-' :- '. Else

End;

Onpcrv. Функция вычисляет jir-й член тчлелою-ольностн Фп(х<н.1ччи. первые дв;1 члена которой рав-JM 1. каждый последующий есть сумма двух преды-■л щих (1, 1. 3. 5. S.. ^ч 3.

Function iijc: byte): ior.girit; Begin

If ■; = 1 Than S := aikj Else г := a;k; - S(k -1) End,

Ontvm. функция оп]?еле.и1ет сумму злементов .«-■..итого числового массим ,i, элементами котортм яв-\ яются целые числа. KoMMCutr.jpuu

Парлмет]! функции: к — количество элементов мас­сива, сумма которых рассчитывается при каждом вы-.мве фх-нкиии. Когда к - 1. то значение функции равно единственному элементу такого массива, иначе — сум­ме последнею элемента и значения этой же функции для массива без учета последнего элеменга.

От редакции. Б приведенном виде функция может рыть

. именем * Для создания функции, которая .может -обрабатывать" люоые массивы одною тим, следует обрабатываемы» массив сделать пярд-четром фикции.

4. Процедура вывода цифр р-,,чною _П!чиставлення .«данного десятичного натурального 4ncv;» (2 < р < 9\

НлмЗхадимо встюмнить, как происходит перевод це-н у^еТ^Ч"^{ЫХ Ч}"^С" " ^{СИСтему} °"^«ии* •: АРУ™-« *-■-

деление счт;>тк.1 от деления нд /> числа п и ;1;ггем пр<\ме-жут^тых частных до тех нор, пока не получится част­ное, меньшее р. \\о если ироцедур\', 1Чч.*спсчивлюи|ую ощч'деление и вывод остатков (имя величины — гг'гггД о*|ч1рл\11ть п нидс:

Procedure Frorr.'-, t."i: ':.-г ~i'>■.*■......

V»r remin: by

Beyin

■; On r t- яел нем ос таток j ic-rr.u. :« a mod p;

If End,

премежутечн л >- p Tbttn F

— то цифры будут выведены, нлчинлй ^ «икледнен. Для получения требуемого релультэта необходимо опреде­ление и вывод остатков проводить после рекурсинного

Procedure Frcz:!Zia: ■ --V*r remin: byte;

{Если нужне, вызываем процедур;-

лля промежуточного частного}

If а >= с Then Frerr.iOU dxv p, p);

:Спсе~еляем остаток д.~я текуяшх

значений параметрсн npcuezypt;}

remin := a mod p;

{Вывслкм его}

write(rem.in) End;

От редакции. Последний вариант реклреивнои iTpoqeA^TMJ н.1-швл(.*т\:я "Фop.^AД с выпечненкем демсткий гкхле pf кл*р>:нвного вызова (или с выполненном действий на рекурсивном возврате)". Возможны также фор.«*л с выпо.чнен»«^« действий до рекурсивного вызова (или с выполнением действии на ■,ч-курсмвно.м спуске) м <}ч>рма с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий кяк на рекурсивном спуске, так и на рекурсивном возврате) — ел*. 5длJ^lиor:^м^^л■wi Л.М. Программирование: типовые .идачи. алгоритмы, методы. М- БИНОМ. Лаборатория днлний, *сХ>7. Схемы этих трех вариантов и примеры их применения приведены в радделе 5.

5. Вывлл всех делителей натл^тй-хьною hjk^i.

Разбор

Снлчя-u рассматтяимется и обсуждается

Var г., d: longint;

BEGIN

Ftor d : = 1 To r. d iv 2 Do

If n div ^ = 0 Then «-vr--- -write(n)

В ней находятся и выводятся все делители числа ?:. Например, для м = 30 t4\\vr Rsv^^-v ^i'.-'- i ^{л ;} ^ ;^ 10,15, .4).

2008 № 5 ИНФОРМАТИКА

МАТЕРИАЛЫ К УРОКУ

17

Далее надо заметить, что для того чтобы найти дели­тели числа п, достаточно обнаружить делители, не пре­вышающие vtt , — все остальные делители получаются в результате деления п на найденные делители.

Фрагмент программы, учитывающий это обстоя­тельство:

Рог d := 1 То Trunc(Sqrt(n)) - 1 Do If n mod d = 0 Then write(d, ' ',

n div d, ' '); If Sqr(Trunc(Sqrt(n))) = n then «rite

(Trunc(Sqrt(n)l);

Последний оператор используется для того, чтобы в случае, когда п — точный квадрат, делитель, равный V п , не выводился дважды. В результате, когда п = 100, будут выведены числа:

1,100,2,50,4,25, 5,20,10.

А как сделать так, чтобы делители были напечатаны в порядке возрастания?

Ответ — надо использовать рекурсию. Процедура, решающая рассматриваемую задачу, имеет вид: Procedure Dived(n, d: longint); Var dd: longint; {dd — делитель, 'симметричный' найденному делителю} Begin

If n mod d = 0 Then {Встретился делитель числа п} Begin

{Выводим ето]

write (d, ' ');

{Запоминаем 'симметричный' делитель}

dd := n div d;

If d <> dd Then

Begin

{Переходим к проверке следующего числа d} Dived(n, d + 1);

{После 'возврата' из процедуры Dived печатаем делитель dd} write(dd, ' ') End End

Else {n mod d о 0} {Переходим к проверке следующего числа d}

Dived (n, d + 1) End;

Вызов процедуры из основной программы осущест­вляется следующим образом:

Dived (п, 1);

От редакции. Здесь используется форма рекурсивной процедуры с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

6. Процедура получения и вывода на экран всех ва­риантов разложения заданного натурального числа п на множители (без повторений).

Разбор задачи

Решение будем получать в строковом виде, аналогич­ном следующему (для п - 12): 2*2*3 2*6

Можем рассуждать так. Проверим все числа, которые могут быть множителями числа п, начиная с двойки. Если среди них окажется множитель, то учтем его в за­писи разложения (как — опишем ниже), а затем решим задачу разложения на множители числа, равного част­ному от деления п на этот множитель. Итак, мы вышли на использование рекурсии.

Параметрами создаваемой рекурсивной процедуры (ее имя — К) будут:

к — число, разлагаемое на множители (не только за­данное);

first — первый возможный множитель числа к;

s — величина строкового типа, представляющая собой запись разложения, полученного до вызова процедуры R,

Искать возможные множители можно не до целой части от к/2, з до целой части квадратного корня из к (см. обсуждение предыдущей задачи).

Что делается в процедуре R?

Необходимо проверить, являются ли множителями

числа к числа т, равные first, first + 1,.., v& (p/it —

целая часть квадратного корня из к). Если множитель (очередной) встретился, то необходимо:

1) его строковое представление sm "добавить" к уже полученной ранее залиси 5 с учетом символа "*' — полу­ченная величина (j2) будет передана в качестве парамет­ра при очередном рекурсивном вызове процедуры R;

2) вызвать процедуру R с параметрами к div m, m, s2.

После проверки всех чисел т необходимо учесть в за­писи разложения также число к и вывести полученный результат на экран.

Процедура R, решающая задачу:

Procedure R(k, first: longint; s: string); Var m: word;

sm, s2: string; {sm - строковое представление

очередного множителя} Begin

For m := first to Trunc(Sqrt(k)) Do {Если m - множитель числа к} If k mod m = 0 Then Begin (to: - получаем строковое представление m,}

Str(m, sm);

{- добавляем его к ранее полученной

записи разложения} s2 := s + sm + '*' {- вызываем (рекурсивно) процедуру R

с новыми параметрами} R(k div m, m, s2) End;

18

\\\w рч<оомотренич iv^vex i»o'«mo*hnx- множителей читывдем в разложении MKtf чм _х ■ r<k, s2):

w.'it«4nts> End.

Кы.Ч-* рЛЦХК'чП-.ШНОН процедуры IU ОСНОВНОЙ Ч.1С1Н '.ЦЧЧ^МММЫ ДОЛЧчСН ВЫГЛ«ДеГ1> СЛОДуКЧИНМ OOp.UOXl ;_i:ii ^₍ "1;

После ООСуЖДСННЧ П1ХЧ']\1Л\МЫ ЦелССОООр,1.1НО 1ЦЧ'Л ЛОЖИТЬ уч;ПЦНМСЯ проследить noC.Ve.VOlurCAMUVl'b [4^V

курсивных ны.ювов процедуры К.

От редакции. В приведенном инле п(ччюлуры тчлоднее рлможение будог niVACr.in.44Tt. оосой строковое чредстлялемнс числ.1 ч (6с-1 множителя, равного П. например, дли случлч

s :- s ♦ s-\-vriteln(s) End

«) » vVH^NWK⁴M Ч.1СТН П;Ч^ГТ\»Л\Ч1Ы (К^Ш^Ч¹ l.U.44WHv4'!^ JVLvVO^C-M1K' ПЛ\уЧНТЬГ.1К

writeinll,

7. Функция Akkoj\m.ih;i

Учитель сл^цлет. что функцич Акксрм.шл длч мо-

ОТрНЦЛТСЛЬНЫХ ЧИССЛ '*! It П ОЦ|Ч'ЛСЛЯ01\'М СЛСДуЮШИЛ1

i v! + 1. при ': =■ О А(п.т) = i А(п - 1,1). при и ж 0, т = О

[А(п -1. АС". '•■' - 01, при п> 0. т i 0

Соответствующая рекурсивная функция Function Akktn, m: byte): worci; Begin

If :-. С Then Akk := m ♦ 1 Else

If in. ^^ 0) And (m » 0)

Then Akk :- A k k t:' Else

If (n > 0) And (m >- 0) then

Akk := Akk(n - 1, Akkln, m - D) End;

Or редакции

1. Функцию Аккормани на схч.1 функции и ,ч_дш, ,,., «. a

к-п- "дв.и*сды рокурсишюн", т.к. 'imw ои|ч-дг.и-ны 4O1VJ (JW»

-. Рдсчпмничсиия функции Аккорм.т.1длжо при тчч>лыпн\ личемнмх шцммет^н и и ш Tjietiyt'r .ничитсльных объемов 1U1MMTU для риамечцениа функции при рекурсивных вы.*ой!»х (см. [хидсл 1). Можно предложить учаи1пл»ом нроиернчч. .nv утворжденпс. напрнмор, при и - -I, m - 5.