<< 上一主题 | 下一主题 >>

投票 交易 悬赏 活动

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#1 发表于 2011-12-21 00:09 资料 个人空间 短消息 看全部作者 找头盔3 源头：http://www.xycq.net/forum/thread-225830-1-1.html 题：有5个洞窟，排成一排，前一天晚上有人会在其中一个洞窟放一个头盔，次日白天你可以去找头盔，但是只能找一个洞窟，如果没有找到，那么那人会在晚上移动一次头盔，但是只能向右或者向左移动一格，必须移动，请给出一个方案，必定能够找到头盔。 引申：http://www.xycq.net/forum/thread-226001-1-1.html 题：有9个洞窟排成三行三列，前一天晚上有人会在其中一个洞窟放一个头盔，次日白天你可以去找头盔，但是只能找两个洞窟，如果没有找到，那么那人会在晚上移动一次头盔，但是只能向“前后左右”四个方向中的某个方向移动一格，必须移动，请给出一个方案，必定能够找到头盔。 新题1：立方体8个顶点。一个球在某一个点上。每一个回合，甲可以查看3个（原来错写成2个）点是否有球；查看完毕乙将球换到临近的一个点中。请给出一个方案，甲必定能够找到该球。（第一个给出完整答案的100TB） 新题2：立方体8个顶点和12条棱共20个点。一个球在某一个点中。每一个回合，甲可以查看3个点是否有球；查看完毕乙将球换到临近的一个点中。请给出一个方案，甲必定能够找到该球。（第一个给出完整答案的100TB） 注：球位于顶点时，可以跳到该顶点所在的棱的中点。     球位于某条棱的中点时，可以跳到该棱的二个端点。 新题3：立方体8个顶点、12条棱的中点和6个面的中心共20个点。一个球在某一个点中。每一个回合，甲可以查看n个点是否有球；查看完毕乙将球换到临近的一个点中。请问n的最小值，甲能使A必定能够找到该球。（第一个给出完整答案的500TB） 注：球位于顶点时，可以跳到该顶点所在的棱的中点。      球位于某条棱的中点时，可以跳到该棱的二个端点或者该棱所在面的中心。      球位于某个面的中点时，可以跳到该面的四条棱的中点。 本人用图像解题，提供本人解题用到的图。 不能上传附件，将附件放到以下位置。 http://www.xycq.net/forum/viewth ... ;page=11#pid3321611 [ 本帖最后由 墨叶 于 2011-12-21 08:21 编辑 ] [广告] 《精忠报国岳飞传完整版》火热发布

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#2 发表于 2011-12-21 00:09 资料 个人空间 短消息 看全部作者 定义和定理 点： 球：每一个回合结束，球会移动到附近的一个点。 回合：每回合开始甲查看N个点。若所有的球均在这些点中，游戏结束；          否则该回合结束，乙必须将所有球移动到临近的点上。 邻点与相邻：球能在一个回合从A点移动到的B点，则B点为A点的邻点。                   AB为相邻关系，用线段连结。任意点的邻点个数为该点的邻点数。 图：图包含所有点以及相邻点之间的连线。 白点：该回合不可能有球的点。条件为该点的所有邻点前一回合均为明点或者白点。 灰点与黑点：无法确定是否有球的点为灰点。多球状态有球的点为黑点。 明点：明点为该回合甲查看的点。每回合甲查看的明点的个数为定值，记为x。 起点：规定最早确定为一个白点的为起点。                      第一个回合能确定多个点时选择邻点最少的点为起点。                      一般情况下，选择邻点最少的点为起点。 奇（偶）点：从起点移动到该点需要的回合数一定为奇数（偶数），则该点为奇点（偶点）。 非奇非偶点：从起点移动到该点需要的回合数可以是奇数也可以是偶数，                  则该点为非奇非偶点，可简称为非点。 对称图：只有奇点和偶点，没有非点的图为对称图。 解：对一个确定的图和确定的球数。存在一个最小的N使甲能在有限回合之后必定能找到所有的球，则N为该图的解。      明点取最小值N时，需要的最少回合数为P。则（N、P）为最优解。 定理： 1、N不少于邻点数的最小值。 2、若存在一种方式使对称图的所有奇点（或者偶点）为明点，则该图有解。 [ 本帖最后由 墨叶 于 2011-12-21 14:01 编辑 ] [广告] 《精忠报国岳飞传完整版》火热发布

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#3 发表于 2011-12-21 00:10 资料 个人空间 短消息 看全部作者 常见对称图及答案 为了表述简单，本贴所有题都满足“总题干”。不同题M、N不同。不能保证答案完全正确。 总题干：某图形中有M个点。有线段连结的两点为邻点。 开始前乙将一个球放入任意一点。每回合开始甲查看N个点。若所有的球均在这些点中，游戏结束；          否则该回合结束，乙必须将所有球移动到邻点上。求以下各题的解，即甲能找到球的N的最小值。 题型一、一维。 题1：已知常数M。线段上有M个点，端点有1个邻点，其他的点均有2个邻点（M>1）。 解:N=1。 题2：已知常数M。闭合线段上有M个点，每个点均有2个邻点（M>2 ）。 解：N=2。 题型二、二维 题3：已知常数L，L>3。有一个2*（L-1）的矩形，均匀分布3*L个点。距离为1的两点为邻点。 即顶点有2个邻点，边上的点有3个邻点，中间的点有4个邻点。 解：N=2。 题4：已知常数A和L，L>2A-1。有一个（2A-2）*（L-1）的矩形，均匀分布（2A-1）*L个点。距离为1的两点为邻点。 即顶点有2个邻点，边上的点有3个邻点，中间的点有4个邻点。 解：N=A。 [ 本帖最后由 墨叶 于 2011-12-21 14:08 编辑 ] [广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#4 发表于 2011-12-21 00:11 资料 个人空间 短消息 看全部作者 典型非对称图分析 为了表述简单，本贴所有题都满足“总题干”。不同题M、N不同。不能保证答案完全正确。 总题干：某图形中有M个点。有线段连结的两点为邻点。 开始前乙将一个球放入任意一点。每回合开始甲查看N个点。若所有的球均在这些点中，游戏结束；          否则该回合结束，乙必须将所有球移动到邻点上。求以下各题的解，即甲能找到球的N的最小值。 题型一、三角形 题1：正三角形。答案：N=2 题2：正四面体。 等价图形：正三角以及中心点，且中心点与三个顶点相邻。答案：N=3 题3：梯形以及底边的中心，且底边的中点与四个顶点都相邻，底边的两个顶点不相邻。答案：N=3 等价图形：3个正三角形边重合得到的图形。 题4：正六边形及其中心，且中心点与所有顶点相邻。答案：N=3 等价图形：六棱锥。 题5：棱锥。答案：N=3 题6：三棱柱。答案：N=3 题7：四棱柱，即长方体、正方体。答案：N=3 题8：棱柱。答案：N=3 [ 本帖最后由 墨叶 于 2011-12-21 14:27 编辑 ] [广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#5 发表于 2011-12-21 00:11 资料 个人空间 短消息 看全部作者 两球问题分析 略 [广告] 《精忠报国岳飞传完整版》火热发布

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#6 发表于 2012-7-15 22:50 资料 个人空间 短消息 看全部作者 回复 #9 toushion 的帖子 严格证明很麻烦。用反证法可以大致说明结论的合理性。 [广告] 真诚支持说岳，携手共创辉煌

墨叶 ★★★★ 节度留后虎豹骑 组别 虎豹骑 级别 大将军 功绩 359 帖子 23258 编号 97330 注册 2006-12-26 家族 轩辕少林寺

#7 发表于 2012-7-16 17:42 资料 个人空间 短消息 看全部作者 回复 #11 toushion 的帖子 我也没算。 二元的通解有点麻烦，可能还要分类。 思路不变。也没必要写通解。 [广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！

投票 交易 悬赏 活动

当前时区 GMT+8, 现在时间是 2025-8-4 12:57
京ICP备2023018092号 轩辕春秋 2003-2023 www.xycq.org.cn