ProjectEuler 382 Generating polygons - 拼圖

Delia avatar
By Delia
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

Donna avatar
By Donna
at 2012-05-02T20:36
只要最大邊的長度大於其他邊的長度總合, 就能成為多邊形
Edward Lewis avatar
By Edward Lewis
at 2012-05-07T02:49
剛才暴力跑了一下f(25), 數字吻合, 這假設應該是對的
Tristan Cohan avatar
By Tristan Cohan
at 2012-05-07T15:14
得到2個遞迴關係式, 為什麼不出到10^8就好? 我就可以解了

台大拼圖大賽 5/1(二) 二活705登場!

Blanche avatar
By Blanche
at 2012-04-26T21:12
^L1.3 想更了解拼圖研習社是怎麼一回事嗎? ...

liberty puzzle 團購

Ina avatar
By Ina
at 2012-04-23T21:19
美國木頭拼團購 FB團購頁面: https://www.facebook.com/events/383096688397592/ 官網: http://www.libertypuzzles.com/ 目標50盒(美國說才有折扣 收單時間到5/4 有任何問題都可以到FB粉絲團詢問喔~!! 謝謝!! ...

ProjectEuler 381 (prime-k) factorial

Hedwig avatar
By Hedwig
at 2012-04-22T20:33
381. (prime-k) factorial http://projecteuler.net/problem=381 對一個質數 p,令 S(p) = (Σ(p-k)!) mod p 其中 k = 1 ~ 5。 例如若 p = 7,則 (7-1)! + (7-2)! + (7-3)! + (7 ...

這幅拼圖是瑕疵品嗎?

Elizabeth avatar
By Elizabeth
at 2012-04-22T16:53
今天拆了一盒新的拼圖來拼 是clementoni的 有夜光 圖長這樣(小圖應該是夜光效果)http://ppt.cc/lJ;_ 小圖http://ppt.cc/9Bn- 現在只拼了十分之一左右吧 拼的時候發現好幾塊上面都有一大片夜光漆 http://ppt.cc/3i,w http://ppt.cc ...

生活工場的框

Rae avatar
By Rae
at 2012-04-22T10:44
不知道有沒有人在生活工場買過框 最近拼了一幅1000片的拼圖 前幾天在逛生活工場時碰巧看到有賣框 大約1000元,是黑色框還蠻漂亮的 有沒有人去那邊買過框的 可以分享一下品質怎麼樣呢? 謝謝:) - ...