[讨论]青蛙该怎样过桥？

那个桥长50的题是对的。
桥长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]
document.body.clientWidth*0.5) {this.resized=true;this.width=document.body.clientWidth*0.5;this.style.cursor='pointer';} else {this.onclick=null}" alt="" />
document.body.clientWidth*0.5) {this.resized=true;this.width=document.body.clientWidth*0.5;this.style.cursor='pointer';} else {this.onclick=null}" alt="" />
document.body.clientWidth*0.5) {this.resized=true;this.width=document.body.clientWidth*0.5;this.style.cursor='pointer';} else {this.onclick=null}" alt="" />

----------------解决方案--------------------------------------------------------
斑竹，辛苦啦，我代过了河的青蛙姑娘谢谢您。要不要锁呢？斑竹斟酌，LZ无意见。
----------------解决方案--------------------------------------------------------
其速度之快，真叫一个爽！为什么昨天的就那么慢呢？
----------------解决方案--------------------------------------------------------

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

----------------解决方案--------------------------------------------------------

以下是引用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();

}

----------------解决方案--------------------------------------------------------

我算了下，１００的还是得算很久，不过步长相差倒是比较无所谓．
哎！还是版主的运算速度快！

----------------解决方案--------------------------------------------------------