两道道智力逻辑题,一直没弄明白,求详细解答。

断桥是否下过雪 发布于 2014/03/02 23:48
阅读 664
收藏 2

first:30枚面值不全相同的硬币摆成一排,甲、乙两个人轮流选择这排硬币的其中一端,并取走最外边的那枚硬币。如果你先取硬币,能保证得到的钱不会比对手少吗


second:一个环形轨道上有n个加油站,所有加油站的油量总和正好够车跑一圈。证明,总能找到其中一个加油站,使得初始时油箱为空的汽车从这里出发,能够顺利环行一圈回到起点

加载中
2
3_14159265359
3_14159265359

第二题其实应该是这么个情况:

汽车加油 a+b+c+d+e+f = N;

汽车耗油A+B+C+D+E+F = N;

(a-A)+(b-B)+(c-C)+(d-D)+(e-E)+(f-F) = 0

要保证上式中每个+前面的式子算出来是正数,不然就表示油不够用了。

我们可以遍历计算所有加号前面的式子的结果R;

R1 = (a-A)

R2 = (a-A) + (b-B)

R3 = (a-A) + (b-B) + (c-C)

.......

如果R1 ~ Rn都是正数,那现在就是满足要求的,不用调整。

否则找出R1 ~ Rn中最小的那个负数,比如R3,然后把这个式子移到后面去

变成(d-D)+(e-E)+(f-F)+(a-A)+(b-B)+(c-C),那现在就能保证能跑完了。

从d跑到f绝对不可能出现负数,因为R3是最小负数。

f之后也不可能出现负数,因为从f出发的时候,油箱里的油还有|R3|。

当然,你得有一个那么大的油箱~~~~

1
3_14159265359
3_14159265359
第一题,我觉得你先把所有奇数硬币和和偶数硬币和加起来算一下。如果奇数大就取第一个,偶数大取最后一个。我们对硬币编号,如果你开始取奇数,剩下两端都是偶数,别人只能取偶数,两端变成一奇一偶,你再取奇数...,你能保证你把奇数编号硬币取完。同理也能保证偶数,如果开始取30号硬币的话。抱歉没有从0开始计数。
雷男
雷男
回复 @3_14159265359 : 哦,你说编号为奇数啊。我没仔细看,我以为和为奇数呢
3_14159265359
3_14159265359
回复 @他乡之客 : 什么情况下会出现都是奇数的情况,你先取奇数1,两端是2或者30,都是偶数。无论他取2还是30,必然剩下一奇一偶,你取其中的奇数,他取得时候又两端都是偶数。如此往复,你取全部奇数,他取全部偶数。
雷男
雷男
如果都是奇数呢?
在下赵日天
在下赵日天
这个说的非常正确
0
leo108
leo108
第一题是我想简单了么……一直取两头中最大的那个就行了啊
3_14159265359
3_14159265359
比如有四颗硬币1 1 3 2。如果开始取2,别人取3,肯定会输,开始取1却能赢
保护单身狗协会理事长_退休
保护单身狗协会理事长_退休
感觉是贪心算法
0
dukerr
dukerr
第二个用反证法很直观嘛。如果所有加油站的油都不能跑到下一个加油站,那么显然不能满足前提条件。所以必然至少存在一个加油站,可以至少跑到下一个。之后可以把这两个加油站看成是一个,变成同样的前提,n-1个加油站,依此类推最后变成两个加油站。
MKZ1991
MKZ1991
回复 @con : 对的 加油站之间是有方向的
con
con
这个证明方式必须假定汽车能在任意站之间瞬间转移。 n和n-1之间是有依赖:如果n的时候找到了某个站,n-1时汽车就不能从任意站出发了,只能从n条件中的终点站出发
0
con
con

第一题的答案是不能找到这种方式。

1、首先要假定,甲乙两人都会努力使自己得到的钱最多。


2、一定存在一个算法,能确保在剩余的奇数个硬币中,使自己取到的钱最多。这个算法就是永远取两端中较大的一个。 注:不是题目中的保证比对手钱多的算法,这个算法只能保证自己尽可能的多拿,但不能保证比对手多。


3、为了使自己的钱最多,后取的人必定选择2中的算法,在29个硬币中取到15个硬币,甲得到剩余的14个硬币,假设乙15个硬币钱数 - 甲14个硬币钱数 = M


4、因为不能确定30个硬币的面值和排列,无论从哪端开始取,甲都不能保证取到的第一枚硬币面值大于M


5、反例:1,2,3,4……14,15,15,14……4,3,2,1 ,这种排列方式,甲最多只能拿到一半的钱,与乙相等。

con
con
回复 @·zhi : 啊,sorry,估计是我瞧错题了 =.=
断桥是否下过雪
断桥是否下过雪
回复 @con : 我没改过啊,做晚编辑的时候添加了第二题而已,你的回答很精彩啊。。。。
con
con
擦,楼主不厚道把题改了,刚刚不是保证比对手多么
0
雷男
雷男

第二题用数学归纳法;


0
修改登录密码
修改登录密码

第二题可以用贪心法求解

假设每个加油站的油量为ai,  到下一站的距离为di

先证明必然存在一个加油站  ai满足   ai>di, 且 ai+a(i+1)>=di+d(i+1)

(反证如果不存在这样的加油站的话,可以推出 ai之和< di之和  )

然后找到这样的 ai,  把 ai  a(i+1)合并为一个站 M1,

然后依次类推 最后只剩下两个站  M(n-1)和 ax

然后M(n-1)的合并顺序反推回去就是所要的路线 

返回顶部
顶部