Библиотека программи�та
Пользователь

Добро пожаловать,

Реги�траци� или входРеги�траци� или вход
Потер�ли пароль?Потер�ли пароль?

�ик:
Пароль:

Меню �айта




Ваше мнение
Легко ли найти нужную информацию на �айте?

Очень про�то
�ахожу почти �разу
Приходит�� тщательно покопать��
Почти невозможно
�е нашел (лень разбирать��)


Результаты
Другие опро�ы

В�его голо�ов: 594
Комментарии: 0


�аши партнеры



Стати�тика




Programming books  Download software  Documentation  Scripts  Content Managment Systems(CMS)  Templates  Icon Sets  Articles  Contacts  Voting  Site Search




Книги-online



Ëàáîðàòîðíàÿ ðàáîòà ¹5

Ëàáîðàòîðíàÿ ðàáîòà ¹5


Ðåêóðñèÿ

Öåëü ðàáîòû:
Ïîçíàêîìèòüñÿ ñ îäíèì èç ýôôåêòèâíûõ ñïîñîáîâ ðåøåíèÿ ñëîæíûõ çàäà÷ – ðåêóðñèåé.

Îáùèå ñâåäåíèÿ:

Î÷åíü ÷àñòî, ðàçðàáàòûâàÿ ïðîãðàììó, óäàåòñÿ ñâåñòè èñõîäíóþ çàäà÷ó ê áîëåå ïðîñòûì. Ñðåäè ýòèõ çàäà÷ ìîæåò îêàçàòüñÿ è ïåðâîíà÷àëüíàÿ, íî â óïðîùåííîé ôîðìå. Íàïðèìåð, âû÷èñëåíèå ôóíêöèè F(n) ìîæåò ïîòðåáîâàòü âû÷èñëåíèÿ F(n-1) è åùå êàêèõ-òî îïåðàöèé. Èíûìè ñëîâàìè, ÷àñòüþ àëãîðèòìà âû÷èñëåíèÿ ôóíêöèè áóäåò âû÷èñëåíèå ýòîé æå ôóíêöèè.
Àëãîðèòì íàçûâàåòñÿ ðåêóðñèâíûì, åñëè îí ïðÿìî èëè êîñâåííî îáðàùàåòñÿ ê ñàìîìó ñåáå. ×àñòî â îñíîâå òàêîãî àëãîðèòìà ëåæèò ðåêóðñèâíîå îïðåäåëåíèå êàêîãî-òî ïîíÿòèÿ. Íàïðèìåð, î ôàêòîðèàëå ÷èñëà N ìîæíî ñêàçàòü, ÷òî N! = N*(N – 1)!, åñëè N > 0 è N! = 1 åñëè N = 0. Ýòî – ðåêóðñèâíîå îïðåäåëåíèå.
Âîò åùå îäíî ðåêóðñèâíîå îïðåäåëåíèå.
1. 3 êîðîâû – ýòî ñòàäî êîðîâ.
2. Ñòàäî èç n êîðîâ – ýòî ñòàäî èç n – 1 êîðîâû è åùå îäíà êîðîâà.
Ïîïðîáóåì ïðèìåíèòü ýòî îïðåäåëåíèå äëÿ ïðîâåðêè, ÿâëÿåòñÿ ëè ñòàäîì ãðóïïà èç ïÿòè êîðîâ (îáîçíà÷èì åå Ê5). Îáúåêò Ê5 íå óäîâëåòâîðÿåò ïåðâîìó ïóíêòó îïðåäåëåíèÿ, ïîñêîëüêó ïÿòü êîðîâ – ýòî íå òðè êîðîâû. Ñîãëàñíî âòîðîìó ïóíêòó Ê5 – ñòàäî, åñëè òàì åñòü îäíà êîðîâà, à îñòàëüíàÿ ÷àñòü Ê5, íàçîâåì åå Ê4, – òîæå ñòàäî êîðîâ. Ðåøåíèå îòíîñèòåëüíî îáúåêòà Ê5 îòêëàäûâàåòñÿ, ïîêà íå áóäåò ïðèíÿòî ðåøåíèå îòíîñèòåëüíî Ê4. Îáúåêò Ê4 ñíîâà íå ïîäõîäèò ïîä ïåðâûé ïóíêò, à âòîðîé ïóíêò ãëàñèò, ÷òî Ê4 – ñòàäî, åñëè îáúåêò Ê3, ïîëó÷åííûé èç Ê4 ïóòåì îòäåëåíèÿ îäíîé êîðîâû, òîæå ñòàäî. Ðåøåíèå î Ê4 òîæå îòêëàäûâàåòñÿ. Íàêîíåö, îáúåêò Ê3 óäîâëåòâîðÿåò ïåðâîìó ïóíêòó îïðåäåëåíèÿ, è ìû ìîæåì ñìåëî óòâåðæäàòü, ÷òî Ê3– ñòàäî êîðîâ. Òåïåðü è î Ê4 ìîæíî óòâåðæäàòü, ÷òî ýòî ñòàäî, à çíà÷èò, è Ê5 ÿâëÿåòñÿ ñòàäîì êîðîâ.
Ëþáîå ðåêóðñèâíîå îïðåäåëåíèå ñîñòîèò èç äâóõ ÷àñòåé. Ýòè ÷àñòè ïðèíÿòî íàçûâàòü áàçîâîé è ðåêóðñèâíîé ÷àñòÿìè. Áàçîâàÿ ÷àñòü ÿâëÿåòñÿ íåðåêóðñèâíîé è çàäàåò îïðåäåëåíèå äëÿ íåêîòîðîé ôèêñèðîâàííîé ÷àñòè îáúåêòîâ. Ðåêóðñèâíàÿ ÷àñòü îïðåäåëÿåò ïîíÿòèå ÷åðåç íåãî æå è çàïèñûâàåòñÿ òàê, ÷òîáû ïðè öåïî÷êå ïîâòîðíûõ ïðèìåíåíèé îíà ðåäóöèðîâàëàñü áû ê áàçå.

