好像通過(guò)這個(gè)進(jìn)會(huì)快一點(diǎn)
http://mars1344.spaces.live.com
呵呵！感謝！ 原來(lái)是這么細(xì)微的問(wèn)題！ 暈哦
謝謝哈
另外，你說(shuō)的第二個(gè)問(wèn)題是不存在的,我也考慮到你說(shuō)的問(wèn)題；因?yàn)槟闳匀挥玫?
for(k=2;k<=n;k++)
for(i=1;i<k;i++)
for(j=1;j<k;j++)
仍然是完全窮舉
時(shí)間效率上沒(méi)有任何改進(jìn)，反而因?yàn)橹貜?fù)計(jì)算降低了效率。
其實(shí)可以這樣改，會(huì)提高一點(diǎn)點(diǎn)效率：
for(k=2;k<=n;k++)
for(i=1;i<k;i++)
for(j=i;i<k;j++)
假設(shè)i,j<k
f[i][j][k-1]表示狀態(tài): 三個(gè)車(chē)分別在i,j,k-1的位置
狀態(tài)轉(zhuǎn)移有三個(gè),要么是從某車(chē)i開(kāi)到k ,要么是j開(kāi)到k,要么是k-1開(kāi)到k(遞推方式,每次加1)
所以狀態(tài)轉(zhuǎn)移方程是:
f[i][j][k-1]+d[i][k] -> f[j][k-1][k]
f[i][j][k-1]+d[j][k] -> f[i][k-1][k]
f[i][j][k-1]+d[k-1][k] -> f[i][k-1][k]
這是3維動(dòng)態(tài)規(guī)劃的基本模型
唉,不知道怎么過(guò)不去啊~
你要是有興趣就幫忙測(cè)試一下吧~ 呵呵
@Run&Run
呵呵,其實(shí)很簡(jiǎn)單,你紙上畫(huà)一下就知道了
s==0;for(i=2;i<=n;i++)s=(s+m)%i;
是指n個(gè)人,編號(hào)從0到n-1 .輸出的時(shí)候必須輸出s+1 (編號(hào)s的人是第s+1個(gè)人)
而s==1;for(i=2;i<=n-1;i++)s=(s+m-1)%i+1; ㈠是有n-1個(gè)人,編號(hào)是從1開(kāi)始的(題目其實(shí)是除去了第一個(gè)人的約瑟夫問(wèn)題,所以只有n-1個(gè)人);㈡從約瑟夫問(wèn)題回歸到在這道題中,發(fā)現(xiàn)編號(hào)并不是真正從1開(kāi)始的,第一個(gè)人首先出去.所以依次向后移動(dòng)一個(gè)編號(hào),故也需要輸出s+1 ,和上面的s+1不同,這一點(diǎn)注意.
我這樣寫(xiě)是為了方便自己理解,當(dāng)然從數(shù)學(xué)的角度,你完全可以化簡(jiǎn)它
其實(shí)我自己做的時(shí)候并沒(méi)有注意到這些細(xì)節(jié),也沒(méi)有把兩個(gè)s+1拿出去比較,這些東西也不是需要強(qiáng)記硬背的,重點(diǎn)還是要看透徹問(wèn)題的本身
以上是一點(diǎn)心得,呵呵,謝謝關(guān)注,希望我的解答對(duì)你有幫助.
哦對(duì)了,注意兩點(diǎn).
一是數(shù)組定義一定要放在全局的位置,局部變量名字最好不要重復(fù), 不知道為什么,否則有時(shí)通不過(guò),很詭異..但是在自己的機(jī)器上測(cè)試卻不存在這點(diǎn)
呵呵,這道題寫(xiě)得太快了,代碼竟然這么多疏漏,,,雖然AC了,但是低級(jí)錯(cuò)誤也不少