三百二十六節查錯的數學理論
三百二十六節查錯的數學理論(第1/4頁)
錢羽之的眼神最早開始恍惚，李加奈堅持到這裡也開始走神了，隻有馮珊還在聽。
“二分查找從一個有序表裡找特定值，本質是一種分治策略，也就是把一個大問題分割為若乾相似的子問題，然後要麼直接求解，要麼繼續分割。它為什麼要求有序表？是為了確保每次運算能夠同時求解全部子問題。舉個例子，如果升序表的中位值小於被查找值，我可以同時確保兩個結論，一，被查找值不在有序表的前一半中，二，被查找值在有序表的後一半中——那麼接下來我在有序表的後一半中重複上述操作就行了。”
“我們的問題是類似的，從概率上，首先我們可以合理地假設有且僅有1張卡是錯誤的。然後，我們每次統計已知的包含錯誤卡片的所有卡片中的一半，如果統計結果表明錯誤卡片不在這一半中，那麼一定在另一半中，反之亦然。於是我就縮小了一半的錯誤卡片‘嫌疑範圍’。我反複進行折半操作縮小嫌疑範圍、縮小到一定程度時，問題也就不再是問題了。”
“我以前和你說過，我們現在做的穿孔卡計算機，其實際能力並不限於眼前看到的這些。剛才我的折半操作很機械吧――總是分出一半、輸入，然後檢查結果，把包含錯卡的那疊拿來重複操作。”
“那麼如果有一天，我們設計一臺機器來代替我剛才的重複機械操作，與製表機聯合起來就能夠完成更多的事情，很多大問題將被分解為小問題，然後采用同一個操作流程解決。”
“把看似複雜的問題層層分解為與原問題相似的規模較小的問題，反複用類似的一係列機械性操作求解，讓計算機也能夠完成，這樣的思想叫做‘遞歸’。這是我們利用計算機很本質的一種思路，你們要好好思考。特彆是，在思考這類問題時，不要把現有機械計算機的運行速度考慮進去，覺得還不如人力快。關鍵要想一想，在人不加以乾涉的情形下，計算機僅依照規則運行能夠求解什麼問題。也就是，什麼樣的問題是計算機可以解決的，我們叫‘可計算問題’。至於速度，那不是問題――麵包會有的。”
馮諾停了下來，讓馮珊仔細咀嚼這段話，對她來說，這樣的思維模式與數學類似，但又與以前學習的數學相當不同。而李加奈和錢羽之的數學也就是四則運算的水平，要他們理解實在是有點勉為其難。因為昨晚都冇睡好，這時已經十分迷糊了，這番話不啻於催眠曲――迷糊間錢羽之還在納悶這事和麵包有什麼關係。
“好了，你倆睡覺去吧。我看看這張卡片究竟是怎麼回事。”馮諾把還在呆呆思考的馮珊撇在一邊，對錢羽之和李加奈說道，他一指裡間，“可以在那張床上睡。”說完，
（本章未完，請點擊下一頁繼續閱讀）