亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

基礎(chǔ)算法-遞推法

系統(tǒng) 2607 0

實用算法 ( 基礎(chǔ)算法 - 遞推法 -01)

    有一類試題,每相鄰兩項數(shù)之間的變化有一定的規(guī)律性,我們可將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式:

    Fn=g(Fn-1)

    這就在數(shù)的序列中,建立起后項和前項之間的關(guān)系,然后從初始條件 ( 或最終結(jié)果 ) 入手,一步步地按遞推關(guān)系遞推,直至求出最終結(jié)果 ( 或初始值 ) 。很多程序就是按這樣的方法逐步求解的。如果對一個試題,我們要是能找到后一項與前一項的關(guān)系并清楚其起始條件 ( 最終結(jié)果 ) ,問題就好解決,讓計算機一步步算就是了,讓高速的計算機做這種重復(fù)運算,可真正起到 物盡其用 的效果。

    遞推分倒推法和順推法兩種形式。一般分析思路:

    if 求解條件 F1

    then begin{ 倒推 }

    由題意 ( 或遞推關(guān)系 ) 確定最終結(jié)果 Fa

    求出倒推關(guān)系式 Fi-1=g'(Fi);

    i=n;{ 從最終結(jié)果 Fn 出發(fā)進(jìn)行倒推 }

    while 當(dāng)前結(jié)果 Fi 非初始值 F1 do Fi-1=g(F1) 倒推前項;

    輸出倒推結(jié)果 F1 和倒推過程;

    end {then}

    else begin{ 順推 }

    由題意 ( 或順推關(guān)系 ) 確定初始值 F1( 邊界條件 )

    求出順推關(guān)系式 F1=g(Fi-1);

    i=1;{ 由邊界條件 F1 出發(fā)進(jìn)行順推 }

    while 當(dāng)前結(jié)果 Fi 非最終結(jié)果 Fn do Fi=g(Fi-1) 順推后項;

    輸出順推結(jié)果 Fn 和順推過程;

    end; {else}

    一、倒推法

    所謂倒推法,就是在不知初始值的情況下,經(jīng)某種遞推關(guān)系而獲知問題的解或目標(biāo),再倒推過來,推知它的初始條件。因為這類問題的運算過程是一一映射的,故可分析得其遞推公式。然后再從這個解或目標(biāo)出發(fā),采用倒推手段,一步步地倒推到這個問題的初始陳述。

    下面舉例說明。

    [ 1] 貯油點

    一輛重型卡車欲穿過 1000 公里的沙漠,卡車耗油為 1 / 公里,卡車總載油能力為 500 公升。顯然卡車一次是過不了沙漠的。因此司機必須設(shè)法在沿途建立幾個儲油點,使卡車能順利穿越沙漠,試問司機如何建立這些儲油點?每一儲油點應(yīng)存多少油,才能使卡車以消耗最少油的代價通過沙漠?

    算法分析:

    編程計算及打印建立的貯油點序號,各貯油點距沙漠邊沿出發(fā)的距離以及存油量。

    No. Distance(k.m.) oil(litre)

    1 X X X X

    2 X X X X

    3 X X X X

    ........ ......

    設(shè) dis[i] 為第 i 個貯油點至終點 (i=0) 的距離;

    oil[i] 為第 i 個貯油點的存貯油量;

    我們可以用倒推法來解決這個問題。從終點向始點倒推,逐一求出每個貯油點的位置及存油量。

    下圖表示倒推時的返回點:

    從貯油點 i 向貯油點 i+1 倒推的策略是,卡車在點 i 和點 i+1 間往返若干次。卡車每次返回 i+1 處時正好耗盡 500 公升汽油,而每次從 i+1 出發(fā)時又必須裝足 500 公升汽油。兩點之間的距離必須滿足在耗油最少的條件下使 i 點貯足 i*500 分升汽油的要求 (0<=i<=n-1) 。具體地講,第一個貯油點 i=1 應(yīng)距終點 i=0 500km 且在該處貯藏 500 公升汽油,這樣才能保證卡車能由 i=1 處到達(dá)終點 i=0 處,這就是說

    dis[1]=500 oil[1]=500;

    為了在 i=1 處貯藏 500 公升汽油,卡車至少從 i=2 處開兩趟滿載油的車至 i=1 處。所以 i=2 處至少貯有 2*500 公升汽油,即 oil[2]=500*2=1000 。另外,再加上從 i=1 返回至 i=2 處的一趟空載,合計往返 3 次。三次往返路程的耗油量按最省要求只能為 500 公升。即 d12=500/3km

    dis[2]=dis[1]+d12=dis[1]+500/3

    為了在 i=2 處貯存 1000 公升汽油,卡車至少從 i=3 處開三趟滿載油的車至 i=2 處。報以 i=3 處至少貯有 3*500 公升汽油,即 oil[3]=500*3=1500 。加上 i=2 i=3 處的二趟返程空車,合計 5 次。路途耗油量也應(yīng)為 500 公升,即 d23=500/5,

    dis[3]=dis[2]+d23=dis[2]+500/5;

    依此類推,為了在 i=k 處貯藏 k*500 公升汽油,卡車至少從 i=k+1 處開 k 趟滿載車至 i=k 處,即

    oil[k+1]=[k+1]*500=oil[k]+500 ,加上從 i=k 處返回 i=k+1 k-1 趟返程空間,合計 2k-1 次。這 2k-1 次總耗油量按最省要求為 500 公升,即

    dk,k+1=500/(2k-1)

    dis[k+1]=dis[k]+dk,k+1

    =dis[k]+500/(2k-1);

    最后, i=n 至始點的距離為 1000-dis[n],oil[n]=500*n 。為了在 i=n 處取得 n*500 公升汽油,卡車至少從始點開 n+1 次滿載車至 i=n ,加上從 i=n 返回始點的 n 趟返程空車,合計 2n+1 次, 2n+1 趟的總耗油量應(yīng)正好為 (1000-dis[n])*(2n+1) ,即始點藏油為 oil[n]+(1000-dis[n])*(2n+1)

    下面為程序代碼:

    program oil_lib;

    var

    k:integer; { 貯油點位置序號 }

    d, { 累計終點至當(dāng)前貯油點的距離 }

    d1:real;{i=n 至始點的距離 }

    oil,dis:array[1..10] of real;

    i:integer; { 輔助變量 }

    begin

    writeln('NO.','distance(k.m)':30,'oil(1.)':80);

    k:=1;

    d:=500; { i=1 處開始向始點倒推 }

    dis[1]:=500;

    oil[1]:=500;

    repeat

    k:=k+1;

    d:=d+500/(2*k-1);

    dis[k]:=d;

    oil[k]:=oil[k-1]+500;

    until d>=1000;

    dis[k]:=1000; { 置始點至終點的距離值 }

    d1:=1000-dis[k-1]; { i=n 處至始點的距離 }

    oil[k]:=d1*(2*k+1)+oil[k-1]; { 求始點藏油量 }

    for i:=0 to k do { 由始點開始,逐一打印始點至當(dāng)前貯油點的距離和藏油量 }

    writeln(i,1000-dis[k-i]:30,oil[k-i]:80);

    end. {main}

    轉(zhuǎn)換為 C 語言程序如下:

    #include<stdio.h>

    void main()

    {

    int k;/* 貯油點位置序號 */

    float d,d1; /*d: 累計終點至當(dāng)前貯油點的距離 ,d1:i=n 至始點的距離 */

    float oil[10],dis[10];

    int i;

    printf("NO. distance(k.m.)/toil(l.)/n");

    k=1;

    d=500; /* i=1 處開始向始點倒推 */

    dis[1]=500;

    oil[1]=500;

    do{

    k=k+1;

    d=d+500/(2*k-1);

    dis[k]=d;

    oil[k]=oil[k-1]+500;

    }while(!(d>=1000));

    dis[k]=1000; /* 置始點至終點的距離值 */

    d1=1000-dis[k-1]; /* i=n 處至始點的距離 */

    oil[k]=d1*(2*k+1)+oil[k-1]; /* 求始點藏油量 */

    for(i=0;i<k;i++) /* 由始點開始逐一打印始點至當(dāng)前貯油點的距離和藏油量 */

    printf("%d/t%f/t%f/t/n",i,1000-dis[k-i],oil[k-i]);

    }

