洛谷P2404自然数的拆分问题 P1157组合的输出

    科技2024-11-29  16

    P2404 问题描述

    自然数的拆分问题 任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n,要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。

    输入输出样例

    Sample Input

    7

    Sample Output

    1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4

    Wrong Answer

    #include <bits/stdc++.h> using namespace std; int n; vector<int> track; void dfs(int sum) { if(sum==n){ cout<<track[0]; for(int i=1;i<track.size();i++) cout<<"+"<<track[i]; cout<<endl; return ; } for(int i=1;i+sum<=n;i++){ //错误之处 track.push_back(i); dfs(sum+i); track.pop_back(); } } int main() { cin>>n; dfs(0); return 0; }

    这个代码的错误之处就在于深搜时每个分支都从1开始,实际上这样写的话会造成排列重复,比如1+1+1+1+1+2 和1+1+1+1+2+1 都会输出。 措施:观察样例我们发现,后面输出的数总是大于等于前面输出的数,因此可以引入前缀,每次都从前缀的值开始循环。 同时,注意循环结束的条件。

    改进

    #include <bits/stdc++.h> using namespace std; int n; vector<int> track; void dfs(int pre,int sum) { if(sum==n){ cout<<track[0]; for(int i=1;i<track.size();i++) cout<<"+"<<track[i]; cout<<endl; return ; } for(int i=pre;i+sum<=n&&i!=n;i++){ track.push_back(i); dfs(i,sum+i); track.pop_back(); } } int main() { cin>>n; dfs(1,0); return 0; }

    P1157 问题描述

    组合的输出 排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元素, 请你输出所有组合。我们可以简单地将n个元素理解为自然数1,2,…,n,从中任取r个数。 所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个字符的位置,所有的组合也按字典顺序。

    输入输出样例

    Sample Input

    5 3

    Sample Output

    1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

    思路1

    using namespace std; int n,r; vector<int> track; void dfs(int dep) { if(dep==n+1){ if(track.size()==r){ for(int i=0;i<r;i++) printf("%3d",track[i]); cout<<endl; } return; } else{ track.push_back(dep); dfs(dep+1); track.pop_back(); dfs(dep+1); } } int main() { cin>>n>>r; dfs(1); return 0; }

    这是在求子集的基础上,只在筛选条件上选择子集个数为r的子集输出,需要耗费较高的时间。

    思路2

    #include <bits/stdc++.h> using namespace std; int n,r; vector<int> track; void dfs(int pre) { if(track.size()==r){ for(int i=0;i<r;i++) printf("%3d",track[i]); cout<<endl; return ; } for(int i=pre;i<=n;i++){ track.push_back(i); dfs(i+1); track.pop_back(); } } int main() { cin>>n>>r; dfs(1); return 0; }

    P1157拓展

    根据思路2,不仅可以写出组合的输出C(m,n),还可以写出排列的输出A(m,n) 需要一个vis数组判断该数是否已加入track数组

    #include <bits/stdc++.h> using namespace std; int n,r; vector<int> track; int vis[25]; void dfs(int dep) { if(dep>r){ for(int i=0;i<r;i++) printf("%3d",track[i]); cout<<endl; return ; } for(int i=1;i<=n;i++){ if(!vis[i]){ track.push_back(i); vis[i]=1; dfs(dep+1); track.pop_back(); vis[i]=0; } } } int main() { cin>>n>>r; dfs(1); return 0; }
    Processed: 0.028, SQL: 8