首先我们认识到,这是个循环遍历求解的过程(暂且这样分析求解这个问题吧!也不能否认会有高人找到规律,用递归回溯的方法解之,如果有的话请与大家分享哦,反正我考虑了很久,都没有发现捷径!)然后,我发现的一个稍微点的规律吧,能够节省一下计算量的,就是在循环的时候可以设置循环上限为(num+1)/2,证明很简单,这里略之!
我看了下你上面的代码,好像输入5也会出现问题!
你能文字描述下你的算法吗?可以进一步讨论!望追问!
我的算法如下:
0~(num+1)/2之间用两个数i,j(i<=j),通过双重循环i、j,不断取得和为num的连续自然数,
同时比较j-i与之前_j-_i大小,取较大值存入_j、_i!
直到双重循环结束,最后得到的连续自然数为_j~_i。
源码如下:
// Decompose_into_123.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
void decompose(int);
int _tmain(int argc, _TCHAR* argv[])
{
int N;
printf("请输入需要分解的整数n =");
scanf("%d",&N);
decompose(N);
return 0;
}
void decompose(int num)
{
int s=(num+1)/2,T=0,n=0,i=0,j=0,_i=0,_j=0,l;
while(j<(num+1)/2)
{
for(i=j;i<=(num+1)/2;i++)
{
T=T+i;
if(T==num)
{
n++;l=i-j;
if(l>_i-_j)
{_i=i;_j=j;}
}
}
if(n==0)
T=0;
j++;
}
if(n==0)
printf("No Answer");
else
{
printf("%d =",num);
for(int k=_j;k<_i;k++)
printf("%d+",k);
printf("%d",_i);
}
}
VS2010下成功实现功能!希望对你有用!谢谢
for循环中有三部分: if (z>0),else if (z==0),else
第一部分功能是尝试 i+(i+1)+(i+2)+……看能否刚好等于输入值,(i第一次取值为1,从1开始)
等于 就进入第二部分:输出结果
不等于 就进入第三部分:i加一个后,再回到第一部分,从新开始尝试,
【错误原因】
因为i第一次在第三部分取2后,回到 for (;i<=x&&i>0;i++)又自加了一次,
所以,第二次尝试是从3开始了,而不是2,
只需要把第三部分中 y=y+1; i=y;先后顺序调换一下就可以了
虽然有点罗嗦,但能看懂吧!!!
我不知道