實用算法 ( 基礎(chǔ)算法 - 遞推法 -02)

順推法

倒推法的逆過程就是順推法,即由邊界條件出發(fā),通過遞推關(guān)系式推出后項值,再由后項值按遞推關(guān)系式推出再后項值 ...... ,依次遞推,直至從問題初始陳述向前推進(jìn)到這個問題的解為止。

實數(shù)數(shù)列:一個實數(shù)數(shù)列共有 N 項,已知

ai=(ai-1-ai+1)/2+d, (1<i<N)(N<60)

鍵盤輸入 N,d,a1,an,m, 輸出 am

輸入數(shù)據(jù)均不需判錯。

算法分析:

分析該題,對公式:

Ai=(Ai-1-Ai+1)/2+d (1<i<N) (n<60)

作一翻推敲,探討其數(shù)字變換規(guī)律。不然的話會無從下手。

X=A2 s2[i]=(pi,Qi,Ri) 表示 Ai=PiX+QiD+RiA1

我們可以根據(jù)

Ai=Ai-2-2Ai-1+2D

=PiX+QiD+RiA1

A(i-1)=( A(i-2)-A(i) )/2+d, 可以推出 A(i)=A(i-2)-2A(i-1)+2d

A(i)=A(i-2)-2A(i-1)+2d=P(i)X+Q(i)d+R(i)A(1)