Ïðèìåðû

1. Çàäà÷à. Íàïèñàòü ðåêóðñèâíóþ ïðîãðàììó ïîèñêà ìèíèìàëüíîãî ýëåìåíòà ìàññèâà.
Ðåøåíèå. Îïèøåì ôóíêöèþ Pmin, êîòîðàÿ îïðåäåëÿåò ìèíèìóì ñðåäè ïåðâûõ n ýëåìåíòîâ ìàññèâà à. Ïàðàìåòðàìè ýòîé ôóíêöèè ÿâëÿþòñÿ êîëè÷åñòâî ýëåìåíòîâ â ðàññìàòðèâàåìîé ÷àñòè ìàññèâà - n è çíà÷åíèå ïîñëåäíåãî ýëåìåíòà ýòîé ÷àñòè – à[n]. Ïðè ýòîì åñëè n>2, òî ðåçóëüòàòîì ÿâëÿåòñÿ ìèíèìàëüíîå èç äâóõ ÷èñåë – à[n] è ìèíèìàëüíîãî ÷èñëà èç ïåðâûõ (n-1) ýëåìåíòîâ ìàññèâà.  ýòîì çàêëþ÷àåòñÿ ðåêóðñèâíûé âûçîâ. Åñëè æå n=2, òî ðåçóëüòàòîì ÿâëÿåòñÿ ìèíèìàëüíîå èç ïåðâûõ äâóõ ýëåìåíòîâ ìàññèâà. ×òîáû íàéòè ìèíèìóì âñåõ ýëåìåíòîâ ìàññèâà, íóæíî îáðàòèòüñÿ ê ôóíêöèè Pmin, óêàçàâ â êà÷åñòâå ïàðàìåòðîâ çíà÷åíèå ðàçìåðíîñòè ìàññèâà è çíà÷åíèå ïîñëåäíåãî åãî ýëåìåíòà. Ìèíèìàëüíîå èç äâóõ ÷èñåë îïðåäåëÿåòñÿ ñ ïîìîùüþ ôóíêöèè Min, ïàðàìåòðàìè êîòîðîé ÿâëÿþòñÿ ýòè ÷èñëà.
Program Example _1;
Const n=10;
Type MyArray=Array[1..n] of Integer;
Const a : MyArray = (4,2, -1,5,2,9,4,8,5,3);
Function Min (a, b : Integer) : Integer;
Begin
  if a>b then Min := b else Min:=a;
End;
Function Pmin(n, b : Integer) : Integer;
Begin
  if n = 2 then Pmin := Min(n,a[1]) else Pmin := Min(a[n], Pmin(n-1,a[n]));
End;
BEGIN
  Writeln(‘Ìèíèìàëüíûé ýëåìåíò ìàññèâà  - ‘, Pmin(n,a[n]));
