一道计算机报上的难题\C语言QQ群新建(页 1) - C语言论坛

幻帆发表于 2005-3-31 20:03

一道计算机报上的难题\C语言QQ群新建

对于一个数列，第一项为零，如果前后两项之差为一，
比如：1，2，1，－1。。。或者1，2，3，2，3，4，5，4，3，就称做是1S序列，
要求输入两个整数：sum和len，len表示这个数列的长度sum表示数列之和，
最后寻找这样的数列，如果有就输出，
比如输入1,6,那么输出1，0，－1，0，1，0。这是其中一个符合的数列
如果只输出一个好像比较简单，我们要求高点，输出所有符合数列.

另:本人新设C语言学习QQ群:805053.欢迎有兴趣者加入,共同讨论.

幻帆发表于 2005-4-1 11:51

这道题难道没人会解??

乌鸦丘比特 发表于 2005-4-1 12:32

好象楼主对数列的要求表述不清楚……
对于一个数列，第一项为零，如果前后两项之差为一，/*这里的如果两个字是什么意思？是不是一定要求满足条件？*/

乌鸦丘比特 发表于 2005-4-1 12:33

还有就是是不是限制时间和空间？
SUM和LEN 的范围是多少？
如果不限制时间空间的话搜索应该就可以了。

想你的天空 发表于 2005-4-1 13:22

楼主题目说的不清楚

乌鸦丘比特 发表于 2005-4-1 19:04

如果我的理解没错的话,这个题目的本质就是给数列B:len,....3,2,1个数加上+号或者-号,最后相加,如果=SUM,那么可疑推导出满足条件的数列,a[n]=a[n-1]-1或者a[n]=a[n-1]+1;其中-1或者+1取决于前面B[N]的符号,这个题目可以利用数学方法+一点点递归构造出目标数列
[align=right][color=#000066][此贴子已经被作者于2005-4-2 20:03:05编辑过][/color][/align]

幻帆发表于 2005-4-2 01:04

乌雅理解的没错,我前面的第一项为零打错了.可以删去.
乌雅能给出具体的程序吗

疯狂魔神 发表于 2005-4-2 11:56

<DIV class=quote>以下是引用乌鸦丘比特在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]的符号,这个题目可以利用数学方法+一点点递归构造出目标数列</DIV>
 抱歉抱歉，这道是我给他的，当时漏了一句话，就是输入两个数之后先判断有没有这种数列存在，如有再列出数列。

 没想到差这句话引来这么多误解的，
 其实这道题的本意是要我们列出指定了数列总和以及数列项数的1s数列，
而1s数列就是前面说的第一项为0，从第二项开始，前后项之差为1，也就是说：
第二项可以是1或者－1，那么第四项就有三种可能

疯狂魔神 发表于 2005-4-2 12:04

乌鸦丘比特 发表于 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[i-1]))

 {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[i]=0;}

void make1(long sum)

{long min,sum1;

first();

while(top>=0)

{if(!sum){print();top--;sum=sum+stack[top];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;}<STDIO.H><MAX><STACK sum1="(min+max)*(max-min-1); " if(sum="" if(min="=max){stack[top]=0;top--;sum=sum+stack[top];continue;} " min="" [top])min="stack[top]; "></STACK></MAX></STDIO.H>
[align=right][color=#000066][此贴子已经被作者于2005-4-3 10:33:46编辑过][/color][/align]

乌鸦丘比特 发表于 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