所以 A(i-2)=P(i-2)X+Q(i-2)d+R(i-2)A(1)

A(i-1)=P(i-1)X+Q(i-1)d+R(i-1)A(1)

這樣就推出 PiX+QiD+RiA1=(Pi-2-2Pi-1)X+(Qi-2-2Qi-1+2)D+(Ri-2-2Ri-1)A1

推出公式

PiX+QiD+RiA1=(Pi-2-2Pi-1)X+(Qi-2-2Qi-1+2)D+(Ri-2-2Ri-1)A1

比較等號兩端 X,D A1 的系數(shù)項,可得

Pi=Pi-2-2Pi-1

Qi=Qi-2-2Qi-1+2

Ri=Ri-2-2Ri-1

加上兩個邊界條件

P1=0 Q1=0 R1=1 (A1=A1)

P2=1 Q2=0 R2=0 (A2=A2)

根據(jù) Pi Qi Ri 的遞推式,可以計算出

S2[1]=(0,0,1);

S2[3]=(-2,2,1);

S2[4]=(5,-2,-2);

S2[5]=(-12,8,5);

...................

S2[i]=(Pi,Qi,Ri);

...................

S2[N]=(PN,QN,RN);

有了上述基礎(chǔ), AM 便不難求得。有兩種方法:

1 、由于 AN A1 PN QN RN 已知,因此可以先根據(jù)公式:

A2=AN-QND-RNA1/PN

求出 A2 。然后將 A2 代入公式

A3=A1-2A2+2D

求出 A3 。然后將 A3 代入公式

A4=A2-2A3+2D

求出 A4 。然后將 A4 代入公式

............................

求出 Ai-1 。然后將 Ai-1 代入公式

Ai=Ai-2-2Ai-1+2D

求出 Ai 。依此類推,直至遞推至 AM 為止。

上述算法的缺陷是由于 A2 是兩數(shù)相除的結(jié)果,而除數(shù) PN 遞增,因此精度誤差在所難免,以后的遞推過程又不斷地將誤差擴(kuò)大,以至當(dāng) M 超過 40 時,求出的 AM 明顯徧離正確值。顯然這種方法簡單但不可靠。

2 、我們令 A2=A2,A3=X ,由 S3[i]=(Pi,Qi,Ri) 表示 Ai=PiX+QiD+RiA2 (i>=2) 可計算出:

S3[2]=(0,0,1)=S2[1];

S3[3]=(1,0,0)=S2[2];

S3[4]=(-2,2,1)=S2[3];

S3[5]=(5,-2-2)=S2[4];

......................

S3[i]=(..........)=S2[i-1];

.....................

S3[N]=(..........)=S2[N-1];

再令 A3=A3,A4=X, S4[i]=(pi,Qi,Ri) 表示 Ai=PiX+QiD+RiA3 (i>=3) 可計算得出:

S4[3]=(0,0,1)=S3[2]=S2[1];

S4[4]=(1,0,0)=S3[3]=S2[2];

