SSOJ2364自然数的拆分问题
4986+
作者:crxis 发布:2017-07-28 分类:深度优先搜索
题目大意:任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和,请把所有拆分方案输出来。
输入
输入一个自然数n(1<n<10)
输出
输出不同的拆分方法,每一种拆分方法输出到一行。
样例输入
7
样例输出
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
解题思路
按照“格子填数”的思想,一个一个填数字,与前面几道题不同的是,自然数拆分的格子数是不固定的,什么时候才结束递归呢?不能再划分下去的时候!
搜索时记录两个参数,一个是k,表示填到第k个格子;一个是s,表示剩余多少需要划分。先确定每个格子填数的范围——不比前一个数小,最大为s。当前格子确定数字i后,搜索下一个格子k+1,且修改剩余划分数字为s-i。最后考虑特殊情况,如k=2时没划分,输出时注意加号个数和换行等等。