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


正在瀏覽:   1 名遊客


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

« 1 (2) 3 4 »


回覆: 想想這題如何用程式解?...
會員二級
註冊日期:
2008/4/21 1:19
來自 台北
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 190
MP : 31 / 7235
EXP: 62
離線
QQQQQ 寫到:
找到可以玩的了,載點如下(不過是exe格式的):
flash執行檔

來源網址

補充:
1.5台電梯有起始樓層,分別為17,26,20,19,31樓
2.若當下電梯無法+8樓或-13樓,則電梯不會動!
ex.若電梯在42樓以上,則只能選擇-13樓...
...
以上!...(汗)
感謝提供可以玩的檔案
運氣真好,玩第一次就解出來了= =
1,2 +8
2,3 -13
3,4 +8
3,4 +8
4,5 -13
2,5 +8
2,5 +8
2,5 -13

共8次移動

如果樓層是隨機的話
要寫程式來搞也不容易 (我給ACM的3顆星
解題方向我還沒有頭緒

2009/7/2 18:32
C#開發者
熱愛C#
ACM解題魂~爆發中
kgame的blog
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
啊,我剛剛正好寫好,如果都是從一樓開始的暴力解。
不過樓層有變化的話,暴力就不好解了,還是乖乖算數學好了 xD。

既然我都寫好了,也許有參考價值,就先 po 上來。
#!/usr/bin/python
#-*- encoding: UTF-8 -*-

#It's a solver of ...
#某棟大樓有49樓,5個電梯,
#若要讓電梯門開啟,
#所有電梯都必須在21-25樓之間(第二級為21-23樓),
#每個電梯只有兩個按鈕: +8 和 -13,
#每次必須同時移動2個電梯。
#http://www.plastelina.net/game5twn.html
#本解法假設五座電梯都從一樓開始。

#電梯移動函數
#傳入所在樓層 (base),往上、下移動次數 (up and down),傳回最後樓層
#若最後樓層不符題目要求,則傳回 -1
def move(up,down,base=1):
	a = 8* up
	b = -13* down
	if a+b+base >= 0 and a+b+base <= 49:
		return a+b+base
	else:
		return -1
#傳入電梯所在範圍,上下移動的範圍限制,列出所有可能
def solver(base_range,amount_limit):
	print "--- Solver ---"
	print "[up,down,base] [up+down] floor_in_end"
	for b in range(base_range[0], base_range[1]+1):
		print "base on",b
		i = 1
		j = 1
		while i+j <= amount_limit:	
			while i+j <= amount_limit:
				temp = move(i,j,b)
				if temp >= 21 and temp <= 25:
					print [i,j,b], [(i+j)], temp
				i += 1
			i = 0
			j += 1
	print "--------------"

#首先求得前四座電梯的解法
#限制次數只是為了避免無限迴圈
solver([1,1],30)

#求第四座電梯由目標範圍返回目標範圍的可行解
#可行解對應的次數再對應回上一個所解出的次數就可以得解了
solver([21,25],30)


in Python

執行結果:
--- Solver ---
[up,down,base] [up+down] floor_in_end
base on 1
[6, 2, 1] [8] 23
[9, 4, 1] [13] 21
[11, 5, 1] [16] 24
[14, 7, 1] [21] 22
[16, 8, 1] [24] 25
[19, 10, 1] [29] 23
--------------
--- Solver ---
[up,down,base] [up+down] floor_in_end
base on 21
[2, 1, 21] [3] 24
[5, 3, 21] [8] 22
[7, 4, 21] [11] 25
[10, 6, 21] [16] 23
[13, 8, 21] [21] 21
[15, 9, 21] [24] 24
[18, 11, 21] [29] 22
base on 22
[2, 1, 22] [3] 25
[5, 3, 22] [8] 23
[8, 5, 22] [13] 21
[10, 6, 22] [16] 24
[13, 8, 22] [21] 22
[15, 9, 22] [24] 25
[18, 11, 22] [29] 23
base on 23
[3, 2, 23] [5] 21
[5, 3, 23] [8] 24
[8, 5, 23] [13] 22
[10, 6, 23] [16] 25
[13, 8, 23] [21] 23
[16, 10, 23] [26] 21
[18, 11, 23] [29] 24
base on 24
[3, 2, 24] [5] 22
[5, 3, 24] [8] 25
[8, 5, 24] [13] 23
[11, 7, 24] [18] 21
[13, 8, 24] [21] 24
[16, 10, 24] [26] 22
[18, 11, 24] [29] 25
base on 25
[3, 2, 25] [5] 23
[6, 4, 25] [10] 21
[8, 5, 25] [13] 24
[11, 7, 25] [18] 22
[13, 8, 25] [21] 25
[16, 10, 25] [26] 23
--------------


update:
解出來的結果跟剛剛我寫得有點不一樣,
剛剛以為 21~25 重新移動回去需要的次數都相同,
不過還是可以解出如果都從一樓開始的解法 : )。