S4[5]=(-22,1)=S3[4]=S2[3];

..........................

S4[i]=(...........)=S3[i-1]=S2[i-2];

.......................

S4[N]=(...........)=S3[N-1]=S2[N-2];

依此類推,我們可以發(fā)現(xiàn)一個有趣的式子:

AN=PN-i+2*Ai+QN-i+2*D+RN-i+2*Ai-1,

Ai=(AN-QN-i+2*D-RN-i+2*Ai-1)/PN-i+2

我們從已知量 A1 AN 出發(fā),依據(jù)上述公式順序遞推 A2 A3 ... AM. 由于 PN-i+2 遞減,因此最后得出的 AM 要比第一種算法趨于精確。

程序代碼如下:

program ND1P4;

const

maxn=60;

var

n,m,i:integer;

d:real;

list :array[1..maxn] of real;{list[i]------- 對應(yīng) ai}

s:array[1..maxn,1..3] of real;{s[i,1]-------- 對應(yīng) Pi}

{s[i,2]-------- 對應(yīng) Qi}

{s[i,3]-------- 對應(yīng) Ri}

procedure init;

begin

write('n m d =');

readln(n,m,d);{ 輸入項數(shù),輸出項序號和常數(shù) }

write('a1 a',n,'=');

readln(list[1],list[n]);{ 輸入 a1 an}

end;{init}

procedure solve;

begin

s[1,1]:=0;s[1,2]:=0;s[1,3]:=1; { 求遞推邊界 (P1,Q1,R1) (P2,Q2,R2)}

s[2,1]:=1;s[2,2]:=0;s[2,3]:=0;{ 根據(jù)公式 Pi<---Pi-2 - 2*Pi-1}

{Qi<---Qi-2 - 2*Qi-1}

{Ri<---Ri-2 - 2*Ri-1}

{ 遞推 (P3,Q3,R3)......Pn,Qn,Rn)}

fori:=3 to n do

begin

s[i,1]:=s[i-2,1]-2*s[i-1,1];

s[i,2]:=s[i-2,2]-2*s[i-1,2]+2;

s[i,3]:=s[i-2,3]-2*s[i-1,3];

end; {for}

end;{solve}

procedure main;

begin

solve;{ (P1,Q1,R1)..(Pn,Qn,Rn)}

{ 根據(jù)公式 Ai=(An-Qn-i+2 * d-Rn-i+2 * Ai-1)/Pn-i+2}

{ 遞推 A2..Am}

for i:=2 to m do

list[i]:=(list[n]-s[n-i+2,2]*d-s[n-i+2,3]*list[i-1])/s[n-i+2,1];

writeln('a',m,'=',list[m]:20:10);{ 輸出 Am}

end;{main}

begin

init;{ 輸入數(shù)據(jù) }

main;{ 遞推和輸出 Am}

readln;

end.{main}

基礎(chǔ)算法-遞推法


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 美女视频很黄很暴黄是免费的 | 一级毛片直接看 | 国产毛片视频 | 国产91在线精品福利 | 欧美日韩视频一区三区二区 | 久久国产乱子伦精品免费强 | 大学生不戴套毛片视频 | 四虎色影院 | 视频一区亚洲 | 99热在线精品免费播放6 | 四虎国产精品4hu永久 | 日韩精品一区二区三区中文在线 | 色综合中文 | 亚洲成人精品视频 | 天天干天天干天天干 | 国产在线91精品入口首页 | 亚洲视频一区在线 | 国产中文字幕久久 | 99精品视频看国产啪视频 | 伊人久久成人爱综合网 | 一级黄色毛片子 | 国产农村妇女毛片精品久久久 | 一区二区三区在线免费看 | 国产成人亚洲综合91精品555 | 香蕉视频网站入口 | 97色在线观看 | 日本a∨在线 | 成人区精品一区二区毛片不卡 | japanese60成熟老妇 | 天天曰天天干 | 中文字幕三级理论影院 | 天天综合久久久网 | 日韩黄网| 中文字幕在线一区二区三区 | 国产精品资源网站在线观看 | 精品在线小视频 | 亚洲精品国产精品乱码视色 | 国产成人禁片免费观看 | 久色一区| 午夜精品影院 | 中文欧美一级强 |