n=1+1+1…+1

muc180 2010-09-29 06:21:23
今天老师出了个题目,题目如下。

输入任意一个数字。
例如3.
然后打印成
3=1+1+1
3=1+2
3=3+1
反正有可能等于3的都列举起来。

百思不得其解...
...全文
613 40 打赏 收藏 转发到动态 举报
写回复
用AI写文章
40 条回复
切换为时间正序
请发表友善的回复…
发表回复
gaara777 2010-10-22
  • 打赏
  • 举报
回复
学习中。。。
suchx 2010-10-01
  • 打赏
  • 举报
回复
http://en.wikipedia.org/wiki/Partition_(number_theory)
Here is the algorithm for the problem. Read it carefully.
chinesebear 2010-10-01
  • 打赏
  • 举报
回复
按照你的要求重新写的程序。
#include <stdio.h>
main()
{
int i=1,n,sum=0;
printf("input value of n :");/*输入n值*/
scanf("%d",&n);

if (n == 0)
return (0);/*输入n为0是返回退出程序*/
else if(n !=0 && n % 2 == 0)/*输入偶数时*/
{
printf("input odd number:");
scanf ("%d" , &n );
while(i<=n)
{sum=sum+i;
i=i+2;}
}
else/*输入奇数时*/
{

while(i<=n)
{sum=sum+i;
i=i+2;}
}
printf("n=%d sum=%d\n",n,sum);/*结果打印*/


}
Joevan 2010-10-01
  • 打赏
  • 举报
回复
递归是解决数学类编程的好方法,在工作中递归是需要避免的。
千杯不醉-sen 2010-10-01
  • 打赏
  • 举报
回复

#include <stdio.h>
#include <malloc.h>

int *pn;
int num;

void output()
{
int i=1;
if (pn[0] != num)
{
printf("%d = %d", num, pn[0]);
while(pn[i]!=0 && i<num)
printf(" + %d", pn[i++]);
printf("\n");
}
}

void decompose(int num, int *n, int max)
{
int i;
if (num<=max)
{
n[0] = num;
output();
}
for (i=(max<num? max: num-1); i>0; i--)
{
n[0] = i;
decompose(num - i, &n[1], i);
}
n[0] = 0;
}


void main()
{
int i;
printf("Please input a integer: ");
scanf("%d", &num);
printf("%d = %d\n", num, num);
pn = (int*)malloc(sizeof(int) * num);
if (pn)
{
for (i=0; i<num; i++) pn[i] = 0;
decompose(num, pn, num);
free(pn);
}
else
{
printf("Out memory\n");
}
}


如:
Please input a integer: 10
10 = 10
10 = 9 + 1
10 = 8 + 2
10 = 8 + 1 + 1
10 = 7 + 3
10 = 7 + 2 + 1
10 = 7 + 1 + 1 + 1
10 = 6 + 4
10 = 6 + 3 + 1
10 = 6 + 2 + 2
10 = 6 + 2 + 1 + 1
10 = 6 + 1 + 1 + 1 + 1
10 = 5 + 5
10 = 5 + 4 + 1
10 = 5 + 3 + 2
10 = 5 + 3 + 1 + 1
10 = 5 + 2 + 2 + 1
10 = 5 + 2 + 1 + 1 + 1
10 = 5 + 1 + 1 + 1 + 1 + 1
10 = 4 + 4 + 2
10 = 4 + 4 + 1 + 1
10 = 4 + 3 + 3
10 = 4 + 3 + 2 + 1
10 = 4 + 3 + 1 + 1 + 1
10 = 4 + 2 + 2 + 2
10 = 4 + 2 + 2 + 1 + 1
10 = 4 + 2 + 1 + 1 + 1 + 1
10 = 4 + 1 + 1 + 1 + 1 + 1 + 1
10 = 3 + 3 + 3 + 1
10 = 3 + 3 + 2 + 2
10 = 3 + 3 + 2 + 1 + 1
10 = 3 + 3 + 1 + 1 + 1 + 1
10 = 3 + 2 + 2 + 2 + 1
10 = 3 + 2 + 2 + 1 + 1 + 1
10 = 3 + 2 + 1 + 1 + 1 + 1 + 1
10 = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 2 + 2 + 2 + 2 + 2
10 = 2 + 2 + 2 + 2 + 1 + 1
10 = 2 + 2 + 2 + 1 + 1 + 1 + 1
10 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Press any key to continue
yaganblw 2010-09-30
  • 打赏
  • 举报
