tao~bao的两道笔试题

1. 现在有7 Kg的米，200g和50g的砝码，问用天平最少称几次可以称出1350g的米？如何用算法实现?

 2.有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k，请给出输入为N和M,输出为鸡蛋的放法的程序，重点部分请加详细注释。

 

评论

48 楼 蛋呢823 2011-03-31  

<div class="quote_title">chriszeng87 写道</div>
<div class="quote_div">
<div class="quote_title">lyw985 写道</div>
<div class="quote_div">
<div class="quote_title">chriszeng87 写道</div>
<div class="quote_div">
<p> 2.有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意<span style="color: #ff0000;">小于</span>N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k，请给出输入为N和M,输出为鸡蛋的放法的程序，重点部分请加详细注释。</p>
<p> </p>
</div>
<p>你确定是小于，而不是小于等于？</p>
</div>
<p>原题是“不大于”</p>
</div>
<p>有必要吗？  N是肯定取得到的呀， 把所有篮子加起来就是N了，OK吧？</p>

47 楼 chinpom 2011-03-28  

<div class="quote_title">cttnbcj 写道</div>
<div class="quote_div">题意不是一样吗？ 5 个鸡蛋 3个篮子 ，且要求满足对任意小于5个的鸡蛋数k，都可以找出3个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k。<br>(x^1+x^2+..x^n)^k<br>n=5<br><br>x^k有几项，就是所求。</div>
<p><img src="/images/smiles/icon_biggrin.gif" alt=""> 介个不就是母函数吗？母函数挺有作用的</p>

46 楼 fucktianya 2011-03-28  

cttnbcj 写道

我还真听不懂了，8个球放3个篮子按 1 .3 .5 不就k=4了吗
2.3.4不就k=5了吗
当N>M时，肯定能求出任意k<M，从M个某些篮子中。

弱弱的问一下：

8个球怎么放出 1 3 5来？

45 楼 fucktianya 2011-03-28  

弱弱的问一下：

8个球怎么放出 1 3 5来？

44 楼 niuniu_cyz 2011-03-28  

不是吧 ，淘宝也考这样的题？？ 楼主工作几年了？？

43 楼 sspoo 2011-03-28  

第一题我的解法，序号表示是称的过程(=两边表示天秤的两端)
1、200砝码放天平的一端，将7000g的米分别倒入两端，直到天平平衡。则得出3600=（3400+200）
2、200砝码放入天平的一段，将3400g的米分别倒入两端，直到天平平衡。则得出1800=（1600+200）
3、保留1600mi，（200+50）砝码放入天平的一段，到米，直到平衡。则得出1600=1350+（200+50）
总计3次

42 楼 b_lee 2011-03-28  

200×4=1400
1400-50=1350

41 楼 cttnbcj 2011-03-28  

lyw985 写道

http://blog.csdn.net/huangkangying/archive/2011/03/28/6283776.aspx

发表于 @ 2011年03月28日　15:47:00 | 评论( 0 ) | 编辑| 举报| 收藏

偷笑中……

  别笑了，毕竟人家亲眼见过该题。我也是这样理解这个题意了，才得出用生成函数解。虽然我没当面见过这个题目，

40 楼 kanny87929 2011-03-28  

说实在第2题连题目都看不懂

39 楼 lyw985 2011-03-28  

http://blog.csdn.net/huangkangying/archive/2011/03/28/6283776.aspx

发表于 @ 2011年03月28日　15:47:00 | 评论( 0 ) | 编辑| 举报| 收藏

偷笑中……

38 楼 cttnbcj 2011-03-28  

zhifeidie 写道

lyw985 写道

cttnbcj 写道

有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k.

这句话歧义太多了，
1. 满足任意小于N的k数，我可以理解求随便那个k，只要小于N就行了，鸡蛋的顺序随便我怎么放，都可以，甚至每次都可以放不一样的摆法....,只要随便几个篮子等于k就行了。
2.一种序列摆下后，不能更改，这个也没写，这个条件太重要.

你觉得会有可能是1么？？你完全可以去做个投票么。。。

这个问题中的M和N之间的关系是有限制的，N大于M，并小于2的M次方，才可能有解

举一个极端的例子，如果只有两个篮子，100个鸡蛋，显然无论如何都没有可能有解。。。

