Re: [問題] 求最小整數解

看板Mathematica作者LPH66 (1597463007)時間10年前 (2014/06/04 02:58)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《sweetycool (tina)》之銘言： : 已知 a,b,c,d皆為正整數 : a+b=c+d : 1/13 = ac/bd : 令s=a+b+c+d : 求min s ? : ans: 170 : 想問一下這題有辦法跑出來嗎?感恩嗯，雖然數學版已經有人回說答案不對了，不過還是來跑一下順便介紹幾個函式首先是本題 (合併成一行之後的) 程式 Catch[ Do[ If[Length[#] != 0, Throw[Append[#, n]]] &[ Position[Outer[Times, #, #], 1/13] &[ Table[a/(n - a), {a, 1, n - 1}] ] ], {n, 1, 85} ]; {{}, -1} ] 以下由內而外解說最內層是一個 Table，裡面列出分子分母的和是固定值 n 的所有分數主要是看到條件裡的 ac/bd 可以看成 (a/b)*(c/d) 而這兩個分數由於有 a+b = c+d 的條件，分子分母的和是相同的所以就先列出所有這些分數外面一層是 Position 包 Outer，還有一個純函式的代值先講純函式代值，這招我很常用在 one-liner 裡取代重覆的東西基本模式是一個純函式 ...& 後面馬上用 [] 代值進去用處是在當我要運算的式子裡有重覆的東西時可以只寫一次這一層的函式是 Position[Outer[Times, #, #], 1/13]&，代的值是內層的 Table 其實這跟先把內層收進變數裡再重覆運用變數是一樣的也就是這裡相當於 list = Table[...] Position[Outer[Times, list, list], 1/13] 再來講 Outer，這個是廣義外積，簡單說明即是: Outer[f, {a, b}, {x, y, z}] 會得到 {{f[a, x], f[a, y], f[a, z]}, {f[b, x], f[b, y], f[b, z]}} 於是在這裡 Outer[Times, list, list] 就會列出所有 list 裡任意兩個元素的乘積這正好是我要尋找 1/13 的對象，因此就用 Position 去找出 1/13 在哪裡了再外一層也是純函式代值，函式是 If[Length[#] != 0, Throw[Append[#, n]]]& 代的值是內層 Position 的結果由於 Position 在找不到東西時回傳的是 {} 而找到東西時回傳的則是 {{位置一座標}, {位置二座標}, ...} 因此判斷它的長度是不是 0，如果不是的話就表示找到東西了就在這個結果後面塞進 n 值之後 Throw 出來這裡要講解的是 Throw / Catch 這一對函式 (jurian0101 在 #1JTHjnoX 有提過, 這裡再多講解一點) 這一對函式是屬於外包內結構，Catch 在外，Throw 在內執行 Catch 時會先執行它的參數如果這當中碰到 Throw 被執行了，則 Catch 的參數執行就到此中斷 Catch 的結果就是剛剛執行的 Throw 的參數否則 (當中都沒有執行到 Throw) 則是參數執行結果這例子中的 Catch 是在最外層也就是說只要找到東西之後就會馬上停止計算，把結果丟出來給最外層反之如果沒找到則繼續計算再往外一層是一個 Do，這就只是很簡單的讓 n 從 1 開始試而已上界填一個足夠大的數就好，這裡填 85 的原因是因為原 PO 貼的答案是 170 的關係 (不能填 Infinity，它會說這不能跑 XD) 當然萬一跑完範圍都找不到我們需要一個方式知道才行因此分號後面就是 Do 跑完之後要執行的東西如果真的跑到那裡的話會得到 {{}, -1} 這東西然後因為這中間都沒碰到 Throw，所以外面的 Catch 得到的結果就會是這個 (其實不用擺也行, 因為 Do 的執行結果永遠是 Null，只要跑完了卻沒有結果就是找不到) 最外層就是收答案用的 Catch 了執行結果得到 {{1, 7}, {7, 1}, 14} 這表示在 n = 14 時，那個 Outer 的大陣列裡的 {1, 7} 及 {7, 1} 兩個位置是 1/13 但那個 Outer 陣列的元素是由內層的 Table 乘起來的它的 {1, 7} 位置就是內層 Table 第一個元素跟第七個元素相乘的結果而內層 Table 的第 a 個元素是分子為 a, 分子分母和為 n 的分數因此從這個結果我們就能讀出 1/13 跟 7/7 的乘積是 1/13 也就是所求最小 s 的 (a, b, c, d) 是 (1, 13, 7, 7) -- 題外話，同樣屬於外包內的函式對還有 Sow / Reap (直譯是播種 / 收成) 這一對函式用來分類和收集非常好用也由於這種外包內函式的特性，所以我們會常常看到 Catch[Do[..... Throw[...] ... , {...}]] Reap[Do[..... Sow[...] ... , {...}]] 這種結構，可以很方便地掃過全部的內容後再決定之後要怎麼處理至於 jurian0101 在 #1JTHjnoX 提到的 Throw / Catch 在其他語言的記憶體管理問題主要是因為那些語言裡有一些比較低階的操作的關係那種低階操作會被例外流程給打亂進而產生問題不過其實 MMA 的 Throw / Catch 又更異類：有另外一個程式語言 Python 常常被人說濫用例外因為 Python 裡只要有什麼事發生了就會扔個例外出來最常被拿來舉的例子是迴圈跑完了還會扔一個 StopIteration 例外出來；但 MMA 這裡根本就不只是例外，什麼東西都可以拿來丟像這個例子裡 Throw 出去的原因根本就只是我找到答案了所以停止而已…… MMA 的 Throw / Catch 比較接近於另外幾個函式 Return / Break / Abort 沒有其他語言中的例外概念，純化成為直接的流程控制函式了 -- 1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町つぐみ歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬チサト 1998/06/18 守野くるみ打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙 2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85 ※ 文章網址: http://www.ptt.cc/bbs/Mathematica/M.1401821922.A.805.html