最新更新
 
您现在的位置:主页 > 新闻中心 >  
巧断金链
发布时间:2021-06-15 12:55  来源:未知  点击量:

  来自阿肯色州的年轻妻子格洛丽亚,正在加利福尼亚旅行。她想在酒店租一个房间,租赁期限为一周。店员此时情绪低落。职员:“房费是每天20元,需要支付现金。格洛里亚:“对不起,先生,我没有带现金。但是我有一条金链,总共7节,每节价值超过20元。职员:“好吧,给我金链。”“格洛里亚:“我现在不能给你。我要请珠宝商剪掉金链,我每天会给你一节我等到周末才有了现金,然后才兑换金链。店员终于同意了,但是,格洛里亚必须决定如何打破金链。格洛里亚:“我应该三思而后行,因为珠宝商根据他削减的打结数量收取价格,后来又重新连接。格洛丽亚想了一会儿。意识到她不必删节,因为她可以交换进出的金链段,用这种方式支付房间。当她计算出珠宝商需要削减的结数时,她几乎没有信心。考虑一下您需要削减多少个结?

  只需要切一段。此部分应该是从一端算起的第三部分。将金链分成1个部分,2节在4个部分和3个部分之后, 可以每天以换入和换出的方式向业务员支付房费的一部分。

  啊哈!理解以下两点可以解决问题。首先,至少需要1个部分,2 sections,4 sections like three sections (that is, some sections whose sections are in double series),这样, a section can be formed in various combinations,2 sections,3 sections,4 sections,5 knots,6 knots and 7 knots.We already know in the drug chaos problem,This is the power series that is the basis of the binary notation.

  second,You only need to cut one section to divide the gold chain into three sections that meet the requirements.about this issue,If the length of the gold chain is increased,Then you can think of some new problems.E.g,Suppose Gloria has a gold chain with 63 knots,She wanted to cut the golden chain,Pay the room rate for 63 days in the same way as above (the price remains unchanged).To achieve this goal, only three sections need to be cut.Have you figured it out yet?Can you design a general problem-solving program according to the different lengths of the gold chain,Is the number of sections required to be divided at least?

  There is an interesting disguised problem: if the n sections of the closed loop that are connected end to end,例如, Gloria has a gold necklace,It is made up of 79 sections connected together,If the room rate is one session per day,May I ask at least how many sections need to be divided to pay for the 79-day room rate?

  All these problems are closely related to binary notation.例如, how to divide Gloria's 63-section gold necklace?Just convert 63 into a binary representation: equal to "111111", that is, 63 = 1 + 2+4+8+16+32. As long as the two sections starting from the second section are separated,I will cut off the eighth quarter from the eighth,And the 32 verses starting from verse 32 can be cut off,In this way, from 1,2,3。4.5.6,The number of all knots up to 63.normally,If there are n gold chains,n is a number of type 2k-1,Convert n into a binary representation,Then divide all the powers of 2 represented by the positions of "1" at intervals to achieve the goal.But for any other type of numbers,But it doesn't work,For example, for Gloria's 79-section gold necklace,79 is expressed in binary notation as "1001111".That is, 79=1+2+4+8+0+0+64,In this way, it can be expressed from 1 to 15,But it can't be expressed from 16 to 63.I made this question here,I also became confused for a while,But this problem is not very complicated after all,Let's also learn from Minkowski's zeal to solve the four-color problem in class.Fumble to solve it.Let's do this: Don't you require the least number of sessions?Suppose n=a+b, where a is the number of the largest section that has been found,b is the solved gold chain problem that is smaller than n,Since b has been resolved,Therefore, the split of b can be expressed from 1,2,3.b-1,b的所有金连接数,不能代表更大的数字。For example, b + 1,所以必须参加如果n是奇数设a = b + 1所以n = 2b + 1所以b =(n-1)/ 2,a =(n + 1)/ 2,In this way, 找到最大部分的部分编号a,然后继续将上述方法应用于b =(n-1)/ 2,这个问题可以解决。如果n是偶数设a = b这样虽然a本身不能表示出b + 1,但是可以从b的突破中拿出一个1来(这个1是必须存在的,因为要表示从1,2,3.b-1,b的所有数)与a组成a + 1也就是b + 1。所以n = a + b = 2a = 2b,a = b = n / 2。这样也找到了n为偶数时最大的分段金链的节数。对于b继续如上的过程,就可以找到全部应该对准的金链节数,我算出了从1到15的所有细分如下:

  1 = 1

  2 = 1 + 1

  3=1+2

  4 = 1 + 1 + 2

  5 = 1 + 1 + 3

  6 = 1 + 2 + 3

  7 = 1 + 2 + 4

  8 = 1 + 1 + 2 + 4

  9 = 1 + 1 + 2 + 5

  10 = 1 + 1 + 3 + 5

  11 = 1 + 1 + 3 + 6

  12 = 1 + 2 + 3 + 6

  13 = 1 + 2 + 3 + 7

  14 = 1 + 2 + 4 + 7

  15 = 1 + 2 + 4 + 8

  对于上面的格罗丽亚太太的79节金项链,79 + 1 = 80,80/2 = 40,所以最大的两端就是40节,79-40 = 39,39 + 1 = 40,40/2 = 20,所以第二大的海滨就是20节,39-20 = 19,19 + 1 = 20,20/2 = 10,第三大的两端是10节,19-10 = 9,9 + 1 = 10,10/2 = 5,又找到了一段是5,9-5 = 4。4的表示法如上已经列出来了:4 = 1 + 1 + 2。最后得到79节的金项链的分割法:1,1,2,5,10,20,40过去我也碰到过一道类似的题,是23节金项链,也能够很容易地解决:23 + 1 = 24,24/2 = 12; 23-12 = 11,11 = 1 + 1 + 3 + 6;所以23的分割法为:1,1,3,6.12明显,对于2k-1类型的数,用这里的方法与用二进制记数法得出的结果是一致的。

  从上面所列出的细分法可以抛光,如果2k =

  可以用数学归纳法很容易地证明这是正确的。那么还有没有比这这的的分割法呢?可以证明没有了。从我们的分析方法中可以研磨,这是一个构造性的推理过程,假如还有比这十年的分割法,那么相当于在表达式n = a0 + a1 + a2 +。+ ak。中进行了某些组合,例如将a1 + a2合并成新的a1,然后,某些原始组合将无法表达。例如a0 + a2,没有办法将它们结合起来。当然,数字的分割不是唯一的,前面的23节金链也可以分为1个2,3,6,11。你可以试试,这种分割方法仍然可以满足要求。在之前的分析中, (n-1)/ 2也可以保留为最大结数,但是以这种方式划分的部分数量不一定是最少的。For example, 像这样分15将得到:1,1,2,4,7。虽然可以满足付款要求,但这不是最佳解决方案。最后, 总结一下,制定先前的算法过程可以得到:

  of course,It is easier to compile a computer program or to use a recursive program.These formulas are listed here for preservation.

上一篇:跑步时背单词的同时上体育课
下一篇:《琵琶行》案例分析
 
 
Copyright (c) 2015 www.youmooyouyoung.com  All Right Reserved.   版权所有:北京新影学院
   网备51080202000207 网站地图