{"id":233227,"date":"2023-02-08T11:29:00","date_gmt":"2023-02-08T08:29:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233227"},"modified":"2022-11-10T19:59:52","modified_gmt":"2022-11-10T16:59:52","slug":"kodeerimisharjutus-trepist-ueles-ronimine-fibonacci-numbrid-c-vorgukohtunik","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/et\/kodeerimisharjutus-trepist-ueles-ronimine-fibonacci-numbrid-c-vorgukohtunik\/","title":{"rendered":"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik"},"content":{"rendered":"<p><strong>K\u00fcsimus:<\/strong> Ronite trepist. Tippu j\u00f5udmiseks kulub n sammu. Iga kord saate teha 1 v\u00f5i 2 sammu. Kui palju erinevaid viise tippu j\u00f5udmiseks?<\/p>\n<p><strong>Probleemi kirjeldus<\/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>See probleem v\u00f5ib esmapilgul tunduda keeruline, kuid kui te hetkeks j\u00e4rele m\u00f5tlete, v\u00f5ib see osutuda nii lihtsaks. Vastus on <a href=\"https:\/\/helloacm.com\/fibonacci-numbers-windows-batch-programming-revisited\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">Fibonacci numbrid<\/a> (vt <a href=\"https:\/\/helloacm.com\/iterative-computing-fib-number-using-excel\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">siit<\/a>, <a href=\"https:\/\/helloacm.com\/fib-number-inline-assembly-delphi\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">siit<\/a> )<\/p>\n<p>Algsed Fibonacci numbrid on m\u00e4\u00e4ratletud jadadena:<\/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=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" ><\/a><\/p>\n<p>Selle probleemi lahendamiseks peame lihtsalt veidi muutma:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e819351b.png\" alt=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" \/>ja <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e827d250.png\" alt=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" \/>kuna ainult 1 sammu jaoks on ainult 1 eristatav viis ja 2 sammu jaoks, on meil kaks lahendust: 1 + 1 v\u00f5i 2.<\/p>\n<p>\u00dclej\u00e4\u00e4nud on nagu Fibonacci seeria. <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8370df1.png\" alt=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" \/>Sest praegusest positsioonist oleme t\u00f5en\u00e4oliselt kahest eelmisest positsioonist, F(n-1) ja F(n-2) .<\/p>\n<p>V\u00f5ite kasutada rekursiooni, kuid seda saab lahendada t\u00f5husama iteratiivse lahendusega.<\/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>V\u00f5i eelistate lihtsamat rekursiivset funktsiooni:<\/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>M\u00e4rkus. Rekursiiv annab\u00a0 testis 44 v\u00e4\u00e4rtuse <strong>TIME LIMIT EXCEEDED<\/strong>. Seda seet\u00f5ttu, et rekursiivne funktsioon arvutab tavaliselt vahev\u00e4\u00e4rtusi mitu korda. N\u00e4iteks <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e846babc.png\" alt=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" \/>, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8555f24.png\" alt=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" \/>. <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8638fbc.png\" alt=\"Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik\" \/>\u00a0arvutatakse kaks korda.<\/p>\n<p><div id=\"PostUnique_PostSource\" style=\"padding-top: 50px\">:  <a target=\"_blank\" rel=\"noopener nofollow\" href=\"\/\/helloacm.com\" class=\"external external_icon\">helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Kodeerimisharjutus \u2013 trepist \u00fcles ronimine \u2013 Fibonacci numbrid \u2013 C++ \u2013 v\u00f5rgukohtunik<\/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":[718,894,842],"tags":[1165],"class_list":["post-233227","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-arendaja","category-kood","category-opetused","tag-affiai-et"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/posts\/233227","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/comments?post=233227"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/posts\/233227\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/media?parent=233227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/categories?post=233227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/et\/wp-json\/wp\/v2\/tags?post=233227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}