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

哦，俺看差了,知道了,不好意思，来瞎搅和.呵呵
----------------解决方案--------------------------------------------------------

#include <stdio.h>
/*
函数功能：递归计算青蛙踩到石子的总数。
函数入口：对调后的石头位置，石头总数，最短步长，最大步长，桥的总长。
函数出口：返回青蛙踩到石子的总数。
特别注意：该函数的处理是颠倒处理，即已经把终点看成起点，起点看成终点。
*/
int findway(int a[],int num,int min,int max,int len)
{
int count1=0,count2=0,s=0,q=0,j;
if(len<=max) /*如果最大步长大于等于桥的总长，则无须踩到石子*/
return 0; /*递归出口*/
else /*处理步长小于桥长的情况*/
{
for(j=0;j<num;j++) /*青蛙挑一步，循环判断青蛙是否跳到石头的地方*/
{
if(a[j]!=len-min) /*小步长的处理*/
s++; /*如果没跳着，就加1*/
if(a[j]!=len-max) /*大步长的处理*/
q++; /*如果没跳着，加1*/
}
/*
如果跳着石头的地方，count加1，然后递归计算总跳到的石头数
*/
s!=num?(count1=1+findway(a,num,min,max,len-min)):(count1=findway(a,num,min,max,len-min));
q!=num?(count2=1+findway(a,num,min,max,len-max)):(count2=findway(a,num,min,max,len-max));
return count1>count2?count2:count1; /*函数出口，返回跳到石头数最小的数*/
}
}
main()
{
int length,minpace,maxpace,stone_num,st_place,i;
int aplace[20];

/*
输入数据
*/
printf("Please input the length of the bridge:");
scanf("%d",&length);
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",&aplace[i]);

/*
为方便函数处理，把起点也终点对换。
*/
for (i=0;i<stone_num;i++)
aplace[i]=length-aplace[i];
printf("OK,loading- - - -\n");
/*
打印出结果。
*/
printf("%d",findway(aplace,stone_num,minpace,maxpace,length));
getch();

}
这个程序不知道对不?我只检验了楼主的数据,是对的，但别的数据不好检验，请楼主帮忙看下.

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

起跳点是0,终点是10或更大,我忘记交代清楚

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

我的程序又出错了，
我在写的时候,把它理解成就只能跳那两个步了,晕!
不过改个循环,应该能实现，只是不知道有没有算法上的问题.

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

#include <stdio.h>
/*
函数功能：递归计算青蛙踩到石子的总数。
函数入口：对调后的石头位置，石头总数，最短步长，最大步长，桥的总长。
函数出口：返回青蛙踩到石子的总数。
特别注意：该函数的处理是颠倒处理，即已经把终点看成起点，起点看成终点。
*/
int findway(int a[],int num,int min,int max,int len)
{
int count1=0,count2=0,s=0,q=0,j;
if(len<=max) /*如果最大步长大于等于桥的总长，则无须踩到石子*/
return 0; /*递归出口*/
else /*处理步长小于桥长的情况*/
{
for(j=0;j<num;j++) /*青蛙挑一步，循环判断青蛙是否跳到石头的地方*/
{
if(a[j]!=len-min) /*小步长的处理*/
s++; /*如果没跳着，就加1*/
if(a[j]!=len-max) /*大步长的处理*/
q++; /*如果没跳着，加1*/
}
/*
如果跳着石头的地方，count加1，然后递归计算总跳到的石头数
*/
s!=num?(count1=1+findway(a,num,min,max,len-min)):(count1=findway(a,num,min,max,len-min));
q!=num?(count2=1+findway(a,num,min,max,len-max)):(count2=findway(a,num,min,max,len-max));
return count1>count2?count2:count1; /*函数出口，返回跳到石头数最小的数*/
}
}
main()
{
int length,minpace,maxpace,stone_num,st_place,i;
int aplace[20];
int total[20];
int k;
/*
输入数据
*/
printf("Please input the length of the bridge:");
scanf("%d",&length);
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",&aplace[i]);

/*
为方便函数处理，把起点也终点对换。
*/
for (i=0;i<stone_num;i++)
aplace[i]=length-aplace[i];
printf("OK,loading- - - -\n");
/*
打印出结果。
*/
for(k=minpace;k<=maxpace;k+=2)
total[k-minpace]=findway(aplace,stone_num,k,k+1,length);
for(k=1;k<maxpace-minpace+1;k++)
if(total[k]<total[0])
total[0]=total[k];
printf("%d",total[0]);
getch();

}

哎,今天脑袋不灵光,改这个循环，竟然花了我这么长时间.晕死了.

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

晕啊,我大概想出来我程序的算法是对的了，
但上面那个程序还是没改好，哎,
下面这个是对的
#include <stdio.h>
/*
函数功能：递归计算青蛙踩到石子的总数。
函数入口：对调后的石头位置，石头总数，最短步长，最大步长，桥的总长。
函数出口：返回青蛙踩到石子的总数。
特别注意：该函数的处理是颠倒处理，即已经把终点看成起点，起点看成终点。
*/
int findway(int a[],int num,int min,int max,int len)
{
int count1=0,count2=0,s=0,q=0,j;
if(len<=max) /*如果最大步长大于等于桥的总长，则无须踩到石子*/
return 0; /*递归出口*/
else /*处理步长小于桥长的情况*/
{
for(j=0;j<num;j++) /*青蛙挑一步，循环判断青蛙是否跳到石头的地方*/
{
if(a[j]!=len-min) /*小步长的处理*/
s++; /*如果没跳着，就加1*/
if(a[j]!=len-max) /*大步长的处理*/
q++; /*如果没跳着，加1*/
}
/*
如果跳着石头的地方，count加1，然后递归计算总跳到的石头数
*/
s!=num?(count1=1+findway(a,num,min,max,len-min)):(count1=findway(a,num,min,max,len-min));
q!=num?(count2=1+findway(a,num,min,max,len-max)):(count2=findway(a,num,min,max,len-max));
return count1>count2?count2:count1; /*函数出口，返回跳到石头数最小的数*/
}
}
main()
{
int length,minpace,maxpace,stone_num,st_place,i,k,m,n;
int aplace[20];

/*
输入数据
*/
printf("Please input the length of the bridge:");
scanf("%d",&length);
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",&aplace[i]);

/*
为方便函数处理，把起点也终点对换。
*/
for (i=0;i<stone_num;i++)
aplace[i]=length-aplace[i];
printf("OK,loading- - - -\n");
/*
打印出结果。
*/
for(k=0;k<maxpace-minpace;k++)
{
if(k==0)
m=findway(aplace,stone_num,k+minpace,k+1+minpace,length);
else
m=m>(n=findway(aplace,stone_num,k+minpace,k+1+minpace,length))?n:m;
}
printf("%d",m);
getch();

}

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

哎,检测的时候又出现个错误，谁能帮我改下，
最上面的程序应该是没问题的。
在上面的基础上再加个循环,我不会加啊,晕啊!
改了这么多次，还没改好啊!!

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

不帮你改，哈哈，我来了

我要把我的优化下

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

我的好版主啊，咱们同校的，对吧，怎么能这么绝情呢！！！
等你对你程序满意的时候，帮我看看啦！

----------------解决方案--------------------------------------------------------
4楼和12楼的程序用下列数据
100 //桥长100
2 3 //蛙步范围
10 //石子总数
7 19 29 37 47 59 71 79 89 97 //石子的位置
测试，都难以忍受其低速度。
当然，这并不意味着LZ拥有好的答案。

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