﹝問題來源﹞
幾天終於翻起這學期最初教的coding theory，當時對於課文中的意
思有些誤解，因此意外的聯想到一個覆蓋的問題。
﹝問題﹞
現有一 4x4的正方形，想用直徑為 1的圓覆蓋住整個正方形，圓容許
可重疊、也可超出正方形。問怎樣的覆蓋法才能使得所需圓的個數越
少。
例如，第一層放置 5x5個圓，最外層的圓心落在正方形邊上。第二層
放置 4x4個圓，最外層的圓與正方形相切，所以共需25+16=41個圓才
能蓋滿正方形，感覺上面的方法頗浪費的，有沒有更好的方法。
﹝討論﹞
有多數益智玩具也有這種覆蓋、填滿的蓋念。那些問題大都要求把一
些東西完全的塞到一個指定的空間，不要凸出。覆蓋這題，基本想法
也是如此，但容許物件可跑出指定的範圍，而求最少的個數，不知還
有沒有人有想到類似此概念的益玩呢。
﹝備註﹞
我不知正確答案:)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
> -------------------------------------------------------------------------- <
作者: A1Yoshi (封網閉關...) 看板: puzzle
標題: Re: 【益智問題】【設計】覆蓋
時間: Sun Apr 21 02:52:26 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: ﹝問題來源﹞
: 幾天終於翻起這學期最初教的coding theory，當時對於課文中的意
: 思有些誤解，因此意外的聯想到一個覆蓋的問題。
: ﹝問題﹞
: 現有一 4x4的正方形，想用直徑為 1的圓覆蓋住整個正方形，圓容許
: 可重疊、也可超出正方形。問怎樣的覆蓋法才能使得所需圓的個數越
: 少。
: 例如，第一層放置 5x5個圓，最外層的圓心落在正方形邊上。第二層
: 放置 4x4個圓，最外層的圓與正方形相切，所以共需25+16=41個圓才
: 能蓋滿正方形，感覺上面的方法頗浪費的，有沒有更好的方法。
: ﹝討論﹞
: 有多數益智玩具也有這種覆蓋、填滿的蓋念。那些問題大都要求把一
: 些東西完全的塞到一個指定的空間，不要凸出。覆蓋這題，基本想法
: 也是如此，但容許物件可跑出指定的範圍，而求最少的個數，不知還
: 有沒有人有想到類似此概念的益玩呢。
: ﹝備註﹞
: 我不知正確答案:)
我先從面積去求...最少需要21個圓...
然後先做一個2x2的正方形以方便思考。
我在2x2的正方形裡面做出來可以只用9個圓就把正方形蓋住。
所以4x4可以只用36個圓。
概述如下（以2x2為例子）：
1.以2x2正方形中心點畫一圓。
2.以2x2正方形ABCD的A頂點為例（其餘由頂點畫圓同理）：
從2x2正方形A點到C點畫一對角線，以A點為圓直徑的一個端點，
直徑落在此對角線上。以此方法另畫三個圓。至此共畫5個圓。
3.另外四個圓取其一為例：直徑在2x2正方形任兩對邊中點連線上（正方形ABCD，
做AB與CD中點連線），位置可以翹一翹，可以把剩下尚未覆蓋的都覆蓋住。
備註：
這是用窮舉的方式trial and error試出來的...以我的數學功力
還無法看出此問題解法的通則...無法提出系統性演繹式的解答。
所以...
參考參考囉！^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.0.22
> -------------------------------------------------------------------------- <
作者: arist (這實在是太複雜了) 看板: puzzle
標題: Re: 【益智問題】【設計】覆蓋
時間: Mon Apr 22 12:43:44 2002
※ 引述《A1Yoshi (封網閉關...)》之銘言：
: 2.以2x2正方形ABCD的A頂點為例（其餘由頂點畫圓同理）：
: 從2x2正方形A點到C點畫一對角線，以A點為圓直徑的一個端點，
: 直徑落在此對角線上。以此方法另畫三個圓。至此共畫5個圓。
: 3.另外四個圓取其一為例：直徑在2x2正方形任兩對邊中點連線上（正方形ABCD，
: 做AB與CD中點連線），位置可以翹一翹，可以把剩下尚未覆蓋的都覆蓋住。
: 備註：
: 這是用窮舉的方式trial and error試出來的...以我的數學功力
: 還無法看出此問題解法的通則...無法提出系統性演繹式的解答。
: 所以...
: 參考參考囉！^^
算是因你的答案 讓我想到一種34個圓就可蓋住的方法 ^^(應該沒想錯)
用我這方法處理 其他邊長也不算太複雜....
再看看其他版友有沒有新的方法
我的方法一周後若沒人提再po出來
我的方法其實頗簡單的 或許有其他人也能想到
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.50.112
※ 編輯: arist 來自: 140.112.50.112 (04/22 12:44)
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【益智問題】【設計】覆蓋
時間: Tue Apr 23 02:44:34 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: 算是因你的答案 讓我想到一種34個圓就可蓋住的方法 ^^(應該沒想錯)
: 用我這方法處理 其他邊長也不算太複雜....
: 再看看其他版友有沒有新的方法
: 我的方法一周後若沒人提再po出來
: 我的方法其實頗簡單的 或許有其他人也能想到
用最簡單的正三角形覆蓋，應該33個就夠了。
一層五個，一層六個，重複三次。
可能計算錯誤。
另外用圓的內接正方形，也是6x6，
但是可以先用5x5覆蓋，剩下的部分，可以用比較少的圓去覆蓋，
九個應該就夠了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.252.206
> -------------------------------------------------------------------------- <
作者: weijr (173/124) 看板: puzzle
標題: Re: 【益智問題】【設計】覆蓋
時間: Wed Apr 24 04:02:27 2002
※ 引述《arist (這實在是太複雜了)》之銘言：
: ※ 引述《weijr (173/124)》之銘言：
: : 用最簡單的正三角形覆蓋，應該33個就夠了。
: : 一層五個，一層六個，重複三次。
: : 可能計算錯誤。
: 這部份有些不太了解 一層五個 是指怎樣的排法?
: : 另外用圓的內接正方形，也是6x6，
: 我是從正方形去修改的 可調整到再少兩個
你說的應該就是5x5+1+8了
正三角形覆蓋，指的是 o o o
o o
o o o
這樣的。
其實可以看成是用圓內接正六邊形去覆蓋。
如果nXn正方形的n夠大，這樣的覆蓋當然比用內接正方形有效率。
: : 但是可以先用5x5覆蓋，剩下的部分，可以用比較少的圓去覆蓋，
: : 九個應該就夠了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 131.215.108.166
※ 編輯: weijr 來自: 131.215.108.166 (04/24 04:09)