| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4240 人关注过本帖
标题:一道计算机报上的难题\C语言QQ群新建
只看楼主 加入收藏
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
这是比较高效但是稍微难理解的算法,用栈搜索代替递归,思想我在上面说过

我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2005-04-02 19:57
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 

乌鸦的程序有问题,高效算法俺就懒得想了,顺手写了个穷举的验证一下你的程序的正确性^_^ #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"); } 把你的算法再说清楚一点,让俺学习学习


九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-04-02 22:38
aakissyou
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2005-3-30
收藏
得分:0 
不会吧这么难地啊!怪不得想爆头都没想到!连皮毛都没学到!唉!啥时候有你们那么厉害啊

2005-04-02 22:42
空前
Rank: 1
等 级:新手上路
帖 子:1146
专家分:0
注 册:2004-5-11
收藏
得分:0 
我也看到过这个题……

2005-04-03 08:41
空前
Rank: 1
等 级:新手上路
帖 子:1146
专家分:0
注 册:2004-5-11
收藏
得分:0 
数列的第一项必须为零,他抄错题了!

2005-04-03 09:25
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
晕,算法有错……?

我测了几个好象没啊……
说算法吧:
看楼主的题目:
我给个数列: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-04-03 10:21
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
knocker 你的穷举程序没输出数列啊

我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2005-04-03 10:25
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
昨天在FC3下面编译没问题啊……,怎么今天拿WIN-TC,好象出问题……

我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2005-04-03 10:27
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
居然犯低级错误……
已经改好了

我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2005-04-03 10:34
疯狂魔神
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2005-4-2
收藏
得分:0 
说实话,看完之后……

不是很清楚,可否多点注释?

对我的帮助我记在心里 对我的取笑我看在眼中 比菜,我说了算 我努力在学~
2005-04-03 12:28
快速回复:一道计算机报上的难题\C语言QQ群新建
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039903 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved