Re: [問題] 隨變數增加而增加條件式
※ 引述《mycircle (Careless whisper)》之銘言:
: ※ 引述《TonyQ (骨頭)》之銘言:
: 感謝回文和推文的網友 我把我的問題再說清楚一點好了
: 這個問題其實是一個老問題了 我拿來做練習而已
: 題目如下
: 如何列出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上
: 第一種 :
: ======== 問題來了 ======
: 在寫的過程中 在第一種窮舉法時
: 我本來是想寫成動態的 也就是我希望當使用者只要改變N的大小 就可以了
: 但是我發現 以這個問題為例
: 像for next 以及 if then 的這些條件式 都會隨著N的增加而增加
: 我就突然想到 如果以後碰到這類問題時該如何解決
: 如果我以後只要碰到 變數增加時 我的條件式也會增加時 我該如何處理
: 程式寫得很糟 只是在寫的過程中 想到這個問題
: 所以想問看看高手是如何處理這類問題的 感謝您抽空看完我的文章 謝謝
基本上正常的問題碰到這種狀況都會想辦法轉換成
不用變數增加判斷式就跟著增加的寫法 -.-;;
這就是為甚麼會有 NP complete & transfer and conquer的由來 XD
因為要轉換問題變成比較好解決的問題。
我剛有寫個sample , 不過該死的vb 6竟然不報備關掉了 ,
就算了 , 只留下一個recursive解 .Q_Q
────────────────────────────────
當初在做這題的時候我是取巧用string來做
當然這題也是典型的遞回題
記得他沒有內建stack類別 , 所以就建議用遞回寫
當然算排列組合的話 , 這還不是最快的 ,
因為你可以把reverse算一種 , 可以減少一半的cost .
────────────────────────────────
Dim inputStr As String
inputStr = "12345"
Dim n As Integer
n = Len(inputStr)
printStr "", inputStr
Sub printStr(strNow As String, strNext As String)
Dim n
n = Len(strNext)
If n = 0 Then
List1.AddItem (strNow)
'用你想要顯示的方法替換掉
Else
For i = 1 To n
printStr strNow & Mid(strNext, i, 1), Mid(strNext, 1, i - 1) & _
Mid(strNext, i + 1, n - i)
Next
End If
End Sub
--
▄▅▆▇███▇▆▅▄▃ ╰┼╯─╮ ╮
◥███████████◣ ╰┼╯=│=│
◥██████───────◣ *. ╯ ╯ ╯ の 物 語 .*
◥███████──────◣ ~ ◢◣ ◢◣
◥██████───────◤ ◥◤* 空白的世界.翼 *◥◤
◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂~telnet://tony1223.no-ip.info
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.59.247
※ 編輯: TonyQ 來自: 220.132.59.247 (10/13 16:59)
討論串 (同標題文章)