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


正在瀏覽:   1 名遊客


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

« 1 2 3 (4)


QQQQQ
回覆: 想想這題如何用程式解?...
#31
Anon:QQQQQ
QQQQQ 寫到：
...
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

...

最後我把每台電梯的(M,N)解 換成 合法操作的排列組合,
也就是第一台17樓的電梯(M,N)=(1,0)被換成8種操作順序,
([+8,0,0,0,0,0,0,0],[0,+8,0,0,0,0,0,0],...)
第二台...
之後再去作配對, 找出最終解...,
效率有比暴力解快多了,
但對於步驟要13步的第二級(21-23)題目,
仍然很耗時間...>"<

底下是第一級(21-25)的結果:
第一種狀況可配對出 89856 組解,
第二種狀況可配對出 283920 組解,
第三種狀況可配對出 786240 組解,
全部解有 1160016 組!
下面為程式輸出的一部份,
加入自己標示的 3種狀況的解 的個數:
===== 1 =====                               <--- [1 - 89856] : 89856 組
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .   .   .   .  +8   21
20    . -13   .   .   .  +8  +8   .   23
19    .   .  +8  +8 -13   .   .   .   22
31  -13 -13  +8  +8 -13  +8  +8   .   24
===== 2 =====
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .   .   .   .  +8   21
20    . -13   .   .  +8   .  +8   .   23
19    .   .  +8  +8   . -13   .   .   22
31  -13 -13  +8  +8  +8 -13  +8   .   24
===== 3 =====
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .   .   .   .  +8   21
20    . -13   .   .  +8  +8   .   .   23
19    .   .  +8  +8   .   . -13   .   22
31  -13 -13  +8  +8  +8  +8 -13   .   24

...(略)...

===== 89854 =====
17   +8   .   .   .   .   .   .   .   25
26   +8   .   .   .   .   .   . -13   21
20    .  +8  +8 -13   .   .   .   .   23
19    .   .   .   .  +8 -13  +8   .   22
31    .  +8  +8 -13  +8 -13  +8 -13   24
===== 89855 =====
17   +8   .   .   .   .   .   .   .   25
26   +8   .   .   .   .   .   . -13   21
20    .  +8  +8   . -13   .   .   .   23
19    .   .   . -13   .  +8  +8   .   22
31    .  +8  +8 -13 -13  +8  +8 -13   24
===== 89856 =====
17   +8   .   .   .   .   .   .   .   25
26   +8   .   .   .   .   .   . -13   21
20    .  +8  +8   .   . -13   .   .   23
19    .   .   . -13  +8   .  +8   .   22
31    .  +8  +8 -13  +8 -13  +8 -13   24
===== 89857 =====                           <--- [89857 - 373776] : 283920 組
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .   .   .   .  +8   21
20  -13   .   .   .   .  +8  +8   .   23
19    . -13  +8 -13  +8  +8  +8   .   25
31    . -13  +8 -13  +8   .   .   .   21
===== 89858 =====
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .   .   .   .  +8   21
20  -13   .   .   .   .  +8  +8   .   23
19    . -13  +8  +8 -13  +8  +8   .   25
31    . -13  +8  +8 -13   .   .   .   21
===== 89859 =====
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .   .   .   .  +8   21
20  -13   .   .   .   .  +8  +8   .   23
19    .  +8 -13 -13  +8  +8  +8   .   25
31    .  +8 -13 -13  +8   .   .   .   21

...(略)...

===== 373774 =====
17   +8   .   .   .   .   .   .   .   25
26   +8   .   .   .   .   .   . -13   21
20    .  +8  +8   .   .   .   . -13   23
19    .  +8  +8 -13  +8  +8 -13   .   25
31    .   .   . -13  +8  +8 -13   .   21
===== 373775 =====
17   +8   .   .   .   .   .   .   .   25
26   +8   .   .   .   .   .   . -13   21
20    .  +8  +8   .   .   .   . -13   23
19    .  +8  +8  +8 -13 -13  +8   .   25
31    .   .   .  +8 -13 -13  +8   .   21
===== 373776 =====
17   +8   .   .   .   .   .   .   .   25
26   +8   .   .   .   .   .   . -13   21
20    .  +8  +8   .   .   .   . -13   23
19    .  +8  +8  +8 -13  +8 -13   .   25
31    .   .   .  +8 -13  +8 -13   .   21
===== 373777 =====                          <--- [373777 - 1160016] : 786240 組
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .  +8 -13  +8  +8   24
20  -13   .   .   .  +8   .  +8   .   23
19    . -13  +8  +8   .   .   .   .   22
31    . -13  +8  +8   . -13   .   .   21
===== 373778 =====
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .  +8 -13  +8  +8   24
20  -13   .   .   .  +8   .  +8   .   23
19    .  +8 -13  +8   .   .   .   .   22
31    .  +8 -13  +8   . -13   .   .   21
===== 373779 =====
17    .   .   .   .   .   .   .  +8   25
26  -13   .   .   .  +8 -13  +8  +8   24
20  -13   .   .   .  +8   .  +8   .   23
19    .  +8  +8 -13   .   .   .   .   22
31    .  +8  +8 -13   . -13   .   .   21

