热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【智力题】过桥问题和倒水问题

原文:http:blog.csdn.netmorewindowsarticledetails7481851过桥问题和倒水问题都是笔试面试中的热门智力题,

原文:http://blog.csdn.net/morewindows/article/details/7481851

过桥问题和倒水问题都是笔试面试中的热门智力题,不但微软、GOOGLE、百度、腾讯等公司采用,甚至在IQ测试与公务员考试中都能见到。本文不但教你如何快速用手算来解决这两种问题,并且教你如何用程序代码来计算这两种问题。绝对让你大有收获。

一.过桥问题

在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时通过。如果各自单独过桥的话,四人所需要的时间分别是1,2,5,8分钟;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,你如何设计一个方案,让用的时间最少。

这个题目被微软、GOOGLE、百度、华硕、建设银行等很多公司用作笔试题或面试题。当然也有用在IQ测试中。

解答其实也容易,能者多劳这四个字就足以形容解答方案了——用时短的人必须要多跑几趟以便传递手电筒。

设这四个人叫做A,B,C,D,他们所需要的时间分别是1,2,5,8分钟。

第一步:AB过桥,花费2分钟。

第二步:A回来,花费1分钟。

第三步:CD过桥,花费8分钟。

第四步:B回来,花费2分钟。

第五步:AB过桥,花费2分钟。

这样只要花费2+1+8+2+2=15分钟,下面再来考虑如何用程序来解决这类问题,在写程序之前还有个细节要考虑下,比如A,B,C,D四个人所需要的时间分别是1,8,9,10分钟。

方案一

第一步:AB过桥,花费8分钟。

第二步:A回来,花费1分钟。

第三步:CD过桥,花费10分钟。

第四步:B回来,花费8分钟。

第五步:AB过桥,花费8分钟。

一共要8+1+10+8+8=35分钟。

方案二

第一步:AB过桥,花费8分钟。

第二步:A回来,花费1分钟。

第三步:AC过桥,花费9分钟。

第四步:A回来,花费1分钟。

第五步:AD过桥,花费10分钟。

一共要8+1+9+1+10=29分钟。

因此可以得出更加细化的解决方案——要么是最快者将最慢的2个送过桥,要么是最快的2个将最慢的2个送过桥。即将过桥的人按其过桥的时间从小到大排列,设为A,B,…… Y,Z。其中AB是最快的二个,YZ是最慢的二个。那么就有二种方案:

方案一 最快者将最慢的2个送过桥

第一步:AZ过桥,花费Z分钟。

第二步:A回来,花费A分钟。

第三步:AY过桥,花费Y分钟。

第四步:A回来,花费A分钟。

这四步后总人数就减小2个,花费时间为A + A + Y + Z分钟。

方案二 最快的2个将最慢的2个送过桥

第一步:AB过桥,花费B分钟。

第二步:A回来,花费A分钟。

第三步:YZ过桥,花费Z分钟。

第四步:B回来,花费B分钟。

这四步后总人数同样减小2个,花费时间为A + B + B + Z分钟。

这样,每次比较一下这二种方案就能将总人数减小2。然后我们再考虑一些边界情况:

有三个人过桥设为A,B,C(已经排好序,下同)。应该花费A + B + C分钟。

有二个人过桥设为A,B。那么肯定是花费B分钟。

有一个人过桥设为A。肯定花费A分钟。

 

//热门智力题 - 过桥问题
#include
#include

