→ j129008:總覺得還是有很多東西不清楚...... 05/04 06:16
※ 編輯: j129008 來自: 140.113.68.131 (05/04 06:43)
※ 編輯: j129008 來自: 140.113.68.131 (05/04 06:52)
推 xatier:遞迴只因天上有，凡人應當用迴圈 05/04 18:44
→ j129008:QQ 05/04 19:18
※ 引述《yauhh (喲)》之銘言：
: ※ 引述《j129008 (j129008)》之銘言：
: : 問題(Question)：
: : 無法了解網路上的某篇程式
: goto ......
: : 程式碼(Code)：(請善用置底文網頁, 記得排版)
: break ......
: : void make (int now,int a,int n,int m)
: : {
: : int b=a,c;
: : if(now==m+1)
: : {
: : for(c=1; c<=m; c++)printf("%d ",way[c]);
: : printf("\n");
: : return;
: : }
: : else
: : for(b=a; b<=n; b++)
: : {
: : way[now]=b;
: : make(now+1,b+1,n,m);
: : }
: : }
: : main()
: : {
: : while(scanf("%d %d",&n,&m)==2)
: : make(1,1,n,m);
: 先看主程式呼叫 make 函數怎麼呼叫的,
: : return 0;
: : }
: : 補充說明(Supplement)：
: : 已經想破腦袋了
: : 甚至使用暴力法把程式怎麼跑的一一列出
: : 結果就是看到函式進入堆疊以後不斷的recurtion就排出答案
: : 最弄不懂的地方是make前面的兩個參數到底是怎麼做到組合的
: : 希望有人可以幫我解答一下
: 主程式先取 n m 二數,表示 C n 取 m 的意思. 這二個數字本身有意義.
: 但是卻會呼叫 make(1,1,n,m) 開始. 前面二個參數看不出意義,但是在程式執行時
: 很重要,因為那些是執行時的中繼變數.
: 從定義 void make (int now,int a,int n,int m) 看到二個變數一個叫 now,
: 另一個叫 a, 很顯然 now 是指目前函式內容中最關注的一項訊息.
: 看一下 now 在 make 函式中出現的位置.
: 1. 在 else 之後第一個 now: 操作陣列中一個位置,使那個位置存入 b, 而 b
: 可能是 a 到 n 之間的數字.
: 2. else 之後第二個 now: now 是陣列中的位置,在下一個遞迴中, now 也變成
: 下一個 now (指 now+1).
: 3. 在 if 判斷中的 now: 如果 now 是 m+1, 而 m 的意思是取 m 的意思,
: m+1 就是指 m 都取完了. 所以 now == m+1 是要結束遞迴. 結束的方法就是
: 把 way 陣列全都印出來. 而 way 陣列在前面 1. 2. 的 now 取值過程中,
: 有收集一些東西,那些東西就是答案.
: 所以看著 make 函式中的迴圈,
: 你可以想像迴圈從上往下把 way 的可能結果展開成一列一列.
: 把 way[now] = b 想像成從上往下在每一列同一個位置依序寫 a,b,c,..., 寫到 n.
: (因為迴圈設定 a 到 n 嘛)
: 然後從迴圈中二行可以看到,前面把一列的前一個位置寫了一個 b, 之後遞迴呼叫
: 一定要給一個 b+1, 顯然這個 b, 即 make 函式的參數 a, 代表一個底數.
: 也就是說 make(now, a, n, m) 意思是在 a 到 n 範圍中取 m 個數字組合,
: 而目前正在取的數字位置是 now.
: 這樣胡言亂語一番之後,不知你是否懂了?
: 假如你看懂了,接下來會發現 make 函式一個怪怪的地方是,如果 n 比 m 小......
標題應該是Cn取m才對XD
總算看懂了XD
根據我的理解，make(now,a,n,m)裡的"now"跟"a"
分別代表著Cn取m取了第幾個與目前要從哪裡開始取
所以它recurtion的方法是
ex:C5取3 代表 C5取1 + C4取1 + C3取1
->>for(b=a; b<=n; b++)
由於從loop上看，第一次可以取1~n
第二次從2~n
第三次從3~n
"now"就是代表取第幾次，所以會 1~m
"a"則是取到的內容，為避免重複所以每取一次便 +1
也就是now+1時他也要+1
所以C5取3
總共會取三次
第一次會從1取到3
第二次從2取到4
第三次從3取到5
為什麼一次只會從1取到3呢?
因為當取4時，now==4什麼也不會印
所以說造成第二次跟第三次都只會取三個 //因為每次都會前進1
但是我還是不懂要怎麼樣想到要這樣設計
我只能說如果他取到4的話那就只剩下一個數字就沒辦法做成組合了
當第一次取1時，第二次就可以從2取到4，這樣就不會重複
第二次如果取到3，第三次就可以從4取到5
我只能說這種recurtion法實在非常不直覺
能想出這種方法的人真是奇才.....
不然就是有人能提供更直覺的想法嗎?
我覺得我的理解方法似乎有些問題......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.68.131