Re: [問題] 隨變數增加而增加條件式
看板Programming作者mycircle (Careless whisper)時間18年前 (2007/10/12 20:30)推噓0(0推 0噓 0→)留言0則, 0人參與討論串5/7 (看更多)
※ 引述《TonyQ (骨頭)》之銘言：
: ※ 引述《璉璉 <devil@tainan.com.tw.x>, 看板: Programming》之銘言：
: : 這種一般都是用遞迴在做...
: : 比如說所有階層子目錄的列舉。
: 它只舉了一個情境，遞回也只是其中一個邏輯解，
: 而且以這個情境來講，遞回不見得比較好用。XD
: 遞回適合用來解 divide and conquer的問題，
: 如果他的子問題具有相依性(需要用到a...n的值)，
: iterator配上 dynamic programming 會是比較好的解。
: 遞回 跟 Iterator 之間的轉換是演算法裡面的其中一個部分，
: 基本上一般會建議能不用遞回就不用遞回，除非他有其必要性(夠簡單)。
: 遞迴流程難以掌握，也容易造成stack空間的溢出。
感謝回文和推文的網友 我把我的問題再說清楚一點好了
這個問題其實是一個老問題了 我拿來做練習而已
題目如下
如何列出1..n 的所有排列組合
例如 123 的所有排列組合 為 123 132 321 132 213 231 3! = 6種
可是如果12345 勒 就將近有120種排列組合 如果擴增到 1...10勒
就會有10!=3628800種
的排列組合
這時人腦便沒辦法一個一個將他展現出來了
而且此類問題可以歸類為NP hard 問題 也就是數字規模增大
求解時間以及複雜度將會非線性的來增加
我一開始的想法是用暴力法 也就是所謂的窮舉法一一把他列出
但我知道如網路上這位網友所提的概念
http://new-acos.blogspot.com/2007/07/blog-post_04.html
會比較節省演算的效率與記憶體
不過還是嘗試寫看看 因為我還是新手
兩種窮舉法的原始碼列舉如下(意思是差不多的) 我寫在EXCEL 的VBA上
第一種 :
Dim y(5)
y(1) = 1
y(2) = 2
y(3) = 3
y(4) = 4
y(5) = 5
'==================================================
k = 1
For a = 1 To 5
For b = 1 To 5
For c = 1 To 5
For d = 1 To 5
For e = 1 To 5
If e <> d And e <> c And e <> b And e <> a Then
If d <> c And d <> b And d <> a Then
If c <> b And c <> a Then
If b <> a Then
Cells(k, 1) = y(a) & y(b) & y(c) & y(d) & y(e)
k = k + 1
End If
End If
End If
End If
Next
Next
Next
Next
Next
第二種
'=================================================
'==使用者輸入
'=================================================
n = 5
s = 120
Dim y(5)
Dim U(120)
'=================================================
'==使用者輸入
'=================================================
y(1) = 1
y(2) = 2
y(3) = 3
y(4) = 4
y(5) = 5
'==================================================
k = 1
For a = 1 To n '==使用者輸入
For b = 1 To n
For c = 1 To n
For d = 1 To n
For e = 1 To n
Cells(k, 1) = y(a) & y(b) & y(c) & y(d) & y(e) '==使用者輸入
k = k + 1
Next
Next
Next
Next
Next
'==================================================
For a = 1 To n ^ n
For i = 1 To n
For j = 1 To n
ten = Mid(Cells(a, 1), i, 1)
ten2 = Mid(Cells(a, 1), i + j, 1)
If Mid(Cells(a, 1), i, 1) = Mid(Cells(a, 1), i + j, 1) Then
Cells(a, 1) = ""
End If
Next
Next
Next
k = 1
For x = 1 To n ^ n
If Cells(x, 1) <> "" Then
U(k) = Cells(x, 1)
k = k + 1
End If
Next
For x = 1 To s
Cells(x, 2) = U(x)
Next
======== 問題來了 ======
在寫的過程中 在第一種窮舉法時
我本來是想寫成動態的 也就是我希望當使用者只要改變N的大小 就可以了
但是我發現 以這個問題為例
像for next 以及 if then 的這些條件式 都會隨著N的增加而增加
我就突然想到 如果以後碰到這類問題時該如何解決
如果我以後只要碰到 變數增加時 我的條件式也會增加時 我該如何處理
程式寫得很糟 只是在寫的過程中 想到這個問題
所以想問看看高手是如何處理這類問題的 感謝您抽空看完我的文章 謝謝
--
\(^▽^)/ 人客來坐 http://tomycircle.spaces.live.com/default.aspx
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.104.167.3
※ mycircle:轉錄至看板 Visual_Basic 10/13 04:34
討論串 (同標題文章)