END.
2. Çàäà÷à. Õàíîéñêèå áàøíè. Èìååòñÿ òðè ñòåðæíÿ À, Â, Ñ. Íà ñòåðæåíü À íàíèçàíî ï äèñêîâ ðàäèóñà 1, 2,..., ï òàêèì îáðàçîì, ÷òî äèñê ðàäèóñà i ÿâëÿåòñÿ i-ì ñâåðõó. Òðåáóåòñÿ ïåðåìåñòèòü âñå äèñêè íà ñòåðæåíü Â, ñîõðàíÿÿ èõ ïîðÿäîê ðàñïîëîæåíèÿ (äèñê ñ áîëüøèì ðàäèóñîì íàõîäèòñÿ íèæå). Çà îäèí ðàç ìîæíî ïåðåìåùàòü òîëüêî îäèí äèñê ñ ëþáîãî ñòåðæíÿ íà ëþáîé äðóãîé ñòåðæåíü. Ïðè ýòîì äîëæíî âûïîëíÿòüñÿ ñëåäóþùåå óñëîâèå: íà êàæäîì ñòåðæíå íè â êàêîé ìîìåíò âðåìåíè íèêàêîé äèñê íå ìîæåò íàõîäèòüñÿ âûøå äèñêà ñ ìåíüøèì ðàäèóñîì.
Ðåøåíèå. Ïðåäïîëîæèì, ÷òî ìû óìååì ïåðåêëàäûâàòü ïèðàìèäó èç (n-1) äèñêà. Ðàññìîòðèì ïèðàìèäó èç n äèñêîâ. Ïåðåìåñòèì ïåðâûå (n-1) äèñêîâ íà ñòåðæåíü Ñ (ýòî ìû óìååì). Çàòåì ïåðåíåñåì ïîñëåäíèé n-é äèñê ñî ñòåðæíÿ À íà ñòåðæåíü Â. Äàëåå ïåðåíåñåì ïèðàìèäó èç (n-1) äèñêà ñî ñòåðæíÿ Ñ íà ñòåðæåíü Â. Òàê êàê n-é äèñê ñàìûé áîëüøîé, òî óñëîâèå çàäà÷è íå áóäåò íàðóøåíî. Òàêèì îáðàçîì, âñÿ ïèðàìèäà áóäåò íà ñòåðæíå Â. Àíàëîãè÷íûì îáðàçîì ìîæíî ïåðåíåñòè n – 2, n – 3 è ò. ä. äèñêîâ. Êîãäà n=1, îñóùåñòâèòü ïåðåíîñ î÷åíü ïðîñòî: íåïîñðåäñòâåííî ñ ïåðâîãî ñòåðæíÿ íà âòîðîé. Ïðè ýòîì äëÿ ðåøåíèÿ çàäà÷è áóäåò äîñòàòî÷íî 2n - 1 ïåðåêëàäûâàíèé.
Program Example_2;
Const k = 3;
Var a,b,c : Char;
Procedure Disk(n : Integer; a, b, c: Char);
Begin
  if n>0 then
     begin
       Disk(n-1,a,c,b);
       Writeln(‘Äèñê ‘,n, ’ c ‘, a,’->’, b);
       Disk(n-1,c,b,a);
     end;
End;
BEGIN
  a := ‘A’; b := ‘B’; c := ‘C’;
  Disk(k,a,b,c);
 ReadLn;
END.

Êîíòðîëüíûå âîïðîñû

1. Íà ÷åì îñíîâàí ðåêóðñèâíûé ìåòîä ïðîãðàììèðîâàíèÿ?
2.  ÷åì ðàçíèöà ìåæäó «öèêëè÷åñêèì» è «ðåêóðñèâíûì» ñïîñîáàìè îïðåäåëåíèÿ? Êàêîé ýëåìåíò ÿâëÿåòñÿ îáÿçàòåëüíûì â ðåêóðñèâíîì îïðåäåëåíèè?
3. ×òî òàêîå «ôðåéì àêòèâàöèè»?
4. Ê êàêèì ïîñëåäñòâèÿì ïðèâîäèò «ðåêóðñèâíîå çàöèêëèâàíèå»?
5. Êàêîå óñëîâèå äîëæíî îáÿçàòåëüíî ïðèñóòñòâîâàòü â ëþáîé ðåêóðñèâíîé ïðîöåäóðå?
6. ×òî òàêîå ÿâíàÿ è êîñâåííàÿ ðåêóðñèè?
7. Äàéòå ðåêóðñèâíîå îïðåäåëåíèå öåëîé ñòåïåíè ÷èñëà N.

Âàðèàíòû çàäàíèé

