创建序列与每个可能的组合

-3

我想解决以下问题：对于给定的n和α，确定最小数目k，其中n可以表示为k个数字的总和，其中每个数字都是完美的α-th功率。创建序列与每个可能的组合

我的第一个想法是创建一个长度为n的序列，然后使用递归创建具有完美α次方的所有可能序列。在创建序列之后，我会检查序列中所有数字的总和是否等于n，然后检查总数是否小于k，如果这些都是真的，那么我会更新k。我写了一个解决大多数情况的程序，但由于某种原因不能创建所有可能的序列。例如，如果用户输入92代表n和3代表α，那么k应该是3，因为4^3 + 3^3 + 1^3 = 92，但是我的程序返回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; 
}

来源

2017-04-13 idknuttin

尝试用调试器逐句通过。这是一个调试器的用途。 – Peter

@Peter我试图在创建它们时显示所有序列，并且我发现它并没有创建所有可能性，每次都打印出每个序列的总和，循环和递归看起来应该创建每个可能的序列我无法弄清楚为什么它不是。 – idknuttin

好的，您没有任何反馈信息。让我们举一个例子：循环创建数组... 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

来源

2017-04-14 00:05:06 Sklert

创建序列与每个可能的组合

回答

相关问题