搜索
【14】有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的电影院开始卖票时1分钱也没有。问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱注：1美元=100美分拥有1美元的人，拥有的是纸币，没法破成2个50美分本题可用递归算法，但时间复杂度为2的n次方，也可以用动态规划法，时间复杂度为n的平方，实现起来相对要简单得多，但最方便的就是直接运用公式：排队的种数=(2n)!/[n!(n+1)!]。如果不考虑电影院能否找钱，那么一共有(2n)!/[n!n!]种排队方法（即从2n个人中取出n个人的组合数），对于每一种排队方法，如果他会导致电影院无法找钱，则称为不合格的，这种的排队方法有(2n)!/[(n-1)!(n+1)!]（从2n个人中取出n-1个人的组合数）种，所以合格的排队种数就是(2n)!/[n!n!]-(2n)!/[(n-1)!(n+1)!]=(2n)!/[n!(n+1)!]。至于为什么不合格数是(2n)!/[(n-1)!(n+1)!]，说起来太复杂，这里就不讲了。【15】一个人花8块钱买了一只鸡，9块钱卖掉了，然后他觉得不划算，花10块钱又买回来了，11块卖给另外一个人。问他赚了多少?2元【16】有一种体育竞赛共含M个项目，有运动员A，B，C参加，在每一项目中，第一,第二,第三名分别的X，Y，Z分，其中X,Y,Z为正整数且XYZ。最后A得22分，B与C均得9分，B在百米赛中取得第一。求M的值，并问在跳高中谁得第二名。因为ABC三人得分共40分,三名得分都为正整数且不等,所以前三名得分最少为6分,40=5*8=4*10=2*20=1*20,不难得出项目数只能是5.即M=5.A得分为22分,共5项,所以每项第一名得分只能是5,故A应得4个一名一个二名.22=5*4+2,第二名得1分,又B百米得第一,所以A只能得这个第二.B的5项共9分,其中百米第一5分,其它4项全是1分,9=5+1=1+1+1.即B除百米第一外全是第三,跳高第二必定是C所得.【17】前提：1有五栋五种颜色的房子2每一位房子的主人国籍都不同3这五个人每人只喝一种饮料，只抽一种牌子的香烟，只养一种宠物4没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料提示：１英国人住在红房子里２瑞典人养了一条狗３丹麦人喝茶４绿房子在白房子左边５绿房子主人喝咖啡６抽ＰＡＬＬＭＡＬＬ烟的人养了一只鸟７黄房子主人抽ＤＵＮＨＩＬＬ烟８住在中间那间房子的人喝牛奶９挪威人住第一间房子１０抽混合烟的人住在养猫人的旁边１１养马人住在抽ＤＵＮＨＩＬＬ烟的人旁边１２抽ＢＬＵＥＭＡＳＴＥＲ烟的人喝啤酒１３德国人抽ＰＲＩＮＣＥ烟１４挪威人住在蓝房子旁边１５抽混合烟的人的邻居喝矿泉水问题是：谁养鱼？？？第一间是黄房子，挪威人住，喝矿泉水，抽DUNHILL香烟，养猫；!f/[%a:\6L!J.Q9x第二间是蓝房子，丹麦人住，喝茶，抽混合烟，养马；+o8_0S)L8i'E'u第三间是红房子，英国人住，喝牛奶，抽PALLMALL烟，养鸟；/N9o/n2M#Uc第四间是绿房子，德国人住，喝咖啡，抽PRINCE烟，养猫、马、鸟、狗以外的宠物；7P5l)G,G,|;C,{7V第五间是白房子，瑞典人住，喝啤酒，抽BLUEMASTER烟，养狗。【18】5个人来自不同地方，住不同房子，养不同动物，吸不同牌子香烟，喝不同饮料，喜欢不同食物。根据以下线索确定谁是养猫的人。1．红房子在蓝房子的右边，白房子的左边（不一定紧邻）2．黄房子的主人来自香港，而且他的房子不在最左边。3．爱吃比萨的人住在爱喝矿泉水的人的隔壁。4．来自北京的人爱喝茅台，住在来自上海的人的隔壁。5．吸希尔顿香烟的人住在养马人的右边隔壁。6．爱喝啤酒的人也爱吃鸡。7．绿房子的人养狗。8．爱吃面条的人住在养蛇人的隔壁。9．来自天津的人的邻居（紧邻）一个爱吃牛肉，另一个来自成都。10．养鱼的人住在最右边的房子里。11．吸万宝路香烟的人住在吸希尔顿香烟的人和吸“555”香烟的人的中间（紧邻）12．红房子的人爱喝茶。13．爱喝葡萄酒的人住在爱吃豆腐的人的右边隔壁。14．吸红塔山香烟的人既不住在吸健牌香烟的人的隔壁，也不与来自上海的人相邻。15．来自上海的人住在左数第二间房子里。16．爱喝矿泉水的人住在最中间的房子里。17．爱吃面条的人也爱喝葡萄酒。18．吸“555”香烟的人比吸希尔顿香烟的人住的靠右第一间是兰房子，住北京人，养马，抽健牌香烟，喝茅台，吃豆腐；2G7x%z0v;C第二间是绿房子，住上海人，养狗，抽希尔顿，喝葡萄酒，吃面条；%C2k4o8tp6L*x第三间是黄房子，住香港人，养蛇，抽万宝路，喝矿泉水，吃牛肉；&NS%x#o3a;g第四间是红房子，住天津人，抽555，喝茶，吃比萨；7\5s.J#d,Q/N%N'O#]第五间是白房子，住成都人，养鱼，抽红塔山，喝啤酒，吃鸡。【19】斗地主附残局地主手中牌2、K、Q、J、10、9、8、8、6、6、5、5、3、3、3、3、7、7、7、7长工甲手中牌大王、小王、2、A、K、Q、J、10、Q、J、10、9、8、5、5、4、4长工乙手中牌2、2、A、A、A、K、K、Q、J、10、9、9、8、6、6、4、4三家都是明手，互知底牌。要求是：在三家都不打错牌的情况下，地主必须要么输要么赢。问：哪方会赢？无解地主怎么出都会输【20】一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？先拿下第一楼的钻石，然后在每一楼把手中的钻石与那一楼的钻石相比较，如果那一楼的钻石比手中的钻石大的话那就把手中的钻石换成那一层的钻石。【21】U2合唱团在17分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同行则以较慢者的速度为准。Bono需花1分钟过桥，Edge需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。他们要如何在17分钟内过桥呢？2＋1先过2然后1回来送手电筒15＋10再过102回来送手电筒22＋1过去2总共2＋1＋10＋2＋2＝17分钟【22】一个家庭有两个小孩，其中有一个是女孩，问另一个也是女孩的概率（假定生男生女的概率一样）1/3样本空间为（男男）（女女）（男女）（女男）A＝（已知其中一个是女孩）＝）（女女）（男女）（女男）B＝（另一个也是女孩）＝（女女）于是P（B／A）＝P（AB）／P（A）＝（1／4）／（3／4）＝1／3【23】为什么下水道的盖子是圆的？不会掉下去【24】有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐分成50、90克各一份？140-70＋7070-35＋3535＋70＝105105-50＋7＋55＋255＋35＝90【25】芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片好芯片，说明你所用的比较次数上限．其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．坏芯片和其它芯片比较时，会随机的给出好或是坏。把第一块芯片与其它逐一对比，看看其它芯片对第一块芯片给出的是好是坏，如果给出是好的过半，那么说明这是好芯片，完毕。如果给出的是坏的过半，说明第一块芯片是坏的，那么就要在那些在给出第一块芯片是坏的芯片中，重复上述步骤，直到找到好的芯片为止。【26】12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢？（注意此题并未说明那个球的重量是轻是重）12个时可以找出那个是重还是轻，13个时只能找出是哪个球，轻重不知。把球编为①②③④⑤⑥⑦⑧⑨⑩⑾⑿。（13个时编号为⒀）第一次称：先把①②③④与⑤⑥⑦⑧放天平两边，㈠如相等，说明特别球在剩下4个球中。把①⑨与⑩⑾作第二次称量，⒈如相等，说明⑿特别，把①与⑿作第三次称量即可判断是⑿是重还是轻⒉如①⑨＜⑩⑾说明要么是⑩⑾中有一个重的，要么⑨是轻的。把⑩与⑾作第三次称量，如相等说明⑨轻，不等可找出谁是重球。⒊如①⑨＞⑩⑾说明要么是⑩⑾中有一个轻的，要么⑨是重的。把⑩与⑾作第三次称量，如相等说明⑨重，不等可找出谁是轻球。㈡如左边＜右边，说明左边有轻的或右边有重的把①②⑤与③④⑥做第二次称量⒈如相等，说明⑦⑧中有一个重，把①与⑦作第三次称量即可判断是⑦与⑧中谁是重球⒉如①②⑤＜③④⑥说明要么是①②中有一个轻的，要么⑥是重的。把①与②作第三次称量，如相等说明⑥重，不等可找出谁是轻球。⒊如①②⑤＞③④⑥说明要么是⑤是重的，要么③④中有一个是轻的。把③与④作第三次称量，如相等说明⑤重，不等可找出谁是轻球。㈢如左边＞右边，参照㈡相反进行。当13个球时，第㈠步以后如下进行。把①⑨与⑩⑾作第二次称量，⒈如相等，说明⑿⒀特别，把①与⑿作第三次称量即可判断是⑿还是⒀特别，但判断不了轻重了。⒉不等的情况参见第㈠步的⒉⒊【27】100个人回答五道试题，有81人答对第一题，91人答对第二题，85人答对第三题，79人答对第四题，74人答对第五题，答对三道题或三道题以上的人算及格，那么，在这100人中，至少有（）人及格。首先求解原题。每道题的答错人数为（次序不重要）：26，21，19，15，9第3分布层：答错3道题的最多人数为：（26+21+19+15+9）/3=30第2分布层：答错2道题的最多人数为：（21+19+15+9）/2=32第1分布层：答错1道题的最多人数为：（19+15+9）/1=43Max_3=Min(30,32,43)=30。因此答案为：100-30=70。其实，因为26小于30，所以在求出第一分布层后，就可以判断答案为70了。要让及格的人数最少，就要做到两点：1.不及格的人答对的题目尽量多，这样就减少了及格的人需要答对的题目的数量，也就只需要更少的及格的人2.每个及格的人答对的题目数尽量多，这样也能减少及格的人数由1得每个人都至少做对两道题目由2得要把剩余的210道题目分给其中的70人：210/3=70，让这70人全部题目都做对，而其它30人只做对了两道题也很容易给出一个具体的实现方案：让70人答对全部五道题，11人仅答对第一、二道题，10人仅答对第二、三道题，5人答对第三、四道题，4人仅答对第四、五道题显然稍有变动都会使及格的人数上升。所以最少及格人数就是70人！【28】陈奕迅有首歌叫十年吕珊有首歌叫3650夜那现在问,十年可能有多少天?十年可能包含2-3个闰年，3652或3653天。1900年这个闰年就是28天，1898~1907这10年就是3651天，闰年如果是整百的倍数，如1800，1900，那么这个数必须是400的倍数才有29天，比如1900年2月有28天，2000年2月有29天。【29】1，11，21，1211，111221，下一个数是什么？下行是对上一行的解释所以新的应该是3个12个21个1：312211【30】烧一根不均匀的绳要用一个小时，如何用它来判断半个小时？烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子,问如何用烧绳的方法来计时一个小时十五分钟呢?（微软的笔试题）一，一根绳子从两头烧，烧完就是半个小时。二，一根要一头烧，一根从两头烧，两头烧完的时候（30分），将剩下的一根另一端点着，烧尽就是45分钟。再从两头点燃第三根，烧尽就是1时15分。【31】共有三类药，分别重1g,2g,3g，放到若干个瓶子中，现在能确定每个瓶子中只有其中一种药，且每瓶中的药片足够多，能只称一次就知道各个瓶子中都是盛的哪类药吗？如果有4类药呢？5类呢？N类呢(N可数)？如果是共有m个瓶子盛着n类药呢(m，n为正整数，药的质量各不相同但各种药的质量已知)？你能只称一次就知道每瓶的药是什么吗？注：当然是有代价的，称过的药我们就不用了第一