怎么没解，要是按的题意就是有解  1 99 . 2 98  3 97 这样分也符合题意啊。没说可以无限次摆放，我每次选一个不就行了，反正都是小于k。
----------------------------------------------------------------------------------------
一不小心baidu一下，这位兄弟，说的情况又和LZ说的题意不一样，搜索打开几个网页，发现每个人对题目的理解都不一样。悲剧，题目的意思远远大于算法的难度。

  1 昨天参加淘宝笔试，给几道算法题整懵了，其实也不难，但好久没有碰算法，只是有思路，要让我在这么短的时间内写出程序来还是不行。
  2 这里将其中一道稍微复杂一点的算法题写下来，以此小结。
  3
  4 题目描述：
  5 将N个鸡蛋放入到M个篮子中去（N>M），保证每个篮子中至少一个鸡蛋，然后指定一个数X, 要求从篮子中找出任意个篮子，这些篮子中鸡蛋的总和加起来要等于X。请找出所有这样的情况。
  6
  7 思路：
  8 由于N个鸡蛋放入M个篮子中有很多种放法，所以这里存在多种组合的情况。解决这个是第一步。
  9 对于已经放好的篮子，又有很多种情况可以等于X。这是第二步。


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/huangkangying/archive/2011/03/28/6283776.aspx

37 楼 liuningbo 2011-03-28  

<div class="quote_title">chriszeng87 写道</div>
<div class="quote_div">
<p>1. 现在有7 Kg的米，200g和50g的砝码，问用天平最少称几次可以称出1350g的米？如何用算法实现?</p>
<p> 2.有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k，请给出输入为N和M,输出为鸡蛋的放法的程序，重点部分请加详细注释。</p>
<p> </p>
</div>
<p><br>想了下，如果砝码可以有多个，就好办了。如果不是，觉得两次就可以，分两步：第一,：200g和50g的砝码各放在天平一边，调整使其平衡，这样就是1：4的关系，</p>
<p>                                                第二,：不放砝码7000g米分别放于天平两边使平衡，这样就是1400g和5600g，再称一次就是1400g里减去50g就是1350g了</p>
<p> </p>
<p>个人想法，现在去看看第二题</p>

36 楼 zhifeidie 2011-03-28  

lyw985 写道

cttnbcj 写道

有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k.

这句话歧义太多了，
1. 满足任意小于N的k数，我可以理解求随便那个k，只要小于N就行了，鸡蛋的顺序随便我怎么放，都可以，甚至每次都可以放不一样的摆法....,只要随便几个篮子等于k就行了。
2.一种序列摆下后，不能更改，这个也没写，这个条件太重要.

你觉得会有可能是1么？？你完全可以去做个投票么。。。

这个问题中的M和N之间的关系是有限制的，N大于M，并小于2的M次方，才可能有解

举一个极端的例子，如果只有两个篮子，100个鸡蛋，显然无论如何都没有可能有解。。。

35 楼 chriszeng87 2011-03-28  

風一樣的男子 写道

第一题是 4 次?

是3次的，见三楼

34 楼 風一樣的男子 2011-03-28  

第一题是 4 次?

33 楼 lyw985 2011-03-28  

cttnbcj 写道

有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k.

这句话歧义太多了，
1. 满足任意小于N的k数，我可以理解求随便那个k，只要小于N就行了，鸡蛋的顺序随便我怎么放，都可以，甚至每次都可以放不一样的摆法....,只要随便几个篮子等于k就行了。
2.一种序列摆下后，不能更改，这个也没写，这个条件太重要.

你觉得会有可能是1么？？你完全可以去做个投票么。。。

32 楼 lyw985 2011-03-28  

cttnbcj 写道

这个题意真的是不想说了。。。。
有N个鸡蛋，M个篮子，但只能摆放一种序列，必须保证每个篮子至少要有一个鸡蛋，且要求满足对任意(应该是每个)小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k 
这个才是楼主的意思吧

是这个意思没错，那我给2个参数没有错哦

31 楼 chriszeng87 2011-03-28  

cttnbcj 写道

这个题意真的是不想说了。。。。
有N个鸡蛋，M个篮子，但只能摆放一种序列，必须保证每个篮子至少要有一个鸡蛋，且要求满足对任意(应该是每个)小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k 
这个才是楼主的意思吧

嗯，是这个意思的

引用

2.一种序列摆下后，不能更改

这个我没弄明白，反正题目最后是要求给出对于给定的N和M，能打印出所有放法的算法
做题的时候，我真是完全没看懂题啊

30 楼 cttnbcj 2011-03-28  

有N个鸡蛋，M个篮子，每个篮子至少要有一个鸡蛋，且要求满足对任意小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k.

这句话歧义太多了，
1. 满足任意小于N的k数，我可以理解求随便那个k，只要小于N就行了，鸡蛋的顺序随便我怎么放，都可以，甚至每次都可以放不一样的摆法....,只要随便几个篮子等于k就行了。
2.一种序列摆下后，不能更改，这个也没写，这个条件太重要.

29 楼 cttnbcj 2011-03-28  

这个题意真的是不想说了。。。。
有N个鸡蛋，M个篮子，但只能摆放一种序列，必须保证每个篮子至少要有一个鸡蛋，且要求满足对任意(应该是每个)小于N个的鸡蛋数k，都可以找出M个篮子中的某几个，使得这几个篮子中的鸡蛋的个数之和为k 
这个才是楼主的意思吧