...(略)...

===== 1160014 =====
17   +8   .   .   .   .   .   .   .   25
26   +8  +8   .   .   . -13  +8 -13   24
20    .  +8  +8   .   .   .   . -13   23
19    .   .   .  +8 -13   .  +8   .   22
31    .   .  +8  +8 -13 -13   .   .   21
===== 1160015 =====
17   +8   .   .   .   .   .   .   .   25
26   +8  +8   .   .   . -13  +8 -13   24
20    .  +8  +8   .   .   .   . -13   23
19    .   .  +8 -13  +8   .   .   .   22
31    .   .   . -13  +8 -13  +8   .   21
===== 1160016 =====
17   +8   .   .   .   .   .   .   .   25
26   +8  +8   .   .   . -13  +8 -13   24
20    .  +8  +8   .   .   .   . -13   23
19    .   .  +8  +8 -13   .   .   .   22
31    .   .   .  +8 -13 -13  +8   .   21

total solutions = 1160016

Spent time: 0 hour(s), 18 min(s), 47 sec(s)

[註1]:話說有沒有數學高手可以用數學直接算出最後有幾組解?!
      難道這種題目只能叫程式一個一個數嗎?!...(好奇)
      一方面也可以確定自己的程式有沒有數對...
[註2]:程式改著改著,看著效率變好,有莫名成就感...嘻
      (程式改著改著,一直想不出好方法改善效率,有莫名無力感...唉)
[註3]:另外,還有一個有可能效率加倍的方法...就是...
      把一組解的操作順序對調(由最後一步做到第一步)會是另一組解!!(binbon)
      可以省下近半時間...(只是還沒想到程式要怎麼做...),
      所以最終解個數一定是偶數(這結論好像沒啥用)...

2009/7/9 16:31 | b8ac6 d845d 6f4e8 b6683
應用擴展 工具箱
QQQQQ
回覆: 想想這題如何用程式解?...
#32
Anon:QQQQQ
QQQQQ 寫到：
...
...
[註3]:另外,還有一個有可能效率加倍的方法...就是...
      把一組解的操作順序對調(由最後一步做到第一步)會是另一組解!!(binbon)
      可以省下近半時間...(只是還沒想到程式要怎麼做...),
      所以最終解個數一定是偶數(這結論好像沒啥用)...

註3 應該不對了!!
因為剛想到一個例子,
若初始樓層是4樓,
則會有一解為 [+8 +8 +8 -13 +8] 最後樓層為 23 樓,
4  +8  +8  +8 -13  +8  = 23

但操作順序顛倒則不為其解...
4  +8 -13  +8  +8  +8  = 23
      ^^^^
        不可行

唉~希望破滅...G~ (過河遊戲解太多~~ =3=)

2009/7/9 22:23 | 81690 614c9 36612 3c7e4
應用擴展 工具箱
Yu-Lin
把它挖出來，有趣的題目
#33
會員二級
註冊日期:
2009/4/17 14:44
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 175
MP : 27 / 6141
EXP: 0
離線
本來要找數學軟體，
結果發現這題，
用程式解真的不太好寫，
花了很長一段時間才寫出來(這都過了好幾天了)，
但是用手算就很快......(而且我還算錯...算出九步...=o=|||)

我先講一下我個人的推論

條件
[A].　21-Ci <= 8*xi-13*yi <= 25-Ci
　　　　i=1,2,3,4,5

推論
1.電梯的總移動次數　(ETM)　= 各電梯移動次數合　= 2*該解的步驟數　(STEP)

　　　　已知每一步都要移動兩台電梯-[1]

　　　　且任意一台電梯 A 的移動不影響另一台電梯 B 的移動-[2]
　　　　[2]指的是任意電梯　A　往上或往下，並不代表一定要選擇電梯　B　才能移動，剩下可移動的電梯，都可以選擇當移動對象

　　　　一台電梯不可能同時往上又往下-[3]

　　　　假設　xi　與　yi　分別代表電梯　A　向上與向下的次數，
　　　　則由　[3]　知道若電梯　A (+8 x1次,-13 y1次)可以符合條件[A]，
　　　　則至少要移動　x1+y1　次才會符合最後結果-[4]

　　　　假設現在有五台電梯其移動次數分別為
　　　　A1 (x1,y1) = x1+y1 = a1
　　　　A2 (x2,y2) = x2+y2 = a2
　　　　A3 (x3,y3) = x3+y3 = a3
　　　　A4 (x4,y4) = x4+y4 = a4
　　　　A5 (x5,y5) = x5+y5 = a5
　　　　則電梯總移動次數 = a1+a2+a3+a4+a5-[5]

　　　　假設用 n 步找出解答，
　　　　由　[1]　知道電梯總移動次數 = 2*n-[6]
　　　　由　[5]與[6]　得到 推論1.

2.任意步驟數若存在一個符合條件[A]的矩陣，則至少有兩組以上的解

　　　　在不考慮排列情況下，
　　　　設存在至少一個矩陣 (X,Y) 符合條件 [A]
　　　　設 (X,Y) = (x1,..,x5,y1,..y5)

　　　　 設我們移動電梯次數的矩陣為 (X',Y') = (x1',..x5',y1',..,y5')
　　　　且 x1'=x2'=..=x5'=y1'=y2'=..=y5'=0

　　　　每次從 (X',Y')　中取出任意兩變數各加一，
　　　　並將該值放回　(X',Y') 原來的位置中，
　　　　直到　(X',Y') = (X,Y)

　　　　由　[3]與[2]　知道，
　　　　若取　xi 加一，則可以取任意　xk 或 yk 加一，只要　k　不等於　i，
　　　　由上述知道，雖然取變數加一的最後組合相同，但取變數的順序可以不同-[7]，
　　　　由 [7] 得到　推論2.


附上 Perl 程式碼

#! /usr/bin/perl

#這裡指的是 25 跟 21 那個範圍
print "請輸入想給予的最大值範圍\n";
$mx = <>;
print "請輸入想給予的最小值範圍\n";
$mn = <>;

#這是指起始樓層
for ($j=0; $j<=4; $j++) {
    print "請輸入想要的第",$j+1,"個定值C\n";
    chomp ($C[$j] = <>);
    $max[$j] = $mx - $C[$j];
    $min[$j] = $mn - $C[$j];
}


EN: for ($n=1;$n<=50;$n++) {
#下面是以推論1為限制去做推論2
for ($a[0]=0; $a[0] <= $n; $a[0]++) {
    for ($a[1]=0; $a[1] <= $n; $a[1]++) {
        for ($a[2]=0; $a[2] <= $n; $a[2]++) {
last if ($a[2] + $a[1] + $a[0] > 2*$n);
            for ($a[3]=0; $a[3] <= $n; $a[3]++) {
last if ($a[3] + $a[2] + $a[1] + $a[0] > 2*$n || $a[3] + $a[2] + $a[1] + $a[0] < $n);
            OUT: for ($a[4]=0; $a[4] <= $n; $a[4]++) {
                    next if ($a[0] + $a[1] + $a[2] + $a[3] + $a[4] != 2*$n);#以推論1為限制條件
                    for ($i=0; $i<=4; $i++) {#這行到下面last OUT 為止，都是推論2的實做
                        $x[$i] = $a[$i];
                        $x[$i+5] = $a[$i] - $x[$i];
                        until (8 * $x[$i] - 13 * $x[$i+5] >= $min[$i] && 8 * $x[$i] - 13 * $x[$i+5] <= $max[$i]) {#以條件[A]去判斷是否符合遊戲規則
                                $x[$i]--;
                                $x[$i+5]++;
                                last OUT if ($x[$i] < 0)
}}
                        $y = join ',',@x;
                        print "第$n步有此種組合\n";
                        for ($j=0; $j<=4; $j++) {
                        print "$C[$j](+8,-13) = ($x[$j] , $x[$j+5])\n";
} last EN if ($a[0] + $a[1] + $a[2] + $a[3] + $a[4] == 2*$n);
}}}}}}
#這程式是用來直接判定”第 n 步”是否有解的程式
#如果”第 n 步”有解，程式就會列出可能的組合
#本來是要寫成可以自動列出到”第 n 步”為止，有那些解組合的


2009/11/29 17:03
應用擴展 工具箱
Blake
回覆: 把它挖出來，有趣的題目
#34
Anon:Blake
路過...
但覺真有趣，讓我想到以前求學，還蠻懷念以前寫小程式做數值分析～

2009/11/29 17:39 | 971b7 85c4c 85d5b fe382
應用擴展 工具箱
Kevin Peng
回覆: 想想這題如何用程式解?...
#35
會員一級
註冊日期:
2008/8/15 10:35
所屬群組:
已註冊使用者
等級: 4
HP : 0 / 78
MP : 9 / 2893
EXP: 12
離線
用 dynamic programming 解很簡單.

