查看完整版本: 遞迴基本觀念詢問

論壇 › C & C++ 語言 › 遞迴基本觀念詢問

st474ddr 發表於 2016-5-20 04:11 PM

遞迴基本觀念詢問

本帖最後由 st474ddr 於 2016-5-20 04:12 PM 編輯

小弟剛開始學程式
最近看到了遞迴這個東西
對這個觀念還不是很了解
就做一些線上題目來練習
但是碰到了瓶頸>"<
像這題
https://judgegirl.csie.org/problem/0/38
我就不懂遞迴要用在什麼地方(腦筋轉不動>"<)
所以我先嘗試著用迴圈去寫
code如下:
#include <stdio.h>
main()
{
    int i, j, k, num, sum, a, b, c, lv_a, lv_b, lv_c, flag;
    scanf("%d", &num);
    while(num--)
    {
        scanf("%d %d %d %d %d %d %d", &sum, &a, &b, &c, &lv_a, &lv_b, &lv_c);
        flag = 0;
        for(i = 0; i < a; i++)
            for(j = 0; j < b; j++)
                for(k = 0; k < c; k++)
                {
                    //print f("i = %d, j = %d, k = %d, sum = %d\n", i, j, k, lv_a * i + lv_b * j + lv_c * k);
                    if(sum == lv_a * i + lv_b * j + lv_c * k)
                    {
                        flag = 1;
                        goto result;
                    }
                }
result:
        if(flag == 1)
            print f("yes");
        else
            print f("no");
        if(num != 0)
            print f("\n");
    }
}

可是竟然吃了一個WA
是我沒看懂題目嗎?
還是一定要遞迴才能解這題?
感恩各位大大




...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div>

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

本帖最後由 gitlab 於 2016-5-20 08:26 PM 編輯

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

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

本帖最後由 st474ddr 於 2016-5-21 01:45 AM 編輯

gitlab 發表於 2016-5-20 08:26 PM static/image/common/back.gif
i 應該是 0 ~ a 吧? j,k 同理應該是 0~b, 0~c

而且題目是說 "每個test case 輸出一行"，你現在最後會少一 ...
恩恩感謝大大
我也有考慮到TLE的情況
但是是吃了WA
所以沒考慮那麼多....我會再改改的~
那請問大大這題有套的到遞迴的解法嗎??
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

st474ddr 發表於 2016-5-21 07:41 PM

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

gitlab 發表於 2016-5-21 09:57 PM

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

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

本帖最後由 snowflying 於 2016-5-22 06:35 AM 編輯

st474ddr 發表於 2016-5-21 01:41 AM static/image/common/back.gif
恩恩感謝大大
我也有考慮到TLE的情況
但是是吃了WA

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

for(i = 0 ; i <= a ; ++i)
{
      for(j = 0 ; j <= b ; ++j)
      {
           int remain = D - i * A - j * B;
                        
           if(C == 0 && remain == 0)
                return 1;
           if(C != 0 && remain % C == 0 && remain / C <= c)
                return 1;
      }
}

這題看題目規定不能用指標和陣列，實在不想用遞迴
而且遞迴有可能還比較慢


...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

ren1244 發表於 2016-5-22 11:38 AM

snowflying 發表於 2016-5-22 06:34 AM static/image/common/back.gif
其實可以少掉一層，前兩層的和知道後，最後一層用數學處理




借用snowflying程式碼再加一些東西：
1.判斷 i , j 要跑的上限，避免A*i或B*j>remain的情形
2.因為c用數學計算，所以把最大的數字放在c，可以減少迴圈數
int IsLotion(int D,int a,int b,int c,int A,int B,int C)
{//傳入一組資料(D,a,b,c,A,B,C)，回傳此筆資料是否符合條件(yes=1,no=0)
        int remain_A,remain_B,na,nb,i,j;
        na=a<D/A?a:D/A;
        for(i=0;i<=na;++i)
        {
                remain_A=D-A*i;
                nb=b<remain/B?b:remain/B;
                for(j=0;j<=nb;++j)
                {
                        if((remain_B=remain_A-B*j)==0)
                                return 1;
                        if(C!=0 && remain_B%C==0 && remain_B/C<=c)
                                return 1;
                }
        }
        return 0;
}
int IsLotionHasten(int D,int a,int b,int c,int A,int B,int C)
{//將最大的數字放最後，直接使用數學計算，不用跑迴圈
        if(c>=b && c>=a)
                return IsLotion(D,a,b,c,A,B,C);
        if(b>=c && b>=a)
                return IsLotion(D,a,c,b,A,C,B);
        if(a>=b && a>=c)
                return IsLotion(D,b,c,a,B,C,A);
}
使用時呼叫2個函數其中之一即可，IsLotionHasten會把最大的放最後直接用數學計算...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

gitlab 發表於 2016-5-22 03:54 PM

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

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

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

還是我誤會了

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

a333221 發表於 2016-5-22 04:55 PM static/image/common/back.gif
題目是不是有等全部的 input 輸入完，再一次將所有結果 output 的意思？

還是我誤會了


沒有 一個case 的 input輸入完後
會馬上output <br><br><br><br><br><div></div>

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

st474ddr 發表於 2016-5-23 12:01 AM static/image/common/back.gif
沒有 一個case 的 input輸入完後
會馬上output

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

「感覺會遞迴可以方便很多~」將你「 while(num--) {...}」裡面的 code 寫成一個函數，
就可以把 flag 變數拿掉，也可以省掉 goto，code 會變好寫，也較清晰容易閱讀...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

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

a333221 發表於 2016-5-23 09:37 PM static/image/common/back.gif
如果沒有「等全部的 input 輸入完，再一次將所有結果 output」的要求，
那 notes 的要求好像沒什麼必要， ...

依照印象，大部分都是把輸出寫到檔案，然後與答案的檔案比對
所以是不是一次輸出，都可以
至於 notes 的部份，個人感覺兩者都差不多


寫成函式不代表用到遞迴
這也是我看不懂題目到底想要大家怎麼寫的原因
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

ren1244 發表於 2016-5-24 03:00 AM

還是勉強自己寫遞迴版了。
真的覺得不能用陣列跟指標不合理阿，能用的話根本不用switch…case那段。int a,b,c,A,B,C,D; //讀取資料後，存放在廣域變數中(因為不能用陣列跟指標，又不想重複傳資料)

int IsLotion(int remain,int id)
{
        int num,power,i,r;
        switch(id) //不能用陣列跟指標，只好用這麼醜的寫法
        {
                case 0:
                        num=a;
                        power=A;
                        break;
                case 1:
                        num=b;
                        power=B;
                        break;
                case 2:
                        num=c;
                        power=C;
                        break;
        }
        for(i=num<=remain/power?num:remain/power;i>=0;--i)
        {
                r=remain-i*power;
                if(r==0 || (id<2 && func(r,id+1)))
                        return 1;
        }
        return 0;
}
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

a333221 發表於 2016-5-24 11:46 PM

snowflying 發表於 2016-5-24 12:56 AM static/image/common/back.gif
依照印象，大部分都是把輸出寫到檔案，然後與答案的檔案比對
所以是不是一次輸出，都可以
至於 notes 的 ...

我的意思是原 po 如果要的是方便，
那麼將寫法改寫一下就可以達到一些效果，
原 po 那句的重點我想是在「方便很多」不在「遞迴」，
這題如果硬要用遞迴，我想得到的是輾轉相除法，
但那只會讓 code 變得更複雜，
也不見得就弄得出來...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div>

inunu 發表於 2016-5-25 08:06 AM

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

#define MIN(a, b)       ((a) < (b) ? (a) : (b))
#define MAX(a, b)       ((a) > (b) ? (a) : (b))

static int power;
static int qtyA, qtyB, qtyC;
static int powA, powB, powC;

int TestR(int a, int b, int which)
{
    int min, max, i;
    int powerNeeded;

    switch(which)
    {
    case 0:
        min = (power - qtyB * powB - qtyC * powC) / powA;
        min = MAX(min, 0);
        max = power / powA;
        max = MIN(max, qtyA);
        for (i = min; i <= max; i++)
        {
            if (TestR(i, 0, 1))
            {
                return 1;
            }
        }
        break;

    case 1:
        powerNeeded = power - a * powA;
        min = (powerNeeded - qtyC * powC) / powB;
        min = MAX(min, 0);
        max = powerNeeded / powB;
        max = MIN(max, qtyB);
        for (i = min; i <= max; i++)
        {
            if (TestR(a, i, 2))
            {
                return 1;
            }
        }
        break;

    default:
        powerNeeded = power - a * powA - b * powB;
        if (powerNeeded % powC == 0)
        {
            if (powerNeeded / powC <= qtyC)
            {
                return 1;
            }
        }
        break;
    }

    return 0;
}

int TestL()
{
    int minA = (power - qtyB * powB - qtyC * powC) / powA;
    minA = MAX(minA, 0);
    int maxA = power / powA;
    maxA = MIN(maxA, qtyA);
    int a;

    for (a = minA; a <= maxA; a++)
    {
        int powerNeededB = power - a * powA;
        int minB = (powerNeededB - qtyC * powC) / powB;
        minB = MAX(minB, 0);
        int maxB = powerNeededB / powB;
        maxB = MIN(maxB, qtyB);
        int b;

        for (b = minB; b <= maxB; b++)
        {
            int powerNeededC = powerNeededB - b * powB;
            if (powerNeededC % powC == 0)
            {
                int c = powerNeededC / powC;
                if (c <= qtyC)
                {
                    return 1;
                }
            }
        }
    }

    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int found = 0;

        scanf("%d %d %d %d %d %d %d", &power,
              &qtyA, &qtyB, &qtyC,
              &powA, &powB, &powC);

        found = TestR(0, 0, 0);
        print f("%s\n", found ? "yes" : "no");

        found = TestL();
        print f("%s\n", found ? "yes" : "no");
    }

    return 0;
}

...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div>