2017-04-13 20 views
-3

私は以下の問題を解決しようとしています:与えられたnとαに対して、nが完全なα番目のk個の数字の和として表現できる最小の数kを求めますパワー。可能な組み合わせでシーケンスを作成する

私の最初のアイデアは、長さnのシーケンスを作成し、その後、完全なα乗を持つすべての可能なシーケンスを作成するために再帰を使用することでした。シーケンスを作成した後、シーケンスのすべての数値の合計がnに達したかどうかを確認し、合計の数値がkより小さいかどうかを確認します。両方が真の場合はkを更新します。私はほとんどのケースを解決するプログラムを書いたが、何らかの理由ですべての可能なシーケンスを作成していない。例えば、ユーザがnに対して92を、αに対して3を入力すると、4^3 + 3^3 + 1^3 = 92であるので、kは3でなければならないが、プログラムはk = 92を返す。

#include<iostream> 
#include<cmath> 

void check(const int &N, const int &A, int *pSeq, int position, int &K){ 
    int sum=0; 
    int total=0; 
    for(int i=0; i<N; ++i){ 
    sum+=pSeq[i]; 
    if(pSeq[i]>0){ 
     ++total; 
    } 
    } 
    if(sum==N){ 
    if(total < k){ 
     K=total; 
     std::cout<<"Print seq: "; 
     for(int i =0; i<N; ++i){ 
     std::cout<<pSeq[i] <<" "; 
     } 
     std::cout<<std::endl; 
    } 
    } 
    if(sum<N){ 
    if(position < N){ 
     for(int i=0; pow(i, A)<N+1; ++i){ 
     pSeq[position]=pow(i, A); 
     check(N, A, pSeq, position+1, K); 
     } 
    } 
    } 
} 

int main(){ 
    int n, a; 
    std::cout<<"Enter n and a: "; 
    std::cin>>n >>a; 
    int k=n; 
    int *sequence=new int[n]; 
    for(int i=0; i<n; ++i){ 
    sequence[i]=0; 
    } 

    check(n, a, sequence, 0, k); 

    std::cout<<"k=" <<k <<std::endl; 

    return 0; 
} 
+2

デバッガでステップ実行してみています。これがデバッガの目的です。 – Peter

+1

@Peterすべてのシーケンスを作成して表示しようとしましたが、すべての可能性を生み出していないことがわかりました。毎回各シーケンスの合計を印刷しました。ループと再帰は可能な限りすべて作成する必要がありますなぜ私はそれがなぜではないのか分からない。 – idknuttin

答えて

1

あなたはフィードバックをお寄せください。あなたの例を見てみましょう:ループは配列を作る... 0 0 64 64そしてそれらは行く... 0 1 64 64など64 64 = 128> 92.したがって、 。0 1 27 64、それは答えです。これらの「フィードバック」をコードに追加しました。

#include<iostream> 
#include<cmath> 

int k = 99999; 

void check(const int &N, const int &A, int *pSeq, int position, int &K,bool& too_big,bool& ready){ 
    if (ready) 
    return; 
    int sum=0; 
    int total=0; 
    for(int i=0; i<N; ++i){ 
    sum+=pSeq[i]; 
    if(pSeq[i]>0){ 
     ++total; 
    } 
    } 
    if(sum==N){ 
    if(total < k){ 
     K=total; 
     std::cout<<"Print seq: "; 
     for(int i =0; i<N; ++i){ 
     std::cout<<pSeq[i] <<" "; 
     } 
     std::cout<<std::endl; 
     ready = true; 
     return; 
    } 
    } 
    if(sum<N){ 
    if(position < N){ 
     for(int i=0; pow(i, A)<N+1; ++i){ 
     pSeq[position]=pow(i, A); 
     check(N, A, pSeq, position+1, K,too_big,ready); 
     if (too_big) { 
      too_big = false; 
      pSeq[position]=pow(i-1, A); 
      return; 
     } 
     } 
    } 
    } 
    else 
    too_big = true; 

} 

int main(){ 
    int n, a; 
    std::cout<<"Enter n and a: "; 
    std::cin>>n >>a; 
    int k=n; 
    int *sequence=new int[n]; 
    for(int i=0; i<n; ++i){ 
    sequence[i]=0; 
    } 

    bool too_big = false,ready = false; 
    check(n, a, sequence, 0, k,too_big,ready); 

    std::cout<<"k=" <<k <<std::endl; 

    return 0; 
} 

そして答えは

Print seq: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 27 64 
k=3 
関連する問題