none
编程算法问题 RRS feed

  • 问题

  • 箱子问题:(c++)

    有10箱产品,每箱有1000件,正品每件100克,其中几箱是次品,每件次品比正品轻10克,问能否只称一次,就找出哪箱是次品(用C++编写代码)

    2011年10月7日 0:42

答案

  • 第1箱取1个,第2箱取2个,第3箱取4个,第4箱取8个,……,第10箱取512个,一共1023个,称一下缺了几个10克,如缺了500克,即50个,50的二进制表示是110010,从右边开始算第1批产品,若为0则正常,若为1则为次品.故是第2批,第5批,第6批为次品.因为50=2+2^4+2^5,仅有这种表示.
    Visual C++ enthusiast, like network programming and driver development. At present is being engaged in the WinCE/Windows Mobile platform embedded development.
    • 已标记为答案 积极 2011年10月8日 8:07
    2011年10月8日 1:43
    版主

全部回复

  • 先不说编程的问题

    但就问题本身

    10箱产品称一次怎么可能确定哪箱是正品

    2011年10月7日 2:28
  • 你就没弄明白,

    第一步

    把他们分别标记为1,2,3,4,5,6,7,8,9,10,对应的箱数取2^(n-1)件,第一箱取1件,第二箱取两件,以此类推,然后把取出来的去称量,对比全部为正品是时的差,算出多少件不合格。(已作出)

    第二步

    组合法求数组两项的和,然后再加上原有的元素,成为下一次的求和结果,这样就把任意两项,任意三项的和求出来,再用递归的方法,直到n个数全部相加,就是求n个数中的任意m个数的和(已作出)。

    第三步

    记录(未作出)

    第三步就是做不出来,就差这一步了


    • 已编辑 积极 2011年10月7日 3:06
    2011年10月7日 3:05
  • 第1箱取1个,第2箱取2个,第3箱取4个,第4箱取8个,……,第10箱取512个,一共1023个,称一下缺了几个10克,如缺了500克,即50个,50的二进制表示是110010,从右边开始算第1批产品,若为0则正常,若为1则为次品.故是第2批,第5批,第6批为次品.因为50=2+2^4+2^5,仅有这种表示.
    Visual C++ enthusiast, like network programming and driver development. At present is being engaged in the WinCE/Windows Mobile platform embedded development.
    • 已标记为答案 积极 2011年10月8日 8:07
    2011年10月8日 1:43
    版主
  • 多谢,做出来了
    2011年10月8日 8:07