輸入一個正整數N，求出所有1~N之間相加起來等於N的組合
例如：
輸入
5
輸出
5
41
32
311
221
2111
11111
輸入
10
輸出
10
91
82
811
73
721
7111
64
631
622
6211
61111
55
541
532
5311
5221
52111
511111
442
4411
4321
43111
4222
42211
421111
4111111
3331
3322
33211
331111
3223
32221
322111
3211111
31111111
22222
222211
2221111
22111111
211111111
1111111111
我不太清楚題目應該怎麼打比較好，
因為拿到的題目只有後面輸入輸出的部份(~"~
以下是我寫的程式碼：
Private Sub Command1_Click()
Open App.Path & "\\out.txt" For Output As #2
n = Val(InputBox("請輸入一正整數(N<=10)"))
If n > 10 Then Print "N 必須 <= 10": Exit Sub
Print #2, Trim(n)
For i = n - 1 To 1 Step -1
Call f(i, n)
Next i
Close
End Sub
Sub f(i, n)
s = i & (n - i)
Do While Val(Right(s, 1)) > Val(Mid(s, Len(s) - 1, 1))
k = k + 1
s = Left(s, k) & Left(s, 1) & Val(Right(s, 1)) - i
Loop
Print #2, IIf(Val(Left(s, 1)) = n, Trim(Str(i)), s)
c = IIf(Len(s) = 2 Or Val(Right(s, 1)) > 1, Len(s), Len(s) - 1)
Do While Val(Mid(s, c, 1)) > 1
While (Val(Mid(s, c, 1)) - 1) >= (Val(Mid(s, c + 1, 1)) + 1)
y = 0
s = Left(s, c - 1) & Val(Mid(s, c, 1)) - 1 & Val(Mid(s, c + 1, 1)) + 1
For j = 1 To Len(s)
y = y + Val(Mid(s, j, 1))
Next j
If y < n Then s = s & n - y: c = c + 1
Print #2, s
Wend
If Right(s, 1) > 1 Then c = Len(s)
If Val(Mid(s, c, 1)) <> 1 Then
s = Left(s, c - 1) & Val(Mid(s, c, 1)) - 1 & 1 & Mid(s, c + 1)
Print #2, s
End If
If Val(Mid(s, c, 1)) = 1 Then c = c - 1
If c = 1 Then Exit Do
Loop
End Sub
希望各位大大提供更好的作法，或是指點小妹我一些該改進的地方~~謝謝~
2006-11-14 12:55:43 · 6 個解答 · 發問者 以晴 2 in 電腦與網際網路 ➔ 程式設計
哈哈~~ 是的！我會小心不會太早結束問題的~
這題果然要用陣列呀~ 至於遞迴......我沒想過要用遞迴......
謝謝亡靈大讓我見識到「原來這題本來就用遞迴做的」
嗯...現在來挑戰N>1000的數字！
必須在30秒內執行完畢。
好像有點難...我瘋了 不要理我.......
2006-11-15 03:44:05 · update #1
'一樣很沒新意地使用遞迴...XD
Private Sub Form_Load()
Call anatFor(Val(InputBox("輸入一個正整數")), "")
End Sub
Private Sub anatFor(eoNum As Integer, anatNum As String)
Dim I As Integer
If eoNum = 0 Then List1.AddItem anatNum
For I = eoNum To 1 Step -1
Call anatFor(eoNum - I, anatNum & I)
Next I
End Sub
2006-11-14 23:32:48 補充：
對ㄏㄡ~~
我居然都沒發現... /_\
2006-11-15 00:10:51 補充：
更正,多加一個參數記錄上層遞迴的值...Private Sub Form_Load() Dim eoNum As Integer eoNum = Val(InputBox("輸入一個正整數")) Call anatFor(eoNum, eoNum, "")End Sub
2006-11-15 00:15:42 補充：
Private Sub anatFor(eoNum As Integer, upNum As Integer, anatNum As String) Dim I As Integer If eoNum = 0 Then List1.AddItem anatNum For I = IIf(upNum < eoNum, upNum, eoNum) To 1 Step -1 Call anatFor(eoNum - I, I, anatNum & I) Next IEnd Sub
2006-11-15 00:22:05 補充：
改好囉~~~
多加一個參數,記錄上層遞迴的值..
比較上層的值upNum,和遞減值eoNum誰小,
值小的由來Run For迴圈...
謝謝愁痕大囉!這樣程式執行效能又快了許多,省了一堆迴圈....
W.J.S大,我正在思考這題不用遞迴怎麼解...
2006-11-16 00:58:39 補充：
這次月島大沒加入...
真想看看他的寫法 :p
2006-11-17 10:10:09 補充：
http://specterglobe.myweb.hinet.net/test001.txt
我也不用遞迴寫了一個..
基本上並沒有寫得並不好,只是想換個思考方式...
輸入多少就同時產生其他的答案..
比方輸入5,就同時產生4,3,2,1的答案,放在nAry陣列中...
2006-11-17 10:19:51 補充：
月島大不愧為我的恩師哪~~
果然出手了... XD
...
.......
其實月島大是我學做料理的恩師..
冷~~~~~~~~
2006-11-18 11:17:33 補充：
我原本的想法是...
先產生N的答案出來,再去取用N的答案來產生N+1的答案..
比如5的答案的第3至第4列..
32
311
遮著3的部份
2
11
不就正是2的答案
2006-11-18 11:17:50 補充：
而第5至第6列..
221
2111
遮著2的部份
21
111
不就正是3的答案的下半部...
後來愁大教我,這正是'動態規劃'的想法...
這想法在理論上執行速度應可更快(因為可直接取用,不用重新執行迴圈)
不過因為我個人的寫法及方式不佳,導至執行效率反正比遞迴更慢...
貼上網址,純綷是因為食之無味,棄之可惜哪....
2006-11-19 13:52:28 補充：
W.J.S大您過獎了...
我還要向各位大大多學習...
2006-11-14 16:41:52 · answer #1 · answered by 幽靈 5 · 0⤊ 0⤋
在下的作法只能解N<=10以下的狀況既然被點名了 就上來獻醜一下吧 望眾高手莫見怪 ^^Private Sub Command2_Click()Dim mString As StringN = Val(InputBox("N="))Call BB(N, N, mString)End SubSub BB(ByVal N As Integer, ByVal Num As Integer, ByVal Cannot As String)For i = Num To 1 Step -1 If ST(Cannot) + i = N Then Print Cannot & CStr(i) ElseIf ST(Cannot) + i < N Then Cannot = Cannot + CStr(i) Call BB(N, i, Cannot) Cannot = Mid$(Cannot, 1, Len(Cannot) - 1) End IfNext iEnd SubFunction ST(Word As String) As IntegerFor i = 1 To Len(Word) ST = ST + Val(Mid$(Word, i, 1))Next iEnd Function
2006-11-16 06:05:24 · answer #2 · answered by ? 5 · 0⤊ 0⤋
TO:愁大
怎麼會這麼問我呢？
你有要去比？（好奇）
TO:亡靈大
常動腦不只有趣，還可以防老化~XD
大家一起來作『防老化運動』吧！
（我真的病了，而且病得不輕...）
2006-11-15 11:20:27 補充：
哈哈~是呀是呀~XD
2006-11-15 14:10:44 補充：
愁大~DP是什麼？
2006-11-15 16:50:35 補充：
ㄛ~~這個講中文我就知道了 (^^
我現在在煩惱之後要怎麼選最佳解答ㄋㄟˋ
各位大大的程式都各有優點......
2006-11-16 07:33:15 補充：
嗯ㄚ......
我也想看看月島大的寫法 (一.一
2006-11-16 07:40:01 補充：
請問...
各位老大~
還有人要發表更簡短執行效率更好的程式嗎？
沒有的話，小妹將在11月17日上午11點30分送交投票ㄛ~~
（請把握機會，要買要快ㄛ~）
2006-11-17 07:24:55 補充：
有~收到了~~
目前正在消化當中。。。
2006-11-20 07:11:16 補充：
To:何大
不能用可能是因為我的電腦沒開...
(假日或者是晚上就不會在學校了...^^)
2006-11-20 07:49:19 補充：
各位老大~~
要小的我在發問幾個問題嗎？
發問來跟老大們一起討論可以多學很多東西~~
當然，我也會貼上程式碼的~~(^^
2006-11-15 03:51:23 · answer #3 · answered by 以晴 2 · 0⤊ 0⤋
'請將程式考到VB編輯視窗裏面才容易閱讀
Private Sub Command1_Click()
1: Dim 整數&, 指標&, 分割&(10) '程式使用到這 3 組變數
2: 整數 = InputBox("輸入1~10之整數") * 2
'上面這列設 整數 為輸入的兩倍
'以便讓程式切割成兩半
3: 分割&(0) = 整數 / 2 + 1 '先設 分割&(0) 為輸入之數+1
'以配合程式第 10 列會減 1
4: Cls '清除螢幕,以便下次
'執行能重新輸出
5: Do '5~22 為整個大迴路,執行完
'全部分割完畢
6: Do Until 分割(指標) > 1 '6~9 從右往左加回整數
'直到陣列大於 1
7: 指標 = 指標 - 1 '指標往下移
8: 整數 = 整數 + 分割(指標) '整數一直累加
9: Loop '迴路之底
10: 分割(指標) = 分割(指標) - 1 '將陣列減 1,準備繼續往下分割
11: Do Until 整數 <= 分割(指標) '11~15 從左往右分割
'直到 整數 小於等於分割數為止
12: 整數 = 整數 - 分割(指標) '分割
13: 指標 = 指標 + 1 '指標往上移
14: 分割(指標) = 分割(指標 - 1) '先設定陣列為分割數
15: Loop '迴路之底
16: 分割(指標) = 整數 '假如 整數 小於分割數,
'此列保證陣列尾端數值正確
17: Print 分割(0); "="; '17~21將每次分割輸出
18: For 指標 = 1 To 指標 - 1 '
19: Print 分割(指標); "+"; '
20: Next '
21: Print 分割(指標) '
22: Loop Until 分割(1) = 1 '大迴路之底,做到 分割(1) = 1
'為止
End Sub
2006-11-15 10:52:15 補充：
24小時不寫成程式,病情就會惡化
2006-11-16 11:59:00 補充：
以晴
我已寫好誠"完全排列",也寄給你了
2006-11-17 00:31:31 補充：
以晴
"完全排列"程式,收到了嗎?
不用遞迴,不用多巢迴路,10個元素
,執行約5秒,編譯成.EXE檔,執行只須0.1秒
因我的英文不好,程式裏有許多中文變數.
想了解程式,請用即時通
TUAN_YAO@YAHOO.COM.TW
2006-11-18 01:13:15 補充：
來自亡靈的信函
你在寫什麼?
以晴
我無法成功使用你傳給我的檔
案
2006-11-20 19:32:44 補充：
好!
再發問.
2006-11-20 19:32:48 補充：
好!
再發問.
2006-11-14 20:16:27 · answer #4 · answered by ? 2 · 0⤊ 0⤋
以晴: 妳是不是十二月要到彰商比賽呀..?
2006-11-14 23:18:13 補充：
找碴一下..來函兄的演算法有小小瑕疵
2006-11-14 23:19:27 補充：
N=7
則 1 6 是不應出現的結果:P
2006-11-15 00:51:20 補充：
'這次用的是DP的概念,請參考Private Sub Command1_Click() Dim i&, j&, N% Dim flag As Boolean Do N = Abs(Val(InputBox("輸入一個正整數 , 1<=N<=10"))) Loop Until N > 0 And N <= 10 ReDim arr_num(N) As String arr_num(1) = "1" 'N=1時,為1 Cls '動態規劃 For i = 2 To N arr_num(i) = arr_num(i - 1) '先取前一個結果 arr_tmp = Split(arr_num(i), vbCrLf) '以換行字元切割出一個tmp陣列 arr_tmp2 = arr_tmp '再複製一個tmp2陣列 For j = 0 To UBound(arr_tmp) arr_tmp(j) = Val(Mid(arr_tmp(j), 1, 1)) + 1 & Mid(arr_tmp(j), 2) '左邊第一字+1 arr_tmp2(j) = "1" & arr_tmp2(j) '左邊串接一個1 Next '兩tmp陣列合併 arr_num(i) = Join(arr_tmp, vbCrLf) & vbCrLf & Join(arr_tmp2, vbCrLf) Next '輸出 arr_out = Split(arr_num(N), vbCrLf) For i = 0 To UBound(arr_out) flag = True '檢查是否為合法的分割數列 For j = 1 To Len(arr_out(i)) - 1 If Mid(arr_out(i), j, 1) < Mid(arr_out(i), j + 1, 1) Then flag = False: Exit For Next If flag Then Print arr_out(i) NextEnd Sub ps: 因應題目只能run 1~10,就不多做處理了
2006-11-15 15:13:35 補充：
Dynamic Programming 動態規劃
2006-11-14 19:51:20 · answer #5 · answered by ? 6 · 0⤊ 0⤋
Private Sub Command1_Click() Dim I As Integer, J As Integer, A As Integer, N As Integer Do N = Abs(Int(Val(InputBox("請輸入正整數", , 5)))) Loop Until N Cls ReDim X(1 To N) As String: X(1) = N Do Print Join(X, "") For I = N To 1 Step -1 If Val(X(I)) > 1 Then X(I) = X(I) - 1: A = N For J = 1 To I A = A - X(J) Next Do While A > Val(X(J - 1)) X(J) = X(J - 1) A = A - X(J): J = J + 1 Loop X(J) = A: Exit For Else X(I) = "" End If Next DoEvents Loop While IEnd Sub
2006-11-14 18:57:55 補充：
這次別太早結束題目XD
2006-11-14 23:08:34 補充：
來..函兄:
簡潔又易懂,棒,嗯....應該規定不可用遞迴啦XD
2006-11-18 23:24:41 補充：
亡靈兄:
我跟月大都覺得您的邏輯觀念粉強ㄋㄟ
請受我一拜 Orz
2006-11-14 13:46:27 · answer #6 · answered by W.J.S. 7 · 0⤊ 0⤋