热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

从抽火柴的问题思考中去如何从结论推导条件

看了刘未鹏的文章《跟波利亚学解题》之后关于解题方法的一些想法。这篇文章提到了我们从小大到看到的数学书上无一不是欧几里得方式定义的:从定义到定理,再到推

看了刘未鹏的文章《跟波利亚学解题》之后关于解题方法的一些想法。

这篇文章提到了我们从小大到看到的数学书上无一不是欧几里得方式定义的:从定义到定理,再到推论。是属于“顺流而下”式的。但这样的书其实完全扭曲了数学的发现过程。所以作者推荐我们去看波利亚的书《How to solve it》中的启发思考方法。刘未鹏自己也总结出了以下几点:

1. 时刻不忘未知量

2. 用特例启发思考

3. 反过来推导(归约)

4. 试错(这是大部分人一拿到题目都会尝试的方法)

5. 调整题目条件

6. 求解一个类似的问题

7. 列出所有跟问题有关的定理或者性质(这是我们高中解数学题常用的方法)

8. 考察反面,考察其他的情况

9. 将问题泛化,并求解这个泛化后的问题

其中我对第三点印象比较深刻,就是如何运用反过来推导的思维。意思就是从题目要得出的结论本身去推导一些对我们解题有用的推论,无论这个推论是充分的还是必要的。如果这个推论是充要的,那我们就将问题进行了一次“双向”规约,如果原问题不容易解决,那么可能推论的问题容易解决。即使得到的推论是必要而非充分的,那我们也可以知道——任何不满足这个推论的解都不是原问题的解。

我们可以用这个方法来尝试解决一下抽火柴的问题。问题描述如下:

100根火柴,两个人轮流取,每个人每次只能取1~7根,谁拿到最后一根火柴谁赢;问有必胜策略吗,有的话是先手还是后手必胜?

如果按照正常的思维习惯,我们会从条件入手,不断的进行试错。但是这个问题如果使用这个方法,我们会感觉无从下手,因为问题的整个解的搜索空间会很大。但如果我们先从要求解的结论入手就会感到容易很多。

我们先假设存在必胜的策略&#xff0c;如果我们最后给对手留下了1&#xff0c;2.....7根火柴的话&#xff0c;对手可以一次性的拿走所有的火柴&#xff0c;那对手可以获胜。但如果我们给对手留下8根火柴&#xff0c;我们可以发现&#xff0c;无论下一次对手如何取火柴&#xff0c;我们都可以把留下的火柴一次性取走&#xff0c;那么我们一定可以获胜。从这里我们可以知道8是一个分界点&#xff01;接着我们再思考给对手留下9&#xff0c;10&#xff0c;.......15根火柴&#xff0c;如果对手足够聪明&#xff0c;那他一定会拿走一些火柴&#xff08;如果剩9&#xff0c;那么他就拿1根&#xff1b;如果剩下10&#xff0c;他就拿2根&#xff1b;依此类推&#xff09;&#xff0c;只剩下8跟火柴&#xff0c;那这个时候我们就陷入了必输的状态当中了。如果我们给对手留下16根火柴&#xff0c;假设对手取走x根火柴&#xff08;1<&#61;x<&#61;7&#xff09;&#xff0c;我们这时对应的取走&#xff08;8-x&#xff09;根火柴&#xff0c;那么就又留给对手8根火柴&#xff0c;那他也就陷入了必输的状态当中了。此时我们可以发现16也是一个分界点&#xff01;

再往下推到我们不难发现&#xff0c;当我们留下8,16,24.....96&#xff08;都是8的倍数&#xff09;根火柴时候&#xff0c;对手一定处于必输的状态当中&#xff0c;因为对手如果取x跟&#xff0c;我们就取对应的&#xff08;8-x&#xff09;根&#xff0c;使得对手永远处于必输的状态当中&#xff08;都剩下8的倍数根火柴&#xff09;。再回到题目本身我们可以发现&#xff1a;存在着必胜的策略&#xff0c;而且是先手必胜。先手一开始先取走4跟火柴&#xff0c;那么就剩下了100-4&#61;96根火柴&#xff0c;那么后手就一定处于必输。

其实这个问题可以泛化为&#xff1a;

m根火柴&#xff0c;两个人轮流取&#xff0c;每个人只能取1~n根(n<&#61;m)&#xff0c;问是否有必胜策略&#xff0c;有的话是先手必胜还是后手必胜&#xff1f;

当我们知道了上面这个特例的思想以后&#xff0c;这个泛化后的问题也就很容易解决了。如果m是&#xff08;n&#43;1&#xff09;的倍数&#xff0c;那么后手必胜&#xff1b;反之&#xff0c;先手必胜。


如果我们从这个问题本身衍生出来&#xff0c;可以变种为下列几个同样思路的问题&#xff1a;

