Ф Е Д Е РА Л Ь Н О Е
АГ Е Н Т СТ ВО
ПО
О Б Р А ЗО В А Н И Ю
В О РО НЕ Ж С К И Й ГО СУ Д А РС Т В Е ННЫ Й У НИ В Е РС И Т Е Т
Я з ы к программирования Pascal П р оцед у р ы и ф у н к ци и . Р ек у р си я
П р актикум С п ециа л ь но с ть 010101 (010100) М а тем а тика
ВО РО Н Е Ж 2005
2
У твержденонаучно-методическим советом М атематическогофакультета – ( 28 февраля 2005 года, протокол№ 6 )
С оставители: В асильевВ .В ., Х ливненкоЛ .В .
П рактикум подготовлен на кафедрематематическогомоделирования математическогофакультета В оронежскогогосударственногоуниверситета. Рекомендуется для студентоввечернегоотделения математическогофакультета В оронежскогогосударственногоуниверситета.
3
1. М ето д п о с л едо ва тел ь но й дета л иза ции. Ф у нкции П ри реш ении объемны х з адач, приводя щ их к больш им программам, приходится структурироватьпрограммы , тоестьраз биватьна части - блоки. П од а л го ритм ичес ким бл о ко м обы чнопонимаю т частьалгоритма, имею щ ую определенноеназ начениес одним входом и одним вы ходом (к о нстр ук ц и я , напо м и наю щ ая “чер ны й” я щ и к ). Д ля алгоритмическогоблока четко определяю тся исходны е(вхо дны е) данны еи рез ультаты (вы хо дны е данны е), реакция на неправильны еданны е(ано м али и данны х) и работа вособы х случая х. А лгоритмический блок, вы з ы ваемы й из другогоблока, наз ы вается подблоком или п о дп ро гра м м о й. С труктурированием ето до м п о с л едо ва тел ь но й дета л иза ции з аклю чается впош аговой раз работкеалгоритма. В началепиш ется общ ая крупноблочная схема реш ения з адачи. П отом кажды й крупны й блок раз бивается на болеемелкиеи т.д. В итогемы получаем иерархически упоря доченны й набор э лементарны х блоков, представимы х через имею щ иеся процедуры и функции. П ри нис хо дящ ем с п о с о бе написания и отладки программы (м ето де пр о гр ам м и р о вани я свер ху вни з) пиш ется крупноблочная схема программы . На начальном э тапекажды й блок з аменя ется за гл у ш ко й (о дно и м енны й бло к , и м и ти р ую щ и й пр ави льны е р езультаты пр и к о нк р етны х и схо дны х данны х, ли бо пусто й бло к ). В процесседетализ ации программы з аглуш ки з аменя ю тся работаю щ ими блоками. П ри во с хо дящ ем с п о с о бе написания и отладки программы (м ето де пр о гр ам м и р о вани я сни зу ввер х) детальнопрорабаты ваю тся э лементарны еблоки, которы ез атем состы кую тся вболеесложны еблоки. В осходя щ ая раз работка программ использ уется при создании однотипны х программ. Е сли В ы располагаетеколлекцией отлаженны х работаю щ их блоков, точастьиз них может подойти для новы х программ. Новую з адачулучш евначалераз битьна болеепросты ез адачи (пр о вести дек о м по зи ц и ю задачи ), а з атем при желании посмотретьсвою коллекцию алгоритмических блоковреш ения просты х з адач. В э том случаевероя тностьупуститьиз видуважны едетали несколькониже, чем если пы таться собратьреш ениеновой з адачи из того, чтоВ ы делали раньш е. Я з ы ки программирования , располагаю щ иесредствами структурирования программ, наз ы ваю тся п ро цеду рно -о риентиро ва нным и. Turbo Pascal я вляется процедурно-ориентированны м я з ы ком. О сновной файлпрограммы содержит главны й блок - основную программу. К основной программеможноподклю чатьблоки, расположенны евдругих файлах - м о ду л и. И з основной программы можновы з ы ватьвложенны евнееи вподклю ченны емодули блоки, реализ ованны евП аскалеввидеп ро цеду р и ф у нкций. П роцедуры и функции я вляю тся подпрограммами. Нам з накомы стандартны епроцедуры (напр и м ер , read(), write()) и функции
4
(напр и м ер , abs(), exp()). Научимся создаватьсобственны е(по льзо вательск и е) процедуры и функции. Ф у нкции могут вы числяться на основенескольких входны х данны х, но всегда имею т единственны й рез ультат, определенноговз аголовкефункции типа. Т ип з начения , возвращ аемогофункцией, может бы тьлю бы м поря дковы м, вещ ественны м, строковы м типом String (безук азани я дли ны стр о к и !) и типом Point (ссы ло чны м ти по м ). Рез ультат возвращ ается через имя функции. П оэтомудопустимовклю чать функции ввы ражения , условия и процедуры вы вода. Д ля возвращ ения з начения из функции ввы з ы ваю щ ую программучастонеобходимоналичиеоператора присваивания . В общ ем видеописаниефункции вы глядит так: Function Имя (С п исок ф ор м а л ьны х п а р а м етр ов): Тип результата; Label Описание локальных меток; Const Описание локальных констант; Type Описание локальных типов; Var Описание локальных переменных; Procedure Описание внутренних процедур; Function Описание внутренних функций; Begin Операторы, среди которых должен быть хотя бы один, который присваивает имени функции значение результата End; П а ра м етро м ф у нкции наз ы вается входноеданное, передаваемоевподпрограммуиз основной программы (и ли и зпо дпр о гр ам м ы , о бр ащ аю щ ейся к данно й функ ц и и ). Ф о рм а л ь ный п а ра м етр ф у нкции - переменная , вы полня ю щ ая роль аргумента функции. Ф а ктичес кий п а ра м етр ф у нкции - вы ражение, переменная или константа типа формальногопараметра функции, з начениефактическогопараметра передается вподпрограммувкачествеаргумента функции. О бл а с ть ю видим о с ти (действи я ) данны х наз ы ваю т тучастьпрограммы , гдеони могут бы тьиспольз ованы . М етки, константы , типы , переменны е наз ы ваю тся л о ка л ь ным и, если они использ ую тся тольковрамках одной функции или процедуры . Е сли метки, константы , типы , переменны едействую т врамках нескольких процедур или функций, тоони наз ы ваю тся гл о ба л ь ным и. П оня тия “локальны е” и “глобальны е” весьма условны , и их нужнотрактоватьпоотнош ению к конкретной процедуреили функции. Например, для некоторой функции описанны евней переменны ебудут локальны ми, а для ее внутренней функции тежепеременны ебудут глобальны ми. П ри определении области видимости переменны х следует помнить, что: - внутри процедуры и функции действую т всеидентификаторы , которы е определены вэ той процедуреили функции; - внутри процедуры и функции действую т всеидентификаторы внеш них
5
блоков, вкоторы евложена данная процедура или функция (если и м ена и денти фи к ато р о ви звнешнего о к р уж ени я о тли чны о т и м ен, о бъя вленны х внутр и пр о ц едур ы и ли функ ц и и ); - локальны еидентификаторы вовнеш нем окружении недействую т; - вслучаесовпадения имен локальны х и глобальны х идентификаторов внутри функции или процедуры действиеглобальны х идентификаторовотменя ется и использ ую тся одноименны елокальны еидентификаторы . Напиш ем программу, вкоторой создается и использ уется новая функция . За да ча 1. Найти всечисла М ерсенна типа integer. ♣ Ф ранцуз ский математик М .М ер сен н (1588-1648) з аметил, чтомногие просты ечисла имею т вид 2P-1, гдеp я вляется тожепросты м числом. В сечисла указ анноговида наз ы ваю тся числами М ерсенна. Невсечисла М ерсенна я вляю тся просты ми. Например, до1903 г. считалось, чточисло267-1- простое. На самом деле, э точислопредставляет собой произ ведениедвух просты х чисел 193 707 721 и 761 838 257 287. Нея сно, бесконечноли множествочиселМ ерсенна. p+1-ечислоуказ анноговида можновы раз итьчерез p-ечислоследую щ им образ ом 2P+1-1=2(2P-1)+1. П еременная p принимает з начения идущ их подря д натуральны х чисел(2,3,4,...). П ереход к вы числению очередногочисла будем делатьпослепроверки на непереполнениетипа integer. На э кран будем вы водить толькотечисла вида 2P-1, для которы х p - простоечисло. Ч тобы найти числа М ерсенна, нам потребуется функция , проверя ю щ ая , я вляется ли числоp просты м. П роверим, имеет ли числоp ( p ≥ 2 ) делители в интервале [2, p div 2] . Д елители будем искатьтолькодля нечетны х чисел. Напомним, чтофункция odd() возвращ ает з начениеи с ти на, если аргумент я вляется нечетны м числом. В основной программепеременная n использ уется для перебора показ ателей степеней двойки. Mers хранит очередноечисловида 2n-1. П еременная логическоготипа p принимает з начениеtrue при вы ходеочередногочисла вида 2n-1 из диапаз она integer. В подпрограммеаргументом служит переменная p целоготипа. П еременная n предназ начена для перебора делителей числа p. ♠ Program Mersenn; Uses crt; Var n,mers:integer; p:boolean; Function prost(p:integer):boolean; Var n:integer; Begin if p=2 then prost:=true else if not odd(p) then prost:=false else
6
begin n:=p div 2; if not odd(n) then n:=n+1; while p mod n <> 0 do n:=n-2; prost:=n=1 end End; {prost} Begin Textbackground(7); Textcolor(blue); Clrscr; writeln('Ч исл а М ер сенна :'); n:=2; mers:=3; p:=false; repeat if prost(n) then writeln(mers); n:=n+1;+ if mers<=maxint div 2 then mers:=mers*2 else p:=true; if mers<maxint then mers:=mers+1 else p:=true until p; readkey End.{Mersenn} В рез ультатеработы программы должнобы тьнапечатанош естьчисел М ерсенна: 3, 7, 31, 127, 2047, 8191. Следую щ еечисло131071 вы ходит з а пределы типа integer. Л окальны еданны есоздаю тся при вы з овепроцедуры или функции и сущ ествую т тольковпериод ееисполнения . В началевы полнения процедуры или функции вы деляется памя тьпод локальны еданны е. К огда вы полнениепроцедуры или функции з аканчивается , топамя ть, отведенная под хранениелокальны х данны х, освобождается . Т аким образ ом, врем я жизни л о ка л ь ных да нных совпадает современем работы процедуры или функции, вкоторой они определены . П оэтомуз начения всех локальны х данны х теря ю тся вместес освобождением памя ти поз аверш ении работы процедуры или функции. За да ча 2. В книгеn страниц (n - вхо дно е данно е). Составьтепрограмму, которая будет находить, сколькоцифр понадобится для того, чтобы з анумероватьвсестраницы данной книги. ♣ Ч тобы з анумероватьвсеоднозначны енатуральны ечисла, нужно9 цифр. Ч тобы з анумероватьвседвуз начны ечисла, нужно90*2 цифр. Д ля трехз начны х чиселпонадобится 900*3 цифр и т.д. Ч тобы з анумероватьвсеkз начны ечисла, нужно900 1 2...300 * k цифр. k −1
К оличестводвуз начны х чиселнаходится как раз ностьнаибольш егои наименьш егодвуз начногочисла плю с один: 90 = 99 - 10 + 1. К оличествотрехз начны х чиселнаходится как раз ностьнаибольш егои наименьш еготрехз начногочисла плю с один: 900 = 999 - 100 + 1. К оличествоk-з начны х чиселнаходит-
7
ся как раз ностьнаибольш егои наименьш егоk-з начногочисла плю с один: s = max - min + 1. Напиш ем функцию str(n), которая будет вы числятьколичествоцифр вкнигеиз n страниц. Д ля э тогоопределим количествоцифр k вчислеn, написав функцию kol_cifr(n) . И скомоез начениеstr(n) найдем как суммуцифр, необходимы х для нумерации всех i-з начны х чисел(i=1,2,...,k-1), и цифр, необходимы х для нумерации оставш ихся k-з начны х чисел. ♠ Program Nomer; Uses crt; Var k:integer; function kol_cifr(n:integer):integer; {кол ичество циф р в числ е n} var s:integer; begin s:=0; repeat s:=s+1; n:=n div 10 until n=0; kol_cifr:=s; end; {kol_cifr} function str(n:integer):integer; {кол ичество циф р в ном ер а х книги из n стр а ниц} var i, min, max, s:integer; begin s:=0; min:=1; max:=9; for i:=1 to kol_cifr(n)-1 do begin s:=s+(max-min+1)*i; min:=min*10; max:=min*10-1 end; str:=s+(n-min+1)*kol_cifr(n) end; {str} Begin Textbackground(7); Textcolor(blue); Clrscr; repeat write('Введите кол ичество стр а ниц в книге:'); readln(k) until k>0; writeln('Дл я нум ер а ции всех стр а ниц книги нужно ',str(k),' циф р '); readkey End.{Nomer} В программек з адаче2 при вы числении функции str() идет обращ ениек функции kol_cifr(). Ф ункция kol_cifr() я вляется подчиненной функции str(), хотя функция kol_cifr() нея вляется внутренней функцией для str(). Бло к и по хо ж и на “чер ны е я щ и к и ” с о дно сто р о нне зер к ально й к р ы шк о й: и з ни х ви дны (до ступны ) бло к и и данны е, о пи санны е вы ше!
2. П ро цеду ры. С п о с о бы п ереда чи п а ра м етро в
8
Е сли подпрограмма должна возвращ атьвосновную программунесколько з начений, либовозвращ атьрез ультаты структурированноготипа, либовообщ е неиметьпараметров, тотакую подпрограммуоформляю т ввидеп ро цеду ры. В общ ем видеописаниепроцедуры имеет следую щ ий вид: Procedure Имя (Список формальных параметров); Label Описание локальных меток; Const Описание локальных констант; Type Описание локальных типов; Var Описание локальных переменных; Procedure Описание внутренних процедур; Function Описание внутренних функций; Begin Операторы End; П а ра м етро м п ро цеду ры наз ы вается переменная (и но гда к о нстанта и ли вы р аж ени е), которая содержит входны еи/или вы ходны еданны епроцедуры . П араметры , указ ы ваемы евз аголовкепроцедуры при ееописании, наз ы ваю тся ф о рм а л ь ным и п а ра м етра м и. П араметры , указ ы ваемы епри вы з ове процедуры , наз ы ваю тся ф а ктичес ким и п а ра м етра м и. С писок формальны х параметровможет вклю чатьи рез ультаты , передаваемы еиз подпрограммы восновную программу. П еред параметрами, возвращ аемы ми восновную программу, пиш ется служебноесловоvar. П ри обращ ении к процедурез начения фактических параметровприсваиваю тся соответствую щ им формальны м параметрам. П оз аверш ению работы процедуры з начения формальны х параметров, объя вленны х рез ультатами, доступны ввы з ы ваю щ ем блоке. С оответствиеопределяется поря дком следования формальны х и фактических параметров. Ф актическиепараметры необходиморасполагатьвтом жепоря дкеследования , вкотором расположены соответствую щ иеим формальны епараметры . За корректностьпередачи данны х вподпрограммуи обратноотвечает программист. К омпилятор отслеживает лиш ьочевидны еслучаи несоответствия формальны х и фактических параметров- раз ноеколичествопараметрови несоответствиетипов. Ф ормальны епараметры могут бы тьтолькопеременны ми. Ф актические параметры , з начения которы х передаю тся вподпрограмму, могут бы тьпеременны ми, константами и вы ражения ми (ти пы фо р м альны х и фак ти ческ и х пар ам етр о вдо лж ны со впадать!). Ф ак ти ческ и е пар ам етр ы м о гут бы ть и м енам и др уги х функ ц и й! Ф актическиепараметры , служащ иебуфером для вы ходны х данны х подпрограммы , должны бы тьпеременны ми. Им ена фак ти ческ и х и фо р м альны х пар ам етр о вм о гут не со впадать! Рассмотрим з адачу, приводя щ ую к программес процедурой. За да ча 1. А ня нарвала я блок и поровнураз дала своим сестрам О ле, М аш еи Свете, а чтоосталось, съела. О ля свои я блоки поделила междутремя сестрами, а чтоосталось, съела. Т ожесамоесделали М аш а и Света. Сколькоя б-
9
лок съела каждая сестра? ♣ К оличествоя блок, собранны х А ней, обозначим через n. Б удем считать, чтодевочки при дележенераз рез али я блоки на части. К аждую из четы рех раз дач можновы раз итьпроцедурой, имею щ ей четы репараметра- количествоя блок уА ни, О ли, М аш и и С веты . В сечеты репараметра служат одновременнои входны ми и вы ходны ми данны ми для процедуры . П ри обращ ении к процедуре параметры храня т количества я блок доочередной раз дачи. П ри вы ходеиз процедуры фактическим параметрам присваиваю тся количества я блок послеочередной раз дачи. П ервы м вспискеформальны х параметровстоит количество я блок утой сестры , которая ими делится . ♠ Program Sestri; Uses crt; Var a,o,m,s:integer; procedure delezh(var w,x,y,z:integer); begin x:=x+w div 3;y:=y+w div 3; z:=z+w div 3; w:=w mod 3 end;{delezh} Begin Textbackground(7); Textcolor(blue); Clrscr; write('Сколько яблок нарвала Аня?');readln(a); o:=0; m:=0; s:=0; delezh(a,o,m,s); delezh(o,a,m,s); delezh(m,a,o,s); delezh(s,a,o,m); writeln('П осл е дел ежа у Ани - ',a,', у Ол и - ',o,', у М а ши - ',m,', у С веты -',s,' ябл ока '); readkey End.{Sestri} Область ви ди м о сти фо р м альны х пар ам етр о втак ая ж е, к ак у ло к альны х данны х! Рассмотрим с п о с о бы п ереда чи п а ра м етро в, приня ты евП аскале. П о м еха н и зм у пер ед а чи па р а м етр овпроцедуры /функции раз личаю т передачупо з начению и передачупоссы лке(по адр есу). П ри п ереда че п а ра м етро в п о зна чению при вы з овепроцедуры / функции вы полня ется копированиез начений фактических параметроввпамя ть, вы деляемую для формальны х параметров. П ри п ереда че п а ра м етро в п о с с ыл ке при вы з овепроцедуры / функции вы полня ется копированиеадресов( но не значени й!) фактических параметровввы деляемую для них памя ть. П о вза и м од ействи ю вы зы ва ющ его и вы зы ва ем ого блок а параметры могут передаваться толькокак входны е, толькокак вы ходны е, одновременно как входны еи вы ходны е.
10
Т еоретически возможны ш естьспособовпередачи параметров. 1. П ередача входногопараметра поз начению . 2. П ередача входногопараметра поссы лке. 3. П ередача вы ходногопараметра поз начению . 4. П ередача вы ходногопараметра поссы лке. 5. П ередача входногои вы ходногопараметра поз начению . 6. П ередача входногои вы ходногопараметра поссы лке. В П аскалереализ ованы три из ш ести возможны х способовпередачи параметровпроцедуры /функции. 1. П ереда ча вхо дно го п а ра м етра п о зна чению . П ри вы з овепроцедуры / функции вы полня ется копированиез начений фактических параметроввпамя ть, вы деляемую для формальны х параметров. В овремя работы процедуры /функции из менениез начений формальны х параметровневлия ет на содержимоея чеек фактических параметров. П ри з аверш ении работы процедуры /функции памя ть, отведенная для з начений формальны х параметров, очищ ается , и з начения формальны х параметровтеря ю тся . В ходны епараметры , передаваемы епоз начению , наз ы ваю тся п а ра м етра м и-зна чениям и. В з аголовкепроцедуры /функции при описании таких параметровперед их идентификаторами дополнительны еслужебны еслова не ставя тся . Ф актическиепараметры -з начения могут бы тьпеременны ми, константами, вы ражения ми. Недопустимы ми я вляю тся файловы етипы и их произ водны е. 2. П ереда ча вхо дно го п а ра м етра п о с с ыл ке. П ри вы з овепроцедуры / функции вы полня ется копированиеадресовфактических параметровввы деляемую для них памя ть, а такжевы деляется памя тьдля локальны х данны х. В овремя работы процедуры /функции з апрещ еноиз меня тьз начения формальны х параметров. Запрещ енотакжепередаватьпараметры -константы в качествефактических параметровдругим процедурам/функция м. П ри з аверш ении работы процедуры /функции памя ть, отведенная для работы процедуры , очищ ается . В ходны епараметры , передаваемы епоссы лке, наз ы ваю тся п а ра м етра м ико нс та нта м и. В з аголовкепроцедуры /функции при описании параметровконстант перед их идентификаторами ставится служебноесловоconst. Ф актическиепараметры -константы могут бы тьпеременны ми, константами, вы ражения ми. Недопустимы ми я вляю тся файловы етипы и их произ водны е. П араметры -константы обы чноиспольз ую т при передачи больш их структур данны х. П ри э том э кономится оперативная памя тьи обеспечивается целостностьданны х. 3. П ереда ча вхо дно го и выхо дно го п а ра м етра п о с с ыл ке. П ри вы з ове процедуры /функции вы полня ется копированиеадресовфактических параметровввы деляемую для них памя ть, а такжевы деляется памя тьдля локальны х данны х. Запрещ ается использ оватьвкачествевходны х параметровконстанты и вы ражения . В овремя работы процедуры /функции раз реш еноиз ме-
11
ня тьз начения формальны х параметров. П ри э том из менениевы полня ется непосредственновя чейках памя ти фактических параметров. П ри з аверш ении работы процедуры / функции памя ть, отведенная для работы процедуры , очищ ается . П ри э том новы ез начения фактических параметровнетеря ю тся . В ходны е/вы ходны епараметры , передаваемы епоссы лке, наз ы ваю тся п а ра м етра м и-п ерем енным и. В з аголовкепроцедуры /функции при описании параметров-переменны х перед их идентификаторами ставится служебное словоvar. Ф актическиепараметры -переменны емогут бы тьпеременны ми лю боготипа, втом числеи файлового. О дной из распространенны х з адач, приводя щ их к процедурам и функция м, я вляется з адача, свя з анная с операция ми над больш ими числами. Е стьлю ди, которы м нравится получатьточны ез начения математических величин. Например, вXVI в. Р у д ольф Ва н К ойн е(Го лланди я ) вы числилз начение π c точностью до35-гоз нака послез апя той и з авещ алвы сечьэ точисло на своем надгробии. За да ча 2. В ы числитьчислоe c точностью до50-гоз нака послез апя той. ♣ М ногиефункции вы числяю тся вП К поформулам Т ейлора. М атематическиеконстанты могут бы тьнайдены как суммы бесконечны х последовательно-
( −1) +... π 1 1 1 = 1 − + − +...+ стей, вы ражаю щ их данны еконстанты . Например, 4 3 5 7 2n − 1 n −1
x Раз ложим функцию e вря д М аклорена при
x = 1 :e = 1+
1 1 1 1 + + + ...+ + ... 1! 2 ! 3! n!
Е сли переменная , храня щ ая очередной член ря да, будет иметьтип real, то мы несможем достигнутьжелаемой точности, посколькуочередной член ря да будет слиш ком мал(фак ти ческ и , впам я ти будет хр ани ться но ль). Д ействительны ечисла впамя ти П К представлены приближенно. К оличествоточны х цифр числа ограничивается количеством з наков, вы деленны х для представления числа. Нижеприведен текст программы , которая печатает числодеся тичны х з наков, вы деляемы х для представления действительногочисла. Program Tochnost; Uses crt; Const a=1.0; Var n:integer; r:real; Begin Textbackground(7); Textcolor(blue); Clrscr; r:=1.0; n:=0; repeat n:=n+1; r:=r/10 until a=a+r; write('Точность типа real равна 1Е-',n);
12
readkey End.{Tochnost} П олученны й ответ з ависит от типа П К и приблиз ительноравен 10-13. Е сли переменная , храня щ ая очередной член ря да, будет иметьтип real, томы можем получитьчислоe с точностью до13-гоз нака послез апя той. Д ля тогочтобы найти числоe с точностью до50-гоз нака послез апя той, цифры числа e сохраним вмассивеследую щ еготипа: const t=50; type vector = array [0..t] of [0..9]; Заметим, чтодля получения e с больш ей точностью достаточнобудет в программеиз менитьз начениеконстанты t (то чно сть). П ервы й э лемент массива цифр числа e , имею щ ий индекс 0, содержит целую частьчисла e . Д робная частьначинается с э лемента, индекс которогоравен 1. П роведем декомпозицию поставленной з адачи. 1. Начальноез аполнениемассива e (с ц и фр ам и чи сла e ) и массива i (с ц и фр ам и n-го члена р я да). 2. Сложениечисел, цифры которы х храня тся вмассивах e и i, и з аписьрез ультата вмассивe. 3. П олучениеследую щ егочлена ря да вмассивеi. 4. П овторениепунктов2 , 3 додостижения желаемой точности. 5. П ечатьчисла e (ц и фр , хр аня щ и хся вм асси ве e). Раз берем болеедетальнокаждую из перечисленны х вы ш епросты х з адач. 1. П ервы едва слагаемы х впоследовательности, вы ражаю щ ей числоe , равны единице. П ервую единицубудем считатьначальны м з начением, з аписы ваемы м вмассивe. В торую единицуз апиш ем как начальноез начениемассива i (n=1). Д ля начальногоз аполнения массивовсоставим процедуруone(var a:vector), которая э лементумассива a (фо р м альны й пар ам етр ) с индексом 0 (ц елая часть чи сла) присваивает 1, а всеостальны еэ лементы (др о бная часть) з аполня ет нулями. 2. Склады ватьчисла, цифры которы х храня тся вмассивах e и i, будем, использ уя способ сложения “встолбик” . Напиш ем процедуруadd(var e,i: vector). В ведем локальную переменную v_ume (вум е). Найдем суммуs э лементовe[k] и i[k], k = t, t-1,..., 0. П еременной v_ume присвоим частноеот целочисленногоделения s на 10, а e[k] присвоим остаток от такогоделения . П ри k=0 (ц елая часть чи сла) мы неперейдем границу10, потомучтосклады ваю тся члены последовательности, вы ражаю щ ей числоe . 3. Д ля получения n-гочлена ря да достаточноn-1-й член (ц и фр ы к о то р о го хр аня тся вм асси ве i) раз делитьна n. Составим процедуруdivision(var i:vector; n:integer), вкоторой числоиз массива i делится столбиком на числоn. В ведем локальны епеременны еr для остатка и a для делимого. П ервоначальноез начениеr равнонулю . a получается как остаток, увеличенны й в10 раз и сложенны й с очередной цифрой делимогоi[k] (k = 0, 1, ..., t).
13
Ц ифры искомогочастного(но во е значени е i[k]) получаю тся как частны еот целочисленногоделения a на n, новы е з начения r получаю тся как остатки от такогоделения .
С хема алгоритма процедуры ONE ( a: vector )
С хема алгоритма процедуры ADD ( e, i: vector )
Схема алгоритма функции END_ ( i: vector ) Схема алгоритма процедуры DIVISION (a:vector; n:integer)
С хема алгоритма процедуры PRINT (e:vector)
14
4. Б удем считать, чтожелаемая точностьдостигается , когда очередной член ря да оказ ы вается настолькомаленьким, чтоегоцифры , отличны еот нуля, начинаю тся с позиции, имею щ ей номер превосходя щ ей t+1. Т оестьдля новогочлена ря да всеi[k] (k = 0, 1, ..., t) равны нулю . Напиш ем функцию end_(const i:vector):boolean, которая будет проверя ть“малость” очередногочлена ря да. Ф ункция возвращ ает з начения “истина” толькокогда всеi[k] (k = 0, 1, ..., t) равны нулю . В э том случаецикл, входекоторогонакапливается сумма членовря да и находится новы й член ря да, прекращ ается . 5. П роцедура print(const e:vector)вы водит на э кран э лемент e[0] (ц елая часть чи сла e ). Затем вы водится з апя тая и вциклепечатаю тся остальны е э лементы массива e. На стр. 13 представлена блок-схема основной программы и блок-схемы , вы з ы ваемы х восновной программепроцедур и функции. Обр ати те вни м ани е на но вы е элем енты во фо р м лени и бло к -схем ! ♠ Program Epsilon; Uses crt; Const t=50;{кол ичество зна ков п осл е зап ятой в числ е е} Type vector=array [0..t] of 0..9; {тип м а ссива дл я хр а нения t+1 цифр } Var n:integer; {ном ер чл ена р яда } e,i:vector; {м а ссивы дл я хр а нения циф р числ а е и очер едного чл ена р яда } Procedure one (var a:vector); {первоначальное заполнение массива} var k:1..t;{п а р а м етр цикл а } begin a[0]:=1; for k:=1 to t do a[k]:=0 end; {one} Procedure add(var e,i:vector);{сл ожение двух бол ьших чисел } var v_ume:0..1{в_уме}; s:0..19{сумма двух цифр + в_уме}; k:0..t;{параметр цикла} begin v_ume:=0; for k:=t downto 0 do begin s:=e[k]+i[k]+v_ume; e[k]:= s mod 10; v_ume:=s div 10 end; end;{add} Procedure division(var i:vector; n:integer); {нахождение n-го члена ряда} var r{остаток от деления}, k{параметр цикла}, a{делимое}:integer; begin r:=0;
15
for k:=0 to t do begin a:=r*10+i[k]; i[k]:=a div n; r:=a mod n end end;{division} function end_(const i:vector):boolean; {проверка достижения заданной точности} var k:integer;{параметр цикла} begin k:=-1; repeat k:=k+1 until (i[k]<>0) or (k=t); end_:=i[k]=0 end; {end_} procedure print(const e:vector); {печать массива с цифрами числа е} var k:1..t;{параметр цикла} begin write('e=',e[0]:1,','); for k:=1 to t do write(e[k]:1); end; {print} Begin Textbackground(7); Textcolor(blue); Clrscr; one(i); one(e); n:=1; repeat add(e,i); n:=n+1; division(i,n) until end_(i); print(e); readkey End.{Epsilon} В рез ультатеработы программы на э кранепоя вится з апись e = 2,71828182845904523536028747135266249775724709369978 В Паск але до пусти м о и спо льзо вать пр о ц едур ы безпар ам етр о в! В это м случае взаго ло вк е пр о ц едур ы по сле ее и м ени к р углы е ск о бк и не ставя тся . П ознакомимся с о ткрытым и п а ра м етра м и-м а с с ива м и. В процедуру можнопередаватьчерез один параметр массивы раз личногораз мера. В э том случаевз аголовкепроцедуры надоописатьоткры ты й параметр-массив: procedure имя_процедуры ( имя_массива: array of тип_элементов_массива ); Например, впроцедуруsymbol нужнопередаватьмассивы раз ногораз мера, состоя щ иеиз символов. Напиш ем з аголовок процедуры : procedure symbol ( m: array of char ); Д ля определения характеристик переданногофактическогопараметра в процедуремогут бы тьиспольз ованы три стандартны х функции: Low() - всегда возвращ ает 0 (и ндек с пер во го элем ента м асси ва), High() - возвращ ает индекс
16
последнегоэ лемента массива, SizeOf() - возвращ ает раз мер фактическогопараметра - массива. Ф ак ти ческ и е пар ам етр ы -м асси вы до лж ны со сто я ть и зэлем енто во дно го ти па (со впадаю щ его с ти по м элем енто вфо р м ально го пар ам етр ам асси ва) и м о гут бы ть о пи саны к ак м асси вы р азно го р азм ер а. Раз берем з адачу, вкоторой вфункцию требуется передаватьмассивы раз ной длины . За да ча 3. Д ля з аданной вещ ественной матрицы определите, образ ую т ли ееэ лементы упоря доченную последовательностьпри их переборепоспирали, представленной справа. Д ля определения факта упоря доченности части строки (столбца) использ уйтефункции. ♣ Б удем считать, чтоз адана вещ ественная матрица A раз мера mxn. Э лементы матрицы , перебираемы епоуказ анной схеме, могут бы тьупоря дочены понеубы ванию и невозрастанию . Создадим логическиефункции rost и spad, которы ебудут проверя ть, упоря дочен ли передаваемы й им вкачествеаргумента массивпоневозрастанию и понеубы ванию соответственно. А ргументом функций rost и spad будет вспомогательны й массивv, вкоторы й помещ ается частьстроки или столбца очередноговитка спирали. В качествеаргумента функция м rost и spad передается и количествоэ лементовв части строки или столбца. На схемесправа показ ана з акономерностьиз менения индексовпри обходематрицы поспирали. p - номер текущ еговитка спирали. К оличествовитковспирали p_max находится как рез ультат целочисленногоделения на два суммы единицы и меньш егоиз m и n. Л огическиепеременны еf и g использ ую тся для хранения ответовна вопросы : “У поря дочены ли э лементы матрицы , перебираемы епоспирали, понеубы ванию и поневозрастанию ?” П ервоначальнопеременны м f и g присваивается з начениеtrue. О рганиз уем циклпоp от 1 доp_max. П роверим, упоря дочена ли вер хн яя стр ок а p-говитка. Д ля э тогоорганиз уем циклпоj от p-1 доn-p+1 (см . схем у вы ше). В циклеперебираю тся столбцы . Запиш ем верхню ю строку p-говитка вовспомогательны й массивv раз мераr, гдеr = n-2p+3. В овспомогательны й массивз аписы ваю тся э лементы матрицы A [p, j]. Начинатьциклот p-1 нужнодля того, чтобы обеспечитьпроверкуупоря доченности “сты ков” двух витковспирали. О тсю да следует о с о бый с л у ча й: на первом виткеспирали “сты ков” нет, поэтомупри p=1 первую итерацию цикла нужнопропуститьбез действий. П еременная f принимает з начениерез ультата конъю нкции своегопрежнегоз начения и з начения функции rost(v,r). П еременная g принимает з начение
17
рез ультата конъю нкции своегопрежнегоз начения и з начения функции spad(v,r). Е сли оказ ы вается , чтообепеременны еf и g имею т з начениеfalse, тоцикл поp прекращ ается и печатается неудовлетворительны й рез ультат. П роверка упоря доченности пр а вого столбца p-говитка проводится аналогично. Д ля формирования вспомогательногомассива организ уется циклпоj от p доm-p+1, вкотором перебираю тся строки (см . схем у вы ше). В овспомогательны й массивз аписы ваю тся э лементы матрицы A [j,n-p+1]. Е сли на последнем виткеспирали правогостолбца нет (напр и м ер , у м атр и ц р азм ер а 3x5), то вспомогательны й массивбудет содержатьодин э лемент a[p, n-p+1]. Ф ункции rost и spad вэ том случаевозвратя т з начениеtrue, и з начениепеременны х f и g небудет искажено. П ри проверкеупоря доченности н и жн ей стр ок и p-говитка для формирования вспомогательногомассива организ уется циклпоj от n-p+1 доp, вкотором перебираю тся столбцы (см . схем у вы ше). В овспомогательны й массивз аписы ваю тся э лементы матрицы A [m-p+1,j]. О с о бый с л у ча й: на последнем виткеспирали нижней строки нет. В э том случаеформироватьвспомогательны й массиви использ оватьфункции rost и spad для получения новы х з начений f и g нельз я (по дум айте, по чем у?). О собы й случай имеет местона последнем виткеспирали уматриц с нечетны м количеством строк m. П ри проверкеупоря доченности левого столбца p-говитка для формирования вспомогательногомассива организ уется циклпоj от m-p+1 доp+1, вкотором перебираю тся строки (см . схем у вы ше). В овспомогательны й массивз аписы ваю тся э лементы матрицы A [j,p]. О с о бый с л у ча й: на последнем витке спирали левогостолбца нет. В э том случаеформироватьвспомогательны й массиви использ оватьфункции rost и spad для получения новы х з начений f и g нельз я (по дум айте, по чем у?). О собы й случай имеет местона последнем витке спирали уматриц с нечетны м количеством столбцовn. П оз аверш ению внеш негоцикла печатается положительны й рез ультат в случаеистинности диз ъю нкции f и g. В представленной нижепрограммедля наглядности ееработы предусмотрена возможностьвы водитьна э кран э лементы вспомогательны х массивов. О ператоры , печатаю щ иеэ лементы вспомогательны х массивов, оформлены как комментарии, содержащ иеслово“контроль” . ♠ Program Snake; Uses crt; Const m_max=10; n_max=10; Type matr=array[1..m_max,1..n_max] of real; vect=array[1..n_max] of real; Var a:matr;k,r,p,i,j,m,n,p_max:integer; f,g:boolean; v:vect; function rost(v:vect; n:integer):boolean; var s:boolean; i:integer;
18
begin s:=true; for i:=2 to n do s:=s and (v[i-1]<=v[i]); rost:=s end;{rost} function spad (v:vect; n:integer):boolean; var s:boolean; i:integer; begin s:=true; for i:=2 to n do s:=s and (v[i-1]>=v[i]); spad:=s end;{spad} Begin Textbackground(7); Textcolor(blue); Clrscr; writeln('Введите кол ичество стр ок м а тр ицы (не бол ьше ',m_max,')'); readln(m); writeln('Введите кол ичество стол бцов м а тр ицы (не бол ьше ',n_max,')'); readln(n); writeln('Введите вещ ественную м а тр ицу р а зм ер ом ',m,'x',n); for i:=1 to m do for j:=1 to n do read(a[i,j]); writeln('Введена вещественная матрица:'); for i:=1 to m do begin for j:=1 to n do write (a[i,j]:7:1); writeln end; {------------------------------------------------------} f:=true; g:=true; if m<=n then p_max:=(m+1) div 2 else p_max:=(n+1) div 2; for p:=1 to p_max do begin {верхняя строка р-го витка} k:=1; for j:=p-1 to n-p+1 do begin if j=0 then continue; v[k]:=a[p,j]; k:=k+1 end; r:=k-1; { (* контр оль *) for j:=1 to r do write(v[j]:3:0,' '); writeln;} f:=f and rost(v,r); g:=g and spad(v,r); if not(f or g) then break; {правый столбец р-го витка} k:=1; for j:=p to m-p+1 do begin v[k]:=a[j,n-p+1]; k:=k+1 end; r:=k-1; { (* контр оль *) for j:=1 to r do write(v[j]:3:0,' '); writeln;} f:=f and rost(v,r); g:=g and spad(v,r); if not(f or g) then break; {нижняя строка р-го витка}
19
k:=1; if not(odd(m)) or (p<>p_max) then begin for j:=n-p+1 downto p do begin v[k]:=a[m-p+1,j]; k:=k+1 end; r:=k-1; { (* контр оль *) for j:=1 to r do write(v[j]:3:0,' '); writeln; } f:=f and rost(v,r); g:=g and spad(v,r); if not(f or g) then break; end; {левый столбец р-го витка} k:=1; if not(odd(n)) or (p<>p_max) then begin for j:=m-p+1 downto p+1 do begin v[k]:=a[j,p]; k:=k+1 end; r:=k-1; { (* контр оль *) for j:=1 to r do write(v[j]:3:0,' '); writeln;} f:=f and rost(v,r); g:=g and spad(v,r); if not(f or g) then break end; end; if f or g then writeln('Эл ем енты обр а зую т уп ор ядоченную п осл едова тел ьность') else writeln('Эл ем енты не обр а зую т уп ор ядоченную п осл едова тел ьность'); readkey End.{Snake} Задача 3 реш ена без использ ования откры ты х параметров-массивов. В созданны енами процедуры rost и spad передавался массиводногораз мера, хотя фактически количествоэ лементоввпередаваемы х массивах бы лораз личны м. Как м о ж но и спр ави ть пр о гр ам м у, вк лю чи ввфунк ц и и о тк р ы ты е пар ам етр ы м асси вы ? П ознакомимся с процедурами, вы з ы ваю щ ими досрочноепрекращ ениеработы блоков. Нам з накома процедура Break, которая позволяет досрочноз аверш итьцикли перейти к оператору, следую щ емуз а циклом. Сущ ествует оператор Exit, которы й досрочноз аверш ает работублока с возвратом ввы з ы ваю щ ий блок. О ператор Halt прекращ ает работупрограммы , дажеесли он находится в подблоке. В основной программедействиеоператоровExit и Halt одинаково. В ы числим неберущ ийся интегралс з аданной точностью . За да ча 4. П устьданы вещ ественны ечисла a, b, e (a
0). С точностью b
∫
e вы числитеинтеграл f ( x ) dx , f ( x ) = a
b
(
sin x x , использ уя формулутрапеций
)
h f (a 0 ) + 2 f (a1 ) + 2 f (a2 )+...+2 f (a n−1 ) + f (a n ) . Д ля обеспечения ∫a 2 нужной точности воспольз уйтесьследую щ им правилом Рунге: если приблиf ( x )dx =
20
женноез начениеинтеграла In вы числятьпри n = no, 2no, 4no и т.д. (где no – нек о то р о е начально е чи сло о тр езк о вр азби ени я , напр и м ер , no=10), тогда при
I2n − In / 3 < e з аискомую величинуможновз я тьI2n. ♣ В ы числениеподы нтегральной функции опиш ем вподпрограммефункции с именем f(x). О с о бый с л у ча й: при х =0 з начением функции будем считатьединицу(пер вы й зам ечательны й пр едел). В процедуреIntegral вы числим In поформулетрапеций. П равилоРунгереализ уем восновной программев видецикла, втелекотороговы з ы вается процедура Integral. Ц иклбудет вы полня ться , пока I 2 n − I n / 3 ≥ e . ♠ Program Runge; Uses crt; Const n0=10; Var n:integer; a,b,e,Ip,I:real; Function f (x:real):real; begin if x=0 then f:=1 else f:=sin(x)/x; end;{f} Procedure Integral(n:integer; var S:real); var i:integer; x,h:real; begin x:=a; S:=f(a); h:=(b-a)/n; for i:=1 to n-1 do begin x:=x+h; S:=S+2*f(x); end; S:=S+f(b); S:=S*h/2 end;{Integral} Begin Textbackground(7); Textcolor(blue); Clrscr; write('Введите пределы интегрирования:'); read(a); repeat readln(b) until b>a; write('Введите точность вычислений:'); repeat readln(e) until e>0; {-------------------------------------------------} Integral(n0,Ip); n:=2*n0; Integral(n,I); while abs(I-Ip)/3>=e do begin Ip:=I; n:=2*n; Integral(n,I); end;
21
writeln('Искомый интеграл равен ',I:8:4); readkey End. {Runge} Пр о вер ьте р або ту пр о гр ам м ы на ПК!
3. Реку рс ивные п о дп ро гра м м ы П роцедуры и функции, которы евы з ы ваю т сами себя , наз ы ваю тся реку рс ивным и. Рекурсивны еобъекты частичноопределяю тся через самих себя . Т оесть рекурсивны еалгоритмы поя вляю тся , когда реш ениез адачи для случая n вы ражается через реш ениез адачи для случая n-1. Например, факториалможноопределитьс помощ ью рекуррентной формулы : 0! = 1, n! = n * (n-1)! Рекурсивная функция для вы числения n! может бы тьтакой: function fact (n:byte) :integer; begin if n=0 then fact:=1 else fact:=n*fact(n-1) end; Реш ениез адачи, реализ уемоерекурсивны м алгоритмом, можновы раз ить нерекурсивны м алгоритмом. Например, n! можновы числитьтак: function fact_ (n:byte) :integer; var i, k:integer; begin k:=1; for i:=2 to n do k:=i*k; fact_:=k end; Рекурсивны епроцедуры и функции просты , наглядны и компактны . О днакорекурсивны епроцедуры и функции требую т больш егораз мера оперативной памя ти вовремя вы полнения , чем нерекурсивны е. Значения всех локальны х переменны х и параметров, передаваемы х по з начению , при очередном вы з оверекурсивной процедуры или функции помещ аю тся встек. С теко м наз ы вается структура, напоминаю щ ая трубкус з апая нны м концом. П ри з аполнении стека действует принцип «первы м приш ел, последним уш ел». Е сли стек з аполня ется 1-м, 2-м, 3-м э лементами, тоиз влекаться э ти э лементы будут вобратном поря дке– 3-й, 2-й, 1-й. Т оестьодной локальной переменной на раз ны х уровня х рекурсии будут соответствоватьраз ны ея чейки памя ти. Гл у бина реку рс ии – максимальноечислорекурсивны х вы з ововпроцедуры . Теку щ ий у ро вень реку рс ии – количестворекурсивны х вы з ововвтекущ ий момент времени.
22
В рекурсивном алгоритмедолжноприсутствоватьусловиевы хода из рекурсии. В противном случаерекурсивны й алгоритм может вы з ы ватьсебя «бесконечное»числораз . Ж датьрез ультатовработы программы придется долго. В действительности, бесконечногосамовы з ова неполучится , так как ресурсы оперативной памя ти ограничены . В ы зо вр ек ур си вно й пр о ц едур ы и ли функ ц и и до лж ен вы по лня ться по усло ви ю , к о то р о е на к ак о м -то ур о вне р ек ур си и станет ло ж ны м ! Е сли условиеистинно, тоосущ ествляется реку рс ивный с п у с к. К ак толькоусловиесталоложны м, начинается реку рс ивный во звра т. Рассмотрим три раз ны х формы рекурсивной процедуры / функции. 1. П роцедура с вы полнением действий на рекурсивном спуске: Procedure Рекурсия; begin Действия; if Условие then Рекурсия end; 2. П роцедура с вы полнением действий на рекурсивном возврате: Procedure Рекурсия; begin if Условие then Рекурсия; Действия; end; 3. П роцедура с вы полнением действий на рекурсивном спускеи возврате: Procedure Рекурсия; begin Действия; if Условие then Рекурсия; Действия; end; Рассмотрим з адачу, вкоторой действия вы полня ю тся на рекурсивном спускеи возврате. За да ча 1. П устьдана строка текста. Напечатайтееевобратном поря дке. ♣ Рекурсивная процедура Rec читает символы строки на рекурсивном спускеи печатает считанны есимволы на рекурсивном возврате. Л окальная переменная c:char хранит считанны й на очередном уровнерекурсии символ. У словием вы хода из рекурсии служит з начениефункции eoln (к о нец стр о к и ). П ри нажатии клавиш и Enter начинается рекурсивны й возврат и считанны есимволы печатаю тся вобратном поря дке. ♠ Program Text; Uses crt; Procedure Rec; var c:char; begin if not eoln
23
then begin read(c); Rec; write(c) end; end; {Rec} Begin Rec; readkey End. {Text} П ознакомимся с красивой з адачей, свя з анной с легендой, реш ениекоторой приводит к рекурсивномуалгоритму. Говоря т, чтокогда-товХ аноестоя л храм, а ря дом с ним – три баш ни (стер ж ня ). На первую баш ню надеты 64 диска раз личногодиаметра. С ложенны едиски на стержнепохожи на детскую игруш ку– пирамиду. М онахи э тогохрама должны переместитьвседиски с первогостержня на третий, соблю дая следую щ иеправила: 1. можноперемещ атьлиш ьпоодномудиску; 2. больш ий диск нельз я кластьна меньш ий; 3. сня ты й диск нельз я отложить– егонеобходимосраз уженадетьна другой стержень. Л егенда утверждает, чтокогда монахи з акончат свою работу– а они перемещ аю т диск з а однусекунду! – наступит конец света. К огда дисковмного, реш ениеэ той з адачи оказ ы вается слиш ком долгим. За да ча 2. « Х ано й с ки е баш ни ». П устьимею тся три столбика А , В , С и n дисковраз ногораз мера, перенумерованны х от 1 доn впоря дкевозрастания их раз меров. Сначала вседиски надеты на столбик А ввиде пирамиды . Т ребуется перенести вседиски состолбика А на столбик С , соблю дая следую щ иеправила: диски можнопереноситьтолькопоодному, диск больш егораз мера нельз я ставитьна меньш ий. Д иск B можноиспольз оватьв качествепромежуточного. ♣ Задачуможнореш ить, составиврекурсивны й алгоритм. Реш ениез адачи для n дисковможносформулироватьчерез реш ениез адачи для n-1 дискови т.д. Д ля случая n=1 реш ениесводится к перемещ ению единственногодиска с исходногостолбика на целевой столбик. С оставим рекурсивны й алгоритм: Если n>0, то переместить верхние n-1 диск со столбика А на столбик В, используя столбик С как вспомогательный, переместить оставшийся нижний диск со столбика А на столбик С, переместить n-1 диск со столбика B на столбик С, используя столбик А как вспомогательный. П араметрами рекурсивной процедуры move я вляю тся переменны еn (чи сло пер ем ещ аем ы х ди ск о вна тек ущ ем ур о вне р ек ур си и ), Source (бук ва и схо дно го сто лби к а), Help (бук ва вспо м о гательно го сто лби к а), Res (бук ва ц елево го сто лби к а). В глобальной переменной k накапливается числосделанны х ходов. ♠ Program Hanoi; Uses crt; Var n,k:integer;
24
Procedure move(n:byte; Source, Help, Res: Char); begin if n>0 then begin move(n-1,Source,Res,Help); k:=k+1; writeln('Снять диск №',n,' со столбика ',Source, ' и надеть на столбик ',Res); move(n-1,Help,Source,Res) end end; {move} Begin Textbackground(7); Textcolor(blue); Clrscr; Write('Введите количество дисков:');Readln(n); Writeln('Последовательность действий:'); k:=0; move(n,'A','B','C'); writeln('Минимальное число ходов:',k); readkey End. {Hanoi} Нижеприведен рез ультат работы программы Hanoi при n=3. Введите количество дисков:3 Последовательность действий: Снять диск №1 со столбика A и надеть на столбик C Снять диск №2 со столбика A и надеть на столбик B Снять диск №1 со столбика C и надеть на столбик B Снять диск №3 со столбика A и надеть на столбик C Снять диск №1 со столбика B и надеть на столбик A Снять диск №2 со столбика B и надеть на столбик C Снять диск №1 со столбика A и надеть на столбик C Минимальное число ходов:7 М ожнопровести аналогию междурекурсивны м методом программирования и методом математической индукции. В началез адача реш ается для простогослучая , например, для n=1. Затем предполагается , чтосущ ествует реш ениедля случая n-1 и реш ениедля случая n сводится к реш ению для случая n-1. П ри э том процедура вы з ы вает сама себя дотех пор, пока небудет достигнута э лементарная ситуация . П ознакомимся с рекурсивны м алгоритмом бы строй сортировки массива. М етод бы строй сортировки бы лраз работан в1962 г. профессором О ксфордскогоуниверситета К . Хоа р ом . За да ча 3. « Б ы с трая с о рти ро вка». У поря дочитеэ лементы одномерного массива понеубы ванию методом бы строй сортировки.
25
♣ М ето д быс тро й с о ртиро вки з аклю чается вследую щ ем: I этап. О бозначим через а и b границы сортируемой части массива Х (n). В началеa=1, b=n. В массивеХ ищ ется э лемент S, стоя щ ий околосередины . Э лементы массивапросматриваю тся поочереднослеванаправои справаналево. П ри перебореэ лементовслева направоопределяется позиция i э лемента Х [i] => S. П ри перебореэ лементовсправа налевоопределяется позиция j э лемента Х [j] <= S. Е сли э лемент Х [i] находится слева от S, а э лемент Х [j] – справа, тонайденны еэ лементы Х [i] и Х [j] меня ю тся местами. В стречны й поиск продолжается дотех пор, пока индексы i и j непересекутся , т.е. i>j. Например, пустьмассивX состоит из 5 э лементов: 5 1 4 2 3. S=4. П ри i=1, j=5 переставляю тся крайниеэ лементы : 3 1 4 2 5. В стречны й поиск будет продолжен при i=2, j=4. П ри i=3, j=4 переставляю тся 3-й и 4-й э лементы : 3 1 2 4 5. Т екущ иез начения i и j из меня ю тся на единицу. i=4, j=3. I э тап з акончен, так как i>j. П ослез аверш ения I э тапа всеэ лементы , меньш иеили равны есреднему, окажутся слева от границы пересечения индексовi и j, а всеэ лементы , которы е больш еили равны среднему, окажутся справа. О днаколевая и правая части массива ещ емогут бы тьнеотсортированны ми. II этап. На втором э тапеповторя ю тся действия первогоэ тапа для левой и правой частей массива. Е сли j оказ ы вается больш еa, тодействия первогоэ тапа реализ ую тся для э лементовмассива с номерами от a доj. Е сли i оказ ы вается меньш еb, тодействия первогоэ тапа реализ ую тся для э лементовмассива с номерами от i доb. В наш ем примерепослепервогоэ тапа i=4, j=3. Значит, на втором уровне рекурсии сортировкебудут подвержены э лементы левой части массива с номерами от 1 до3: 3 1 2│4 5 и правой части с номерами от 4 до5. На втор ом у р овн ер ек у р си и д ля левой ча сти массива: 3 1 2 4│5: S=1. П ри i=1, j=2 переставляю тся 1-й и 2-й э лементы : 1 3 2 4│5. Т екущ иез начения i и j из меня ю тся на единицу. i=2, j=1. В торой уровеньрекурсии з акончен, так как i>j. П ослевторогоуровня рекурсии для левой части массива i=2, j=1. Значит, на третьем уровнерекурсии сортировкебудут подвержены э лементы с номерами от 2 до3: правой части рассматриваемогоучастка:1│3 2│4 5. На тр етьем у р овн ер ек у р си и д ля левой ча сти массива: 1│3 2│4 5: S=3. П ри i=2, j=3 переставляю тся 2-й и 3-й э лементы : 1│2 3│4 5. Т екущ иез начения i и j из меня ю тся на единицу. i=3, j=2. Т ретий уровеньрекурсии з акончен, так как i>j. Д альнейш ий рекурсивны й вы з овневы полня ется , так как последанногош ага i=3, j=2, т.е. j=a, а i=b. На втор ом у р овн ер ек у р си и д ля пр а вой ча сти массива: 1 2 3│4 5: S=4. П ри i=4, j=4 переставляю тся 4-й и 4-й э лементы : 1 2 3│4 5.
26
Т екущ иез начения i и j из меня ю тся на единицу. i=5, j=3. В торой уровеньрекурсии з акончен, так как i>j. Т ретьегоуровня рекурсии для правой части массива небудет, так как js do j:=j-1; if i<=j then begin r:=x[i]; x[i]:=x[j]; x[j]:=r; i:=i+1; j:=j-1 end; end; if a<j then Quick(a,j); if i
пер во й стр о к и и k-го сто лбц а): det A = ∑ ( − 1) k =1
k +1
A1,k det Bk .
♣ С оставим рекурсивную функцию det, вы числяю щ ую определительdet А поря дка n. Е сли n>1, тоопределительdet А расклады вается попервой строке. М инор B1k э лемента a1k получается копированием э лементовматрицы А и смещ ением э лементовна однустрокувверх и на один столбец влево. П ри э том э лементы первой строки и k-гостолбца теря ю тся , а поря док определителя уменьш ается на единицу. Е сли n=1, тоопределительбудет равен э лементуа[1,1]. К онстанта n_max содержит поря док определителя. Т ип Mas описы вает квадратную матрицураз мера n_max x n_max. П еременны еi и j использ ую тся как счетчики циклов.
27
В функции det впеременной s накапливается сумма произ ведений э лементовпервой строки на их алгебраическиедополнения . В переменной sign хранится рез ультат возведения (-1) встепеньk+1. ♠ Program Det_A; Uses crt; Const n_max=3; Type Mas=array[1..n_max,1..n_max] of integer; Var a:Mas;i,j:integer; Function det(a:Mas; n:integer):integer; var i,j,s,k,sign:integer; b:Mas; begin if n>1 then begin s:=0; for k:=1 to n do begin if odd(k+1) then sign:=-1 else sign:=1; b:=a; {вычеркивание 1-й строки и k-го столбца} for i:=1 to n-1 do for j:=1 to n do b[i,j]:=b[i+1,j]; for i:=1 to n-1 do for j:=k to n-1 do b[i,j]:=b[i,j+1]; s:=s+sign*a[1,k]*det(b,n-1); end; det:=s end else det:=a[1,1]; end;{det} Begin Textbackground(7); Textcolor(blue); Clrscr; for i:=1 to n_max do for j:=1 to n_max do read(a[i,j]); writeln('det=',det(a,n_max)); readkey End.{Det_A} По дго то вьтесь к о тветам на в се(!) к о нтр о льны е во пр о сы и вы по лни те в се(!) к о нтр о льны е задани я . До р о гу о си ли т и дущ и й!
Ко нтро л ь ные во п ро с ы и за да ния 1. 2. 3. 4.
1. М ето д п о с л едо ва тел ь но й дета л иза ции. Ф у нкции Ч тотакоеалгоритмический блок? Ч тотакоеблочноепрограммирование? Зачем оноприменя ется ? Ч тоназ ы ваю т подпрограммой? В чем сутьметода последовательной детализ ации?
28
5. В чем з аклю чается метод программирования сверхувниз ? 6. В чем з аклю чается метод программирования сниз увверх? 7. К аким методом программирования целесообраз неереш атьновую з адачу?
О бъя сните, почему. 8. К акиея з ы ки программирования наз ы ваю тся п р оцедур но-ор иентир ова нны м и? 9. Я вляется ли Turbo Pascal процедурно-ориентированны м? П очему? 10. К акиесредства структурирования программ имею тся вП аскале? 11. К акиестандартны епроцедуры и функции В ам из вестны ? 12. Ч тотакоемодуль? П риведитепример стандартногомодуля и процедур из него. 13. В каком случаеподпрограмма наз ы вается функцией? 14. К акоеколичествоз начений возвращ ает функция ? 15. К ак определитьтип з начения , возвращ аемогофункцией? 16. Сущ ествую т ли ограничения на тип возвращ аемогофункцией з начения ? 17. Д опустимоли следую щ ееописаниефункции: function f (x:real) : string [5]? 18. П риведитенесколькоспособоввы з ова функции из основной программы . 19. К ак вобщ ем видеописы вается функция ? 20. Ч тотакоепараметр функции? Ч тоназ ы ваю т фактическим и формальны м параметром функции? 21. Ч тоназ ы ваю т областью видимости данны х? 22. К акиеданны еназ ы ваю тся локальны ми? Глобальны ми? 23. П очемупоня тия “локальны е” и “глобальны е” я вляю тся условны ми? 24. Наз овитечеты реправила определения з оны действия идентификаторовпроцедур и функций. 25. М ожет ли имя локальной переменной совпадатьс именем глобальной? К акая из двух одноименны х переменны х будет действоватьвпроцедуре? В основной программе? 26. М ожноли создаватьпольз овательскиефункции с именами стандартны х функций (напр и м ер , м о ж но ли со здать сво ю функ ц и ю sin())? 27. Напиш итепрограмму, печатаю щ ую всечисла М ерсенна типа integer. И спольз уйтевпрограммефункцию , определяю щ ую , я вляется ли аргумент просты м числом. Напиш итеалгоритм и блок-схему. 28. Ч тоназ ы ваю т временем жиз ни локальны х данны х? 29. В книгеn страниц (n - вхо дно е данно е). С оставьтеалгоритм, блок-схемуи программу, которая будет находить, сколькоцифр понадобится для того, чтобы з анумероватьвсестраницы данной книги. И спольз уйтедвепольз овательскиефункции. 30. П очемублоки сравниваю т с “черны ми я щ иками” с одностороннез еркальной кры ш кой? 31. Напиш итефункцию , вы числяю щ ую sh(x), и для з аданногоз начения переменной x вы числитеследую щ еевы ражение: sh(x) + tg(x+1) - tg2(2 + sh(x - 1)).
29
32. Напиш ите, использ уя данны й фрагмент программы :
type страна = (Швейцария, Нидерланды, Бельгия, Ирландия, Норвегия); столица = (Берн, Амстердам, Брюссель, Дублин, Осло); функцию , которая поз аданной странеопределяет еестолицу. 33. Д ля з аданногонатуральногочисла N определитепервы еN просты х чисел. 34. Напиш итефункцию , проверя ю щ ую , я вляется ли з аданная литера гласной русской буквой. 35. Заданны й массивцелы х чиселделится на три части двумя э лементами: максимальны ми минимальны м. О пределитесуммуэ лементоввкаждой части массива. И спольз уйтефункции для нахождения индексовминимальногои максимальногоэ лементови подсчета суммы э лементоввуказ анной части массива. 36. П устьдана пря моугольная матрица A(nxm), э лементами которой я вляю тся целы ечисла. О пределите, вкакой строкематрицы находится наибольш ее количествосимметричны х чисел. Составьтефункцию , проверя ю щ ую симметричностьчисла. 37. Д ля з аданной строки текста определитеслова, которы есодержат символы , отличны еот букв. Напиш итефункцию , определяю щ ую тип символа строки. 2. П ро цеду ры. С п о с о бы п ереда чи п а ра м етро в 38. Д айтеопределениепроцедуры . 39. К ак вобщ ем видеописы вается процедура? 40. Ч тоназ ы ваю т параметром процедуры ? 41. К акиепараметры наз ы ваю тся формальны ми? Ф актическими? 42. К акоеколичествоз начений возвращ ает процедура? 43. К аким образ ом осущ ествляется обмен данны ми междувы з ы ваю щ им и вы з ы ваемы м блоками? 44. М огут ли формальны епараметры бы тьконстантами? В ы ражения ми? И менами других функций или процедур? О бъя снитеответ. 45. М огут ли фактическиепараметры бы тьпеременны ми? К онстантами? В ы ражения ми? И менами других функций? И менами других процедур? П очему? 46. М огут ли имена формальны х параметровсовпадать/ несовпадатьс именами фактических параметров? 47. К ак определитьобластьвидимости формальногопараметра? 48. Наз овитедва основания классификации способовпередачи параметров. 49. Ч топроисходит при передачепараметровпоз начению ? 50. Ч топроисходит при передачепараметровпоссы лке? 51. Наз овитеш естьтеоретически возможны х способовпередачи параметров. К акиеиз них реализ ованы вП аскале? 52. К ак происходит передача входногопараметра поз начению ? М ожноли из меня тьз начениетакогоформальногопараметра? И з менится ли при э том фактический параметр? И з менится ли одноименны й фактический параметр? 53. Ч тотакоепараметры -з начения ? К акоговида и типа могут бы тьфактические
30
параметры -з начения ? 54. К ак происходит передача входногопараметра поссы лке? М ожноли из меня тьз начениетакогоформальногопараметра? М ожноли передаватьпараметр другим процедурам и функция м? 55. Ч тотакоепараметры -константы ? К ак описатьформальны й параметрконстанту? К акоговида и типа могут бы тьфактическиепараметры константы ? К огда использ ую т параметры -константы ? 56. К ак происходит передача входногои вы ходногопараметра поссы лке? М ожноли из меня тьз начениетакогоформальногопараметра? И з менится ли при э том соответствую щ ий фактический параметр? П очему? Б удет ли доступен формальны й параметр восновной программе? 57. Ч тотакоепараметры -переменны е? К ак описатьформальны й параметрпеременную ? М огут ли фактическиепараметры -переменны ебы тьконстантами, вы ражения ми? К акоготипа могут бы тьфактическиепараметры переменны е? 58. Сущ ествую т ли процедуры без параметров? К ак осущ ествляется обмен данны ми междуосновной программой и подпрограммой без параметров? 59. Ч тотакоеоткры ты епараметры -массивы ? Зачем они нужны ? 60. К ак описатьоткры ты й параметр-массив? П риведитепример. 61. К ак работаю т функции Low(),High(),SizeOf()? 62. К акиеограничения наклады ваю тся на фактическиепараметры -массивы ? 63. К ак работаю т процедуры Exit и Halt? 64. Напиш итепрограммус процедурой для реш ения следую щ ей з адачи: “А ня нарвала я блок и поровнураз дала своим сестрам О ле, М аш еи Свете, а что осталось, съела. О ля свои я блоки поделила междутремя сестрами, а чтоосталось, съела. Т ожесамоесделали М аш а и Света. Сколькоя блок оказ алось укаждой сестры ?” 65. Составьтепрограммудля реш ения з адачи одележевобщ ем случае, тоесть для дележа я блок междуn (входноеданное!) лицами. Д ележ осущ ествляется потем жеправилам, чтои впреды дущ ей з адаче. 66. В ы числитечислоe c точностью до50-гоз нака послез апя той. П роведите декомпозицию з адачи, напиш итеалгоритм, блок-схемуи программу. 67. Напиш итепрограмму, определяю щ ую количестводеся тичны х з наков, вы деляемы х для представления действительногочисла. 68. Составьтепрограмму, которая напечатает числоπ с з аданной точностью . 69. Д ля з аданной вещ ественной матрицы определите, образ ую т ли ееэ лементы упоря доченную последовательностьпри их переборепоспирали. Д ля определения факта упоря доченности части строки (столбца) использ уйтефункции. Напиш итеалгоритм с описанием особы х случаев, блок-схемуи программу. 70. Напиш итепрограммук преды дущ ей з адачи, использ уя функции с откры ты ми параметрами-массивами. 71. Д ля з аданной вещ ественной матрицы определите, образ ую т
31
ли ееэ лементы упоря доченную последовательностьпри их переборепосхеме, указ анной справа. Д ля определения факта упоря доченности части строки (столбца) использ уйте функции. 72. П устьданы вещ ественны ечисла a, b, e (a0). С точностью e вы числите b
интеграл∫ f ( x ) dx , f ( x ) = a
sin x , использ уя формулутрапеций x
b
h ∫ f ( x )dx = 2 ( f (a ) + 2 f (a ) + 2 f (a )+...+2 f (a ) + f (a )) . Д ля обеспечения 0
1
2
n −1
n
a
нужной точности воспольз уйтесьправилом Рунге. 73. О пределитевсеобщ иеделители двух з аданны х натуральны х чисел. 74. Напиш итепроцедурусложения двух дробей, рез ультатом которой я вля ется несократимая правильная дробь. И спольз уйтефункцию для нахождения наибольш егообщ егоделителя. 75. В двух целочисленны х последовательностя х
a1 , a2 ,..., an и b1 , b2 ,..., bm з а-
менитевсеэ лементы , следую щ иез а э лементом с максимальны м з начением, на з начениеминимальногоэ лемента. И спольз уйтевпроцедуреоткры ты й параметр-массив. 76. Ин д и ви д у а льн ое(!) за д а н и е, котороепередается преподавателю перед началом собеседования поэ той теме: Н о м ер и нди ви дуально го задани я о пр еделя ет пр епо даватель! Опи ши тепоста н овк у за д а чи , созд а йтем а тем а ти ческ у ю м од ельеер ешен и я, р а зр а бота йтеблок -схем у и р а бота ющ у ю пр огр а м м у , пр овед и те тести р ова н и еи отла д к у пр огр а м м ы , обд у м а йтеполу чен н ы ер езу льта ты .
Индивиду а л ь ные за да ния 1. Составьтепроцедуру“сжатия ” исходной последовательности символов, ко-
торая з аменя ет последовательность, состоя щ ую из одинаковы х символов, текстом вида x(k), гдеx - символпоследовательности, k - числовхождений. О пределитедля указ анной последовательности коэффициент сжатия (о тно шени е и схо дно й дли ны по следо вательно сти к по лученно й). 2. П устьданы двематрицы A (mxn), B(mxn), состоя щ иеиз вещ ественны х чисел. НеобходимополучитьматрицуС (mxn), гдеэ лемент Cij равен суммеэ лементовi-й строки матрицы А , которы еотсутствую т вj-м столбцематрицы B. Напиш итефункцию вы числения Cij, использ ую щ ую функцию проверки наличия числа вj-м столбцематрицы B. 3. П устьданы двевещ ественны ематрицы поря дка n. П олучитеновую матрицу следую щ им способом (для нахо ж дени я м и ни м ально го элем ента вук азанно й стр о к е и спо льзуйте функ ц и ю ): умножением минимальногоэ лемента каждой строки первой матрицы на наибольш ий э лемент соответствую щ его столбца второй матрицы .
32
4. П устьданы двевещ ественны ематрицы поря дка n. П олучитеновую матрицу
следую щ им способом (для нахо ж дени я пр о и зведени я элем енто ввук азанно й стр о к е и спо льзуйте функ ц и ю ): прибавлением к э лементам каждогостолбца первой матрицы произ ведения э лементовсоответствую щ их строк второй матрицы . 5. П устьдана вещ ественная квадратная матрица поря дка 2n. П олучитеновую матрицу, переставляя ееблоки раз мером n так, как показ анона рисункесправа. Д ля обмена четы рех з аданны х фрагментовматрицы напиш итефункцию . 6. П устьдана вещ ественная квадратная матрица поря дка 2n. П олучитеновую матрицу, переставляя ееблоки раз мером n так, как показ анона рисункесправа. Д ля обмена четы рех з аданны х фрагментовматрицы напиш итефункцию . 7. П устьдана пря моугольная матрица A(mxn), э лементами которой я вляю тся целы ечисла. Заменитевсеположительны ечетны ечисла на числа, я вляю щ иеся их «переверты ш ами». Составьтеподпрограмму, получаю щ ую для з аданногочисла его«переверты ш »(чи сло абудем счи тать « пер евер ты шем » чи сла b, если , чи тая чи сло аспр ава налево , по лучаем чи сло b). 8. Напиш итефункцию , которая вз аданной строкеопределяет количествовхождений внеез аданной подстроки. Д ля з аданны х строки и слова определите количествовхождений слова встроку. 9. Д ля з аданноготекста определитепаруслов, буквенны й составкоторы х наиболеесхож. И спольз уйтефункцию для определения сходства буквенного состава двух слов. 10. П устьдана матрица A(nxn). У поря дочьтестроки понеубы ванию сумм цифр э лементовэ той строки. В оспольз уйтесьфункцией, определяю щ ей для каждогочисла суммуегоцифр. 11. П устьданоn треугольников, з аданны х координатами своих верш ин. Найдитепарутреугольников, максимальноудаленны х другот друга. 12. П устьданоn пря моугольников, з аданны х координатами левой верхней и правой нижней верш ины . Стороны пря моугольниковпараллельны ося м координат. О пределитепарупря моугольниковс максимальной площ адью пересечения . Напиш итефункцию для определения площ ади пересечения двух пря моугольников. 13. П устьданоn отрез ковна интервале(А , В ). О пределитечастьинтервала, которы й покры вается наибольш им количеством отрез ков. Напиш итефункцию для определения количества отрез ков, покры ваю щ их з аданны й интервал. 14. Составьтепроцедуруделения с остатком для многочленов. В ы числите:
a0 + a1 x + a2 x 2 + ...+ an x n ( b0 + b1 x + b2 x 2 +...+bm x m )( bm + bm−1 x + bm−2 x 2 +...+b0 x m ) , 2m < n . 15. Найдитевсечисла, которы еравны суммефакториаловсвоих цифр. Напри-
мер,
33
1!+4!+5! = 145. О пределитеверхню ю границумножества таких чисел. И спольз уйтефункцию , вы числяю щ ую суммуфакториаловцифр числа. 16. У плотнитематрицуA(nxn) влевои вверх. Д ля вы я вления нулевы х строк и столбцовиспольз уйтеподпрограмму. 3. Реку рс ивные п о дп ро гра м м ы 77. Ч тотакоерекурсивны еподпрограммы ? 78. В каком случаереш ениез адачи можновы раз итьрекурсивны м алгоритмом? П риведитепример. 79. Ч тотакоестек? К ак организ ованоз аполнениестека и вы бор э лементовиз стека? 80. К ак свя з аны стек и рекурсия ? 81. Ч тотакоеусловиевы хода из рекурсии? Д ля чегоононужно? 82. М ожет ли рекурсивная процедура вы з ы ватьсебя бесконечноечислораз ? 83. М ожноли рекурсивны й алгоритм з аменитьнерекурсивны м? 84. Ч тотакоеглубина рекурсии? 85. Ч тотакоетекущ ий уровеньрекурсии? 86. Ч тотакоерекурсивны й спуск? Рекурсивны й возврат? 87. П риведитетри раз ны х формы рекурсивной процедуры / функции. 88. П устьдана строка текста. Напечатайтеэ тот текст вобратном поря дке. 89. Д ля чегослужит функция eoln? 90. Напиш итеалгоритм и программудля реш ения з адачи: «Х анойскиебаш ни». 91. В чем з аклю чается метод бы строй сортировки э лементовмассива? 92. У поря дочитеэ лементы одномерногомассива понеубы ванию методом бы строй сортировки. 93. В ы числитеопределительз аданной матрицы , польз уя сьформулой раз ложения попервой строке(м атр и ц а В по лучается вы чер к и вани ем и зА пер во й n
стр о к и и k-го сто лбц а): det A = ∑ (− 1) k =1
k +1
A1,k det Bk .
94. П овещ ественномучислу a >0 вы числитевеличину:
3
a − 6 a2 +1 . К орни 1+ 7 3 + a
y = k x вы числяйтес точностью Е=0,00001 последую щ ей итерационной x k +1 − yn yn , n=0,1,2,… , приня вз а ответ приформуле: y0 = 1 ; yn +1 = yn + k ближение yn +1 , для которого yn+1 − yn < E . 95. Д ля з аданны х границ интегрирования a и
ленногоинтеграла следую щ еговида:
b
вы числитез начениеопреде-
34 b x m+1 n n x m ln n−1 xdx , n > 1, ln x − b ∫ m m + 1 + 1 a ∫a x m lnn xdx = x ln 1 x m+1 − 2 , n = 1. m + 1 ( m + 1)
96. П олучитеколичествораз мещ ений из 10 э лементов1, 2,… , 10 по3 вкаждом.
Раз мещ ением наз ы вается вы борка из n указ анны х э лементовm неповторя ю щ ихся э лементов. 97. Напиш итерекурсивную функцию для нахождения биномиальны х коэффициентов(для з аданного M ≥ i ≥ j > 0 вы числитевсе C j ): i
1, m = 0, n > 0 ∨ m = n ≥ 0, 0, m > n > 0, C = Cmn−−11 + Cmn−1 ,0 < m < n. n m
98. О пиш итерекурсивную функцию , которая поз аданны м границам
a и b,
з аданной функции f ( x ) и з аданной точности ε методом деления отрез ка пополам находит с точностью ε кореньуравнения f ( x ) = 0 на отрез ке
[a , b] . Считать, чтоε > 0 , a < b ,
f ( a) ⋅ f ( b) < 0 , f ( x ) - непреры вная и
монотонная на [a , b] . 99. П остройтесинтаксический анализ атор для поня тия и денти фи к ато р . <Идентификатор> ::= <буква>│<идентификатор> (<цифра>│<буква>).
Литера ту ра 1. А брамовС .А . Начала информатики / С.А .А брамов, Е .В .Зима. – М . : Наука, 1990. 2. Д агенеВ .А . и др. 100 з адач попрограммированию / В .А .Д агенеи др. - М .: П росвещ ение, 1993. 3. Е панеш никовА .М . П рограммированиевсредеTurbo Pascal 7.0 / А .М . Е панеш ников, В .А .Е панеш ников. –3-еиз д. – М .: Д иалог-М И Ф И , 1996. 4. ЗубовВ .С. П рограммированиена я з ы кеTurbo Pascal / В .С.Зубов. – М . : Ф илинъ, 1997. 5. К ассера В . TurboPascal 7.0 / В .К ассера, Ф . К ассера. - 2003. 6. М арченкоА .И . П рограммированиевсредеTurbo Pascal 7.0 / А .И .М арченко, Л .А .М арченко. - М .: Б ином У ниверсал, К . : Ю НИ О Р, 1997. 7. П ильщ иковВ .Н. Сборник упражнений поя з ы куП аскаль/ В .Н.П ильщ иков. М . : Наука, 1989. 8. П рограммированиена я з ы кеП аскаль: з адачник/под ред. У сковой О .Ф . – СП б: П итер, 2002. 9. Ф ароновВ .В . Turbo Pascal 7.0. Начальны й курс/ В .В .Ф аронов. – М . : Нолидж, 1998. 10.Х ерш ельР. Т урбоП аскаль/ Р.Х ерш ель. – В ологда: М П М И К , 1991.
35
©
36
Составители: В асильевВ алерий В икторович, Х ливненкоЛ ю бовьВ ладимировна
Редактор
Т ихомироваО .А .