|
||
|
Senior Member
 
加入日期: Mar 2012 您的住址: 地球
文章: 1,303
|
想問個程式邏輯的問題(數學題)
假設一個巨大2D平面(500*500)，裡面到處放一些矩形物體，每個矩形邊長5~30不等
假設我想用130*130的圈選框圈起來這些矩形，可以重複圈但是不可以有沒圈到的，有沒有辦法計算出"最少"要用幾個圈選框圈出這些矩形???每個圈選框的位置各在哪裡?? 假設同一個程式寫出來會不會有兩種以上答案??(比如說算出來都是兩個圈選框即可，但是第一次算跟第二次算兩個圈選框的位置不同)
__________________
 [/url] 老柏 老柏(第二)   老柏(第三) 老柏(第四) |
|||||||
2012-10-08, 12:13 PM
#1
|
|
|
Major Member
加入日期: Sep 2004
文章: 121
|
5~30的長方體是否重疊？
130圓形是否可重疊？ |
||
|
2012-10-08, 12:48 PM
#2
|
|
|
New Member
加入日期: Oct 2012
文章: 3
|
物體數量未知，在此命題之下基本上應該是無解吧?
 |
|
2012-10-08, 12:54 PM
#3
|
|
|
Senior Member
加入日期: Mar 2012 您的住址: 地球
文章: 1,303
|
引用:
5~30的長方體物體不重疊 圈選框是方型的(130*130)可重疊 引用:
這題是必須寫個程式，當輸入平面上所有矩形物件的大小和座標後，就自動算出(最少)需要幾個圈選框，每個圈選框的座標是什麼 所以其實我是在問做法，不是答案
__________________
[/url] 老柏 老柏(第二) 老柏(第三) 老柏(第四) |
||
|
2012-10-08, 01:00 PM
#4
|
|
|
Power Member
加入日期: Apr 2004 您的住址: 新竹/台北
文章: 652
|
只要你的程式沒有引進亂數，也沒有bug
(像是沒宣告變數就開始用，寫到不該寫的地方等等，這一類的bug可能會產生隨機的行為)， 那同樣輸入就會產生同樣輸出。 |
|
2012-10-08, 01:04 PM
#5
|
|
|
*停權中*
加入日期: Jan 2002
文章: 127
|
矩形和圈選框的邊是否都平行於巨大2D平面？
|
|
2012-10-08, 01:45 PM
#6
|
|
|
Senior Member
加入日期: Mar 2012 您的住址: 地球
文章: 1,303
|
引用:
是阿 我想到用最大邊框(所有矩形所在的位置畫出最大方框)再去除圈選框的方法來做，是可以做得到沒錯，但是要是大多數矩形集中在中央而外圈只有對角兩個的話，反而我的做法找不到"最少"的圈選框
__________________
[/url] 老柏 老柏(第二) 老柏(第三) 老柏(第四) |
|
|
2012-10-08, 03:40 PM
#7
|
|
|
Power Member
加入日期: Apr 2004 您的住址: 新竹/台北
文章: 652
|
從邊邊的方塊開始？
因為邊邊的方塊也需要一個框。 比如說最上面的方塊，那框的上端位置就確定了，只剩下移動水平方向去盡量多框其他方塊。 框完的方塊就刪掉，變成一個新的問題，重複以上。 不過我不確定需不需要比較四個邊上的方塊，先做哪個比較好？ 或者是一直從上面往下做就好？ |
|
2012-10-08, 04:10 PM
#8
|
|
|
*停權中*
加入日期: Jan 2002
文章: 127
|
我建議先把每個矩形簡化成一個點，
在這情況下來思考要如何圈選。 如果這一步演算法想通了， 再來考慮矩形來怎麼處理。 |
|
2012-10-08, 04:44 PM
#9
|
|
|
Major Member
加入日期: Sep 2003
文章: 112
|
上面有人說過了 同資料沒加變數的話 同演算法應該有同結果吧
不過即使是同樣圈選數的解答 應該通常也有不同位置的解法 就看你演算法怎麼寫 上面還是有人說過了 全部當成點來處理 最差就16次 不然就以邊角優先(左上 右上 左下 右下) 計算四次 取最少的 |
|
2012-10-08, 05:13 PM
#10
|
|
