晴天的魔法乐园——自然数分解之最大积(深度优先+剪枝)
编辑:谯胜平 分类:程序与算法 标签:晴天的魔法乐园 发布时间:2019-09-03 浏览次数:1580次
题目链接:https://judger.net/problem/1062
Problem Description
给定一个正整数N,将它表示成至少两个正整数之和(即N=a1+a2+…+ak, k > 1),求a1 × a2 × … × ak的最大值。
例如对N=4来说,共有下面4种不同的方案:
4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
其中最大的乘积是最后一种,最大乘积是2×2=4。
Input
每个输入文件一组数据。
第一行为一个正整数N(2<=N<=20)。
Output
输出一个正整数,表示a1 × a2 × … × ak的最大值。
Sample Input 1
2
Sample Output 1
1
Sample Input 2
4
Sample Output 2
4
Sample Input 3
6
Sample Output 3
9
1、分析
这道题目和浙大PAT甲级真题有点相似,PAT.A.1103 Integer Factorization (30 分),用同样的方法即可。如果使用枚举法肯定是不现实的,采用深度优先搜索+剪枝是一个比较好的方法。由于每次进行递归的时候都有一个临时乘积变量,因此枚举的范围应该是1~N-1,不能是0~N。
2、代码
①本题代码:
#include<stdio.h> int maxProduct = 0, N; //index为当前索引,sum为当前选出的整数和,product为当前积 void DFS(int index, int sum, int product){ if(sum == N){ //找出的几个数的和刚好等于N if(product > maxProduct){ //找出最大积 maxProduct = product; } return; } if(sum > N){ //和大于N,直接返回 return; } for(int i = index; i < N; i++){ //从index ~ N-1进行枚举 DFS(i, sum + i, product * i); } } int main(){ scanf("%d", &N); DFS(1, 0, 1); //注意搜索的起点 printf("%d\n", maxProduct); return 0; }
②如果要保存下来取得最大积时选择的数据可以采用下面的方法,在递归的for循环里面使用vector进行保存,当数据较多时可以在for里面剪枝,如下:
#include<stdio.h> #include<vector> using namespace std; int maxProduct = 0, N; void DFS(int index, int sum, int product, vector<int> &ans, vector<int> temp){ if(sum == N){ if(product > maxProduct){ maxProduct = product; ans = temp; } return; } if(sum > N){ return; } for(int i = index; i < N; i++){ //从index ~ N-1进行枚举 temp.push_back(i); //加入temp中 if(sum + i > N) break; //剪枝 DFS(i, sum + i, product * i, ans, temp); temp.pop_back(); //从temp中除去 } } int main(){ scanf("%d", &N); vector<int> ans, temp; DFS(1, 0, 1, ans, temp); //注意搜索的起点 if(ans.size() == 0) printf("0"); //当输入1时特判输出为0 for(int i = 0; i < ans.size(); i++){ printf("%d", ans[i]); if(i < ans.size() - 1) printf(" "); } return 0; }
③如果要求有多少种方案,直接使用一个变量,在每次递归的时候出现和等于N的时候+1即可
#include<stdio.h> int N; void DFS(int index, int sum, int &ans){ if(sum == N){ ans++; //方案数目+1 return; } if(sum > N){ //和大于N,直接返回 return; } for(int i = index; i < N; i++){ //从index ~ N-1进行枚举 DFS(i, sum + i, ans); } } int main(){ scanf("%d", &N); int ans = 0; DFS(1, 0, ans); printf("%d\n", ans); return 0; }
热门文章
文章标签
- web(1)
- 数据库索引(1)
- 栈(1)
- const(2)
- #define(1)
- 虚函数(1)
- 反转链表(2)
- 深拷贝(1)
- 浅拷贝(1)
- 快速排序(1)
- 线程(1)
- 线程模型(1)
- (41)
- LRU(1)
- C++11(1)
- 一致性哈希算法(1)
- CPU(1)
- malloc(1)
- 迭代器(1)
- linux下编译(1)
- 类模板(1)
- git(1)
- Linux(2)
- 学科评估(2)
- scanf(2)
- gets(1)
- getchar(1)
- 考研经验(1)
- printf(1)
- mysql(2)
- STL(2)
- 富文本编辑器(1)
- 闰月(1)
- vector(1)
- CA(3)
- HTTPS(1)
- 晴天的魔法乐园(1)
- 单例模式(1)
- 谷歌(1)
- unzip(1)
- gcc(1)
- ubuntu(1)
- getline()(1)
- 作息时间表(1)
友情链接