1.
先產生一個表格, 裡面記錄每一樓層要開門需要先移動到哪一樓層.
則 21-25 可直接開門 (起始狀態).
而 13-17 層 +8 後可開門, 34-38 層 -13 後可開門 (第一輪).
5-9 層 +8 後成為 13-17 層, 並代入之後部份...
如此擴張, 直到 1-49 層都有解, 產生以下表格 (請忽略第 0 層):
 0  9 10 11 12  13 14 15 16 17
18 19 20 21 22  23 24 25 26 27
28 21 22 23 24  25 34 35 36 37
38 39 40 41 21  22 23 24 25 47
48 49 29 30 31  32 33 34 35 36

在產生表格的過程中另外記錄每一解需要變換幾次, 則可套入電梯起始樓層 (17,26,20,19,31)
計算出總共移動的回數.

2.
以 C1~C5 代表每一電梯移動的次數, S = C1 + C2 + C3 + C4 + C5.
因為一次需同時移動兩台電梯, 因此:
* S 需為偶數
* C1~C5 都必需 <= S/2, 否則將無法完成配對
若 S 為單數, 則取 C1~C5 中最小者, 找出移動次數最少的電梯再修改.
在產生變換奇偶次數解的過程中發現, 21-25 可以移動到 29-33.
增加 3 或 5 次移動後有解. 因此直接將最短的解後面再額外加上 29-33 的解.

3.
最後配對時只要將 C1~C5 排序, 從次數最多的開始配對就可以了.

2009/12/4 9:46
應用擴展 工具箱
Yu-Lin
回覆: 想想這題如何用程式解?...
#36
會員二級
註冊日期:
2009/4/17 14:44
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 175
MP : 27 / 6141
EXP: 0
離線
Kevin Peng 寫到：
用 dynamic programming 解很簡單.

1.
先產生一個表格, 裡面記錄每一樓層要開門需要先移動到哪一樓層.
則 21-25 可直接開門 (起始狀態).
而 13-17 層 +8 後可開門, 34-38 層 -13 後可開門 (第一輪).
5-9 層 +8 後成為 13-17 層, 並代入之後部份...
如此擴張, 直到 1-49 層都有解, 產生以下表格 (請忽略第 0 層):
<pre> 0 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26 27
28 21 22 23 24 25 34 35 36 37
38 39 40 41 21 22 23 24 25 47
48 49 29 30 31 32 33 34 35 36</pre>
在產生表格的過程中另外記錄每一解需要變換幾次, 則可套入電梯起始樓層 (17,26,20,19,31)
計算出總共移動的回數.

不好意思@@
雖然看的懂理論的部份，但我看不懂那個表格，
可以請前輩講解的更詳細一點嗎?
謝謝^^


雖然沒貼在這邊，
不過從發出那個程式碼之後，
我還有在修改，
關於 $ttl 那邊，算是很失策，
雖然知道 ci <= n , i=1..5 這點，
當初寫的時候卻沒注意到，
害我想說怎麼程式跑這麼久，
一直到改成去尋找最佳解時才發現

已經補上修正過的，
這是我後來用來尋找最佳解用的，
只要把
EN: for ($n=1;$n<=50;$n++) {
跟
last EN if ($a[0] + $a[1] + $a[2] + $a[3] + $a[4] == 2*$n);
紅色部份拆掉，

把
print "請輸入想要驗證的步驟數\n";
$n = <>;
加到
EN: for ($n=1;$n<=50;$n++) {
上方就變成原來的驗證程式了


補上我自己驗證21-23之間的最佳解

請輸入想給予的最大值範圍
23
請輸入想給予的最小值範圍
21
請輸入想要的第1個定值C
17
請輸入想要的第2個定值C
19
請輸入想要的第3個定值C
20
請輸入想要的第4個定值C
26
請輸入想要的第5個定值C
31
第9步有最佳解

2009/12/5 19:45
應用擴展 工具箱
Kevin Peng
回覆: 想想這題如何用程式解?...
#37
會員一級
註冊日期:
2008/8/15 10:35
所屬群組:
已註冊使用者
等級: 4
HP : 0 / 78
MP : 9 / 2893
EXP: 12
離線
這個表格是從目地值推算回起始值的, 主要為了避開從起始值開始的搜尋動作, 直接獲得最短的解. 產生表的運算很簡單, 而且重覆記錄在用同空間就可以了.

例如第 31 層開始的電梯, 查出第 31 項目的內容為 39.
表示 31 可以 +8 後套用 39 的解.

接著看第 39 項目內容為 47, 表示 39 +8 後可套用 47 的解.

繼續查表可得:
31
39 (+8)
47 (+8)
34 (-13)
21 (-13)

2009/12/5 21:18
應用擴展 工具箱

« 1 2 3 (4)

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


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