这题给个思路
本帖最后由 chinalixs 于 2015-2-20 10:36 编辑题目：给定一个非负整数数组，假定你的初始位置为数组第一个下标。
数组中的每个元素代表你在那个位置能够跳跃的最大长度。请确认你是否能够跳跃到数组的最后一个下标。例如：A = ,return true.A = ,return false.格式：第一行输入一个正整数n，接下来的一行，输入数组A。如果能跳到最后一个下标，输出“true”，否则输出“false”样例输入52 0 2 0 1
样例输出true
#include <stdio.h>
int main()
{
int i,n;
scanf("%d",&n);
int a;
for(i=0;i<n;i++)
{
scanf("%d",&a);
}
if(n==1)
{
if(a==0)
printf("true");
else
printf("false");
}
else
{
for(i=0;i<n-1;)
{
i+=a;
if(i==n-1)
printf("true");
if(i>n-1)
printf("false");
if(a==0)
{
if(i<n-1)
printf("false");break;
}
}
}
return 0;
} 明显错了， 人家是最大跳那么多步， 不是就跳那么多步， 所有每一次都是有多重跳法，不断下去而形成一颗数，你可以用深搜，找到一种结果就行了。。。 本帖最后由 yes2 于 2015-2-28 13:18 编辑
我也贴个代码，计蒜客过不去，不知道错在哪
#include <stdio.h>
#include <string.h>
#include <malloc.h>
int main()
{
int n1;
scanf("%d", &n1);
int *psz = (int *)malloc(n1*sizeof(int));
for (int n=0 ; n<n1 ; n++)
{
scanf("%d" , &psz);
}
int nIndex = n1 - 2;
int nEnd = n1 - 1;
int nSuc = 0;
while (nIndex >= 0)
{
if (nIndex + psz >= nEnd)
{
nEnd = nIndex;
nSuc = 1;
}
else
{
nSuc = 0;
}
nIndex--;
}
if (nSuc)
{
printf("true");
}
else
{
printf("false");
}
free(psz);
return 0;
}
⊙﹏⊙说实在的，我不喜欢算法也不擅长算法，也比较菜。
根据8楼 随意之水的一滴 大神的说法，将他的伪代码里的max和i的值改为0，得到以下代码，测试就能通过了，orz。
另外a在OJ可以编译，但在正常编译器里是通不过的，测试环境，VC6，VS2013。
#include<stdio.h>
int main()
{
int n,max=0;
scanf("%d",&n);
int a;
for(int i=0;i<n;i++)
{
scanf("%d",&a);
}
for(int j=0;j<n;j++)
{
if(j>max)
{
printf("false");
return 0;
}
if(j+a>max)
max=j+a;
}
printf("true");
return 0;
} 可以往回跳。。。。。
应该用bfs{:301_1007:} 帮你顶哈等待大牛 lyogoo 发表于 2015-2-19 22:47
明显错了， 人家是最大跳那么多步， 不是就跳那么多步， 所有每一次都是有多重跳法，不断下去而形成一颗数 ...
当然，时间，时间复杂度很大，可以为了练代码去实现以下，应该有专门的算法，只是我不知道，我很水 lyogoo 发表于 2015-2-19 22:47
明显错了， 人家是最大跳那么多步， 不是就跳那么多步， 所有每一次都是有多重跳法，不断下去而形成一颗数 ...
我擦~搜噶死乃。。。我题都读错了。。。。 Anonymouss 发表于 2015-2-19 22:30
可以往回跳。。。。。
应该用bfs
看来要重新补数据结构啊。多谢了！ 这个只需要是不是能够走到就行，也就是一遍顺序遍历就行了。。。。。从1个开始，对这一个判断能到的最远距离，如果大于旧的最远距离，然后更新最远距离，如果下一个在最远距离内，那么久继续判断下一个点，如果下一个点不在，则程序结束false，下个是末尾则true
int max=1
for int i=1;i<n;i++
if i>max then return false
if i+go>max then max=i+go
return true chinalixs 发表于 2015-2-20 10:38
看来要重新补数据结构啊。多谢了！
{:301_986:}不客气~
页:
[1]
2