ProjectEuler 382 Generating polygons - 拼圖
By Delia
at 2012-04-29T07:30
at 2012-04-29T07:30
Table of Contents
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,可自行查閱)
比較大的問題是判斷多邊形...
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ HARUHI █████ <■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ISM By-gamejye ¢|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
Tags:
拼圖
All Comments
By Donna
at 2012-05-02T20:36
at 2012-05-02T20:36
By Edward Lewis
at 2012-05-07T02:49
at 2012-05-07T02:49
By Tristan Cohan
at 2012-05-07T15:14
at 2012-05-07T15:14
Related Posts
台大拼圖大賽 5/1(二) 二活705登場!
By Blanche
at 2012-04-26T21:12
at 2012-04-26T21:12
liberty puzzle 團購
By Ina
at 2012-04-23T21:19
at 2012-04-23T21:19
ProjectEuler 381 (prime-k) factorial
By Hedwig
at 2012-04-22T20:33
at 2012-04-22T20:33
這幅拼圖是瑕疵品嗎?
By Elizabeth
at 2012-04-22T16:53
at 2012-04-22T16:53
生活工場的框
By Rae
at 2012-04-22T10:44
at 2012-04-22T10:44