桥长100就无法忍受其等待了,因而。。。。。。
落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
呵呵,那就好,那是因为我递归造成的,递归需要一步一步来,
影响我的程序第一个要素是桥的长度不能太多,
其次才是步数差距;
不过这两个都是要命的花费时间啦,呵呵。
想想别的算法吧
说明:程序默认坐标原点不放置石头,石头坐标输入严格按照从小到大的顺序
程序中加如了青蛙跳长定值的情况(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]
以下是引用soft_wind在2006-5-5 8:48: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();
}
呵呵,我也只是把我的程序缩减了下,结果却完全出错了,
不过,要是改出来的话,肯定不比版主的花费时间,所以,老兄,你帮俺看下?
/*
算法说明:把桥长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的还是得算很久,不过步长相差倒是比较无所谓.
哎!还是版主的运算速度快!