{"id":233219,"date":"2023-02-08T11:31:00","date_gmt":"2023-02-08T08:31:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233219"},"modified":"2022-11-10T19:57:16","modified_gmt":"2022-11-10T16:57:16","slug":"exercicio-de-codificacao-subindo-escadas-numeros-de-fibonacci-c-juiz-online","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/pt-pt\/exercicio-de-codificacao-subindo-escadas-numeros-de-fibonacci-c-juiz-online\/","title":{"rendered":"Exerc\u00edcio de codifica\u00e7\u00e3o &#8211; Subindo escadas &#8211; N\u00fameros de Fibonacci &#8211; C++ &#8211; Juiz Online"},"content":{"rendered":"<p><strong>Pergunta:<\/strong> Voc\u00ea est\u00e1 subindo escadas. S\u00e3o necess\u00e1rios n passos para chegar ao topo. Cada vez, voc\u00ea pode dar 1 passo ou 2 passos. Quantas maneiras distintas de chegar ao topo?<\/p>\n<p><strong>Descri\u00e7\u00e3o do problema<\/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>Esse problema pode parecer dif\u00edcil no come\u00e7o, mas quando voc\u00ea pensa por um segundo, pode achar muito f\u00e1cil. A resposta \u00e9 <a href=\"https:\/\/helloacm.com\/fibonacci-numbers-windows-batch-programming-revisited\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">N\u00fameros de Fibonacci<\/a> (veja <a href=\"https:\/\/helloacm.com\/iterative-computing-fib-number-using-excel\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">aqui<\/a>, <a href=\"https:\/\/helloacm.com\/fib-number-inline-assembly-delphi\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">aqui<\/a> )<\/p>\n<p>Bem, os N\u00fameros de Fibonacci originais s\u00e3o definidos como sequ\u00eancias:<\/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=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" ><\/a><\/p>\n<p>Para este problema, basta modificar um pouco:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e819351b.png\" alt=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" \/>e <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e827d250.png\" alt=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" \/>porque para apenas 1 passo, h\u00e1 apenas 1 caminho distinto e para 2 passos, temos duas solu\u00e7\u00f5es: 1 + 1 ou 2.<\/p>\n<p>O resto \u00e9 como s\u00e9rie de Fibonacci. O <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8370df1.png\" alt=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" \/>porque da posi\u00e7\u00e3o atual, possivelmente somos das duas posi\u00e7\u00f5es anteriores, F(n-1) e F(n-2).<\/p>\n<p>Voc\u00ea pode usar recurs\u00e3o, mas isso pode ser resolvido por uma solu\u00e7\u00e3o iterativa mais eficaz.<\/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>Ou voc\u00ea prefere uma fun\u00e7\u00e3o recursiva mais direta:<\/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>Nota: A recursiva produzir\u00e1 <strong>TIME LIMIT EXCEEDED<\/strong> no teste 44. Isso porque, a fun\u00e7\u00e3o recursiva normalmente calcula valores intermedi\u00e1rios muitas e muitas vezes. Por exemplo, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e846babc.png\" alt=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" \/>, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8555f24.png\" alt=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" \/>. <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8638fbc.png\" alt=\"Exerc\u00edcio de codifica\u00e7\u00e3o - Subindo escadas - N\u00fameros de Fibonacci - C++ - Juiz Online\" \/>\u00a0\u00e9 calculado duas vezes.<\/p>\n<p><div id=\"PostUnique_PostSource\" style=\"padding-top: 50px\">Fonte de grava\u00e7\u00e3o:  <a target=\"_blank\" rel=\"noopener nofollow\" href=\"\/\/helloacm.com\" class=\"external external_icon\">helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Exerc\u00edcio de codifica\u00e7\u00e3o \u2013 Subindo escadas \u2013 N\u00fameros de Fibonacci \u2013 C++ \u2013 Juiz 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":[898,722,846],"tags":[1170],"class_list":["post-233219","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codigo-2","category-desenvolvedor","category-tutoriais","tag-affiai-pt-pt"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/posts\/233219","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/comments?post=233219"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/posts\/233219\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/media?parent=233219"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/categories?post=233219"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/pt-pt\/wp-json\/wp\/v2\/tags?post=233219"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}