| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4578 人关注过本帖
标题:[讨论]青蛙该怎样过桥?
只看楼主 加入收藏
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
那个桥长50的题是对的。
桥长100就无法忍受其等待了,因而。。。。。。

落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-04 14:28
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

呵呵,那就好,那是因为我递归造成的,递归需要一步一步来,
影响我的程序第一个要素是桥的长度不能太多,
其次才是步数差距;
不过这两个都是要命的花费时间啦,呵呵。
想想别的算法吧


对不礼貌的女生收钱......
2006-05-04 14:40
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
回去想了,一定得找出个更好的算法才行,
呵呵。这种题目挺有意思

对不礼貌的女生收钱......
2006-05-04 16:26
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 

说明:程序默认坐标原点不放置石头,石头坐标输入严格按照从小到大的顺序
程序中加如了青蛙跳长定值的情况(max==min)
最后一项为计算所用去的时间
XP C-Free
[CODE]
#include "stdio.h"
#include "malloc.h"
#include "time.h"
long num_min=0,bridge_len,*array,stone_sum;
int min,max;

int Search(long i)
{
long j;

for(j=0;j<stone_sum && i>=array[j];j++)
;
return j-1;
}

void Frog_Jump(long i,long total)
{
int j;
long num,k;

for(j=min;j<=max;j++)
{
num=total;
k=Search(i+j);
if( k<stone_sum-1 )
{
if(k>=0 && array[k]==i+j)
num=total+1;
if( array[k+1]-i-j>=max)
Frog_Jump(array[k+1]-max,num);
else
Frog_Jump(i+j,num);
}
else
{
if(array[k]==i+j)
num=total+1;
if( num<num_min)
num_min=num;
}
}
}

int main()
{
long i,start,end;

printf("please input the length of bridge :\n");
scanf("%ld",&bridge_len);
printf("please input the range of frog :\n");
scanf("%d%d",&min,&max);
printf("please input the num of stone :\n");
scanf("%ld",&stone_sum);
array=(long *) malloc (sizeof(long)*stone_sum);
for(i=0;i<stone_sum;i++)
scanf("%ld",array+i);
start=clock();
if(max==min)
{
for(i=0;i<stone_sum;i++)
if(array[i]%max==0)
num_min++;
}
else
{
num_min=stone_sum;
Frog_Jump(0,0);
}
printf("\n%ld\n",num_min);
free(array);
end=clock();
printf("The computation took %0.4f seconds.\n",(end-start)/1000.0);
return 0;
}


[/CODE]



叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-05-05 02:08
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
斑竹,辛苦啦,我代过了河的青蛙姑娘谢谢您。要不要锁呢?斑竹斟酌,LZ无意见。

落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-05 07:36
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
回复:(feng1256)说明:程序默认坐标原点不放置石头...
其速度之快,真叫一个爽!为什么昨天的就那么慢呢?

落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-05 07:41
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

版主真强啊,我的程序又卡住了,版主您有空看不?


对不礼貌的女生收钱......
2006-05-05 08:48
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 

以下是引用soft_wind在2006-5-5 8:48:00的发言:

版主真强啊,我的程序又卡住了,版主您有空看不?

急忙赶来,扑了个空,还以为老兄也成功了哩。建议你先运行斑竹的程序,并设法略加修改,让我们看到青蛙最终过桥的细节。


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-05-05 08:53
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

