想想這題如何用程式解?... [論壇 - Ubuntu 程式設計]


正在瀏覽:   1 名遊客


 到底部   前一個主題   下一個主題  [無發表權] 請登錄或者註冊

(1) 2 3 4 »


QQQQQ
想想這題如何用程式解?...
Anon:QQQQQ
某棟大樓有49樓,5個電梯,
若要讓電梯門開啟,
所有電梯都必須在21-25樓之間(第二級為21-23樓),
每個電梯只有兩個按鈕: +8 和 -13,
每次必須同時移動2個電梯。

來源網頁

2009/7/2 16:23 | 04809 ac5c4 f6a7b a1e13
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
詳細解法還沒想到,
不過第一步一定是先把這個問題物件化,
再來想辦法算出符合題目條件的解法,
最悲慘的解法就是暴力解了吧,
一個一個試總會對的,但這個問題不可能只有暴力解行的通,
我想 21 <= 8m-13n <= 25 是一個很重要的關鍵。

2009/7/2 16:42
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
mosky 寫到:
最悲慘的解法就是暴力解了吧,
一個一個試總會對的,但這個問題不可能只有暴力解行的通,

^^|||...我連暴力解也想不出來...(暈)
不過記得大樓只有1到49樓,
沒有56樓也沒有-3樓!!

2009/7/2 17:07 | fd390 48fd3 c8756 4351e
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
上面的link好像沒辦法玩...
貼個flash link(應該可以玩的)
SWF

2009/7/2 17:34 | fd390 48fd3 c8756 4351e
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
QQQQQ 寫到:
上面的link好像沒辦法玩...
貼個flash link(應該可以玩的)
SWF

剛試了,這個也不能玩...(哭)

2009/7/2 17:47 | 79265 b3fe4 0e453 5890f
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員二級
註冊日期:
2008/4/21 1:19
來自 台北
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 190
MP : 31 / 7235
EXP: 62
離線

要購買才能玩咧
沒有Sample很難做題
也不確定目前的資訊是否完全

2009/7/2 18:01
C#開發者
熱愛C#
ACM解題魂~爆發中
kgame的blog
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員五級
註冊日期:
2008/10/31 19:42
來自 大圈圈裡的小圈圈,小圈圈裡的黃圈圈
所屬群組:
已註冊使用者
等級: 25
HP : 0 / 609
MP : 264 / 22184
EXP: 38
離線
剛才看了一下......
典型的離散數學題目
忘記什麼時候做了......
好像以前小弟考AMC10或12的時候玩的題目

Update:別叫我算數學了,才剛考完數甲回來

2009/7/2 18:04
志不立,如無舵之舟,無銜之馬,飄蕩奔逸,終亦何所底乎?-明。王守仁

我的噗浪:http://www.plurk.com/shrekwang/invite
我的Blog:http://shrekat.blogspot.com
非死不可:http://www.facebook.com/shrekwang
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
其實如果用抽象化一點,就不用用到物件,
算數學就好了,剛剛想的太複雜了。

剛剛又稍微分析了一下這道題目:
五座電梯,一次移動兩座,
一開始都可以以兩兩移動的方式達到目的,
且假設五座電梯都在一樓開始。

所以我們先處理前面幾座電梯,也就是 (1,2) (3,4),
它們的解法如下:

[6, 2] 23 23 ( 8 )
[9, 4] 21 21 ( 13 )
[11, 5] 24 24 ( 16 )
[14, 7] 22 22 ( 21 )
[16, 8] 25 25 ( 24 )

有方框前面的數字代表上升的次數,後面的數字代表下降的次數,
後面兩個數字則代表兩座電梯最後位於的樓層。
( n )表示總移動次數,
以上是最精簡的前五種解法,所以表示題目指定的範圍都可以達到。

所以最後移動時,有一座電梯位於 21~25 樓,
另一座電梯位於第一樓,寫程式解就行了:

經過程式運算後發現,上下總和移動次數為:
3, 8, 11, 16, 21
可以將第四座電梯從 21~25 再返回 21~25 樓,
所以第五座電梯也只能移動以上次數。

我們再從上面的推論得知,
8, 13, 16, 21, 24 可以將 1 樓的電梯移動至 21~25 樓,
所以第四、五座電梯可以移動的次數就是取兩者的交集:
8, 16, 21

得解。

以上是暴力解法,我沒用什麼腦袋 XD。

---

by the way:
和離散數學應該沒關係,我半點離散數學的知識都沒用上。

---

update:

程式因為反覆修改有點繁雜,晚些修好完整的程式再 po 上。

2009/7/2 18:05
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員二級
註冊日期:
2008/4/21 1:19
來自 台北
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 190
MP : 31 / 7235
EXP: 62
離線
mosky好像是假設5座都在1樓開始
如果5座電梯初始的樓層是隨機而不是都在1樓呢
我一開始是假設5座電梯是隨機的,還沒想出來 = = (燃燒吧ACM解題魂

2009/7/2 18:14
C#開發者
熱愛C#
ACM解題魂~爆發中
kgame的blog
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
找到可以玩的了,載點如下(不過是exe格式的):
flash執行檔

來源網址

補充:
1.5台電梯有起始樓層,分別為17,26,20,19,31樓
2.若當下電梯無法+8樓或-13樓,則電梯不會動!
ex.若電梯在42樓以上,則只能選擇-13樓...
...
以上!...(汗)

2009/7/2 18:15 | 2c45a 2776e 93c40 a0df8
應用擴展 工具箱

(1) 2 3 4 »

 [無發表權] 請登錄或者註冊


可以查看帖子.
不可發帖.
不可回覆.
不可編輯自己的帖子.
不可刪除自己的帖子.
不可發起投票調查.
不可在投票調查中投票.
不可上傳附件.
不可不經審核直接發帖.