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


正在瀏覽:   1 名遊客


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

« 1 2 (3) 4 »


回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
移動次數相同就可以了,
如果都要一起往上或下,這題無解 XD。

2009/7/3 14:20
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
UGP 寫到:
呃喔,意思是說每動一台電梯往上或往下也要另一台電梯往下或往上相同的樓數喔...


是低!!...
玩玩我PO的flash link就了解了!!

QQQQQ 寫到:
找到可以玩的了,載點如下(不過是exe格式的):
flash執行檔

來源網址

2009/7/3 14:22 | 6eab8 52262 4f173 78fc2
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
不太會用Python語法...@@~
這程式會跑很慢,所以我先固定前4步驟再去跑...
用暴力解的Python Sample code:
#!/usr/bin/python
#-*- encoding: UTF-8 -*-

def show( ary ):
for x in ary:
print "%4d" % x,
print ""

def showstep( ary ):
for x in ary:
if x != 0:
print "%+4d" % x,
else:
print "%4s" % ".",
print ""

def showhistory( Nth, history, init, result ):
print ""
print "=== %d : %d step(s) ===" % (Nth, len( history))
show( init )
for h in history:
showstep( h )
show( result )

def valid( floor, floor_range ):
return ( floor >= floor_range[0] and floor <= floor_range[1] );

def isbingo( elevators, open_range ):
for i in elevators:
if i < open_range[0] or i > open_range[1]:
return 0
return 1

def move( elevators, V, floor_range ):
tmp = [] + elevators
for i in range( len(tmp) ):
tmp[i] += V[i]
if not valid( tmp[i], floor_range ):
return 0

for i in range( len(elevators) ):
elevators[i] = tmp[i]
return 1

def undomove( elevators, V ):
for i in range( len(elevators) ):
elevators[i] -= V[i]

def solve( S, init, curr, max_step, floor_range, open_range, history = [], solve_cnt = [0] ):

if len(history) >= max_step:
return

for V in S:
if not move( curr, V, floor_range ):
continue
history.append( V )
if isbingo( curr, open_range ):
solve_cnt[0] += 1
showhistory( solve_cnt[0], history, init, curr )
else:
solve( S, init, curr, max_step, floor_range, open_range, history, solve_cnt )
history.pop()
undomove( curr, V )

if __name__ == "__main__":
floor_range = [1, 49]
open_range = [21, 25]
up_button = 8
down_button = -13
elevators = [ 17, 26, 20, 19, 31 ]
current = [] + elevators
history = []
S = []
for i in range( len(elevators) - 1 ):
for j in range( len(elevators) - 1 - i ):
Vu = [0] * len(elevators)
Vd = [0] * len(elevators)
Vu[i] = Vu[i+j+1] = up_button
Vd[i] = Vd[i+j+1] = down_button
S.append(Vu)
S.append(Vd)
#"""
#step 1. [+8 +8 . . .]
move( current, [up_button,up_button,0,0,0], floor_range )
history.append( [up_button,up_button,0,0,0] )
#"""
#step 2. [. +8 +8 . .]
move( current, [0,up_button,up_button,0,0], floor_range )
history.append( [0,up_button,up_button,0,0] )
#"""
#step 3. [. -13 -13 . .]
move( current, [0,down_button,down_button,0,0], floor_range )
history.append( [0,down_button,down_button,0,0] )
#"""
#step 4. [. +8 +8 . .]
move( current, [0,up_button,up_button,0,0], floor_range )
history.append( [0,up_button,up_button,0,0] )
#"""
solve( S, elevators, current, 8, floor_range, open_range, history )

2009/7/3 19:11 | c75e0 383fb 321d4 ac397
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
我想到另一個方式去解...(不過程式還沒頭緒)

設開啟電梯的樓層限制: L(最低樓層), H(最高樓層)
並設 E(電梯初始位置), U(+8), D(-13)

找出(M,N) 滿足 L <= E + M x U + N x D <= H, 並限制 M + N <= MAX_STEPS
(延續前人解法...21 <= E + 8M - 13N <= 25)

則 5 台電梯有各自的 (M,N) 解 (若電梯初始位置 E 均不同),
設第1台 的 解為 (M1, N1),
第2台 的 解為 (M2, N2),
第3台 的 解為 (M3, N3),
第4台 的 解為 (M4, N4),
第5台 的 解為 (M5, N5)

