主题:[讨论]一道题目!
2.自然数的拆分work2.???(pas,c,cpp)
任何一个大于1的自然数总可以拆分成若干个自然数之和。
1:4=1+1+1+1
2:4=1+1+2
3:4=1+3
4:4=2+2
5:4=4
分析:设拆分出的数s1≤s2≤…≤sk。定义数组s为一个栈,用来存放因子。从1开始搜索因子,求和,若sum ≤n就将因子压栈;若sum =n,则输出解,出栈;若sum >n,则修改栈顶元素的值,即回溯。
【输入】
输入仅一行,包含一个自然数n。
【输出】
这个自然数拆分结果。拆分出的因子要求满足s1+s2+…+sk=n 且s1≤s2≤…≤sk。具体要求见样例。
【样例】
输入(work2.in)
4
输出(work2.out)
1:4=1+1+1+1
2:4=1+1+2
3:4=1+3
4:4=2+2
5:4=4
我编的程序输出顺序不对,请哪位帮我编一个正确的程序(最好用栈)
或者用递归也行
任何一个大于1的自然数总可以拆分成若干个自然数之和。
1:4=1+1+1+1
2:4=1+1+2
3:4=1+3
4:4=2+2
5:4=4
分析:设拆分出的数s1≤s2≤…≤sk。定义数组s为一个栈,用来存放因子。从1开始搜索因子,求和,若sum ≤n就将因子压栈;若sum =n,则输出解,出栈;若sum >n,则修改栈顶元素的值,即回溯。
【输入】
输入仅一行,包含一个自然数n。
【输出】
这个自然数拆分结果。拆分出的因子要求满足s1+s2+…+sk=n 且s1≤s2≤…≤sk。具体要求见样例。
【样例】
输入(work2.in)
4
输出(work2.out)
1:4=1+1+1+1
2:4=1+1+2
3:4=1+3
4:4=2+2
5:4=4
我编的程序输出顺序不对,请哪位帮我编一个正确的程序(最好用栈)
或者用递归也行