首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
  • 青蛙过河 高手请进 [已结贴,结贴人:zhoufuguo8802]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhoufuguo8802
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    • 揭贴率:
    发表于:2008-08-20 10:32:06 楼主
                          青蛙过河
    Description
    在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。
    输入
    输入包含多组数据,每组数据第一行有一个正整数L(1 <= L <= 20000),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。输入以一个0结束。
    输出
    对每组数据输出一行,这一行只包括一个整数,表示青蛙过河最少需要踩到的石子数。
    请大虾指教(说明C++代码)
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Lx_china
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 10:35:421楼 得分:0
    好麻烦的作业题...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • self_control
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 10:36:232楼 得分:2
    这个不是sysu西西里上的题目么- -!
    动态规划做出来的...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • veloting
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 10:39:173楼 得分:0
    上次的作业题分还没结呢,又出来新题目了の- -
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guzhilei1986
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 10:46:474楼 得分:2
    dp
    d[20011][11];
    d[i][j]//i表示桥上的某一点,j表示上一次跳了j的距离到达i点。
    如果i点有石头,那么
    d[i][j]=min{d[i-k][k]}+1;//k为[s,t]之间的值。
    如果i点没有石头,那么
    d[i][j]=min{d[i-k][k]};

    答案应该是min{ d[l+1到l+T][S到T] };
    楼主试一下。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhoufuguo8802
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 10:48:005楼 得分:0
    声明下:这个不是作业题。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xianyuxiaoqiang
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 11:19:396楼 得分:5
    大概算法如下:没有运行过.楼主可作参考
    C/C++ code
    int f(int s,int t,int start,int end){//start end分别表示当前位置坐标和终点(end==L)   if(start>=end)return 0;//递归在此结束 int min=0; int num=0; num=f(s,t,start+s,end); if(status[start+i]==STONE){//status[]是记录坐标上是否有石头的数组 num++; } min=num; for(int i=s+1;i<=t;i++){ num=f(s,t,start+i,end);//计算跳过i格后至少要踩多少石头 if(status[start+i]==STONE){//此处是石头个数增加的源泉 num++; } if(num<min){//调整最小值 min=num; } } return min;//返回当前位置到终点最少踩到的石头数 }
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guzhilei1986
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 12:27:277楼 得分:1
    楼上的代码的效率很低
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guzhilei1986
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 12:32:118楼 得分:2
    输入包含多组数据,每组数据第一行有一个正整数L(1 <= L <= 20000),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。

    看看数据量哦,6楼的代码相当于深度搜索,算一下时间复杂度。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • e_sharp
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 14:17:589楼 得分:2
    mark先
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wjb_yd
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-20 22:43:3010楼 得分:2
    贪心算法,每次都跳到能够得到的最远的那个石子,这样跳可以保证最优
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hxqing99
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-21 10:33:0711楼 得分:2
    问题貌似还可以用最短路问题求解
    0表示起点,L表示终点,每一个整数点表示一个节点
    i点可跳到的点与i点通路
    将有石头的点所在的边上给个大权(比如10000),其他边上给个小权(比如1)
    这样只要求出最短路然后对10000求余加上除以10000即得出所需的数即为步数
    最短路问题可以用Dijkstra方法求解,效率较动态规划会高点。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guzhilei1986
    • 等级:
    • 可用分等级:
    • 总技术分:
    • 总技术分排名:
    发表于:2008-08-21 16:06:4812楼 得分:2
    引用 11 楼 hxqing99 的回复:
    问题貌似还可以用最短路问题求解
    0表示起点,L表示终点,每一个整数点表示一个节点
    i点可跳到的点与i点通路
    将有石头的点所在的边上给个大权(比如10000),其他边上给个小权(比如1)
    这样只要求出最短路然后对10000求余加上除以10000即得出所需的数即为步数
    最短路问题可以用Dijkstra方法求解,效率较动态规划会高点。

    就是哦,好像可以。
    修改 删除 举报 引用 回复

    网站简介广告服务网站地图帮助联系方式诚聘英才English 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved