iT邦幫忙

0

recursion function的問題

輸入字串 => 1, 3 , (2,4,6), 5, 7
輸出以下

1+3

1+ ( (2+4)+(2+6)+(4+6))

1+5

1+7

3+ ( (2+4)+(2+6)+(4+6))

3+5

3+7

( (2+4)+(2+6)+(4+6)) +5

( (2+4)+(2+6)+(4+6))+7

5+7

我在練習遞迴,所以我寫了一個會先計算 題目中(2,4,6)的總和的程式,
但出來總和一直是錯誤的

以下是我的程式片段

#include<stdio.h>
     int recursion(int* array,int i,int j,int size){
     	int sum = 0;
            if(i < size-1){
                   if(j < size ){
                        printf("%d\n",array[i]+array[j]);
                        sum = sum+array[i]+array[j];
                        j++;
                        recursion(array,i,j,size);
                   }
                   else{
                         printf("\n");
                         i++;
                         j=i+1;
                         recursion(array,i,j,size);
                   }
            }       
            return sum;
     }

    int main(){
       int i=0,j=i+1,sum=0;
       int a[3]={2,4,6};
      
       int c =recursion(a,i,j,3);
       printf("\n\n%d",c);
       return 0;
    }

程式print的地方都是正確的都有印出來,但是sum 一直只有算到 6 (應該是2+4算出的)

所以好像只有抓到第一次進入遞迴function的樣子!

請問錯誤在哪裡呢??

看更多先前的討論...收起先前的討論...
weiclin iT邦高手 4 級 ‧ 2016-07-01 18:08:55 檢舉
(2,4,6) 的總合為什麼是 ( (2+4)+(2+6)+(4+6)) ?
題目的要求是這樣@@,但我算不出來
題目要求的那些1+3
1+ ( (2+4)+(2+6)+(4+6))
1+5
1+7 那些應該也都是要算出來然後print的
weiclin iT邦高手 4 級 ‧ 2016-07-01 18:54:12 檢舉
看起來比較像是"組合", 不是"總和"
weiclin iT邦高手 4 級 ‧ 2016-07-01 19:15:59 檢舉
然後先不要管什麼組合跟總和了, 你的 main 裡面的 sum 跟函式裡面的 sum 根本不是同一個變數, 你知道區域變數嗎? 另外 recursion 裡面 return sum, 那呼叫 recursion 的地方是不是都要加上這些 return 的 sum?
我知道兩個是不一樣的 區域變數我知道,我也知道它CALL BY VALUE 只是複製進去而已
我把它改成
int recursion(int* array,int i,int j,int size,int sum){
if(i < size-1){
if(j < size ){
printf("%d\n",array[i]+array[j]);
sum = sum+array[i]+array[j];
j++;
sum+recursion(array,i,j,size,sum);

}
else{
printf("\n");
i++;
j=i+1;
sum+recursion(array,i,j,size,sum);
}
}
return sum;
}
相加起來 則是回傳一個很怪的數
weiclin iT邦高手 4 級 ‧ 2016-07-02 00:25:16 檢舉
所以正確的數字應該是什麼?
24
fillano iT邦超人 1 級 ‧ 2016-07-02 13:20:06 檢舉
你的處理方式(遞增陣列索引)沒辦法處理4取2耶?你要先正確遞迴出組合的方式再做計算吧?
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 個回答

2
海綿寶寶
iT邦大神 1 級 ‧ 2016-07-02 11:39:37
最佳解答
#include<stdio.h>
     int recursion(int* array,int i,int j,int size){
     	int sum = 0;
            if(i < size-1){
                   if(j < size ){
                        printf("+(%d+%d)",array[i], array[j]);
                        sum = sum+array[i]+array[j];
                        j++;
                        sum = sum + recursion(array,i,j,size);
                   }
                   else{
                         i++;
                         j=i+1;
                         sum = sum + recursion(array,i,j,size);
                   }
            }       
            return sum;
     }

    int main(){
       int i=0,j=i+1,sum=0;
       int a[3]={2,4,6};
      
       int c =recursion(a,i,j,3);
       printf("=%d",c);
       return 0;
    }

感謝,我試過return sum = sum + recursion(array,i,j,size);
這樣意思差不多 怎麼就會抓到奇怪的值@@

WilliamHuang
iT邦研究生 1 級 ‧ 2016-07-01 22:24:26
【**此則訊息已被站方移除**】
0
fillano
iT邦超人 1 級 ‧ 2016-07-02 15:23:02

我寫一個Javascript的例子,你再用C實作看看:

function compose2(arr) {
    if(arr.length < 2) return [];
    if(arr.length > 2) {
        var ret = [];
        for(let i=1; i<arr.length; i++) {
            ret.push([arr[0], arr[i]]);
						//用陣列第一個元素跟其他元素組合
        }
        return ret.concat(compose2(arr.slice(1)));
				//拿掉陣列第一個元素再遞迴下去
    } else {
        return [arr];
				//如果傳入陣列只有兩個元素,直接返回
    }
}

//var a = [1,2,5,3,8,15,24];
var a = [2, 4, 6];
console.log(compose2(a, 2));
//印出 [ [ 2, 4 ], [ 2, 6 ], [ 4, 6 ] ]
console.log(compose2(a, 2).reduce(function(p, c) {return p + c[0] + c[1]}, 0));
//印出 24

我的作法是先找出所有組合,再把這些組合算出來。

我要發表回答

立即登入回答