就像上一篇文章說的，“程式設計永遠是後話”！在有了可靠的問題分析過程和資料結構的選擇，能正确運作的“二分搜尋”代碼出現之前，把其主要的思路先在草稿上實作，即僞代碼。但由于僞代碼執行結果的不确定性，需要有一個驗證的過程。筆者非常不喜歡這個過程，因為這個過程很繁瑣，而且推出的結論不一定是正确的（畢竟沒有實實在在在機器上運作得到正确的結果），在筆者看來，給一個算法題，知道用什麼算法，資料結構，如果能用僞代碼實作，離成功已經不遠了。
但後來我又反駁了自己的觀點（沖突體啊），理由：至少到目前為止，寫的都是小程式、小算法題，驗證過程可能已經被潛移默化解決了。
麻煩來了，今天晚上在實作“動态規劃矩陣連乘最優組合”的算法在這個問題中需要填表，通過動态規劃解體，就因為表的下标混亂，是以填表的過程比較枯燥（debug了好多次）。 我先在稿紙上用僞代碼大概解決了這個問題，但是在真正敲寫代碼的時候，卻發現“僞代碼”除了整體上的走向之外（大概的結構），很多細節都有問題。
“大概”僞代碼：
for i=[0,n-1)
for j=[0,n-1-i)
col =... //col是填表元素的列
min =...
for k=[0,i)
t =....
if t<min
t = min
a[j][col] = min;
其中省略号内的東西待敲進去之後都不正确！需要重新分析這個填表的過程。
順序填表分成n-1組，編号i=[0,n-2]，如圖：
而每組有j=n-1-i個元素需要填寫。于是僞代碼的前兩行是這樣的來的
for j=[0,n-1-i)
首先把當下需要填寫元素的列值得出是col = i+j+1;通過觀察很容易發現的；而j即為當下需要填寫元素的行，于是(j,col)就是需要填寫元素的位置。
而min的計算是瓶頸，畫圖
可以發現計算min的兩個輔助元素的（第一個元素）行和（第二個元素）列都不被當下需填寫元素的(j,col)決定了。于是：
min = a[j][j] + a[j+1][col] + tab[j]*tab[j+1]*tab[col];
接下來的t的計算由上面的min的計算的出來的：
t = a[j][j+k+1] + a[j+k+2][col] + tab[j] * tab[j+k+2] * tab[col+1];
其實是一樣的，隻不過紅色部分多加了個k+1。
分析過程不夠嚴謹細膩，但是縱觀下來，自己有一個清晰的思路。
View Code
要做到上面的條條框框實在是不容易的，但是如果養成“條條框框”的習慣的話，即使沒有稿紙，隻操手MSPAINT，相信敲代碼的效率會提高的。
“腳手架”簡單來說是“驗證程式”的程式，但筆者認為“斷言”的魅力更大些。在每一個程式中，有一些變量資料是至關重要的，經常Debug就是為了這些變量的檢測，看是否和預期中的結果一樣；如果不一樣我的做法就是：結束debug，開始艱苦的錯誤排查，這個過程非常頭疼。assert能夠可以掃清很多的錯誤細節，包括除數為0，資料超出規定的範圍，數組下标越界雲雲。是以添加斷言，能在邏輯上保證你的程式不會出錯，即使現實并非如此。
故在上面“動态規劃矩陣連乘最優組合”中，添加了
assert(n!=0);
assert(col+1<n+1);
assert(j+k+2<n);
來保證數組下标越界問題，很明顯，如果下标越界，将是毀滅性的bug。
另外，添加了一個show函數：
void show(int ** a,int n)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
cout << setw(6) <<a[i][j];
cout << endl;
}// for
cout << endl;
}
非常遺憾，第67章看懂沒多少，大概是要讀者明白如何預見程式的開銷！！相反，第八章有趣多了。第八章提出了找出一個數字序列中最大的、連續的子序列，并且規定全負子序列的和為0。
“如果沒有閱讀過《程式設計珠玑》跳到第四點。”
最原始窮舉的算法時間開銷大到O(n^3)；
另一種窮舉的算法，即平方算法。通過儲存中間結果或者預處理資料，省去了之後重複的計算，是備忘錄算法（簡單的動态規劃），開銷下降了一個數量級O(n^2)；
分治法，這個真沒想到，開銷再次下降O(nlogn)；
以前做過類似的題目，是以最先想到的就是這個方法。形象點就是，“邊吃邊拉”——掃描算法，運作時間為O(n)。
for i=[0,n)
t += a[i]
if t<max case
max = t
if t<0 case
t = 0
end.
課後習題第10題，“找到總和最接近0的子序列或者最接近某個數的子序列”，嘗試着用上面的“邊吃邊拉”算法解決，但是沒有成功；隻能按着上面說的平方算法，僞代碼如下：
nearest = INF
for j=[i,n)
t = tab[j] - tab[i]
if nearest>|t| case
nearest = t
end
第八章最有趣的地方就是“數組索引下标居然可以出現複數”！寫了将近兩年的程式居然還不知道有這個東西，略有自慚形穢的味道。
設原數組a[n],pa = &a[1]，那麼pa[-1]亦即a[0]。但是，這麼巧妙的東西，該怎麼用？ 大家一開始都有寫過“冒泡排序”，看看利用這個“巧妙”能有什麼效果？給出僞代碼：
bubble(a,n)
mustbe(n>1)
pa = &a[1]
for i=[0,n)
for j=[0,n-i)
if a[j]>pa[j] case
swap(a[j],pa[j])
是的，它既沒有改善冒泡的運作開銷和效率，但是代碼美觀了很多：通過把pa定位在a的第二個元素上，是以a[j]和pa[j]其實不是同一個元素，pa[j]在a[j]的後面，即便他們的下标相同。筆者突然想到了一個比較現實而有用例子，大家一開始學習程式設計的時候，幾乎都遇到過這樣的題目，給定一個數字數組，求數組的各元素的總和，最原始的想法：
sum(a,n)
sum += a[i];
看看結合上面的“巧妙”的僞代碼：
pa = &a[n-1]
t = n>1;
for i=[0,t)
sum += (a[i]+pa[i|0x8000]) //下标變為負數
if n&1 case
sum += a[t]
沒錯，他還是做了n次的加法，一次都沒減，但是也有小小的優化：for循環裡對i的判斷判斷和自增都減半！加減開銷比位運算大的。“啊哈，靈機一動！”。非常文藝青年的一個優化，非常詩意...
本文完 Friday, April 06, 2012