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


正在瀏覽:   1 名遊客


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

« 1 2 3 (4)


QQQQQ
回覆: 想想這題如何用程式解?...
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
回覆: 想想這題如何用程式解?...
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
應用擴展 工具箱
把它挖出來,有趣的題目
會員二級
註冊日期:
2009/4/17 14:44
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 175
MP : 27 / 6080
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
回覆: 把它挖出來,有趣的題目
Anon:Blake
路過...
但覺真有趣,讓我想到以前求學,還蠻懷念以前寫小程式做數值分析~

2009/11/29 17:39 | 971b7 85c4c 85d5b fe382
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員一級
註冊日期:
2008/8/15 10:35
所屬群組:
已註冊使用者
等級: 4
HP : 0 / 78
MP : 9 / 2866
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
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員二級
註冊日期:
2009/4/17 14:44
所屬群組:
已註冊使用者
等級: 8
HP : 0 / 175
MP : 27 / 6080
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
應用擴展 工具箱
回覆: 想想這題如何用程式解?...
會員一級
註冊日期:
2008/8/15 10:35
所屬群組:
已註冊使用者
等級: 4
HP : 0 / 78
MP : 9 / 2866
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)

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


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