{"id":43889,"date":"2021-12-22T14:10:38","date_gmt":"2021-12-22T13:10:38","guid":{"rendered":"https:\/\/zsetrakowice.pl\/elearning\/?p=43889"},"modified":"2021-12-19T20:16:13","modified_gmt":"2021-12-19T19:16:13","slug":"informatyka-3-alo-sroda","status":"publish","type":"post","link":"https:\/\/zsetrakowice.pl\/elearning\/2021\/12\/22\/informatyka-3-alo-sroda\/","title":{"rendered":"Informatyka 3 ALO (\u015broda)"},"content":{"rendered":"
\n
\n
\n
Temat: Rekurencja (lekcja 1\/3)<\/strong><\/div>\n
Czy widzia\u0142e\u015b kiedy\u015b Matrioszk\u0119 – zestaw rosyjskich laleczek? Na pocz\u0105tku widzisz tylko jedn\u0105 figurk\u0119, zwykle pomalowane drewno, kt\u00f3re wygl\u0105da tak:<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
<\/div>\n

\"\"<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n
\n
\n
Mo\u017cesz zdj\u0105\u0107 g\u00f3rna po\u0142ow\u0119 pierwszej figurki i co zobaczysz w \u015brodku? Kolejn\u0105, nieco mniejsz\u0105 rosyjsk\u0105 lalk\u0119!<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
<\/div>\n

\"\"<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n
\n
\n
Mo\u017cesz wyj\u0105\u0107 t\u0119 lalk\u0119 i rozdzieli\u0107 g\u00f3rna po\u0142ow\u0119 od dolnej. Wtedy zobaczysz kolejn\u0105 jeszcze mniejsz\u0105 Matrioszk\u0119:<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
<\/div>\n

\"\"<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n
\n
\n
I jeszcze raz:<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
<\/div>\n

\"\"<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n
\n
\n
I mo\u017cesz tak kontynuowa\u0107 i rozdziela\u0107 kolejne figurki. Ostatecznie znajdziesz male\u0144k\u0105 rosyjsk\u0105 laleczk\u0119, zbudowan\u0105 z jednego kawa\u0142ka drewna, w zwi\u0105zku z tym, ostatnia ju\u017c si\u0119 nie otwiera:<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n
\n
\n
<\/div>\n

\"\"<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n
\n
\n
Rozpocz\u0119li\u015bmy od jednej du\u017cej rosyjskiej lalki, a potem znajdowali\u015bmy coraz to mniejsze laleczki, dop\u00f3ki nie zobaczyli\u015bmy tak ma\u0142ej, \u017ce nie mog\u0142a ona ju\u017c w \u015brodku pomie\u015bci\u0107 nast\u0119pnej.<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
Co ma wsp\u00f3lnego Matrioszka z algorytmami? Tak jak rosyjska lalka ma w sobie mniejsz\u0105 lalk\u0119, a ta posiada jeszcze mniejsz\u0105 i tak dalej a\u017c trafimy na laleczk\u0119, kt\u00f3ra jest zbyt ma\u0142a, aby pomie\u015bci\u0107 nast\u0119pn\u0105, tak my zobaczymy jak zaprojektowa\u0107 algorytm, kt\u00f3ry rozwi\u0105\u017ce problem, rozwi\u0105zuj\u0105c najpierw mniejszy przypadek tego samego problemu, dop\u00f3ki ten problem nie jest tak ma\u0142y, aby rozwi\u0105za\u0107 go bezpo\u015brednio. Tak\u0105 technik\u0119 nazywamy\u00a0rekurencj\u0105<\/strong>.<\/div>\n
\n

Stosowanie rekurencji jest charakterystyczne dla algorytm\u00f3w projektowanych metod\u0105\u00a0dziel i zwyci\u0119\u017caj<\/i><\/a>.<\/p>\n

Typowym problemem, dla kt\u00f3rego mo\u017cna zastosowa\u0107 rekurencj\u0119, jest obliczanie silni. Przypomnijmy, \u017ce silnia z\u00a0n<\/i>\u00a0jest zdefiniowana jako\u00a0n!=1\u00d72\u00d7\u2026\u00d7n<\/i>. Funkcja ta mo\u017ce by\u0107 r\u00f3wnowa\u017cnie zapisana jako:<\/p>\n

n!=(n\u22121)!\u00d7n<\/i>, dla\u00a0n>0<\/i>,
\nn!=1<\/i>, dla\u00a0n=0<\/i>.<\/p>\n

W powy\u017cszym przyk\u0142adzie g\u00f3rny wiersz jest og\u00f3lnym r\u00f3wnaniem rekurencji, za\u015b dolny wiersz jest warto\u015bci\u0105 brzegow\u0105. W j\u0119zyku C++ powy\u017csza funkcja by\u0142aby zapisana w poni\u017cszy spos\u00f3b.<\/p>\n

int silnia(int n)\r\n{\r\n    if (n > 0)\r\n    {\r\n        return n * silnia(n-1);\r\n    }\r\n    else\r\n    {\r\n        return 1;\r\n    }\r\n};<\/span><\/pre>\n
Przekszta\u0142cenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, kt\u00f3ra nie zawiera odwo\u0142ania do samej siebie) jest okre\u015blane jako\u00a0rozwi\u0105zanie rekurencji<\/strong>.<\/p>\n
Przyk\u0142ad 1<\/h4>\n
Prze\u015bled\u017amy program wyznaczaj\u0105cy sum\u0119\u00a0n\u00a0<\/strong>kolejnych liczb naturalnych.<\/p>\n
#include<\/span> <iostream><\/span><\/span>\r\nusing<\/span> namespace<\/span> std<\/span>;\r\n\r\nlong<\/span> long<\/span> suma<\/span>(int<\/span> n)<\/span>\r\n<\/span>{\r\n\tif<\/span>(n<1<\/span>) \r\n\t\treturn<\/span> 0<\/span>;\r\n\t\r\n\treturn<\/span> n+suma(n-1<\/span>);\r\n}\r\n\r\nint<\/span> main<\/span>()<\/span>\r\n<\/span>{\r\n\tint<\/span> n;\r\n\t\r\n\tcout<\/span><<\"Podaj liczb\u0119: \"<\/span>;\r\n\tcin<\/span>>>n;\r\n\t\r\n\tcout<\/span><<\"Suma \"<\/span><<n<<\" kolejnych liczb naturalnych wynosi \"<\/span>\r\n<<suma(n)<<endl<\/span>;\r\n\r\n\treturn<\/span> 0<\/span>;\r\n}\r\n<\/code><\/pre>\n
Za\u0142\u00f3\u017cmy, \u017ce na wej\u015bciu podali\u015bmy liczb\u0119\u00a05<\/strong>\u00a0(program ma wyznaczy\u0107 sum\u0119\u00a01+ 2+ 3 + 4 + 5<\/strong>).<\/p>\n
wynik<\/strong>\u00a0= suma<\/em>(5);<\/p>\n
Funkcja\u00a0suma<\/em>(n<\/strong>), wywo\u0142a\u0142a si\u0119 z argumentem r\u00f3wnym\u00a05<\/strong>. Najpierw sprawdzamy, czy\u00a0n< 1<\/strong>\u00a0(5 < 1<\/strong>). Warunek jest fa\u0142szywy, przechodzimy wi\u0119c do nast\u0119pnej linijki\u00a0return<\/strong>\u00a05<\/strong>\u00a0+\u00a0suma<\/em>(5 – 1<\/strong>) . Funkcja suma wywo\u0142ana zosta\u0142a przez sam\u0105 siebie z argumentem r\u00f3wnym 4, a wi\u0119c mamy:<\/p>\n
wynik<\/strong>\u00a0=\u00a0suma<\/em>(5) = 5 +\u00a0suma<\/em>(4),<\/p>\n
dan\u0105 czynno\u015b\u0107 powtarzamy do momentu, gdy argument osi\u0105gnie warto\u015b\u0107\u00a00<\/strong>,<\/p>\n
wtedy funkcja zwr\u00f3ci\u00a00<\/strong>\u00a0(0<1<\/strong>,\u00a0prawda<\/strong>).<\/p>\n
wynik =\u00a0suma<\/em>(5) = 5 +\u00a0suma<\/em>(4) = 5 + 4 +\u00a0suma<\/em>(3) = 5 + 4 + 3 +\u00a0suma<\/em>(2) = 5 + 4 + 3 + 2 +\u00a0suma<\/em>(1) =<\/p>\n
5 + 4 + 3 + 2 + 1 +\u00a0suma<\/em>(0) = 5 + 4 + 3 + 2 + 1 + 0 = 15.<\/p>\n
Na dzi\u015b to tyle z podstaw, mam nadzieje, \u017ce zrozumieli\u015bcie.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Temat: Rekurencja (lekcja 1\/3) Czy widzia\u0142e\u015b kiedy\u015b Matrioszk\u0119 – zestaw rosyjskich laleczek? Na pocz\u0105tku widzisz tylko jedn\u0105 figurk\u0119, zwykle pomalowane drewno, kt\u00f3re wygl\u0105da tak: Mo\u017cesz zdj\u0105\u0107 g\u00f3rna po\u0142ow\u0119 pierwszej figurki i co zobaczysz w \u015brodku? Kolejn\u0105, nieco mniejsz\u0105 rosyjsk\u0105 lalk\u0119! Mo\u017cesz wyj\u0105\u0107 t\u0119 lalk\u0119 i rozdzieli\u0107 g\u00f3rna po\u0142ow\u0119 od dolnej. Wtedy zobaczysz kolejn\u0105 jeszcze mniejsz\u0105 […]<\/p>\n","protected":false},"author":34,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[104,13],"tags":[],"_links":{"self":[{"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/posts\/43889"}],"collection":[{"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/users\/34"}],"replies":[{"embeddable":true,"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/comments?post=43889"}],"version-history":[{"count":1,"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/posts\/43889\/revisions"}],"predecessor-version":[{"id":43890,"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/posts\/43889\/revisions\/43890"}],"wp:attachment":[{"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/media?parent=43889"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/categories?post=43889"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zsetrakowice.pl\/elearning\/wp-json\/wp\/v2\/tags?post=43889"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}