使用所有可能的组合创建序列

Question

我正在尝试解决以下问题：对于给定的 n 和 α，确定 n 可以表示为 k 个数之和的最小数 k，其中每个数都是完美的 α 次方。

我的第一个想法是创建一个长度为 n 的序列，然后使用递归创建具有完美 α 次方的所有可能序列。创建序列后，我将检查序列中所有数字的总和是否为 n，然后检查数字总数是否小于 k，如果两者都为真，则我将更新 k。我编写了一个解决大多数情况的程序，但出于某种原因并没有创建所有可能的序列。例如，如果用户为 n 输入 92，为 α 输入 3，那么 k 应该是 3，因为 4^3 + 3^3 + 1^3 = 92，但是我的程序 returns 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，这就是答案。我将这些 "feedbacks" 添加到您的代码中。

#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

使用所有可能的组合创建序列

Creating sequences with every possible combination

c++

tail-recursion