2009/7/2 18:40
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員三級
註冊日期:
2005/7/22 4:43
所屬群組:
已註冊使用者
等級: 13
HP : 0 / 321
MP : 73 / 14770
EXP: 85
離線
輸入電梯高度: i[1~5];
動作:op(m,n,UP+8 or down-13);
結果:o[1~5];

藉由移動電梯的排列,我們可以指定出下列幾種組合:
1 steps :8,-13
2 steps :-5
3 steps :3
4 steps :11,-10,-2
5 steps :-7,[1]

3[8,-13,8] + -2[8,-13,8,8.-13]=1
同樣的方法用-2和1可以拼出-1
只要排好8,-13的順序,可以把任意兩電梯移到任意地方。
move(m,n,k)表示可以把第m個電梯和第n個電梯移動k樓。

所以問題可以直接簡化成,當四個電梯都在range內,如何移動一個電梯到指定地點?

因為四個電梯容許一個range,所以range等於你的quota。
比方說range 21-25,A電梯在21,你就有quota把最後一個電梯往上移動4樓的quota。
如果A,B,C,D都在25了,但是你還要把E電梯升高。
你可以先用move把A,B先一起降低到21,這樣就有更高的quota可以把E電梯往上升。

這方法沒有考慮到最少步數。
應該可以藉由Greedy method來達成。
不過沒有詳細證明,所以不清楚。

2009/7/2 18:41
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
pokkys 寫到:
...


漂亮 XD,
我先去吃飯,一會回來繼續玩 XD。

2009/7/2 18:44
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員三級
註冊日期:
2008/2/2 17:35
所屬群組:
已註冊使用者
等級: 16
HP : 0 / 375
MP : 98 / 14500
EXP: 3
離線
我連題目講什麼都不知道……
是我文學差還是數學差?
(看到問題的第一個反應是拿電鋸跟電鑽)

2009/7/2 20:19
 Ubuntu 優蹦兔| Kubuntu 酷蹦兔 | Xubuntu 小蹦兔
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
目前只想到暴力解...,
不知道有沒有其它比較有效率的作法?!
也不確定我程式的正確性如何?!
只能看看有沒有人跑出來或算出來的解法跟我一樣多的,才能確定...

=== 暴力解 ===

每次可能做的操作有 20 種, ( C 5取2 )x2, 集合設為 S = { V1, V2, ..., V20 }:
V1. [  +8  +8   .   .   . ]
V2. [ +8 . +8 . . ]
V3. [ +8 . . +8 . ]
V4. [ +8 . . . +8 ]
V5. [ . +8 +8 . . ]
V6. [ . +8 . +8 . ]
V7. [ . +8 . . +8 ]
V8. [ . . +8 +8 . ]
V9. [ . . +8 . +8 ]
V10.[ . . . +8 +8 ]
V11.[ -13 -13 . . . ]
... ...
V20.[ . . . -13 -13 ]

所以作 2 次操作會有 20 x 20 = 400 種, 設容器 G2 = { S, S }
....N 次操作會有 20 的 N 次方種, 則容器 Gn = { S, S, ..., S } ( N 個 S )
暴力解就來了...
=遞迴演算法 (抱歉,英文不是太好,應該還看得懂吧?!...><")=
funtion one_step
foreach Vn in Sn
if move elevators by using Vn is invalid
next Vn
else
move elevators
push Vn in step's history
if elevators can open /// bingo
show all Vn in step's history
else
one_step() /// do next step if step < max_step
pop Vn from step's history
undo move elevators

=Source Code=
(有點亂,C++140行,貼出來也太長了...>"<)

=程式輸出=
我是先預設第一個操作為 V1:[ +8 +8 . . . ] 再求解的...
結果有 4萬多種方法...花了600多秒...
可想而知,要找出所有解,估計也要 20 x 600多 秒 = ...(差不多知道要多久ㄌ...)
(ps. 我電腦是 AMD64 2800+, 1.5G RAM, Ubuntu8.04.amd64, g++4.2.4)
底下貼上一些程式輸出Sample:
=== 1 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. -13 -13 . .
. +8 +8 . .
. -13 . . -13
. . . +8 +8
. . . +8 +8
. . . -13 -13
25 24 23 22 21

=== 2 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. -13 -13 . .
. +8 +8 . .
. -13 . . -13
. . . +8 +8
. . . -13 -13
. . . +8 +8
25 24 23 22 21

=== 3 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. -13 -13 . .
. +8 +8 . .
. -13 . . -13
. . . -13 -13
. . . +8 +8
. . . +8 +8
25 24 23 22 21

=== 4 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. -13 -13 . .
. +8 +8 . .
. . . +8 +8
. -13 . . -13
. . . +8 +8
. . . -13 -13
25 24 23 22 21

=== 5 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. -13 -13 . .
. +8 +8 . .
. . . +8 +8
. -13 . . -13
. . . -13 -13
. . . +8 +8
25 24 23 22 21

... (略) ...

=== 42965 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. . . -13 -13
. . . +8 +8
. . . -13 -13
. . +8 +8 .
. . . +8 +8
. -13 -13 . .
. . +8 +8 .
25 21 23 25 21

=== 42966 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. . . -13 -13
. . . +8 +8
. . . -13 -13
. . +8 +8 .
. . . +8 +8
. . +8 +8 .
. -13 -13 . .
25 21 23 25 21

=== 42967 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. . . -13 -13
. . . +8 +8
. . . -13 -13
. . . +8 +8
. -13 -13 . .
. . +8 +8 .
. . +8 +8 .
25 21 23 25 21

=== 42968 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. . . -13 -13
. . . +8 +8
. . . -13 -13
. . . +8 +8
. . +8 +8 .
. -13 -13 . .
. . +8 +8 .
25 21 23 25 21

=== 42969 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. . . -13 -13
. . . +8 +8
. . . -13 -13
. . . +8 +8
. . +8 +8 .
. . +8 +8 .
. -13 -13 . .
25 21 23 25 21

Spent time: 608.72 sec(s)

以上!...程式輸出有很多只是操作順序上的不同而已,
但並不代表第一組解有 8! 種,
解釋如下(把第一組的步驟3,4對調):
=== 1 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. -13 -13 . . <-- ok
. +8 +8 . . <-- ok
. -13 . . -13
. . . +8 +8
. . . +8 +8
. . . -13 -13
25 24 23 22 21

=== 1 : 8 step(s) ===
17 26 20 19 31
+8 +8 . . .
. +8 +8 . .
. +8 +8 . . <-- (不合法, 第二個電梯樓層超過49)
. -13 -13 . . <--
. -13 . . -13
. . . +8 +8
. . . +8 +8
. . . -13 -13
25 24 23 22 21

2009/7/3 4:52 | 59c55 ab901 9898d 3914c
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員五級
註冊日期:
2008/10/7 21:19
所屬群組:
已註冊使用者
等級: 36
HP : 0 / 896
MP : 661 / 32794
EXP: 85
離線
mosky 寫到:
我想 21 <= 8m-13n <= 25 是一個很重要的關鍵。

我也認為這的確是關鍵,稍微修改一下:
21 <= i +8m-13n <= 25,i是目前位於第i樓
=> 21-i <= 8m-13n
  8m-13n <= 25-i
m初始為0,然後跑程式m++,求n從0開始以上的正整數解滿足於以上兩不等式
然後就用程式按m、n,並不可超過界線1、49,實際跑就可以求出步驟

我是這樣想,不知道前面有沒有人想的和我一樣,有些人寫的程式碼我看不懂 Orz

2009/7/3 11:45
I′m UGP
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員二級
註冊日期:
2008/4/21 1:19
來自 台北
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 190
MP : 31 / 7235
EXP: 62
離線
UGP 寫到:
mosky 寫到:
我想 21 <= 8m-13n <= 25 是一個很重要的關鍵。

我也認為這的確是關鍵,稍微修改一下:
21 <= i +8m-13n <= 25,i是目前位於第i樓
=> 21-i <= 8m-13n
  8m-13n <= 25-i
m初始為0,然後跑程式m++,求n從0開始以上的正整數解滿足於以上兩不等式
然後就用程式按m、n,並不可超過界線1、49,實際跑就可以求出步驟

我是這樣想,不知道前面有沒有人想的和我一樣,有些人寫的程式碼我看不懂 Orz
2台電梯一起動是另一個關鍵
動一台電梯會牽拖到另一台

2009/7/3 11:56
C#開發者
熱愛C#
ACM解題魂~爆發中
kgame的blog
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員五級
註冊日期:
2008/10/7 21:19
所屬群組:
已註冊使用者
等級: 36
HP : 0 / 896
MP : 661 / 32794
EXP: 85
離線
呃喔,意思是說每動一台電梯往上或往下也要另一台電梯往下或往上相同的樓數喔...

2009/7/3 14:16
I′m UGP
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員二級
註冊日期:
2008/4/21 1:19
來自 台北
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 190
MP : 31 / 7235
EXP: 62
離線
正是
10樓有Flash EXE檔
可以抓來玩看看

2009/7/3 14:20
C#開發者
熱愛C#
ACM解題魂~爆發中
kgame的blog
應用擴展 工具箱

« 1 (2) 3 4 »

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


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