const int MAXN = 1000;
int cmp(const void *x,const void *y)
{
return *(int *)x-*(int *)y;
}
int main()
{cout
<<"热门智力题 - 过桥问题"<<endl;cout<<" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n"<<endl; int n, i, sum, a[MAXN];cout<<"请输入人数&#xff1a;";cin>>n;cout<<"请输入每个人过桥时间&#xff0c;以空格分开"<<endl;for (i &#61; 0; i )cin>>a[i];qsort(a, n, sizeof(a[0]), cmp);sum &#61; 0;for (i &#61; n - 1; i > 2; i &#61; i - 2){ //最小者将最大2个送走或最小2个将最大2个送走if (a[0] &#43; a[1] &#43; a[1] &#43; a[i] 0] &#43; a[0] &#43; a[i - 1] &#43; a[i])sum &#61; sum &#43; a[0] &#43; a[1] &#43; a[1] &#43; a[i];elsesum &#61; sum &#43; a[0] &#43; a[0] &#43; a[i - 1] &#43; a[i]; }if (i &#61;&#61; 2)sum &#61; sum &#43; a[0] &#43; a[1] &#43; a[2];else if (i &#61;&#61; 1) sum &#61; sum &#43; a[1];else sum &#61; a[0];cout<<"最短过桥时间为&#xff1a;"<endl;return 0;
}

程序运行结果如下&#xff1a;

 

二&#xff0e;倒水问题

这个题目的版本非常之多&#xff0c;有微软版的&#xff0c;腾讯版的&#xff0c;新浪版的等等&#xff0c;最常见的是给你一个容量为5升的桶和一个容量为3升的桶&#xff0c;水不限使用&#xff0c;要求精确得到4升水。

解法肯定有很多&#xff0c;可以用宽度优先搜索&#xff08;BFS&#xff09;&#xff0c;也可以用穷举法。穷举法实现比较方便&#xff0c;其基本思想是用&#xff1a;用小桶容量的倍数对大桶的容量进行取余。比如3升的桶和5升的桶得到4升水可以这样做&#xff1a;

3 % 5 &#61; 3

6 % 5 &#61; 1

9 % 5 &#61; 4

成功得到4升水。&#xff08;PS&#xff1a;上面的过程用如何用文字描述了&#xff1f;&#xff09;

同样&#xff0c;用7升的桶和11升的桶得到2升水可以这样做&#xff1a;

7 % 11 &#61; 7

14 % 11 &#61; 3

21 % 11 &#61; 10

28 % 11 &#61; 6

35 % 11 &#61; 2

成功得到2升水。

哈哈&#xff0c;有了这个基本思想在用笔算答案时简直是遇神杀神&#xff0c;遇佛杀佛&#xff0c;又方便又快速&#xff01;如果要求用程序来实现如何做了&#xff1f;easy&#xff0c;将倒水问题的基本思想用易于编程的话来翻译下——不断用小桶装水倒入大桶&#xff0c;大桶满了立即清空&#xff0c;每次判断下二个桶中水的容量是否等于指定容量。有了这个倒水问题的编程指导方针后代码非常容易写出&#xff1a;

 

//热门智力题 - 打水问题
//基本思想&#xff1a;用小桶容量的倍数对大桶的容量进行取余。
//指导方针&#xff1a;不断用小桶装水倒入大桶&#xff0c;大桶满了立即清空&#xff0c;
//每次判断下二个桶中水的容量是否等于指定容量。
#include
#include

#include
<string>
using namespace std;
const string OPERATOR_NAME[7] &#61; {"装满A桶","装满B桶","将A桶清空","将B桶清空","A桶中水倒入B桶","B桶中水倒入A桶","成功"
};
int main()
{cout
<<"热门智力题 - 打水问题"<<endl;cout<<" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n"<<endl;int a_volume, b_volume, goal_volume;vector<string> record; //记录操作步数int ai;int i, a_water, b_water;cout<<"请输入A桶容量&#xff0c;B桶容量&#xff0c;目标容量&#xff1a;";cin>>a_volume>>b_volume>>goal_volume;a_water &#61; b_water &#61; 0; //A桶&#xff0c;B桶中有多少升水char szTemp[30];while (true){if (a_water &#61;&#61; 0)//A桶没水,就装满水
{a_water &#61; a_volume;sprintf(szTemp, " A:%d B:%d", a_water, b_water); record.push_back(OPERATOR_NAME[0] &#43; szTemp);//fill A
}else{//如果A桶的水比(B桶容量-B桶的水)要多if (a_water > b_volume - b_water){//A桶的水&#61;&#61;A桶的水&#43;B桶的水-B桶容量a_water &#61; a_water &#43; b_water- b_volume;b_water &#61; b_volume; //B桶的水装满了sprintf(szTemp, " A:%d B:%d", a_water, b_water); record.push_back(OPERATOR_NAME[4] &#43; szTemp);//A->B if (a_water &#61;&#61; goal_volume)break;b_water &#61; 0; //将B桶清空sprintf(szTemp, " A:%d B:%d", a_water, b_water); record.push_back(OPERATOR_NAME[3] &#43; szTemp);}else{//B桶的水&#61;&#61;A桶的水&#43;B桶的水b_water &#43;&#61; a_water; a_water &#61; 0;sprintf(szTemp, " A:%d B:%d", a_water, b_water);record.push_back(OPERATOR_NAME[4] &#43; szTemp);//A->Bif (b_water &#61;&#61; goal_volume) break;}}}record.push_back(OPERATOR_NAME[6]); //successcout<<"\n---------------------------------------------------"<<endl;cout<<"一个可行的倒水方案如下"<<endl;vector<string>::iterator pos;for (pos &#61; record.begin(); pos !&#61; record.end(); pos&#43;&#43;)cout<<*pos<<endl;cout<<"---------------------------------------------------"<<endl;return 0;
}

程序运行结果如下&#xff1a;

 

注意这里只是给出一个可行的倒水方案&#xff0c;不一定是最优解。另外倒水问题要注意下像2升的桶和4升的桶得到3升水这种不可解的情况&#xff0c;这种不可解情况在用本文中对倒水问题所总结的基本思想计算时会得到循环数列。其根本原因是二个桶容量的最大公约数无法被目标容量所整除&#xff0c;如6升的桶和9升的桶无法得到2升水是因为69的最大公约数是3GCD(6&#xff0c;9)&#61;33无法整除2

倒水问题也也容易推广到多个桶的情况&#xff0c;分析方法和上文差不多&#xff0c;这里就不再赘述了。

 

过桥问题和倒水问题就讲解到此&#xff0c;相信以后这二类问题都不会再困扰大家了^_^。

 

 

转:https://www.cnblogs.com/theCambrian/p/3474785.html



推荐阅读
  • 本题探讨了在一个有向图中,如何根据特定规则将城市划分为若干个区域,使得每个区域内的城市之间能够相互到达,并且划分的区域数量最少。题目提供了时间限制和内存限制,要求在给定的城市和道路信息下,计算出最少需要划分的区域数量。 ... [详细]
  • 编程挑战:2019 Nitacm 校赛 D 题 - 雷顿女士与分队(高级版)
    本文深入解析了2019年Nitacm校赛D题——雷顿女士与分队(高级版),详细介绍了问题背景、解题思路及优化方案。 ... [详细]
  • 本文深入探讨了HTTP请求和响应对象的使用,详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外,还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]
  • 树链问题的优化解法:深度优先搜索与质因数分解
    本文介绍了一种通过深度优先搜索(DFS)和质因数分解来解决最长树链问题的方法。我们通过枚举树链上的最大公约数(GCD),将所有节点按其质因子分类,并计算每个类别的最长链,最终求得全局最长链。 ... [详细]
  • 本文详细介绍了C++中map容器的多种删除和交换操作,包括clear、erase、swap、extract和merge方法,并提供了完整的代码示例。 ... [详细]
  • 本文深入探讨了POJ2762问题,旨在通过强连通分量缩点和单向连通性的判断方法,解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤,并附带完整的代码示例。 ... [详细]
  • 本文详细介绍了网络存储技术的基本概念、分类及应用场景。通过分析直连式存储(DAS)、网络附加存储(NAS)和存储区域网络(SAN)的特点,帮助读者理解不同存储方式的优势与局限性。 ... [详细]
  • 开发笔记:2020 BJDCTF Re encode
    开发笔记:2020 BJDCTF Re encode ... [详细]
  • C语言基础入门:7个经典小程序助你快速掌握编程技巧
    本文精选了7个经典的C语言小程序,旨在帮助初学者快速掌握编程基础。通过这些程序的实践,你将更深入地理解C语言的核心概念和语法结构。 ... [详细]
  • PHP 过滤器详解
    本文深入探讨了 PHP 中的过滤器机制,包括常见的 $_SERVER 变量、filter_has_var() 函数、filter_id() 函数、filter_input() 函数及其数组形式、filter_list() 函数以及 filter_var() 和其数组形式。同时,详细介绍了各种过滤器的用途和用法。 ... [详细]
  • 在现代Web应用中,当用户滚动到页面底部时,自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验,还优化了页面性能。本文将探讨如何实现这一功能,并介绍一些实际应用案例。 ... [详细]
  • 本文探讨了在使用Selenium进行自动化测试时,由于webdriver对象实例化位置不同而导致浏览器闪退的问题,并提供了详细的代码示例和解决方案。 ... [详细]
  • 本文介绍如何在 C++ 中使用链表结构存储和管理数据。通过具体示例,展示了静态链表的基本操作,包括节点的创建、链接及遍历。 ... [详细]
  • 磁盘健康检查与维护
    在计算机系统运行过程中,硬件或电源故障可能会导致文件系统出现异常。为确保数据完整性和系统稳定性,定期进行磁盘健康检查至关重要。本文将详细介绍如何使用fsck和badblocks工具来检测和修复文件系统及硬盘扇区的潜在问题。 ... [详细]
  • 本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数,并使用递推算法和大数处理技术来解决这一问题。 ... [详细]
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社区 版权所有