关于算法-数据结构:PAT甲级1103-Integer-Factorization

题目粗心:

给定正整数N,K,P,将N示意为K个正整数的P次方和(递加排序),如果有多个抉择底数和最大的计划,如果还有多个,抉择底数序列字典序最大的序列

算法思路：

题目的思路倒是不难,惯例遍历都能够想得到,然而设计到的技巧还有些,最容易想到的就是从1开始遍历数字,累加以后遍历数字的P次方和,找到相等于N的即可那么在遍历数字的时候会呈现抉择该数或不抉择该数的情,并且能够反复抉择同一个数字,很天然就想到深度优先遍历的思维。上面就大体说下深度优先遍历的根本过程：

• 1、函数的参数有5个，别离是$factor,sum,num,N,K,P$,代表的含意别离是以后抉择的因子，累计的$P$次方和，抉择数字的个数，$N,K,P$为输出的数字，个数和次方数
• 2、在遍历数字的时候就会发现,当数字$N$给定的时候,$N$的因子是有一个上界的(最大也就为$N$),那么咱们能够首先获取$N$的因子的搜寻上界，应用$sup$来保留。
• 3、因为要求抉择字典序最大的序列，那么咱们优先从数字大的($sup$)开始搜寻始终到1为止，这样在获取到$P$次方和为$N$，个数为$K$的序列的时候就只须要获取底数和最大的了
• 4、DFS递归边界：如果找到$P$次方和为$N$，因子个数为$K$的序列，就获取底数更大的序列，如果是$P$次方和大于$N$或者因子个数大于$K$或者待抉择因子等于0就回退。
• 5、DFS递归体：首先，抉择以后因子$factor$,将$factor$保留到$vector$<$int$>$ t$中，而后进入下一轮搜寻，这里的搜寻是能够持续抉择以后因子。DFS(factor,sum+getPowerP(factor,P),num+1,N,K,P);如果不抉择以后因子，那么先将t退出之前抉择的因子，而后在进入下一轮搜寻DFS(factor-1,sum,num,N,K,P);

这里应用了$vector$<$int$>$ result$寄存最优解,每一次在取得一个符合条件的序列后，就应用$getLargerSequence$函数取得序列底数更大的序列，具体代码如下：

// 取得底数更大的序列
void getLargerSequence(){
    if(result.empty()){
        result = t;
    } else {
        int sumT = 0;
        int sumR = 0;
        for (int i = 0; i < t.size(); ++i) {
            sumT += t[i];
            sumR += result[i];
        }
        if(sumT>sumR){
            result.clear();
            result = t;
        }
    }
}

后果的输入：

如果result为空，阐明没有解，输入Impossible，否则从前往后输入每一个因子（搜寻是从大到小，所以就从前往后输入即可）

留神点：

• 1、抉择的因子的上界不能抉择数字N，得通过计算取得其上界sup,不然测试点3，5，6，7运行超时
• 2、在增加了上界sup条件后，如果是从1到sup进行搜寻，会导致测试点5超时
• 3、将搜寻方向改为从大到小后，测试点2有可能会呈现谬误，第一个可能的起因是，没有增加抉择底数之和更大的序列(留神不是字典序之和更大，与从1开始搜寻的区别开)第二个起因可能是DFS的执行过程抉择了先不抉择因子factor，而后再抉择因子factor，也会导致测试点2出错（测试后果是会导致序列乱序的状况，相当于一棵树，走到叶子节点后，再下来一点又上来，到叶子节点后又下来的状况，数字的抉择出现波浪）。
• 4、如果以上还是不能解决运行超时的问题，能够思考应用打表的技巧，将所有N的P次方下的因子全副求出存在在一个数组外面进行搜寻(不肯定有用)。
• 5、vector的赋值操作应用援用赋值能够缩短工夫(尽管不举荐应用)

提交后果：

AC代码：

#include <cstdio>
#include <vector>

using namespace std;

vector<int> t;//暂存以后搜寻的一个解
vector<int> result;//寄存最优解

// 取得底数更大的序列
void getLargerSequence(){
    if(result.empty()){
        result = t;
    } else {
        int sumT = 0;
        int sumR = 0;
        for (int i = 0; i < t.size(); ++i) {
            sumT += t[i];
            sumR += result[i];
        }
        if(sumT>sumR){
            result.clear();
            result = t;
        }
    }
}

// 取得factor的P次方
int getPowerP(int factor,int P){
    int r = 1;
    for (int i = 0; i < P; ++i) {
        r *= factor;
    }
    return r;
}

void DFS(int factor,int sum,int num,int N,int K,int P){
    if(sum==N&&num==K){
        // 找到平方和为N，因子个数为K的序列了
        getLargerSequence();// 保留更大的序列
        return;
    }
    if(sum>N||num>K||factor==0) return;
    //抉择factor
    t.push_back(factor);
    DFS(factor,sum+getPowerP(factor,P),num+1,N,K,P);
    //不抉择factor
    t.pop_back();
    DFS(factor-1,sum,num,N,K,P);
}

int main(){
    int N,K,P;// N为待比拟的数字，K为因子个数，P为指数
    scanf("%d %d %d",&N,&K,&P);
    // 取得factor的上界
    int sup = 1;
    while (getPowerP(sup,P)<=N){
        ++sup;
    }
    DFS(sup-1,0,0,N,K,P);
    if(result.empty()){
        printf("Impossible");
    } else {
        printf("%d =",N);
        for(int i=0;i<result.size();++i){
            printf(" %d^%d",result[i],P);
            if(i<result.size()-1) printf(" +");
        }
    }
    return 0;
}

上面给出应用了打表技巧的代码，速度略微快一点

#include<cstdio>
#include<vector>

using namespace std;
/*
题目要求:给定正整数N,K,P,将N示意为K个正整数的P次方和(递加排序),如果有多个抉择底数和最小的计划,如果还有多个,抉择底数序列字典序最大的序列
算法思路:题目的思路倒是不难,惯例遍历都能够想得到,然而设计到的技巧还有有些,最容易想到的就是从1开始遍历数字,累加以后遍历数字的P次方和,找到相等于n的即可
那么在遍历数字的时候会呈现抉择该数或不抉择该数的状况,很天然就想到深度优先遍历的思维.

1.在遍历数字的时候就会发现,当数字n给定的时候,n的因子是有一个上界的(最大也就为n),而且P最小还为2,那么为了不便起见,能够应用打表的技巧将可能为n的因子的数字
全副保存起来,而后问题就天然转化为在所有可能的因子中寻找组合是的因子的P次方和等于n,这样就好求的多,所以编写函数init(),起始数字从0开始(0不能取),将所有
数字的P次方小于等于N的增加进行数组factor中。其下标就是数字,对应的值就是该数字的P次方
2.在DFS中咱们有4个参数count:统计因子的个数,sumF:因子的总和,sumQ:因子的p次方和,num:以后待增加的因子,同时也是factor的下标,遍历程序咱们能够从前往后,也能够
从后往前遍历,然而这里只能从后往前,前面再解释,DFS分为递归边界和递归体
    1)递归边界,第一个递归边界就是找到满足条件序列时,如果以后的序列的sumF更大,那么保留sumF并且更新序列,第二个递归条件就是找不到满足条件序列时,这里有3个
     num==0||count>k||sumQ>n,也即是0数字不能为因子,如果遍历到0阐明遍历结束,或者曾经抉择了k个数了,不能再抉择,或者以后序列P次方和曾经大于N了,不能再抉择
    2)递归体:分为抉择num数字和不抉择num数字,当咱们抉择num数字的时候要留神一点,这里num可反复抉择,所以递归时num不变,不抉择时,num是减一
    
!!!!这里有一点让我百思不得其解的中央,就是如果不抉择在抉择的后面会在测试点2的中央呈现谬误 
阐明：
1.如果是从返回后遍历得将递归失败num的条件该为num>factor.size()-1,判断上界. 
2.如果是从返回后遍历得那就得每次取得序列后判断是否比之前取得序列字典序更大,这样会导致测试点5超时,所以依照字典序大到小遍历数字会更快
3.判断没有因子的条件是maxFsum==-1
*/
vector<int> r,temp,factor;//保留最终的合成序列和每次遍历的合成序列 ,factor保留数字n可能的因子的p次方,不写这个可能会超时 
int n,k,p;//数字n,合成的个数,幂次
int maxFsum = -1;//保留最大因子的和 

//n的p次方 
int Pow(int n){
    int r = 1;
    for(int i=0;i<p;++i){
        r *= n;
    }
    return r;
}

void init(){//初始化factor数组 
    for(int i=0;Pow(i)<=n;++i){
        factor.push_back(Pow(i));
    }
}
/*
count:统计因子的个数
sumF:因子的总和
sumQ:因子的p次方和 
num:以后待增加的因子,同时也是factor的下标 
*/
void DFS(int count,int sumF,int sumQ,int num){
    if(count==k&&sumQ==n){//递归边界,找到了p次方和为n并且因子个数为k的序列了
        if(maxFsum<sumF){//temp的序列因子和更大 
            r = temp;//将temp赋值给r
            maxFsum = sumF;
        }
        return;
    }
    //num>factor.size()-1,如果是从1开始往前遍历的话,得扭转num的判断条件为这句话,因为上界就是factor.size()-1,不然会进入有限递归 
    if(num==0||count>k||sumQ>n) return;//不能为数字0,曾经抉择了k个数字,或者p次方和大于n,间接返回
//    DFS(count,sumF,sumQ,num-1);//不抉择num,如果先不抉择num的话,测试点2过不了 
    temp.push_back(num);
    DFS(count+1,sumF+num,sumQ+factor[num],num);//num的抉择可能有多个,这里额定要留神 
    temp.pop_back();//退出以后num
    DFS(count,sumF,sumQ,num-1);//不抉择num
}

int main(){
    scanf("%d %d %d",&n,&k,&p);
    init();
    DFS(0,0,0,factor.size()-1);//从最初一个可能的因子开始抉择
    if(maxFsum==-1){//没有因子 
        printf("Impossible");
    } else{//输入r即可,不过得倒序输入 
        printf("%d = ",n);
        int len = r.size();
        for(int i=0;i<len;++i){
            if(i==0){
                printf("%d^%d",r[i],p);
            }else{
                printf(" + %d^%d",r[i],p);
            }
        }
    }
    return 0;
}