遞迴基本觀念詢問

小弟剛開始學程式
最近看到了遞迴這個東西
對這個觀念還不是很了解
就做一些線上題目來練習
但是碰到了瓶頸>"<
像這題

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

i 應該是 0 ~ a 吧? j,k 同理應該是 0~b, 0~c

而且題目是說 "每個test case 輸出一行"，你現在最後會少一個'\n'


最後你這樣寫太容易出錯了...

1. a,b,c 很大時候  這一定TLE
2. lv_a * i + lv_b * j + lv_c * k 這有可能 overflow

gitlab 發表於 2016-5-20 08:26 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

i 應該是 0 ~ a 吧? j,k 同理應該是 0~b, 0~c

而且題目是說 "每個test case 輸出一行"，你現在最後會少一 ...

...

瀏覽完整內容，請先 註冊 或 登入會員

我把範圍改了
真的是0~a的關係
感謝大大~
但是我還是很想知道遞迴的寫法
感覺會遞迴可以方便很多~

gitlab

這題用遞迴不會比較方便 但也有可能是我沒想到..

snowflying

st474ddr 發表於 2016-5-21 01:41 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

恩恩感謝大大
我也有考慮到TLE的情況
但是是吃了WA

...

瀏覽完整內容，請先 註冊 或 登入會員

ren1244

snowflying 發表於 2016-5-22 06:34 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

其實可以少掉一層，前兩層的和知道後，最後一層用數學處理

借用snowflying程式碼再加一些東西：
1.判斷 i , j 要跑的上限，避免A*i或B*j>remain的情形
...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

呃…要減少迴圈數的話 應該把 min(a,D/A), min(b,D/B), min(c,D/C) 數字最大的放"外面"

a333221

題目是不是有等全部的 input 輸入完，再一次將所有結果 output 的意思？

還是我誤會了

a333221 發表於 2016-5-22 04:55 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

題目是不是有等全部的 input 輸入完，再一次將所有結果 output 的意思？

還是我誤會了

沒有 一個case 的 input輸入完後
...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

st474ddr 發表於 2016-5-23 12:01 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

沒有 一個case 的 input輸入完後
會馬上output

如果沒有「等全部的 input 輸入完，再一次將所有結果 output」的要求，
...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

a333221 發表於 2016-5-23 09:37 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

如果沒有「等全部的 input 輸入完，再一次將所有結果 output」的要求，
那 notes 的要求好像沒什麼必要， ...

依照印象，大部分都是把輸出寫到檔案，然後與答案的檔案比對
...

瀏覽完整內容，請先 註冊 或 登入會員

ren1244

還是勉強自己寫遞迴版了。
真的覺得不能用陣列跟指標不合理阿，能用的話根本不用switch…case那段。

1. int a,b,c,A,B,C,D; //讀取資料後，存放在廣域變數中(因為不能用陣列跟指標，又不想重複傳資料)
   
2. 
   
3. int IsLotion(int remain,int id)
   
4. {
   
5.         int num,power,i,r;
   
6.         switch(id) //不能用陣列跟指標，只好用這麼醜的寫法
   
7.         {
   
8.                 case 0:
   
9.                         num=a;
   
10.                         power=A;
    
11.                         break;
    
12.                 case 1:
    
13.                         num=b;
    
14.                         power=B;
    
15.                         break;
    
16.                 case 2:
    
17.                         num=c;
    
18.                         power=C;
    
19.                         break;
    
20.         }
    
21.         for(i=num<=remain/power?num:remain/power;i>=0;--i)
    
22.         {
    
23.                 r=remain-i*power;
    
24.                 if(r==0 || (id<2 && func(r,id+1)))
    
25.                         return 1;
    
26.         }
    
27.         return 0;
    
28. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

snowflying 發表於 2016-5-24 12:56 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

依照印象，大部分都是把輸出寫到檔案，然後與答案的檔案比對
所以是不是一次輸出，都可以
至於 notes 的 ...

...

瀏覽完整內容，請先 註冊 或 登入會員

只要背後的邏輯不變, 迴圈或遞迴都一樣, 只是喜好選擇
為了用遞迴而刻意去套個不一樣的邏輯才是本末倒置

1. #include <stdio.h>
   
2. 
   
3. #define MIN(a, b)       ((a) < (b) ? (a) : (b))
   
4. #define MAX(a, b)       ((a) > (b) ? (a) : (b))
   
5. 
   
6. static int power;
   
7. static int qtyA, qtyB, qtyC;
   
8. static int powA, powB, powC;
   
9. 
   
10. int TestR(int a, int b, int which)
    
11. {
    
12.     int min, max, i;
    
13.     int powerNeeded;
    
14. 
    
15.     switch(which)
    
16.     {
    
17.     case 0:
    
18.         min = (power - qtyB * powB - qtyC * powC) / powA;
    
19.         min = MAX(min, 0);
    
20.         max = power / powA;
    
21.         max = MIN(max, qtyA);
    
22.         for (i = min; i <= max; i++)
    
23.         {
    
24.             if (TestR(i, 0, 1))
    
25.             {
    
26.                 return 1;
    
27.             }
    
28.         }
    
29.         break;
    
30. 
    
31.     case 1:
    
32.         powerNeeded = power - a * powA;
    
33.         min = (powerNeeded - qtyC * powC) / powB;
    
34.         min = MAX(min, 0);
    
35.         max = powerNeeded / powB;
    
36.         max = MIN(max, qtyB);
    
37.         for (i = min; i <= max; i++)
    
38.         {
    
39.             if (TestR(a, i, 2))
    
40.             {
    
41.                 return 1;
    
42.             }
    
43.         }
    
44.         break;
    
45. 
    
46.     default:
    
47.         powerNeeded = power - a * powA - b * powB;
    
48.         if (powerNeeded % powC == 0)
    
49.         {
    
50.             if (powerNeeded / powC <= qtyC)
    
51.             {
    
52.                 return 1;
    
53.             }
    
54.         }
    
55.         break;
    
56.     }
    
57. 
    
58.     return 0;
    
59. }
    
60. 
    
61. int TestL()
    
62. {
    
63.     int minA = (power - qtyB * powB - qtyC * powC) / powA;
    
64.     minA = MAX(minA, 0);
    
65.     int maxA = power / powA;
    
66.     maxA = MIN(maxA, qtyA);
    
67.     int a;
    
68. 
    
69.     for (a = minA; a <= maxA; a++)
    
70.     {
    
71.         int powerNeededB = power - a * powA;
    
72.         int minB = (powerNeededB - qtyC * powC) / powB;
    
73.         minB = MAX(minB, 0);
    
74.         int maxB = powerNeededB / powB;
    
75.         maxB = MIN(maxB, qtyB);
    
76.         int b;
    
77. 
    
78.         for (b = minB; b <= maxB; b++)
    
79.         {
    
80.             int powerNeededC = powerNeededB - b * powB;
    
81.             if (powerNeededC % powC == 0)
    
82.             {
    
83.                 int c = powerNeededC / powC;
    
84.                 if (c <= qtyC)
    
85.                 {
    
86.                     return 1;
    
87.                 }
    
88.             }
    
89.         }
    
90.     }
    
91. 
    
92.     return 0;
    
93. }
    
94. 
    
95. int main()
    
96. {
    
97.     int n;
    
98.     scanf("%d", &n);
    
99.     while(n--)
    
100.     {
     
101.         int found = 0;
     
102. 
     
103.         scanf("%d %d %d %d %d %d %d", &power,
     
104.               &qtyA, &qtyB, &qtyC,
     
105.               &powA, &powB, &powC);
     
106. 
     
107.         found = TestR(0, 0, 0);
     
108.         print f("%s\n", found ? "yes" : "no");
     
109. 
     
110.         found = TestL();
     
111.         print f("%s\n", found ? "yes" : "no");
     
112.     }
     
113. 
     
114.     return 0;
     
115. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員