如果只输出一个好像比较简单，我们要求高点，输出所有符合数列.
另:本人新设C语言学习QQ群:805053.欢迎有兴趣者加入,共同讨论.
幻帆 发布留言 2005-4-2 01:04
乌雅理解的没错,我前面的第一项为零打错了.可以删去.
乌雅能给出具体的程序吗
疯狂魔神 发布留言 2005-4-2 11:56
以下是引用乌鸦丘比特在2005-4-1 19:04:48的发言：
如果我的理解没错的话,这个题目的本质就是给数列B:1,2,3,4....len,个数加上+号或者-号,最后相加,如果=SUM,那么可疑推导出满足条件的数列,a[n]=a[n-1]-1或者a[n]=a[n-1]+1;其中-1或者+1取决于前面B[N]的符号,这个题目可以利用数学方法+一点点递归构造出目标数列
抱歉抱歉，这道是我给他的，当时漏了一句话，就是输入两个数之后先判断有没有这种数列存在，如有再列出数列。
没想到差这句话引来这么多误解的，
其实这道题的本意是要我们列出指定了数列总和以及数列项数的1s数列，
而1s数列就是前面说的第一项为0，从第二项开始，前后项之差为1，也就是说：
第二项可以是1或者－1，那么第四项就有三种可能
疯狂魔神 发布留言 2005-4-2 12:04
以下是引用乌鸦丘比特在2005-4-1 19:04:48的发言：
如果我的理解没错的话,这个题目的本质就是给数列B:1,2,3,4....len,个数加上+号或者-号,最后相加,如果=SUM,那么可疑推导出满足条件的数列,a[n]=a[n-1]-1或者a[n]=a[n-1]+1;其中-1或者+1取决于前面B[N]的符号,这个题目可以利用数学方法+一点点递归构造出目标数列
抱歉抱歉，这道是我给他的，当时漏了一句话，就是输入两个数之后先判断有没有这种数列存在，如有再列出数列。
没想到差这句话引来这么多误解的，
其实这道题的本意是要我们列出指定了数列总和以及数列项数的1s数列，
而1s数列就是前面说的第一项为0，从第二项开始，前后项之差为1，也就是说：
第二项可以是1或者－1，那么第三项就有三种可能，也就是2或者0或者－2，依次…………
而sum跟len就是由用户输入的两个数字，
不知这样说是否清楚一点点？
乌鸦丘比特 发布留言 2005-4-2 19:55
#include <stdio.h>
long max,fuhao;
int stack[1000],top;
void print()
{int i,j,num;
num=0,j=1;
for(i=top;i;i--)
{while(j<(max-stack))
{num=num+fuhao;printf("%d ",num);j++;}
num=num-fuhao;
printf("%d ",num);j++;}
while(j<max)
{num=num+fuhao;
printf("%d ",num);
j++;}
printf("\n");}
long getnumber(long sum,long len)
{long sum1;
sum1=(len+1)*len/2;/*求和公式:1+2+...+len;*/
sum1=sum1-sum;
if(sum1&1)return -1;/*if sum1 是奇数,不存在满足条件的数列*/
sum1=sum1/2;
return sum1;}
void first()
{int i;
top=0;
for(i=0;i<1000;i++)stack;continue;}
min=0;
if(top>0)min=stack[top-1];
if(min<stack[top])min=stack[top];
min++;
if(min==max){stack[top]=0;top--;sum=sum+stack[top];continue;}
sum1=(min+max)*(max-min-1);
if(sum>sum1){stack[top]=0;top--;sum=sum+stack[top];continue;}
stack[top]=min;
sum=sum-min;
top++;} }
int main()
{long sum,len,sum1;
printf("please input sum and len:\n");
scanf("%ld%ld",&sum,&len);
if(sum<0){sum=-sum;fuhao=-1;}
else fuhao=1;
max=len+1;
sum1=getnumber(sum,len);
if(sum1==-1){printf("no answer\n");getch( );return 0;}
make1(sum1);
getch( );
return 0;}
乌鸦丘比特 发布留言 2005-4-2 19:57
这是比较高效但是稍微难理解的算法,用栈搜索代替递归,思想我在上面说过
Knocker 发布留言 2005-4-2 22:38
乌鸦的程序有问题，高效算法俺就懒得想了，顺手写了个穷举的验证一下你的程序的正确性^_^
#include <stdio.h>
#include <alloc.h>
void fun2(struct Test *UP);
void fun(int N,int SUM,struct Test *UP,int T);
int Sum,Len;
struct Test
{
int n;
struct Test * up;
};
main()
{
struct Test * test0;
test0 = (struct Test *) malloc(sizeof(struct Test));
test0->n=0;
test0->up=NULL;
scanf("%d%d",&Sum,&Len);
printf("Sum=%d Len=%d\n\n",Sum,Len);
fun(1,1,test0,2);
fun(-1,-1,test0,2);
}
void fun(int N,int SUM,struct Test *UP,int T)
{
struct Test * test0;
test0 = (struct Test *) malloc(sizeof(struct Test));
test0->n=N;
test0->up=UP;
if(T<Len)
{
fun(N+1,SUM+N+1,test0,T+1);
fun(N-1,SUM+N-1,test0,T+1);
}
if(T==Len&&SUM==Sum)
{
printf(" %d ",test0->n);
fun2(test0->up);
}
}
void fun2(struct Test *UP)
{
printf(" %d ",UP->n);
if(UP->up!=NULL)fun2(UP->up);
else printf("\n");
}
把你的算法再说清楚一点，让俺学习学习[em05][em05]
aakissyou 发布留言 2005-4-2 22:42
不会吧这么难地啊!怪不得想爆头都没想到!连皮毛都没学到!唉!啥时候有你们那么厉害啊
空前 发布留言 2005-4-3 08:41
我也看到过这个题……[em03]
空前 发布留言 2005-4-3 09:25
数列的第一项必须为零，他抄错题了！[em06]
乌鸦丘比特 发布留言 2005-4-3 10:21
晕，算法有错……？
[em03][em03]
我测了几个好象没啊……
说算法吧：
看楼主的题目：
我给个数列：0，0+1，0+1-1，0+1-1+1，0+1-1+1+1,0+1-1+1+1+1
有没有发现我这么写的目的。数列的和=1*5+(-1)*4+1*3+1*2+1*1;
原来的问题转化为：给1,2,3,4,5,……len，每个数加正号或者负号，求和=SUM；
而这个又可以利用另一个算法：
求1+2+3……+len（用求和公式）,然后-SUM,显然这就是符号为负号的所有数的和*2。
继而推出符号为负所有数的和。
递归构造出这些数（利用排序，注意边界），然后再反过来构造数列，
很显然第X项为负的话目标数列的:a[len-x+1]=a[len-x]-1 反之+1
我对于SUM为负数的时候是利用构造符号为正的数（原理一样），并且递归搜索是用栈代替了，第1项0没有计算在内
当然如果没效率要求写个第归搜索就可以了
乌鸦丘比特 发布留言 2005-4-3 10:25
knocker 你的穷举程序没输出数列啊[em03]
乌鸦丘比特 发布留言 2005-4-3 10:27
昨天在FC3下面编译没问题啊……，怎么今天拿WIN-TC，好象出问题……
乌鸦丘比特 发布留言 2005-4-3 10:34
居然犯低级错误……
已经改好了
疯狂魔神 发布留言 2005-4-3 12:28
说实话，看完之后……
不是很清楚，可否多点注释？
[1] [2] 下一页
特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！
