{"id":233255,"date":"2023-02-08T11:45:00","date_gmt":"2023-02-08T08:45:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233255"},"modified":"2022-11-10T20:08:38","modified_gmt":"2022-11-10T17:08:38","slug":"esercizio-di-codifica-salire-le-scale-numeri-di-fibonacci-c-giudice-online","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/it\/esercizio-di-codifica-salire-le-scale-numeri-di-fibonacci-c-giudice-online\/","title":{"rendered":"Esercizio di codifica – Salire le scale – Numeri di Fibonacci – C++ – Giudice online"},"content":{"rendered":"

Domanda:<\/strong> Stai salendo le scale. Ci vogliono n passi per arrivare in cima. Ogni volta, puoi fare 1 passo o 2 passi. Quanti modi distinti per arrivare in cima?<\/p>\n

Descrizione del problema<\/strong>: http:\/\/oj.leetcode.com\/problems\/climbing-stairs\/<\/a><\/p>\n

Questo problema pu\u00f2 sembrare difficile all’inizio, ma quando ci pensi per un secondo, potresti trovarlo cos\u00ec facile. La risposta \u00e8 Numeri di Fibonacci<\/a> (vedi qui<\/a>, qui<\/a> )<\/p>\n

Ebbene, i Numeri di Fibonacci originali sono definiti come sequenze:<\/p>\n

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

Per questo problema, dobbiamo solo modificare un po’:<\/p>\n

\"Esercizioe \"Eserciziopoich\u00e9 per 1 solo passaggio, c’\u00e8 solo 1 modo distinto e per 2 passaggi, abbiamo due soluzioni: 1 + 1 o 2.<\/p>\n

Il resto \u00e8 come la serie di Fibonacci. Il \"Esercizioperch\u00e9 dalla posizione attuale, siamo forse dalle due posizioni precedenti, F(n-1) e F(n-2).<\/p>\n

Puoi usare la ricorsione, ma questo pu\u00f2 essere risolto con una soluzione iterativa pi\u00f9 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
Oppure preferisci una funzione ricorsiva pi\u00f9 semplice:<\/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
Nota: il ricorsivo produrr\u00e0 TIME LIMIT EXCEEDED<\/strong> sul test 44. Questo perch\u00e9 la funzione ricorsiva di solito calcola i valori intermedi molte volte. Ad esempio, \"Esercizio, \"Esercizio. \"Esercizio\u00a0\u00e8 calcolato due volte.<\/p>\n
Fonte di registrazione:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Esercizio di codifica \u2013 Salire le scale \u2013 Numeri di Fibonacci \u2013 C++ \u2013 Giudice 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":[896,720,844],"tags":[1168],"class_list":["post-233255","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-codice","category-sviluppatore","category-tutorial","tag-affiai-it"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/posts\/233255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/comments?post=233255"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/posts\/233255\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/media?parent=233255"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/categories?post=233255"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/it\/wp-json\/wp\/v2\/tags?post=233255"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}