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