中職C語言基礎(chǔ)算法之遞推算法教學(xué)課件

遞推法C語言常見算法中職C語言基礎(chǔ)算法之遞推算法遞推法C語言常見算法遞推是通過數(shù)學(xué)推導(dǎo),將復(fù)雜的運(yùn)算化解為若干重復(fù)的簡單運(yùn)算,以充分發(fā)揮計(jì)算機(jī)擅長重復(fù)處理的特點(diǎn)。遞推關(guān)系是一種簡潔高效的常見數(shù)學(xué)模型如:Fibonacci數(shù)列問題。遞推特點(diǎn):在遞推問題中,每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)(或后面的若干個(gè)數(shù)據(jù)項(xiàng))有定的關(guān)聯(lián),這種關(guān)聯(lián)一般通過“遞推關(guān)系式”表示。遞推是通過數(shù)學(xué)推導(dǎo),將復(fù)雜的運(yùn)算化解為若干重復(fù)的簡單運(yùn)算,以充分發(fā)揮計(jì)算機(jī)擅長重復(fù)處理的特點(diǎn)。遞推關(guān)系是一種簡潔高效的常見數(shù)學(xué)模型如:Fibonacci數(shù)列問題。遞推特點(diǎn):在遞推問題中,每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)(或后面的若干個(gè)數(shù)據(jù)項(xiàng))有定的關(guān)聯(lián),這種關(guān)聯(lián)一般通過“遞推關(guān)系式”表示。遞推過程:從初始的一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)出發(fā),通過遞推關(guān)系式逐步推進(jìn),從而得到最終結(jié)果。其中:初始的若干數(shù)據(jù)項(xiàng)稱為“邊界”。例如:Fibonacci數(shù)列問題已知:F(1)=0,F(2)=1,若:m>2,則F(m)=F(n-1)+F(n-2)注意:1)每個(gè)數(shù)據(jù)項(xiàng)都和它前面的若干個(gè)數(shù)據(jù)項(xiàng)(或后面的若干個(gè)數(shù)據(jù)項(xiàng))有一定的關(guān)聯(lián)遞推關(guān)系式。2)從初始的一個(gè)或若干數(shù)據(jù)項(xiàng)出發(fā),通過遞推關(guān)系式逐步推進(jìn),從而得到最終結(jié)果。注意3)遞推必須有“邊界”。4)解決遞推類型問題有三個(gè)重點(diǎn):基礎(chǔ),重點(diǎn)①如何建立正確的遞推關(guān)系式;②遞推關(guān)系有何性質(zhì);③遞推關(guān)系式如何求解。解決遞推問題的一般步驟建立遞推關(guān)系式確定邊界條件遞推求解按照推導(dǎo)問題的方向,遞推分為:●順推法:從初始數(shù)據(jù)開始推理,例如:n=0時(shí),n!=1;1時(shí),n!=n*(n-1)●倒推法:從結(jié)果數(shù)據(jù)開始推理。例如:n!=n*(n-1)!;邊界:n=0,n!=1例1:猴子第1天摘下若干個(gè)桃子,當(dāng)即吃了一半又一個(gè)。第2天又把剩下的桃吃了一半又一個(gè),以后每天都吃前一天剩下的桃子的一半又一個(gè),到第10天猴子想吃時(shí),只剩下一個(gè)桃子問:猴子第1天一共摘了多少桃子?分析:已知條件:第10天剩下1個(gè)桃子;隱含條件:每一次前一天的桃子個(gè)數(shù)等于后一天桃子的個(gè)數(shù)加1的2倍>逆向思維:從后往前推,可用倒推法求解。例1:逆推法-求解猴子吃桃子①#include<stdio.h②voidmain()③{i