网易首页 > 网易号 > 正文 申请入驻

程序设计实习:11.3讨厌的青蛙

0
分享至

讨厌的青蛙 问题描述

在韩国, 有一种小青蛙

每到晚上, 这种青蛙会跳跃稻田, 从而踩踏稻子

农民早上看到被踩踏的稻子, 希望找到造成最大损害的 那只青蛙经过的路径

每只青蛙总是沿着一条直线跳跃稻田

且每次跳跃的距离都相同

稻田里的稻子组成一个栅格, 每棵稻子位于一个格点上 而青蛙总是从稻田的一侧跳进稻田, 然后沿着某条直线穿 越稻田, 从另一侧跳出去

可能会有多只青蛙从稻田穿越 青蛙每一跳都恰好踩在一棵水稻上, 将这棵水稻拍倒 有些水稻可能被多只青蛙踩踏 农民所见到的是图4中的情形, 并看不到图3中的直线, 也见不到别人家田里被踩踏的水稻

而在一条青蛙行走路径的直线上, 也可能会有些被踩 踏的水稻不属于该行走路径

① 不是一条行走路径: 只有2棵被踩踏的水稻

② 是一条行走路径, 但不包括 (2,6)上的水稻

③ 不是一条行走路径: 虽然有3棵被踩踏的水稻, 但这3 棵水稻之间的距离间隔不相等

题目要求 请写一个程序, 确定:

在各条青蛙行走路径中, 踩踏水稻最多的那一条上, 有多 少颗水稻被踩踏

例如, 图4中答案是7, 因为第6行上全部水稻恰好构成一 条青蛙行走路径

程序输入

从标准输入设备上读入数据

第一行上两个整数R, C, 分别表示稻田中水稻的行数和 列数, 1≤R, C≤5000

第二行是一个整数N, 表示被踩踏的水稻数量, 3≤N≤5000

在剩下的N行中, 每行有两个整数, 分别是一颗被踩踏水 稻的行号(1~R)和列号(1~C), 两个整数用一个空格隔开

且每棵被踩踏水稻只被列出一次

程序输出

从标准输出设备上输出一个整数

如果在稻田中存在青蛙行走路径, 则输出包含最多水稻 的青蛙行走路径中的水稻数量, 否则输出0

解题思路 — 枚举 枚举什么?

枚举每个被踩的稻子作为行走路径起点 (5000个) 对每个起点, 枚举行走方向 (5000种)

对每个方向枚举步长 (5000种)

枚举步长后还要判断是否每步都踩到水稻 时间: 5000*5000*5000 * , 不行! 10 解题思路 — 枚举 枚举什么? 枚举路径上的开始两点 每条青蛙行走路径中至少有3棵水稻 假设一只青蛙进入稻田后踩踏的前两棵水稻分别是 (X1 ,Y1 ),(X2 ,Y2 ). 那么:

青蛙每一跳在 X 方向上的步长 dX = X2 - X1 , 在 Y 方向上的步长 dY = Y2 - Y1 ;

(X1 – dX, Y1 - dY) 需要落在稻田之外;

当青蛙踩在水稻(X, Y)上时, 下一跳踩踏的水稻是 (X + dX, Y + dY); 将路径上的最后一棵水稻记作(XK , YK ), (XK + dX, YK + dY) 需要落在稻田之外; 11 解题思路:猜测一条路径 猜测的办法需要保证: 每条可能的路径都能够被猜测到

从输入的水稻中任取两棵 作为一只青蛙进入稻田后踩踏的前两棵水稻 看能否形成一条穿越稻田的行走路径 12 解题思路:猜测一条路径 猜测的过程需要尽快排除错误的答案

猜测(X1, Y1), (X2, Y2) -- 所要寻找的行走路径上的前两 棵水稻 当下列条件之一满足时, 这个猜测就不成立:

青蛙不能经过一跳从稻田外跳到(X1, Y1)上

按照(X1, Y1), (X2, Y2)确定的步长, 从(X1, Y1)出发, 青 蛙最多经过(MAXSTEPS - 1)步, 就会跳到稻田之外

MAXSTEPS是当前已经找到的最好答案

13 选择合适的数据结构 选择合适的数据结构

采用的数据结构需要与问题描述中的概念对应 关于被踩踏的水稻的坐标, 该如何定义?

方案1: struct { int x, y; } plants[5000];

方案2: int plantsRow[5000], plantsCol[5000]; 显然方案1更符合问题本身的描述

14 设计的算法要简洁 尽量使用C提供的函数完成计算的任务 猜测一条行走路径时, 需要从当前位置(X, Y)出发上时, 看看 (X + dX, Y + dY)位置的水稻是否被踩踏;

方案1: 自己写一段代码, 看看(X + dX, Y + dY) 是否在数组 plants中

方案2: 先用qsort()对plants中的元素排序, 然后用bsearch()从 中查找元素(X + dX, Y + dY) 基于方案2设计的算法更简洁, 更容易实现, 更不容易出错误 通常, 所选用的数据结构对算法的设计有很大影响

15 注意:

一个有n个元素的数组, 每次取两个元素, 遍历所有取法

代码写法: for( int i = 0; i < n – 1; i ++ ) for( int j = i + 1; j < n; j ++ ) { a[i] = …; a[j] = …; }

参考程序:

//x方向过早越界了. 说明本次选的第二点不成立 //如果换下一个点作为第二点, x方向步长只会更大, 更不成立, 所以应该

//认为本次选的第一点必然是不成立的, 那么取下一个点作为第一点再试

小 结 :

枚举顺序十分重要, 好的枚举顺序, 能够及早排除不可 能的情况, 减少枚举次数 本题将踩倒的水稻按照位置进行排序, 枚举的时候先枚 举序号低的, 就能够有效减少枚举次数, 体现在: if (plants[ i ].x + (max - 1) * dX > r) break;