1. Ââåñòè ïîñëåäîâàòåëüíîñòü ÷èñåë (îêîí÷àíèå ââîäà – 0) è âûâåñòè èõ â îáðàòíîé ïîñëåäîâàòåëüíîñòè. Âõîäíûå äàííûå âçÿòü èç òåêñòîâîãî ôàéëà.
2. Èñïîëüçóÿ êîìàíäû write(x) ëèøü ïðè x=0..9, íàïèñàòü ðåêóðñèâíóþ ïðîãðàììó ïå÷àòè äåñÿòè÷íîé çàïèñè öåëîãî ïîëîæèòåëüíîãî ÷èñëà n.
3. Íàïèøèòå ðåêóðñèâíóþ ôóíêöèþ, êîòîðàÿ âîçâðàùàåò ñðåäíåå èç n ýëåìåíòîâ ìàññèâà ÷èñåë.
4. Íàéòè ïåðâûå N ÷èñåë Ôèáîíà÷÷è äâóìÿ ñïîñîáàìè: ñ ïîìîùüþ ðåêóðñèè è ñ ïîìîùüþ èòåðàöèè. Ñðàâíèòü ýôôåêòèâíîñòü àëãîðèòìîâ.
5. Íàïèñàòü ôóíêöèþ ñëîæåíèÿ äâóõ ÷èñåë, èñïîëüçóÿ òîëüêî ïðèáàâëåíèå åäèíèöû.
6. Íàïèñàòü ôóíêöèþ óìíîæåíèÿ äâóõ ÷èñåë, èñïîëüçóÿ òîëüêî îïåðàöèþ ñëîæåíèÿ.
7. Âû÷èñëèòü ñóììó ýëåìåíòîâ îäíîìåðíîãî ìàññèâà.
8. Íàéòè ÍÎÄ (íàèáîëüøèé îáùèé äåëèòåëü) äâóõ íàòóðàëüíûõ ÷èñåë.
9. Âû÷èñëèòü íåñêîëüêî çíà÷åíèé ôóíêöèè Àêêåðìàíà äëÿ íåîòðèöàòåëüíûõ ÷èñåë m è n:
10. Íàïèøèòå ðåêóðñèâíóþ ôóíêöèþ, êîòîðàÿ âû÷èñëÿåò äëèíó ñòðîêè.
11. Íàïèñàòü ôóíêöèþ C(m,n) âû÷èñëåíèÿ áèíîìèàëüíûõ êîýôôèöèåíòîâ ïî ñëåäóþùåé ôîðìóëå:
12. Ïðîâåðèòü, ÿâëÿåòñÿ ëè ôðàãìåíò ñòðîêè ñ i-ãî ïî j-é ñèìâîë ïàëèíäðîìîì.
13. Âû÷èñëèòü ïðîèçâåäåíèå ýëåìåíòîâ îäíîìåðíîãî ìàññèâà.
14. Íàïèñàòü ïðîöåäóðó ñîðòèðîâêè ìàññèâà ìåòîäîì ïðîñòîãî âûáîðà.
15. Ïîäñ÷èòàòü êîëè÷åñòâî öèôð â çàäàííîì ÷èñëå.
16. Íàïèñàòü ôóíêöèþ, ïðîâåðÿþùóþ ïðàâèëüíîñòü èìåíè â ÿçûêå Pascal.
17. Íàïèñàòü ôóíêöèþ êîòîðàÿ ìåòîäîì äåëåíèÿ îòðåçêà ïîïîëàì (ìåòîäîì äèõîòîìèè) íàõîäèò ñ òî÷íîñòüþ eps êîðåíü óðàâíåíèÿ f(x) = 0 íà îòðåçêå [a,b] (). Ìåòîä äèõîòîìèè îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì. Åñëè f(a) è f(b) èìåþò ðàçíûå çíàêè, òî ìåæäó òî÷êàìè a è b ñóùåñòâóåò êîðåíü R. Ïóñòü – ñðåäíÿÿ òî÷êà â èíòåðâàëå Åñëè f(m) = 0, òî êîðåíü R=m. Åñëè íåò, òî ëèáî f(a) è f(m) èìåþò ðàçíûå çíàêè , ëèáî f(m) è f(b) èìåþò ðàçíûå çíàêè. Åñëè, òî êîðåíü ëåæèò â èíòåðâàëå  ïðîòèâíîì ñëó÷àå îí ëåæèò â èíòåðâàëå Òåïåðü âûïîëíèì ýòî äåéñòâèå äëÿ íîâîãî èíòåðâàëà – ïîëîâèíû èñõîäíîãî èíòåðâàëà. Ïðîöåññ ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà èíòåðâàë íå ñòàíåò ìåíüøå eps.
18.  òåêñòîâîì ôàéëå çàäàíà ïîñëåäîâàòåëüíîñòü ïîëîæèòåëüíûõ ÷èñåë, çà êîòîðîé ñëåäóåò îòðèöàòåëüíîå ÷èñëî. Íàïèñàòü ôóíêöèþ áåç ïàðàìåòðîâ äëÿ íàõîæäåíèÿ ñóììû ýòèõ ïîëîæèòåëüíûõ ÷èñåë.
19. Íàïèñàòü ôóíêöèþ áåç ïàðàìåòðîâ, êîòîðàÿ ïîäñ÷èòûâàåò êîëè÷åñòâî öèôð â òåêñòå, çàäàííîì â òåêñòîâîì ôàéëå (çà òåêñòîì ñëåäóåò òî÷êà).
20. Ðàññòîÿíèÿ ìåæäó ãîðîäàìè çàäàíû ìàòðèöåé (Åñëè ìåæäó ãîðîäàìè i,j åñòü ïðÿìîé ïóòü ñ ðàññòîÿíèåì N, òî ýëåìåíòû ìàòðèöû A(i,j) è A(j,i) ñîäåðæàò çíà÷åíèå N, èíà÷å 0). Íàïèñàòü ïðîãðàììó ïîèñêà ìèíèìàëüíîãî ïóòè äëÿ ïðîèçâîëüíîé ïàðû ãîðîäîâ.
21. Âû÷èñëèòü îïðåäåëèòåëü ìàòðèöû, ïîëüçóÿñü ôîðìóëîé ðàçëîæåíèÿ ïî ïåðâîé ñòðîêå:
ãäå ìàòðèöà Bk ïîëó÷àåòñÿ èç A âû÷åðêèâàíèåì ïåðâîé ñòðîêè è k-ãî ñòîëáöà.
22. Íàïèñàòü ôóíêöèþ îïðåäåëåíèÿ, ÿâëÿåòñÿ ëè çàäàííîå íàòóðàëüíîå ÷èñëî ïðîñòûì.
23. Ðåàëèçîâàòü ðåêóðñèâíûé àëãîðèòì ïîñòðîåíèÿ öåïî÷êè èç èìåþùåãîñÿ íàáîðà êîñòåé äîìèíî.
24. Ðàññòîÿíèÿ ìåæäó ãîðîäàìè çàäàíû ìàòðèöåé (Åñëè ìåæäó ãîðîäàìè i,j åñòü ïðÿìîé ïóòü ñ ðàññòîÿíèåì N, òî ýëåìåíòû ìàòðèöû A(i,j) è A(j,i) ñîäåðæàò çíà÷åíèå N, èíà÷å 0). Íàïèñàòü ïðîãðàììó ïîèñêà ìèíèìàëüíîãî ïóòè îáõîäà âñåõ ãîðîäîâ áåç ïîñåùåíèÿ äâàæäû îäíîãî è òîãî æå ãîðîäà (çàäà÷à êîììèâîÿæåðà).
25. Çàäàí íàáîð ñëîâ. Ïîñòðîèòü èç íèõ ëþáóþ öåïî÷êó òàêèì îáðàçîì, ÷òîáû ñèìâîë â êîíöå ñëîâà ñîâïàäàë ñ ñèìâîëîì â íà÷àëå ñëåäóþùåãî.
26. Çàäàí ìàññèâ öåëûõ. Ïîñòðîèòü èç íèõ ëþáóþ ïîñëåäîâàòåëüíîñòü òàêèì îáðàçîì, ÷òîáû ïîñëåäíÿÿ öèôðà ïðåäûäóùåãî ÷èñëà ñîâïàäàëà ñ ïåðâîé öèôðîé ñëåäóþùåãî.
27. Äëÿ äàííîãî n íàïå÷àòàéòå êîýôôèöèåíòû ðàçëîæåíèÿ ïîëèíîìà (1 + x)n.
28. Âû÷èñëèòü, èñïîëüçóÿ ðåêóðñèþ, âûðàæåíèå
29. Íàïèñàòü ïðîöåäóðó ïå÷àòè âñåõ ïåðåñòàíîâîê èç n ñèìâîëîâ.
30. Íàïèñàòü ïðîöåäóðó ïåðåâîäà ÷èñëà èç äåñÿòè÷íîé ñèñòåìû ñ÷èñëåíèÿ â äâîè÷íóþ.
Íàçàä
Íà ãëàâíóþ
    Ó÷åáíèê ïî ÿçûêó Pascal          Ëàáîðàòîðíûå ðàáîòû ïî ïðîãðàììèðîâàíèþ          Ñïðàâî÷íèê


Внимание! Е�ли у ва� не получило�ь найти нужную информацию, и�пользуйте рубрикатор или во�пользуйте�ь пои�ком


.


книги по программированию и�ходники компоненты шаблоны �айтов C++ PHP Delphi �качать