Re: [使徒] 來點提示好了 ;p

[chhsiao (bye~)]

有些同學把 code 寄給我, 問我 code 哪裡有問題,
不過結果常常是通篇都有問題 XD

下面是我回某同學的內容, 希望對大家有幫助 :)

---

我覺得你的想法應該還沒完全弄清楚,
要不然就是你還不會用 C 這個語言去 "說" 你的想法.

傳多少個參數不是重點,
我也可以寫出完全不用傳參數的遞迴.
重要的是要先把遞迴關係明確定義出來,
再用 C 語言按照定義寫出來.

你想用只傳一個參數的話, 我想到的有兩種比較直觀的遞迴式:

1. pick(current) 代表 "決定第 current 個 guest 要不要取":

pick(current) =
    (1) if current == N then output the selection.
    (2) if current < N then
        (a) select the current guest,
            update veriables which should be changee by this selection,
            call pick(current + 1) to complete the selection,
            then restore variables which have been changed by this selection.
        (b) DO NOT select the current guest,
            just call pick(current + 1) to complete the selection.

2. pick(current) 代表 "決定第 current 取的人是誰":

pick(current) =
    (1) if current == sum then output the selection.
    (2) if current < sum then
        let k be the pervious selected id + 1, or the first id if current == 0.
        for all k'th, (k+1)'th, (k+2)'th, ..., N'th id,
            try each id as the current selection,
            update variables which should be changed by this selection,
            call pick(current + 1) to complete the selection,
            then restore variables which have been changed by this selection.

注意一下, 題目不僅要求輸出的列表要排序,
連不同列表之間也要按順序輸出喔!
例如 1 2 4 5 7 一定要在 1 3 4 5 6 之前輸出.
由於不同的遞迴呼叫順序會造成不同的輸出順序,
因此用正確的遞迴順序就可以直接做到.
比方說

假設 1 已經選了, 那我們只要能夠在遞迴選擇時,
確保 "第二個選 2" 比 "第二個選 3" 還要早發生,
那輸出順序一定就對了.

希望這對你有幫助.

--
n;main(i){return n?i<2?i:main(i-1)+main(i-2):
scanf("%d",&n)&&printf("%d\n",n>0?main(n):0);}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.54
推 yangmie:請問第8組測資是特別機車的嗎?其他組都過了...只差1...
推 greenoyster:比較大
推 chhsiao:啊 這樣很大喔? XD
推 DarkKnightX:這樣很大喔? XD
推 BNMAA:       這樣很大喔? XD
→ BNMAA:errata 1. (1)-(a)   com'p'lete
※ 編輯: chhsiao         來自: 140.112.30.54        (10/29 01:27)
推 chhsiao:Corrected.