この関数を末尾再帰として再実装するか、それ以外のメモリを使用しないでください。

Question

次の計算を再帰的に行う必要があります。

1から30までの任意のnに対して、1からnまでのすべての可能な組み合わせを考慮する必要があります。したがって、たとえばn = 5の場合：

1 ± 2 ± 3 ± 4 ± 5 ± 6 = ?; 

数値自体と等しい可能な式の数を見つける必要があります。だから、N = 5、5に等しいだけ、次の二つの表現のために：

5 = 1 + 2 + 3 + 4 − 5 
5 = 1 − 2 − 3 + 4 + 5 

私のアプローチ

私は、再帰の各レベルが "を加算または減算する場所を再帰的なツリーを作成する方法を考え出しました深さ '。結果として、最終的な深さでは、ノードはすでに計算された合計を持つことになります。つまり、最初の数に等しいかどうかを確認するだけです。

Recursive Tree Image

これは大丈夫動作しますが、より多くの数n>は26で私は巨大なメモリ消費量に苦しむとプログラムは時間がかかりすぎます。少しの数学ではなぜそれが明らかになったのか。 これをどうすれば最適化できますか？私はそれを尾の再帰に変えようとしてきましたが、私のためにはうまくいきません...私は2つの再帰的な呼び出しがあるときにそれを実装する方法を理解できません。

node* buildTree(int depth, int data){ 

    node* nNode = addNode(1); 

    if(depth==n+1){ 
     if(data == n) { 
      result++; 
     } 
     return nNode; 
    } 

    else{ 
     nNode->pos = buildTree(depth+1,data+depth); 
     nNode->neg = buildTree(depth+1,data-depth); 
     return nNode; 
    } 
} 

グローバルスコープ変数&メインの私のツリーを構築します

ツリー構造と作成機能

typedef struct nodes { 
    unsigned int value; 
    struct node* pos; 
    struct node* neg; 
} node; 


node* addNode(int data){ 

    node* newNode = (node*)malloc(sizeof(node)); 
    newNode->value = data; 
    newNode->pos = NULL; 
    newNode->neg = NULL; 

    return newNode; 
} 

機能：：ここで

は私のコードです

int result = 0; 
int n; 

int main(int argc, char **argv) 
{ 
    scanf("%i",&n); 
    buildTree(2,1); //build tree starting with recursion depth = 2, first node value = 1. 
    printf("%i\n",result); 

    return 0; 
} 

助けてください - 私はこれに長続きしていません。

Answer 1

私はあなたがこれのために木を必要とは思わない。

いくつかの単純な再帰が何をすべき

：

#include <stdio.h> 

void f(int current_sum, int current_depth, int target_depth) 
{ 
    if (current_depth > target_depth) 
    { 
      // Here you have the final result for this path 
     printf("%d\n", current_sum); 
     return; 
    } 
    f(current_sum+current_depth, current_depth+1, target_depth); 
    f(current_sum-current_depth, current_depth+1, target_depth); 
} 

int main(void) { 
    f(0, 1, 3); // I use n=3 
    return 0; 
} 

出力：

6 
0 
2 
-4 
4 
-2 
0 
-6 

TIP：あなたは後半の番号であることを注目して、実行時のパフォーマンスに多くを向上させることができます前半のネガティブ。

f(current_sum+current_depth, current_depth+1, target_depth); 
    if (current_depth != 1) 
    { 
     f(current_sum-current_depth, current_depth+1, target_depth); 
    } 

のようにしてください。