※ 引述《midoliko (小綠藻)》之銘言：
: 嗯....
: ＄＠＃＄＠＃ 的資結老師又出作業了...
: 題目：
: a為正整數和負整數所構成的陣列。 contigsum(i,j)定義為由元素
: a[i]到a[j]之間的連續元素的和，期中i<=j。請寫個程式來找出另
: contigsum(i,j)為極大值i,j。這遞迴應該同時考慮陣列 a中的兩個半部分
: ex:
: 4 8 -23 30 24 -8 19
: 從 30+24+(-8)+19 會得到最大的解
下面是我臨時想到的遞迴作法....
未經測試.....妳就參考看看吧!
void findMax(int *a, int *b, int i, int j)
{
if(i >= arrayNum) goto end;
if(j >= arrayNum) findMax(a, b, i+1, i+1);
currentMax=contigsum(a,b);
tempMax=contigsum(i,j);
if(tempMax > currentMax) findMax(&i, &j, i, j+1);
else findMax(a, b, i+1, i+1);
end:
}
main()
{
int currentMax, tempMax,arrayNum;
int maxStart=0, maxEnd=0;
findMax(&maxStart, &maxEnd, maxStart, maxEnd + 1);
printf("The Max sum is %d, from %d to %d.", currentMax, maxStart, maxEnd);
}
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: LightKid.Dorm10.NCTU.edu.tw