乐趣区

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

jiezi

题目粗心:

给定正整数 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;
}
退出移动版