根據題目要求每次固定移動2台電梯,
也就是每次移動 要麻2個 +8, 不然就是2個 -13,
所以最終會有 偶數個 +8 與 偶數個 -13, (包含0),
而且 +8 與 -13 總數不超過 2 x MAX_STEPS,
也就是操作2步時, +8 與 -13 總數為 2 x 2 = 4 個

因此上面 M1+M2+M3+M4+M5 必須是偶數, 設 Msum
且 N1+N2+N3+N4+N5 也必須是偶數, 設 Nsum
並且 Msum + Nsum <= 2 x MAX_STEPS

以原題目為例:
可以求出所有滿足上面條件的解如下:
E   (M,N)   最後樓層    Steps(<=8)
--- ----- ------- ------
17 (1,0) 25 +8
26 (1,1) 21 +8 -13
20 (2,1) 23 +8 +8 -13
19 (2,1) 22 +8 +8 -13
31 (4,3) 24 +8 +8 +8 +8 -13 -13 -13
--- ----- ------- ------
17 (1,0) 25 +8
26 (1,1) 21 +8 -13
20 (2,1) 23 +8 +8 -13
19 (4,2) 25 +8 +8 +8 +8 -13 -13
31 (2,2) 21 +8 +8 -13 -13
--- ----- ------- ------
17 (1,0) 25 +8
26 (3,2) 24 +8 +8 +8 -13 -13
20 (2,1) 23 +8 +8 -13
19 (2,1) 22 +8 +8 -13
31 (2,2) 21 +8 +8 -13 -13

^^~這樣答案就很明顯了,(只剩3種狀況)
最後只要把 Steps 調整成每步操作都是2個 +8 或2個 -13 就可以了~~~
看又沒有人可以調出7步以內的...(上面有人8步解出來,所以最多8步)

只是最後這步用我們人自己調整算簡單,很快就可以有1組解了,
不過程式的話,還要再想想 >"<
如果要列出所有解的話,一樣還是要叫程式跑...
但若要算出有幾組解的話...應該..可以..算...吧?!...(排列組合...)(頭暈)
全部-(+8超出49)-(-13低於1)+(+8,-13均超出限制)...(亂寫@#$%...)

2009/7/6 14:54 | 770b8 687a3 0e773 00da7
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
QQQQQ 寫到:
...
看又沒有人可以調出7步以內的...(上面有人8步解出來,所以最多8步)
...

剛剛看ㄌ一下,3種狀況+8,-13的總數都是16,
所以一定要8步,
7步以內是不可能ㄌ!!...甭想ㄌ^^|||

2009/7/6 15:11 | d4de4 94a14 65a03 99cd8
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
其實我解到最後就懶了,
後來就在忙別的事情,也沒繼續寫,你還真有耐心呢 XD"。

等會又有別的事情得做了,
剛剛稍微看一下,覺得新的方法好像有點瑕疵,
不過我也不確定,只有稍微看了一下,我得先去忙了,
晚些再回來看看 : )。

2009/7/6 15:12
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
...順便PO第二級(21-23)的可能解(最少13步):
E   (M,N)   最後樓層    Steps(<=13)
--- ----- ------- ------
17 (4,2) 23 +8 +8 +8 +8 -13 -13
26 (1,1) 21 +8 -13
20 (2,1) 23 +8 +8 -13
19 (2,1) 22 +8 +8 -13
31 (7,5) 22 +8 +8 +8 +8 +8 +8 +8 -13 -13 -13 -13 -13
--- ----- ------- ------
17 (4,2) 23 +8 +8 +8 +8 -13 -13
26 (1,1) 21 +8 -13
20 (2,1) 23 +8 +8 -13
19 (7,4) 23 +8 +8 +8 +8 +8 +8 +8 -13 -13 -13 -13
31 (2,2) 21 +8 +8 -13 -13
--- ----- ------- ------
17 (4,2) 23 +8 +8 +8 +8 -13 -13
26 (6,4) 22 +8 +8 +8 +8 +8 +8 -13 -13 -13 -13
20 (2,1) 23 +8 +8 -13
19 (2,1) 22 +8 +8 -13
31 (2,2) 21 +8 +8 -13 -13

註: 排列時須注意電梯是在可移動的樓層...

附排列例子:
第一級(21-25)
      1    2    3    4    5    6    7    8
