{"id":233217,"date":"2023-02-08T12:11:00","date_gmt":"2023-02-08T09:11:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233217"},"modified":"2022-11-10T19:56:24","modified_gmt":"2022-11-10T16:56:24","slug":"koodausharjoitus-portaiden-kiipeaeminen-fibonacci-numerot-c-online-judge","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/fi\/koodausharjoitus-portaiden-kiipeaeminen-fibonacci-numerot-c-online-judge\/","title":{"rendered":"Koodausharjoitus &#8211; Portaiden kiipe\u00e4minen &#8211; Fibonacci-numerot &#8211; C++ &#8211; Online Judge"},"content":{"rendered":"<p><strong>Kysymys:<\/strong> Kiipe\u00e4t portaita. Huipulle p\u00e4\u00e4seminen kest\u00e4\u00e4 n askelta. Joka kerta voit ottaa 1 tai 2 askelta. Kuinka monta erilaista tapaa p\u00e4\u00e4st\u00e4 huipulle?<\/p>\n<p><strong>Ongelman kuvaus<\/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>T\u00e4m\u00e4 ongelma saattaa aluksi n\u00e4ytt\u00e4\u00e4 vaikealta, mutta kun ajattelet hetken, saatat l\u00f6yt\u00e4\u00e4 sen niin helpoksi. Vastaus on <a href=\"https:\/\/helloacm.com\/fibonacci-numbers-windows-batch-programming-revisited\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">Fibonacci-luvut<\/a> (katso <a href=\"https:\/\/helloacm.com\/iterative-computing-fib-number-using-excel\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">t\u00e4st\u00e4<\/a>, <a href=\"https:\/\/helloacm.com\/fib-number-inline-assembly-delphi\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">t\u00e4\u00e4lt\u00e4<\/a> )<\/p>\n<p>No, alkuper\u00e4iset Fibonacci-luvut m\u00e4\u00e4ritell\u00e4\u00e4n sarjoiksi:<\/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=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" ><\/a><\/p>\n<p>T\u00e4t\u00e4 ongelmaa varten meid\u00e4n on vain muutettava hieman:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e819351b.png\" alt=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" \/>ja <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e827d250.png\" alt=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" \/>koska vain yhdelle vaiheelle on vain yksi erillinen tapa ja kahdelle vaiheelle, meill\u00e4 on kaksi ratkaisua: 1 + 1 tai 2.<\/p>\n<p>Loput ovat kuin Fibonacci-sarja. Koska <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8370df1.png\" alt=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" \/>nykyisest\u00e4 sijainnista, olemme mahdollisesti kahdesta edellisest\u00e4 paikasta, F(n-1) ja F(n-2).<\/p>\n<p>Voit k\u00e4ytt\u00e4\u00e4 rekursiota, mutta t\u00e4m\u00e4 voidaan ratkaista tehokkaammalla iteratiivisella ratkaisulla.<\/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>Tai pid\u00e4t yksinkertaisemmasta rekursiivisesta funktiosta:<\/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>Huomautus: Rekursiivinen antaa\u00a0 testiss\u00e4 44 <strong>AIKARAJA YLITTYY<\/strong>. T\u00e4m\u00e4 johtuu siit\u00e4, ett\u00e4 rekursiivinen funktio yleens\u00e4 laskee v\u00e4liarvot monta kertaa. Esimerkiksi <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e846babc.png\" alt=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" \/>, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8555f24.png\" alt=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" \/>. <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8638fbc.png\" alt=\"Koodausharjoitus - Portaiden kiipe\u00e4minen - Fibonacci-numerot - C++ - Online Judge\" \/>\u00a0lasketaan kahdesti.<\/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>Koodausharjoitus \u2013 Portaiden kiipe\u00e4minen \u2013 Fibonacci-numerot \u2013 C++ \u2013 Online-tuomari<\/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":[719,895,843],"tags":[1166],"class_list":["post-233217","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-kehittaejae","category-koodi","category-opetusohjelmia","tag-affiai-fi"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/posts\/233217","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/comments?post=233217"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/posts\/233217\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/media?parent=233217"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/categories?post=233217"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fi\/wp-json\/wp\/v2\/tags?post=233217"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}