{"id":233208,"date":"2023-02-08T12:05:00","date_gmt":"2023-02-08T09:05:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233208"},"modified":"2022-11-10T19:53:15","modified_gmt":"2022-11-10T16:53:15","slug":"ejercicio-de-codificacion-subir-escaleras-numeros-de-fibonacci-c-juez-en-linea","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/es\/ejercicio-de-codificacion-subir-escaleras-numeros-de-fibonacci-c-juez-en-linea\/","title":{"rendered":"Ejercicio de codificaci\u00f3n &#8211; Subir escaleras &#8211; N\u00fameros de Fibonacci &#8211; C++ &#8211; Juez en l\u00ednea"},"content":{"rendered":"<p><strong>Pregunta:<\/strong> Est\u00e1s subiendo escaleras. Se necesitan n pasos para llegar a la cima. Cada vez, puede dar 1 paso o 2 pasos. \u00bfCu\u00e1ntas maneras distintas de llegar a la cima?<\/p>\n<p><strong>Descripci\u00f3n del 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>Este problema puede parecer dif\u00edcil al principio, pero cuando piensas por un segundo, puede que te resulte muy f\u00e1cil. La respuesta es <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> (ver <a href=\"https:\/\/helloacm.com\/iterative-computing-fib-number-using-excel\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">aqu\u00ed<\/a>, <a href=\"https:\/\/helloacm.com\/fib-number-inline-assembly-delphi\/\" target=\"_blank\" rel=\"noopener nofollow\" class=\"external external_icon\">aqu\u00ed<\/a> )<\/p>\n<p>Bueno, los n\u00fameros de Fibonacci originales se definen como secuencias:<\/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=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" ><\/a><\/p>\n<p>Para este problema, solo tenemos que modificar un poco:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e819351b.png\" alt=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" \/>y <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e827d250.png\" alt=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" \/>porque para solo 1 paso, solo hay 1 manera distinta y para 2 pasos, tenemos dos soluciones: 1 + 1 o 2.<\/p>\n<p>El resto es como serie de Fibonacci. El <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8370df1.png\" alt=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" \/>porque desde la posici\u00f3n actual, posiblemente estemos desde las dos posiciones anteriores, F(n-1) y F(n-2).<\/p>\n<p>Puede usar la recursividad, pero esto se puede resolver mediante una soluci\u00f3n iterativa m\u00e1s efectiva.<\/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>O prefiere una funci\u00f3n recursiva m\u00e1s directa:<\/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: La recursiva producir\u00e1 <strong>TIME LIMIT EXCEEDED<\/strong> en la prueba 44. Esto se debe a que la funci\u00f3n recursiva generalmente calcula valores intermedios muchas veces. Por ejemplo, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e846babc.png\" alt=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" \/>, <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8555f24.png\" alt=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" \/>. <img decoding=\"async\" src=\"https:\/\/wordpress.mediadoma.com\/wp-content\/uploads\/2022\/01\/post-154376-61e53e8638fbc.png\" alt=\"Ejercicio de codificaci\u00f3n - Subir escaleras - N\u00fameros de Fibonacci - C++ - Juez en l\u00ednea\" \/>\u00a0se calcula dos veces.<\/p>\n<p><div id=\"PostUnique_PostSource\" style=\"padding-top: 50px\">Fuente de grabaci\u00f3n:  <a target=\"_blank\" rel=\"noopener nofollow\" href=\"\/\/helloacm.com\" class=\"external external_icon\">helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ejercicio de codificaci\u00f3n \u2013 Subir escaleras \u2013 N\u00fameros de Fibonacci \u2013 C++ \u2013 Juez en l\u00ednea<\/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":[892,716,840],"tags":[1172],"class_list":["post-233208","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codigo","category-desarrollador","category-tutoriales","tag-affiai-es"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/posts\/233208","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/comments?post=233208"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/posts\/233208\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/media?parent=233208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/categories?post=233208"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/es\/wp-json\/wp\/v2\/tags?post=233208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}