éå½ï¼åè¯ä¸ºéåï¼å¨æ°å¦ä¸è®¡ç®æºç§å¦ä¸ï¼æ¯æå¨å½æ°çå®ä¹ä¸ä½¿ç¨å½æ°èªèº«çæ¹æ³ãéå½ä¸è¯è¿è¾å¸¸ç¨äºæ述以èªç¸ä¼¼æ¹æ³éå¤äºç©çè¿ç¨ãä¾å¦ï¼å½ä¸¤é¢éåç¸äºä¹é´è¿ä¼¼å¹³è¡æ¶ï¼éä¸åµå¥çå¾åæ¯ä»¥æ ééå½çå½¢å¼åºç°çãä¹å¯ä»¥ç解为èªæå¤å¶çè¿ç¨ãå¨æ°å¦å计ç®æºç§å¦ä¸ï¼å½ä¸ç±»å¯¹è±¡ææ¹æ³å¯ä»¥ç±ä¸¤ä¸ªå±æ§å®ä¹æ¶ï¼å®ä»¬è¡¨ç°åºéå½è¡ä¸º:
ç®åçåºçº¿æ¡ä»¶---ä¸ä½¿ç¨éå½äº§ççæ¡çç»æ¢æ
åµ
ä¸ç»è§åå°ææå
¶ä»æ
形缩åå°åºçº¿æ¡ä»¶
ä¾å¦ï¼ä»¥ä¸æ¯æ人ç¥å
çéå½å®ä¹:
æ人çç¶æ¯æ¯ä»çç¥å
ï¼åºçº¿æ¡ä»¶ï¼
æ人ç¥å
çç¥å
ä¹æ¯ä»çç¥å
ï¼éå½æ¥éª¤ï¼
ææ³¢é£å¥æ°åæ¯éå½çç»å
¸ä¾å:
Fib(0) = 1 åºçº¿æ¡ä»¶1ï¼
Fib(1) = 1 åºçº¿æ¡ä»¶2ï¼
对æææ´æ°n,n > 1æ¶ï¼Fib(n) = (Fib(n-1) + Fib(n-2))ã
许å¤æ°å¦å
¬çåºäºéå½è§åãä¾å¦ï¼ç®äºè¯ºå
¬ç对èªç¶æ°çå½¢å¼å®ä¹å¯ä»¥æ述为:0æ¯èªç¶æ°ï¼æ¯ä¸ªèªç¶æ°é½æä¸ä¸ªå继æ°ï¼å®ä¹æ¯èªç¶æ°ãéè¿è¿ç§åºçº¿æ¡ä»¶åéå½è§åï¼å¯ä»¥çæææèªç¶æ°çéåã
éå½å®ä¹çæ°å¦å¯¹è±¡å
æ¬å½æ°ãéåï¼å°¤å
¶æ¯åå½¢ã
éå½è¿æå¤ç§å¼ç©ç¬çâå®ä¹âãéå½æ¯å½ç¨åºçä¸ä¸ªæ¥éª¤æ¶åè°ç¨ç¨åºæ¬èº«çè¿ç¨ãç»åéå½çè¿ç¨è¢«ç§°ä¸ºâéå½âã
è¦ç解éå½ï¼å¿
须认è¯å°ç¨åºåç¨åºè¿è¡ä¹é´çåºå«ãç¨åºæ¯åºäºä¸ç»è§åçä¸ç»æ¥éª¤ãç¨åºçè¿è¡å®é
ä¸å
æ¬éµå¾ªè§ååæ§è¡æ¥éª¤ãä¸ä¸ªç±»æ¯:ä¸ä¸ªç¨åºå°±åä¸ä¸ªä¹¦é¢çé£è°±ï¼è¿è¡ä¸ä¸ªç¨åºå°±åå®é
åå¤é¥èä¸æ ·ã
éå½ä¸è¿ç¨è§èä¸å¯¹å
¶ä»ç¨åºæ§è¡çå¼ç¨ç¸å
³ï¼ä½ä¸ç¸åãä¾å¦ï¼é£è°±å¯è½æç¹é¥ªè¬èï¼èéè¦ä¾æ¬¡å æ°´çæ¥éª¤æ¯å¦ä¸ä¸ªç¨åºãç¶èï¼éå½è¿ç¨æ¯æ(è³å°)å
¶ä¸ä¸ä¸ªæ¥éª¤éè¦ä¸ä¸ªç¸åè¿ç¨çæ°å®ä¾ï¼å°±åé
¸é¢å¢é
æ¹éè¦ä¸æ¬¡å¶ä½ç¸åé
æ¹æ¶å©ä¸çä¸äºé¢å¢ãè¿ç«å³äº§çäºä¸ä¸ªæ é循ç¯çå¯è½æ§ï¼å¦æ为äºç¨åºè½å¤å®æï¼å¨æäºæ
åµä¸è·³è¿æé®é¢çæ¥éª¤ï¼è¿æ ·éå½åªè½å¨å®ä¹ä¸è¢«æ£ç¡®ä½¿ç¨ï¼æ¯å¦ä¸ä¸ªé
¸é¢å¢é
æ¹ï¼å®è¿åè¯æ¨å¦ä½è·åä¸äºçé¢å¢ï¼ä»¥é²æ¨ä»¥åä»æªåè¿çé¢å¢ãå³ä½¿å®ä¹æ£ç¡®ï¼éå½è¿ç¨å¯¹äººç±»æ¥è¯´ä¹ä¸å®¹ææ§è¡ï¼å 为å®éè¦åºåè¿ç¨çæ°è°ç¨åæ§è°ç¨(é¨åæ§è¡)ï¼è¿éè¦å¯¹ç¨åºçåç§åæ¥å®ä¾çè¿å±ç¨åº¦è¿è¡ä¸äºç®¡çãå æ¤ï¼éå½å®ä¹å¨æ¥å¸¸æ
åµä¸é常ç½è§ãä¸ä¸ªä¾åå¯ä»¥æ¯ä¸é¢ç寻æ¾è¿·å®«ä¹è·¯çè¿ç¨ï¼ç»§ç»åè¿ï¼ç´å°å°è¾¾åºå£æåæ¯ç¹(æ»è§è¢«è®¤ä¸ºæ¯å¸¦æ0个åæ¯çåæ¯ç¹)ãå¦æå°è¾¾çç¹æ¯åºå£ï¼ç»æ¢ãå¦åï¼éå½å°ä½¿ç¨è¯¥è¿ç¨ï¼ä¾æ¬¡å°è¯æ¯ä¸ªåæ¯ï¼å¦ææ¯æ¬¡è¯éªé½åªå°è¾¾æ»è¡åè失败ï¼è¿åå°å¯¼è´è¿ä¸ªåæ¯ç¹çè·¯å¾å¹¶æ¥å失败ãè¿æ¯å¦çæ£å®ä¹äºç»æ¢è¿ç¨åå³äºè¿·å®«çæ§è´¨:å®ä¸å
许循ç¯ãå¨ä»»ä½æ
åµä¸ï¼æ§è¡è¯¥è¿ç¨é½éè¦ä»ç»è®°å½ææå½åæ¢ç´¢çåæ¯ç¹ï¼ä»¥ååªäºåæ¯å·²ç»è¢«å½»åºå°è¯è¿ã
温馨提示:答案为网友推荐,仅供参考