当前位置:网站首页>Classic interview question [gem pirate]
Classic interview question [gem pirate]
2022-07-06 02:43:00 【Bald cat light King】
Classic interview questions 【 Gem pirates 】
Interview question bank 【 Mice drink water 】List of articles
One 、 Common topics
Five pirates grabbed 100 A gem , Each one is the same size and priceless . They decided to divide up : Draw lots to decide your number (1、2、3、4、5)
First , from 1 Put forward the distribution plan , Then we vote , When and only if more than half of the people agree , Distribute according to his plan , Otherwise they will be thrown into the sea to feed sharks
If 1 After she died , Again by 2 Put forward the distribution plan , And then the rest 4 People vote , When and only if more than half of the people agree , Distribute according to his plan , Otherwise, they will be thrown into the sea to feed sharks , And so on .
Conditions : Every pirate is a very smart person , Can make a rational judgment , To make a choice .
problem : What kind of distribution scheme did the first pirate propose to maximize his own profits ?
Two 、 Detailed ideas
1. Change your mind
From the title, we get that the known condition is :
- Every pirate is a very smart person , Can make a rational judgment .
- according to 1、2、3、4、5 Put forward the allocation scheme in sequence
- Not more than half of the people agree , Will be thrown into the sea to feed sharks
2. Detailed ideas
Because every pirate can make the most rational judgment , Then we can start from the fifth to push back what situation they can get the most gemstones , What is their most rational judgment ?
When 1、2、3、4 When feeding all sharks ,5 Number assigned by yourself :
only 5 No. one
here 5 The number must be 100 A gem
0 0 0 0 100
When 1、2、3 When feeding all sharks ,4 Number assignment :
because 5 After No. 1 objection ,4 No more than half will agree , According to known condition three , that 4 No. 1 must be fed to sharks .
here 5 No. 1 is still necessary 100 A gem
0 0 0 0 100
When 1、2 When feeding all sharks ,3 Number assignment :
As we know above 4 The number is 3 No. 1 will definitely be fed to sharks after death , that 3 Any allocation scheme proposed by , According to condition one , Make the most rational choice , that 4 No. must agree 3 Plan No . here 3 No. holds two tickets ,3 + 4 : 5 = 2 :1 The condition of must hold ,3 Number will be assigned to yourself 100 A gem , At this time, more than half of the two votes , Conditions established , here 3 The number must be 100 A gem .
0 0 100 0 0
When 1 When feeding sharks on the th ,2 Number assignment :
As we know above 3 The number is 2 The plan after death is 0 0 100 0 0, So at this time 4 personal 2 The number needs to be pulled to 2 ticket To ensure the establishment of their own programs . however 3 The expectation of No. 1 is 100 that 2 No. must not be able to win 3 Number , from 3 We can know the distribution scheme of number 4 and 5 Of Expectations are 0 , that 2 Number assigned to 4、5 various 1 A gem can canvass , here 3 The conditions for the implementation of the distribution plan are established , therefore 2 No. button to pull 2 Gemstone , here 2 No 98 A gem .
0 98 0 1 1
Return to the topic , When 1 Number assignment :
As we know above 2 The number is 1 The plan after death is 0 98 0 1 1, So at this time 5 personal 1 The number also needs to be pulled 2 ticket To ensure the establishment of their own programs . however 3 The expectation of No. 1 is 98 that 1 No 2 No. will need to pay 99 Gemstone , By condition one The most rational choice , So by the 2 We can know the distribution scheme of number 3 Of Expectations are 0, and 4 and 5 Of Expectations are 1 , that 1 Number is only assigned to 3 Number 1 A gem can canvass , among 4 and 5 Any one of them 2 Gemstone , here 3 The conditions for the implementation of the distribution plan are established , therefore 1 No. button to pull 3 Gemstone , here 1 No 97 A gem .
97 0 1 2 0 or 97 0 1 0 2
At this point, we can conclude that the final plan is :
97 0 1 2 0 or 97 0 1 0 2 Is the solution that meets the most rational conditions
summary
Gem pirate is a classic algorithm interview question , Maybe from 1 On the th, I began to think about the perfect plan, which is more convoluted , But sort out the ideas from the end , That is from 5 No. thinking , This will make you suddenly realize , The algorithm examines only one idea , We should learn to think in reverse .
I hope this blog will be beneficial to you . I am the light king , I represent myself. .边栏推荐
- 事故指标统计
- 2022.02.13
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 18
- GifCam v7.0 极简GIF动画录制工具中文单文件版
- 球面透镜与柱面透镜
- Shell script updates stored procedure to database
- Introduction to robotframework (I) brief introduction and use
- CobaltStrike-4.4-K8修改版安装使用教程
- 淘宝焦点图布局实战
- Microservice registration and discovery
猜你喜欢
A copy can also produce flowers
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 24
[postgraduate entrance examination English] prepare for 2023, learn list5 words
Force buckle 146 LRU cache
Advanced technology management - what is the physical, mental and mental strength of managers
【若依(ruoyi)】设置主题样式
Qt发布exe软件及修改exe应用程序图标
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 17
[matlab] access of variables and files
Zero foundation self-study STM32 - Review 2 - encapsulating GPIO registers with structures
随机推荐
Differences and usage scenarios between TCP and UDP
Introduction to robotframework (I) brief introduction and use
如何精准识别主数据?
MySQL winter vacation self-study 2022 11 (7)
Accident index statistics
Six stone management: why should leaders ignore product quality
The third level of C language punch in
2020.02.11
数据准备工作
"Hands on learning in depth" Chapter 2 - preparatory knowledge_ 2.3 linear algebra_ Learning thinking and exercise answers
全国大学生信息安全赛创新实践赛初赛---misc(永恒的夜)
High number_ Vector algebra_ Unit vector_ Angle between vector and coordinate axis
C语言sizeof和strlen的区别
微服务注册与发现
Introduction to robotframework (II) app startup of appui automation
Pat 1084 broken keyboard (20 points) string find
Is there a case where sqlcdc monitors multiple tables and then associates them to sink to another table? All operations in MySQL
Initial understanding of pointer variables
SQL table name is passed as a parameter
【MySQL 15】Could not increase number of max_ open_ files to more than 10000 (request: 65535)