-------------------------------------------
17 +8
26 -13 +8
20 +8 +8 -13
19 +8 +8 -13
31 +8 +8 -13 +8 +8 -13 -13

第二級(21-23)
      1    2    3    4    5    6    7    8    9   10   11   12   13
--------------------------------------------------------------------
17 +8 +8 -13 -13 +8 +8
26 +8 +8 -13 -13 +8 +8 +8 -13 +8 -13
20 +8 +8 -13
19 +8 +8 -13
31 +8 -13 +8 -13

2009/7/6 15:47 | 8b3ea c5b72 59f83 1279d
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
管理員
註冊日期:
2009/1/24 18:15
所屬群組:
網站管理員
已註冊使用者
等級: 29
HP : 0 / 712
MP : 377 / 25427
EXP: 48
離線
我剛剛仔細看了文字說明,是我剛剛疏忽了 XD",
是沒有瑕疵的,我以為你是說單一電梯移動的次數一定是偶數。

2009/7/6 16:01
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
QQQQQ 寫到:
...
附排列例子:
第一級(21-25)
      1    2    3    4    5    6    7    8
-------------------------------------------
17 +8
26 -13 +8
20 +8 +8 -13
19 +8 +8 -13
31 +8 +8 -13 +8 +8 -13 -13


[更正]
第一級(21-25)
      1    2    3    4    5    6    7    8
-------------------------------------------
17 +8
26 -13 +8
20 +8 +8 -13
19 +8 -13 +8
31 +8 +8 -13 +8 -13 +8 -13

^^^^^^^
對調後..

2009/7/6 16:07 | 4bccb f1931 c1cc3 48fda
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
Anon:QQQQQ
附上Python程式碼,解(M,N)
(自己修改E, U, D, L, H, MAX_STEPS的值,
就可以找出其他狀況可能的解囉...QQ)
#!/usr/bin/python
#-*- encoding: UTF-8 -*-

def FindMN( E, U, D, L, H, MAX_STEPS ):
"""
Input:
E: 電梯初始位置
L: 最低樓層
H: 最高樓層
U: 上升樓數
D: 下降樓數
MAX_STEPS: 步數限制
Return:
[M,N,與最後樓層] 的所有解: [ [m1,n1,e1], [m2,n2,e2], ... ]
"""
M_N = []
for m in range(MAX_STEPS + 1):
for n in range(MAX_STEPS + 1):
if m < 1 and n < 1 or m+n > MAX_STEPS:
continue;
e = E + U * m + D * n
if e < L or e > H:
continue;
M_N += [ [ m, n, e ] ]
return M_N

if __name__ == "__main__":

E = [ 17, 26, 20, 19, 31 ]
( U, D, L, H, MAX_STEPS ) = ( 8, -13, 21, 25, 8 )

M_N_ofE = []
for i in range(len(E)):
M_N_ofE += [ FindMN( E[i], U, D, L, H, MAX_STEPS ) ]

print ""
if len(M_N_ofE) != len(E):
print " * No solutions!"
else:
solutions = 0
print " E ( M, N ) 最後樓層"
for e0 in M_N_ofE[0]:
for e1 in M_N_ofE[1]:
for e2 in M_N_ofE[2]:
for e3 in M_N_ofE[3]:
for e4 in M_N_ofE[4]:
Msum = e0[0] + e1[0] + e2[0] + e3[0] + e4[0]
Nsum = e0[1] + e1[1] + e2[1] + e3[1] + e4[1]
if Msum % 2 or Nsum % 2 or Msum + Nsum > 2 * MAX_STEPS:
pass
else:
solutions += 1
print "--- -------- -------"
print "%2d (%2d,%2d) %4d" % (E[0], e0[0], e0[1], e0[2])
print "%2d (%2d,%2d) %4d" % (E[1], e1[0], e1[1], e1[2])
print "%2d (%2d,%2d) %4d" % (E[2], e2[0], e2[1], e2[2])
print "%2d (%2d,%2d) %4d" % (E[3], e3[0], e3[1], e3[2])
print "%2d (%2d,%2d) %4d" % (E[4], e4[0], e4[1], e4[2])
print ""
print "total %d solutions" % solutions
print ""

2009/7/6 17:15 | 6e2b4 e8637 30106 132a1
應用擴展 工具箱

« 1 2 (3) 4 »

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


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