{"id":233223,"date":"2023-02-08T12:13:00","date_gmt":"2023-02-08T09:13:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233223"},"modified":"2022-11-10T19:57:55","modified_gmt":"2022-11-10T16:57:55","slug":"cwiczenie-na-kodowanie-wchodzenie-po-schodach-liczby-fibonacciego-c-sedzia-online","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/pl\/cwiczenie-na-kodowanie-wchodzenie-po-schodach-liczby-fibonacciego-c-sedzia-online\/","title":{"rendered":"\u0106wiczenie na kodowanie &#8211; Wchodzenie po schodach &#8211; Liczby Fibonacciego &#8211; C++ &#8211; S\u0119dzia online"},"content":{"rendered":"<p><strong>Pytanie:<\/strong> Wchodzisz po schodach. Aby dosta\u0107 si\u0119 na szczyt, potrzeba n krok\u00f3w. Za ka\u017cdym razem mo\u017cesz zrobi\u0107 1 krok lub 2 kroki. Na ile r\u00f3\u017cnych sposob\u00f3w mo\u017cna dosta\u0107 si\u0119 na szczyt?<\/p>\n<p><strong>Opis problemu<\/strong>: <a href=\"https:\/\/oj.leetcode.com\/problems\/climbing-stairs\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">http:\/\/oj.leetcode.com\/problems\/climbing-stairs\/<\/a><\/p>\n<p>Ten problem mo\u017ce pocz\u0105tkowo wydawa\u0107 si\u0119 trudny, ale kiedy pomy\u015blisz przez chwil\u0119, mo\u017ce si\u0119 okaza\u0107, \u017ce jest to takie proste. Odpowiedzi\u0105 s\u0105 <a href=\"https:\/\/helloacm.com\/fibonacci-numbers-windows-batch-programming-revisited\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">liczby Fibonacciego<\/a> (patrz <a href=\"https:\/\/helloacm.com\/iterative-computing-fib-number-using-excel\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">tutaj<\/a>, <a href=\"https:\/\/helloacm.com\/fib-number-inline-assembly-delphi\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">tutaj<\/a> )<\/p>\n<p>C\u00f3\u017c, oryginalne liczby Fibonacciego s\u0105 zdefiniowane jako sekwencje:<\/p>\n<p><a href=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e809257c.png\" data-rel=\"lightbox\"><img decoding=\"async\" class=\"SDStudio-light-box-enable SDStudio-editor-tools-md-imp\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e809257c.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" ><\/a><\/p>\n<p>W przypadku tego problemu musimy tylko troch\u0119 zmodyfikowa\u0107:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e819351b.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" \/>a <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e827d250.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" \/>poniewa\u017c tylko dla 1 kroku istnieje tylko 1 odr\u0119bna droga, a dla 2 krok\u00f3w mamy dwa rozwi\u0105zania: 1 + 1 lub 2.<\/p>\n<p>Reszta to seria Fibonacciego. Poniewa\u017c <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8370df1.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" \/>z obecnej pozycji jeste\u015bmy prawdopodobnie z dw\u00f3ch poprzednich pozycji, F(n-1) i F(n-2).<\/p>\n<p>Mo\u017cesz u\u017cy\u0107 rekurencji, ale mo\u017cna to rozwi\u0105za\u0107 za pomoc\u0105 bardziej efektywnego rozwi\u0105zania iteracyjnego.<\/p>\n<pre><code>class Solution {\npublic:\n\u00a0 \u00a0 int climbStairs(int n) {\n\u00a0 \u00a0 \u00a0 \u00a0 if (n == 1) return 1;\n\u00a0 \u00a0 \u00a0 \u00a0 if (n == 2) return 2;\n\u00a0 \u00a0 \u00a0 \u00a0 \/\/ f(n) = f(n - 1) + f(n - 2)\n\u00a0 \u00a0 \u00a0 \u00a0 int a = 1, b = 2, c = a + b;\n\u00a0 \u00a0 \u00a0 \u00a0 for (int i = 3; i &lt;= n; i ++) {\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 c = a + b;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 a = b;\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 b = c;\n\u00a0 \u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 \u00a0 \u00a0 return c;\n\u00a0 \u00a0 }\n};<\/code><\/pre>\n<p>Lub wolisz prostsz\u0105 funkcj\u0119 rekurencyjn\u0105:<\/p>\n<pre><code>class Solution {\npublic:\n\u00a0 \u00a0 int climbStairs(int n) {\n\u00a0 \u00a0 \u00a0 \u00a0 if (n == 1) return 1;\n\u00a0 \u00a0 \u00a0 \u00a0 if (n == 2) return 2;\n\u00a0 \u00a0 \u00a0 \u00a0 return climbStairs(n - 1) + climbStairs(n - 2);\n\u00a0 \u00a0 }\n};<\/code><\/pre>\n<p>Uwaga: Funkcja rekurencyjna zwr\u00f3ci <strong>LIMIT CZASU PRZEKROCZONY<\/strong> w te\u015bcie 44. Dzieje si\u0119 tak dlatego, \u017ce funkcja rekurencyjna zwykle oblicza warto\u015bci po\u015brednie wiele razy. Na przyk\u0142ad <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e846babc.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" \/>, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8555f24.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" \/>. <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8638fbc.png\" alt=\"\u0106wiczenie na kodowanie - Wchodzenie po schodach - Liczby Fibonacciego - C++ - S\u0119dzia online\" \/>\u00a0jest obliczana dwukrotnie.<\/p>\n<p><div id=\"PostUnique_PostSource\" style=\"padding-top: 50px\">\u0179r\u00f3d\u0142o nagrywania:  <a target=\"_blank\" rel=\"noopener nofollow\" href=\"\/\/helloacm.com\" class=\"external external_icon\">helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0106wiczenie na kodowanie \u2013 Wchodzenie po schodach \u2013 Liczby Fibonacciego \u2013 C++ \u2013 S\u0119dzia online<\/p>\n","protected":false},"author":1,"featured_media":223984,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_wp_rev_ctl_limit":""},"categories":[721,897,845],"tags":[1169],"class_list":["post-233223","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-deweloper","category-kod","category-samouczki","tag-affiai-pl"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts\/233223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/comments?post=233223"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/posts\/233223\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/media?parent=233223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/categories?post=233223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pl\/wp-json\/wp\/v2\/tags?post=233223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}