{"id":234186,"date":"2023-02-08T11:44:00","date_gmt":"2023-02-08T08:44:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=234186"},"modified":"2022-11-11T23:26:56","modified_gmt":"2022-11-11T20:26:56","slug":"exercice-de-codage-monter-des-escaliers-nombres-de-fibonacci-c-juge-en-ligne","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/fr\/exercice-de-codage-monter-des-escaliers-nombres-de-fibonacci-c-juge-en-ligne\/","title":{"rendered":"Exercice de codage – Monter des escaliers – Nombres de Fibonacci – C++ – Juge en ligne"},"content":{"rendered":"

Question\u00a0:<\/strong> Vous montez des escaliers. Il faut n \u00e9tapes pour arriver au sommet. A chaque fois, vous pouvez faire 1 pas ou 2 pas. Combien de fa\u00e7ons distinctes d’arriver au sommet\u00a0?<\/p>\n

Description du probl\u00e8me<\/strong>: http:\/\/oj.leetcode.com\/problems\/climbing-stairs\/<\/a><\/p>\n

Ce probl\u00e8me peut sembler difficile au premier abord, mais quand vous y r\u00e9fl\u00e9chissez une seconde, vous pourriez le trouver si facile. La r\u00e9ponse est les nombres de Fibonacci<\/a> (voir ici<\/a>, ici<\/a> )<\/p>\n

Eh bien, les nombres de Fibonacci originaux sont d\u00e9finis comme des s\u00e9quences\u00a0:<\/p>\n

\"Exercice<\/a><\/p>\n

Pour ce probl\u00e8me, il suffit de modifier un peu :<\/p>\n

\"Exerciceet \"Exerciceparce que pour 1 seule \u00e9tape, il n’y a qu’1 chemin distinct et pour 2 \u00e9tapes, on a deux solutions: 1 + 1 ou 2.<\/p>\n

Le reste est en s\u00e9rie de Fibonacci. Le \"Exerciceparce qu’\u00e0 partir de la position actuelle, nous sommes peut-\u00eatre des deux positions pr\u00e9c\u00e9dentes, F(n-1) et F(n-2).<\/p>\n

Vous pouvez utiliser la r\u00e9cursivit\u00e9, mais cela peut \u00eatre r\u00e9solu par une solution it\u00e9rative plus efficace.<\/p>\n

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 <= 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
Ou vous pr\u00e9f\u00e9rez une fonction r\u00e9cursive plus simple :<\/p>\n
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
Remarque: La fonction r\u00e9cursive donnera TIME LIMIT EXCEEDED<\/strong> sur le test 44. En effet, la fonction r\u00e9cursive calcule g\u00e9n\u00e9ralement des valeurs interm\u00e9diaires plusieurs fois. Par exemple, \"Exercice, \"Exercice. \"Exercice\u00a0est calcul\u00e9 deux fois.<\/p>\n
Source d’enregistrement:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Exercice de codage \u2013 Monter des escaliers \u2013 Nombres de Fibonacci \u2013 C++ \u2013 Juge en ligne<\/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":[893,717,841],"tags":[1167],"class_list":["post-234186","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-code-2","category-developpeur","category-tutoriels","tag-affiai-fr"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/posts\/234186","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/comments?post=234186"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/posts\/234186\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/media?parent=234186"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/categories?post=234186"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/fr\/wp-json\/wp\/v2\/tags?post=234186"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}