作者chhsiao (bye~)
看板b96902HW
標題Re: [使徒] 來點提示好了 ;p
時間Sun Oct 28 22:31:15 2007
有些同學把 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
1F：推 yangmie:請問第8組測資是特別機車的嗎?其他組都過了...只差1... 10/28 23:01
2F：推 greenoyster:比較大 10/28 23:20
3F：推 chhsiao:啊 這樣很大喔? XD 10/28 23:50
4F：推 DarkKnightX:這樣很大喔? XD 10/29 00:16
5F：推 BNMAA: 這樣很大喔? XD 10/29 00:59
6F：→ BNMAA:errata 1. (1)-(a) com'p'lete 10/29 00:59
※ 編輯: chhsiao 來自: 140.112.30.54 (10/29 01:27)
7F：推 chhsiao:Corrected. 10/29 01:27