read.cash Log in
@ggg0820 more from that month

今天因為上課吸收了過量數學而感到法喜充滿。 昨天軟作的實驗課出了一題：1<m<n≤100,000，且m,n都是正整數，求滿足（m+n)/2算術平均、(m*n)^0.5幾何平均、2*m*n/(m+n)調和平均，三個平均數皆為整數的數對(m,n)有多少？ 一看到題目，起手式就是兩層for loop，再三層if收工。 但問題來了，由於題目是10萬以下，而這樣寫程式要跑25~30分鐘，如果答案還錯就尷尬了。 於是班上同學開始想辦法改良算法，第一步是把算術平均分類成奇數+奇數和偶數+偶數，這步加快了一倍速度，只要10~15分鐘就跑完了。 教授說你們把數字改成1萬就好，看能不能把程式從6秒改到1秒內出來（眼神死），然後全班就卡住了，完全不知道怎麼改才能大幅增加運算效率。 只見教授雙手在鍵盤上不停敲打，指標在投影布幕上不停移動，教授忽然深吸了一口氣，不急不徐的說道：「成了。」 眾人帶著質疑的眼神抬頭一看，看到上界設定為1萬，按下執行後，教授的程式就像變魔術般，不，教授的程式就是魔術，直接把答案印到螢幕上。 眾人不信，大聲要求教授把數字改回10萬，魔術再次出現。 教授邪惡的笑著說：「那再改成100萬試試。」 魔術果然是魔術，又是不到一秒顯示出答案。 要知道，班上同學的程式的時間複雜度大都是n^2，而這魔術的時間複雜度後來經過驗算，降低到n^0.5，也就是n開根號。 下集預告： 想知道怎麼寫出最快的程式嗎？ 請按下喜歡、訂閱和小鈴鐺（X 我掰不下去了

10 comments

Log in to join in Reading is open to everyone. Replying needs an account.