[讨论]青蛙该怎样过桥？ - C语言论坛

问题点数：0 回复次数：51

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

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，
青蛙跳跃的距离范围S,T，
桥上石子的总数，
桥上石子的位置。

你的任务是确定青蛙要想过桥，最少踩到的石子数。

输入的第一行有一个正整数L（1 <= L <= 10的9次方），表示独木桥的长度。
第二行有两个正整数S，T，表示青蛙一次跳跃的最小距离与最大距离，其中1 <= S <= T <= 10。
第三行正整数M，为桥上石子的总数，1 <= M <= 100。
第四行有M个不同的正整数分别表示这M个石子在数轴上的位置
（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用空格分隔开。

输出应为一个整数，表示青蛙过河最少要踩到的石子数。

例如若输入
10
2 3
5
2 3 5 6 7

则输出应为
2

搜索更多相关主题的帖子: 青蛙　

第 2 楼

得分:0

能不能定义一个数组a，然后使带石头位置为1，其他为0，然后从0开始找！k为踩到石子个数！使最远跳距m,近n,t=0；然后(t=t+m;t>t+n;t--)假如在这之中有0的话取第一个t等于0元素的位置。如果没有0,t移到t+m的位置,k++.循环直到t+m>L!不知道行不行这个啊！

用0-1统治世界！

第 3 楼

得分:0

不行，真遗憾啊·！

用0-1统治世界！

第 4 楼

得分:0

尝试写的，测试数据也太少，无法验证是否正确

程序算大数需要时间太长，所以我先去改改

算了，我还是放上来。大家给看看吧，这算法不细致。
如果点的设置间隔比青蛙跳的距离大得多
那计算机都快累死了，我今天忙，谁帮我改改好了
程序中石头坐标默认从小到大输入

#include "stdio.h"
#include "malloc.h"

long num_min,bridge_len,*array,stone_sum;
int min,max;

int Search(long i)
{
long j;

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

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

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

int main()
{
long i;

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);
num_min=stone_sum;
Frog_Jump(0,0);

printf("\n%ld\n",num_min);
free(array);
return 0;
}