可能な組み合わせでシーケンスを作成する

Question

私は以下の問題を解決しようとしています：与えられた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; 
} 

Answer 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