//x方向过早越界了. 说明本次选的第二点不成立

//如果换下一个点作为第二点, x方向步长只会更大, 更不成立

//所以应该认为本次选的第一点必然是不成立的,

//那么取下一个点作为第一点再试

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
张扣扣除夕夜持刀制造灭门案,却独独放过仇敌妻子?究竟为什么

张扣扣除夕夜持刀制造灭门案,却独独放过仇敌妻子?究竟为什么

纸鸢奇谭
2024-03-28 15:41:36
地下人乳交易到底有多变态?躺怀里喝,可包天也可包月

地下人乳交易到底有多变态?躺怀里喝,可包天也可包月

韦一同说
2023-09-21 20:15:56
同曦董事长:我们未来的目标不仅是季后赛 而是进入前八前五前三

同曦董事长:我们未来的目标不仅是季后赛 而是进入前八前五前三

直播吧
2024-03-28 15:55:26
古力娜扎有点过于干瘦了,肉也松松的,看得出平时确实不健身

古力娜扎有点过于干瘦了,肉也松松的,看得出平时确实不健身

娱乐圈酸柠檬
2024-03-28 01:16:35
看谁还敢动中国?欧洲一强国表态力挺中国,拜登这回彻底坐不住了

看谁还敢动中国?欧洲一强国表态力挺中国,拜登这回彻底坐不住了

小lu侃侃而谈
2024-03-25 19:40:33
普京揪出最大“内鬼”,总理竟是敌方间谍,给中方敲响警钟!

普京揪出最大“内鬼”,总理竟是敌方间谍,给中方敲响警钟!

大国观察眼
2024-03-28 00:58:32
春天,这5种蔬菜尽量少买,菜贩子自己都不吃,健康问题,要重视

春天,这5种蔬菜尽量少买,菜贩子自己都不吃,健康问题,要重视

秀厨娘
2024-03-25 16:44:05
美人含笑倚门庭,红妆素裹展春心

美人含笑倚门庭,红妆素裹展春心

娱乐圈酸柠檬
2024-03-27 21:23:45
莫斯科恐袭,俄罗斯后悔了!3个可能的真凶曝光,世界大变局要来

莫斯科恐袭,俄罗斯后悔了!3个可能的真凶曝光,世界大变局要来

李大娱乐糊涂
2024-03-28 13:18:14
周海媚北京豪宅菜园荒芜,人还是要有后代的

周海媚北京豪宅菜园荒芜,人还是要有后代的

九方鱼论
2024-03-25 14:20:29
百度员工自爆,互联网双职工,我年薪78万,老婆50万,武汉有房

百度员工自爆,互联网双职工,我年薪78万,老婆50万,武汉有房

侃故事的阿庆
2024-03-28 13:15:25
杭州一地发现新物种!网友:太萌了

杭州一地发现新物种!网友:太萌了

环球网资讯
2024-03-28 11:29:17
盖世汽车:小米SU7核心零部件配套供应商一览

盖世汽车:小米SU7核心零部件配套供应商一览

户外小阿隋
2024-03-28 14:07:29
上海外卖小哥直言不愿缴纳社保:700元给女儿买点玩具不好吗?

上海外卖小哥直言不愿缴纳社保:700元给女儿买点玩具不好吗?

映射生活的身影
2024-03-27 20:56:59
全红婵被质疑学历低,专家说全红婵不配清华?广州名校抢着要

全红婵被质疑学历低,专家说全红婵不配清华?广州名校抢着要

流沙溪水
2024-03-26 19:56:53
张海波任山东省副省长

张海波任山东省副省长

新京报
2024-03-27 17:12:07
曾黎与左小青,两大女神谁最美

曾黎与左小青,两大女神谁最美

娱乐圈酸柠檬
2024-03-25 15:54:30
为了钱我做一名奶妈,喂完老板的儿子,还要加班照顾我老板

为了钱我做一名奶妈,喂完老板的儿子,还要加班照顾我老板

赵主任故事会
2023-09-10 16:54:10
所罗门总理称作出与台当局“断交”与中国建交的决定是明智的,国台办:高度赞赏

所罗门总理称作出与台当局“断交”与中国建交的决定是明智的,国台办:高度赞赏

环球网资讯
2024-03-27 11:13:19
闹大了!地磁暴竟然对男女有别,地磁暴难道还非性别对待吗?

闹大了!地磁暴竟然对男女有别,地磁暴难道还非性别对待吗?

娱乐圈见解说
2024-03-28 14:01:05
2024-03-28 16:44:49
爱你雅课
爱你雅课
科普知识,科教视频
213文章数 623关注度
往期回顾 全部

科技要闻

王传福称合资品牌份额将降到10%

头条要闻

媒体:中国领导人对"中国见顶论"的回应非常重要

头条要闻

媒体:中国领导人对"中国见顶论"的回应非常重要

体育要闻

池江璃花子:我不打算输

娱乐要闻

莱昂纳多与25岁新女友互相投喂超恩爱

财经要闻

疯狂!三个城市,三个地王!

汽车要闻

混动增程双模式 长安UNI-Z售11.79万起

态度原创

亲子
时尚
家居
手机
军事航空

亲子要闻

这眼神和表情,好委屈呀!

今日热点:9部电影定档2024五一档;林一粉丝团辟谣出演《全球高考》......

家居要闻

邂逅浪漫,注入柔性的法式基因

手机要闻

小米 Redmi Note 13 Turbo 手机曝光:骁龙 8s Gen 3 芯片、5000 万主摄

军事要闻

乌方声称击落两枚俄"锆石"高超音速导弹 俄方未予回应

无障碍浏览 进入关怀版