100根火柴&#xff0c;两个人轮流取&#xff0c;每个人每次只能取1&#xff0c;3&#xff0c;5&#xff0c;7根&#xff0c;谁拿到最后一根火柴谁赢&#xff1b;问有必胜策略吗&#xff0c;

有的话是先手还是后手必胜&#xff1f;&#xff08;思路还是一样的&#xff09;

或者是&#xff1a;

100根火柴&#xff0c;两个人轮流取&#xff0c;每个人每次只能取1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;7根&#xff08;不能取6根&#xff0c;注意&#xff0c;当剩下的火柴是m的时候&#xff0c;

不能因为能取的火柴数目比m大就完全拿下&#xff09;&#xff0c;谁拿到最后一根火柴谁赢&#xff1b;问有必胜策略吗&#xff0c;有的话是先手还是后手必胜&#xff1f;&#xff08;还是存在必胜策略&#xff0c;不过这时候8的倍数不是必输的状态了&#xff0c;而是6的倍数&#xff0c;大家可以自己想一想&#xff0c;也欢迎大家一起讨论。&#xff09;



参考链接&#xff1a;

刘未鹏《跟波利亚学解题》&#xff1a;http://mindhacks.cn/2008/04/18/learning-from-polya/ 



推荐阅读
  • 本文探讨了Web开发与游戏开发之间的主要区别,旨在帮助开发者更好地理解两种开发领域的特性和需求。文章基于作者的实际经验和网络资料整理而成。 ... [详细]
  • 本文探讨了在C语言编程中,如何有效避免多文件项目中的重定义问题,通过合理使用预处理器指令和extern关键字,确保代码的健壮性和可维护性。 ... [详细]
  • 在互联网信息爆炸的时代,当用户需求模糊或难以通过精确查询表达时,推荐系统成为解决信息过载的有效手段。美团作为国内领先的O2O平台,通过深入分析用户行为,运用先进的机器学习技术优化推荐算法,提升用户体验。 ... [详细]
  • 本指南详细介绍了如何在同一台计算机上配置多个GitHub账户,并使用不同的SSH密钥进行身份验证,确保每个账户的安全性和独立性。 ... [详细]
  • 微信小程序中实现位置获取的全面指南
    本文详细介绍了如何在微信小程序中实现地理位置的获取,包括通过微信官方API和腾讯地图API两种方式。文中不仅涵盖了必要的准备工作,如申请开发者密钥、下载并配置SDK等,还提供了处理用户授权及位置信息获取的具体代码示例。 ... [详细]
  • 本文探讨了使用Java创建高效且可靠的基准测试的方法,强调了选择合适的工具和理解潜在影响因素的重要性。 ... [详细]
  • 解决Windows 10频繁提示可选功能的方法
    面对Windows 10频繁弹出可选功能提示的问题,用户往往感到困扰。本文将提供一系列有效的解决方案,帮助您彻底解决这一问题,确保您的系统运行更加顺畅。 ... [详细]
  • 在Linux系统上构建Web服务器的详细步骤
    本文详细介绍了如何在Linux系统上搭建Web服务器的过程,包括安装Apache、PHP和MySQL等关键组件,以及遇到的一些常见问题及其解决方案。 ... [详细]
  • 本文将详细介绍如何在ThinkPHP6框架中实现多数据库的部署,包括读写分离的策略,以及如何通过负载均衡和MySQL同步技术优化数据库性能。 ... [详细]
  • Spring Security框架提供了一种方便的'记住我'功能,该功能通过在客户端存储用户信息来保持用户的登录状态,从而提升用户体验。本文将详细介绍如何配置和使用这一功能。 ... [详细]
  • 本文探讨了如何通过WebBrowser控件在用户点击输入框时自动显示图片验证码。该过程可能涉及JavaScript事件的触发与响应。 ... [详细]
  • MacOS 重装指南
    本文详细介绍了如何通过U盘启动并重新安装MacOS,包括遇到安装问题时的解决方案。 ... [详细]
  • 深入解析SSL Strip攻击机制
    本文详细介绍了SSL Strip(一种网络攻击形式)的工作原理及其对网络安全的影响。通过分析SSL与HTTPS的基本概念,探讨了SSL Strip如何利用某些网站的安全配置不足,实现中间人攻击,以及如何防范此类攻击。 ... [详细]
  • 本文介绍如何在Windows Forms应用程序中使用C#实现DataGridView的多列排序功能,包括升序和降序排序。 ... [详细]
  • MySQL性能测试标准倡议:老叶提出的压测基准
    进行MySQL的压力测试通常是为了评估新旧版本之间的性能差异、验证硬件升级的效果、测试参数调整的影响以及评估新业务的负载承受能力。老叶提出了一个MySQL压力测试基准值倡议,旨在促进行业内的标准化和成果共享。 ... [详细]
author-avatar
帕格迪奥
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有