[中譯] ProjectEuler 382 Generating polygons

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間13年前 (2012/04/29 07:30)推噓2(2推 0噓 1→)

留言3則, 1人參與討論串1/1

382. Generating polygons http://projecteuler.net/problem=382 一個多邊形是為由線段連接成封閉環的平面圖形，至少包含三段直線且不自身相交。（譯註: 就是平常說的「簡單多邊形」）一個僅含正數的集合 S 說它「產生多邊形 P」如果： * P 沒有兩邊長度相同， * P 的所有邊長都在 S 中， * S 不包含其他不是 P 邊長的值。例如： * 集合 {3,4,5} 產生一個三邊長分別為 3,4,5 的多邊形 (這裡是三角形)； * 集合 {6,9,11,24} 產生一個四邊長分別為 6,9,11,24 的多邊形 (這裡是四邊形)； * 集合 {1,2,3} 和集合 {2,3,4,9} 並不產生任何多邊形。考慮數列 S 由以下定義： * S_1 = 1, S_2 = 2, S_3 = 3 * S_n = S_{n-1} + S_{n-3} 再令 U_n 為集合 {S_1, S_2, ..., S_n}。例如 U_10 = {1,2,3,4,6,9,13,19,28,41}。令 f(n) 表示 U_n 的子集中能產生至少一個多邊形的子集個數。給定 f(5) = 7, f(10) = 501, f(25) = 18635853。求 f(10^18) 的末九位數。 -- S 這個數列在很多地方都有出現就不贅述了 (OEIS A930，可自行查閱) 比較大的問題是判斷多邊形... -- ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄ ▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄ ▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌ ▏ζ(▏●‵◥′●▊)Ψ ▏　　　　　　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄ █/|▊ 〃、〃▋ |\ ▎　　　　　　　ハルヒ主義　　　　　█▄▄▄█▄▄ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.91