呵呵,我也只是把我的程序缩减了下,结果却完全出错了,
不过,要是改出来的话,肯定不比版主的花费时间,所以,老兄,你帮俺看下?
/*
算法说明:把桥长L分成0-L个点,青蛙最后一步跳出桥外,相当于跳到前一步(可以为L-max到L-min之间的各个点)然后再跳一次,
于是踩到的石头数等于它跳到前一步踩到的石头数(取L-max到L-min之间踩到石头数的最小值)加上这个步点是否有石子,
有则加1,没有为0,依次递归可得。
*/
#include <stdio.h>
int length;
short *info=NULL;
int function(int len,int min,int max)
{
int i;
int m,minous;
if(len>=min&&len<=max) /*当递归的长度依次递减到它一步就可以跳到的地方*/
{
if(*(info+len)==1)
return 1;
else
return 0;
}
else if(len<min) /*如果递归后长度缩减到比它一步最小步长还小的情况,把值置成桥长,置一个较大的值,表示这个路径不录用*/
return length;
else
{
for(i=len-max;i<len-min;i++)
{
if(i==len-max)
{
if(*(info+len)==1)
minous=1+function(i,min,max);
else minous=function(i,min,max);
}
else
{
if(*(info+len)==1)
m=1+function(i,min,max);
else
m=function(i,min,max);
minous=minous>m?m:minous; /*循环取L-max到L-min之间踩到石头数的最小值*/
}
}
return minous;
}
}
main()
{
int minpace,maxpace,stone_num,temp,st_place,i;
/*
输入数据
*/
printf("Please input the length of the bridge:");
scanf("%d",&length);

info=(short *)malloc(sizeof(short)*(length+1));
for(i=0;i<=length;i++)
*(info+i)=0;
printf("Now enter the min pace and the max pace:");
scanf("%d%*c%d",&minpace,&maxpace);
printf("Input the number of the stones:");
scanf("%d",&stone_num);
printf("The places of the stone:");
for (i=0;i<stone_num;i++)
{
scanf("%d",&temp);
*(info+temp)=1;
}
printf("%d",function(length,minpace,maxpace));
getch();


}


对不礼貌的女生收钱......
2006-05-05 09:04
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
以下是引用soft_wind在2006-5-5 9:04:00的发言:

呵呵,我也只是把我的程序缩减了下,结果却完全出错了,
不过,要是改出来的话,肯定不比版主的花费时间,所以,老兄,你帮俺看下?
/*
算法说明:把桥长L分成0-L个点,青蛙最后一步跳出桥外,相当于跳到前一步(可以为L-max到L-min之间的各个点)然后再跳一次,
于是踩到的石头数等于它跳到前一步踩到的石头数(取L-max到L-min之间踩到石头数的最小值)加上这个步点是否有石子,
有则加1,没有为0,依次递归可得。
*/
#include <stdio.h>
int length;
short *info=NULL;
int function(int len,int min,int max)
{
int i;
int m,minous;
if(len>=min&&len<=max) /*当递归的长度依次递减到它一步就可以跳到的地方*/
{
if(*(info+len)==1)
return 1;
else
return 0;
}
else if(len<min) /*如果递归后长度缩减到比它一步最小步长还小的情况,把值置成桥长,置一个较大的值,表示这个路径不录用*/
return length;
else
{
for(i=len-max;i<=len-min;i++) /*够呛,问题出在这!*/
{
if(i==len-max)
{
if(*(info+len)==1)
minous=1+function(i,min,max);
else minous=function(i,min,max);
}
else
{
if(*(info+len)==1)
m=1+function(i,min,max);
else
m=function(i,min,max);
minous=minous>m?m:minous; /*循环取L-max到L-min之间踩到石头数的最小值*/
}
}
return minous;
}
}
main()
{
int minpace,maxpace,stone_num,temp,st_place,i;
/*
输入数据
*/
printf("Please input the length of the bridge:");
scanf("%d",&length);

info=(short *)malloc(sizeof(short)*(length+1));
for(i=0;i<=length;i++)
*(info+i)=0;
printf("Now enter the min pace and the max pace:");
scanf("%d%*c%d",&minpace,&maxpace);
printf("Input the number of the stones:");
scanf("%d",&stone_num);
printf("The places of the stone:");
for (i=0;i<stone_num;i++)
{
scanf("%d",&temp);
*(info+temp)=1;
}
printf("%d",function(length,minpace,maxpace));
getch();


}

我算了下,100的还是得算很久,不过步长相差倒是比较无所谓.
哎!还是版主的运算速度快!


对不礼貌的女生收钱......
2006-05-05 09:18
快速回复:[讨论]青蛙该怎样过桥?
数据加载中...
 
   



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

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