回复
不懂
bobo364 2010-09-30
  • 打赏
  • 举报
回复
楼上代码收藏,学习了
dingyuanpu 2010-09-30
  • 打赏
  • 举报
回复
学习了
somebody 2010-09-30
  • 打赏
  • 举报
回复
全国人民都验证过了,我就当路过!
顺便说句:这个用拆分、解析多项式都可以实现,但最终还是是递归!
Galasxy 2010-09-30
  • 打赏
  • 举报
回复
分治


很多书上都当例题讲
zhanshen2891 2010-09-30
  • 打赏
  • 举报
回复
[Quote=引用 28 楼 zhanshen2891 的回复:]
for(int i = 0; i <= n / 2; i++)
{
cout << i << " + " << n - i << endl;
}

这样不行么?
[/Quote]

啊,看错了,原来还有多位的,那这样不行
ccccj 2010-09-30
  • 打赏
  • 举报
回复
任何数n可以认为是,1+1+1+1+1+1+1+1..............+1
然后1中间的空格是n-1个,然后可以放一个让一个|的比如: 1|1+1+1+1+....+1 一共有n-1种
假如放两个|的就是(n-1(n-2))/2
依次类推下来.
(依据你的题目应该可以重吧,像3=1+2 ,3=2+1)
zhanshen2891 2010-09-30
  • 打赏
  • 举报
回复
for(int i = 0; i <= n / 2; i++)
{
cout << i << " + " << n - i << endl;
}

这样不行么?
chuchenghao1989 2010-09-30
  • 打赏
  • 举报
回复
数n可以看成n个1的和 然后把n个1进行排列组合
rach09 2010-09-30
  • 打赏
  • 举报
回复
使用是for估计复杂度很高
涟漪不惊 2010-09-30
  • 打赏
  • 举报
回复
楼上基本上正确
martin304201 2010-09-30
  • 打赏
  • 举报
回复
用递归应该好些。
发霉饼干 2010-09-30
  • 打赏
  • 举报
回复
[Quote=引用 9 楼 anchor89 的回复:]
简单的递归,如果只是求方案数话有更简单的动态规划算法,lz可以自己搜一下,本问代码如下

C/C++ code

//////////////////////////
// Author: Anchor89
// Date:
// Title:
// Function:
//////////////////////////
#include <stdio.h>

using……
[/Quote]为什么要用那么多宏替换,何必啊@!
fx397993401 2010-09-30
  • 打赏
  • 举报
回复
[Quote=引用 5 楼 eclipse_2 的回复:]

用递归
n = n-1 + 1
n-1 = n-2 + 1
。。。
2=1+1

然后把每次的解析过程都输出来 就OK了
[/Quote]

是的 用递归可解
发霉饼干 2010-09-30
  • 打赏
  • 举报
回复
说实话,看都看咋地看明白,如果把任何等于那个数的整数都输出,数字一大不就太麻烦了,
比如输入4
4=1+1+1+1
4=2+2
4=1+3
4=3+1
4=4+0
4=0+4
这还才4,到了几万,我估计都能把机子跑爆!
加载更多回复(20)

69,336

社区成员

发帖
与我相关
我的任务
社区描述
C语言相关问题讨论
社区管理员
  • C语言
  • 花神庙码农
  • 架构师李肯
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