{"id":233194,"date":"2023-02-08T11:46:00","date_gmt":"2023-02-08T08:46:00","guid":{"rendered":"https:\/\/wordpress.mediadoma.com\/?p=233194"},"modified":"2022-11-10T19:50:07","modified_gmt":"2022-11-10T16:50:07","slug":"kodningsoevning-gaa-i-trappor-fibonacci-nummer-c-onlinedomare","status":"publish","type":"post","link":"https:\/\/wordpress.mediadoma.com\/sv\/kodningsoevning-gaa-i-trappor-fibonacci-nummer-c-onlinedomare\/","title":{"rendered":"Kodnings\u00f6vning – G\u00e5 i trappor – Fibonacci-nummer – C++ – Onlinedomare"},"content":{"rendered":"

Fr\u00e5ga:<\/strong> Du g\u00e5r i trappor. Det tar n steg f\u00f6r att komma till toppen. Varje g\u00e5ng kan du ta 1 steg eller 2 steg. Hur m\u00e5nga olika s\u00e4tt att ta sig till toppen?<\/p>\n

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

Det h\u00e4r problemet kan se sv\u00e5rt ut i b\u00f6rjan, men n\u00e4r du t\u00e4nker efter en sekund kanske du tycker att det \u00e4r s\u00e5 l\u00e4tt. Svaret \u00e4r Fibonacci Numbers<\/a> (se h\u00e4r<\/a>, h\u00e4r<\/a> )<\/p>\n

Tja, de ursprungliga Fibonacci-numren definieras som sekvenser:<\/p>\n

\"Kodnings\u00f6vning<\/a><\/p>\n

F\u00f6r detta problem m\u00e5ste vi bara \u00e4ndra lite:<\/p>\n

\"Kodnings\u00f6vningoch \"Kodnings\u00f6vningeftersom f\u00f6r endast 1 steg finns det bara 1 distinkt s\u00e4tt och f\u00f6r 2 steg har vi tv\u00e5 l\u00f6sningar: 1 + 1 eller 2.<\/p>\n

Resten \u00e4r som Fibonacci-serien. Eftersom \"Kodnings\u00f6vningfr\u00e5n den aktuella positionen \u00e4r vi m\u00f6jligen fr\u00e5n tidigare tv\u00e5 positioner, F(n-1) och F(n-2).<\/p>\n

Du kan anv\u00e4nda rekursion, men detta kan l\u00f6sas med en mer effektiv iterativ l\u00f6sning.<\/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
Eller s\u00e5 f\u00f6redrar du en mer okomplicerad rekursiv funktion:<\/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
Notera: Rekursiven kommer att ge TIME LIMIT EXCEEDED<\/strong> p\u00e5 test 44. Det beror p\u00e5 att den rekursiva funktionen vanligtvis ber\u00e4knar mellanv\u00e4rden m\u00e5nga m\u00e5nga g\u00e5nger. Till exempel \"Kodnings\u00f6vning, \"Kodnings\u00f6vning. \"Kodnings\u00f6vning\u00a0ber\u00e4knas tv\u00e5 g\u00e5nger.<\/p>\n
Inspelningsk\u00e4lla:  helloacm.com<\/a><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"
Kodnings\u00f6vning \u2013 G\u00e5 i trappor \u2013 Fibonacci-nummer \u2013 C++ \u2013 Onlinedomare<\/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":[848,901,724],"tags":[1173],"class_list":["post-233194","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-handledningar","category-koda","category-utvecklaren","tag-affiai-sv"],"_links":{"self":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts\/233194","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/comments?post=233194"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/posts\/233194\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/media\/223984"}],"wp:attachment":[{"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/media?parent=233194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/categories?post=233194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.mediadoma.com\/sv\/wp-json\/wp\/v2\/tags?post=233194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}