当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2364自然数的拆分问题
4986+

题目大意:任何一个大于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时没划分,输出时注意加号个数和换行等等。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ2364自然数的拆分问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!