山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

面试提一题,现在还不会!!!!!!!!!!

楼主EStarColors（魔化金身）2005-04-22 11:51:27 在 C/C++ / C语言提问

有1000个小球放入10个容器内,随意说出一个数字,要使得挑出几个容器中的小球数目加起来就等于这个数字,问改怎么放改小球

问题点数：50、回复次数：54Top

1 楼SaiRose（Learning......）回复于 2005-04-22 12:00:24 得分 2

２的幂
１　２　４　８　１６　３２　６４　１２８　２５６
最后一个为１０００减去前面９个的和了Top

2 楼SaiRose（Learning......）回复于 2005-04-22 12:02:26 得分 0

４８９Top

3 楼EStarColors（魔化金身）回复于 2005-04-22 12:03:30 得分 0

为什么呢~~Top

4 楼EStarColors（魔化金身）回复于 2005-04-22 12:07:22 得分 0

能写出算法嘛??Top

5 楼wodeyouxian（人生如梦）回复于 2005-04-22 12:14:37 得分 0

学习

Top

6 楼zhang_jiang（Solar）回复于 2005-04-22 12:14:49 得分 2

任意一个数的2进制表达式: xxxxxxxxx 其中x: 0,1
1 2 4 8 16
==>
00001 00010 00100 01000
相当与基底.

对任意一个数X, 如为00101(5), 就是相当于选中两个基底00001和00100.Top

7 楼EStarColors（魔化金身）回复于 2005-04-22 12:25:35 得分 0

学习,学习,几位都很厉害啊Top

8 楼qhfu（改个名字）回复于 2005-04-22 12:42:32 得分 2

1 ，2 ，4，8，16，32，64，128，489Top

9 楼qfeng_zhao（鱼儿鱼儿满天飞）回复于 2005-04-22 12:48:18 得分 1

studying!Top

10 楼mitchy（mitchy chien）回复于 2005-04-22 12:52:46 得分 1

Good,值得学习..Top

11 楼zfeidiyard（菲迪亚特）回复于 2005-04-22 13:10:24 得分 1

呵呵
1 ，2 ，4，8，16，32，64，128，256，489
太强了，又学了一招Top

12 楼vcmute（BCare4 H1Rest Good9!）回复于 2005-04-22 13:12:09 得分 1

还有十几种Top

13 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-04-22 13:12:24 得分 1

强,pf,记下了Top

14 楼vscn（vscn）回复于 2005-04-22 14:15:22 得分 1

markTop

15 楼jingyueid（干宁）回复于 2005-04-22 14:32:54 得分 1

2的幂，知道计算机里面是2进制的吧？
10个2可以表示到2的10次方，好象并不复杂理解吧？

Top

16 楼jihanzhong（逍遥）回复于 2005-04-22 15:10:57 得分 2

思路：
1：10个容器=10个位置
2：容器状态：取，不取 =>2种状态

==>相当于10位2进制数 2的10次方>1000，说明可以实现！

类推：
有1000个小球放入7个容器内,随意说出一个数字,要使得挑出几个容器中的小球数目加起来就等于这个数字,从容器中取小球可以取全部或一半，问改怎么放改小球

1：7个容器=7个位置
2：容器状态：全取，取一半，不取 =>3种状态，且3种状态“等差”

==>相当于7位3进制数 3的7次方>1000，说明可以实现！
实现方案：1号：（3-1）*3^0 , 2号：(3-1)*3^1................

Top

17 楼carloslee（李悠然）回复于 2005-04-23 09:43:19 得分 1

学习Top

18 楼Icynthia（蓝山）回复于 2005-04-23 15:03:15 得分 1

大哥，很厉害喔！！！Top

19 楼Flood1984（峰子）回复于 2005-04-23 15:36:47 得分 1

有人回答了，
接分！Top

20 楼rabi_（`!懒虫!`）回复于 2005-04-23 18:07:51 得分 1

题目看了半天不明白要做什么,看答案才知道
我真是大白痴!Top

21 楼maleo（走向地狱）回复于 2005-04-23 18:28:34 得分 1

489
为什么这里是489而不是512呢？Top

22 楼vcmute（BCare4 H1Rest Good9!）回复于 2005-04-23 18:37:21 得分 1

512不行，最多500
1,2,4,8,16,32,64,128,245,500
P.S. 489到500还有很多种呢Top

23 楼ysbcg（Hummer）回复于 2005-04-23 18:38:31 得分 0

楼上的一共1000个球Top

24 楼mb_1983（远影）回复于 2005-04-23 20:23:43 得分 1

高手真多~
Top

25 楼mb_1983（远影）回复于 2005-04-23 20:26:53 得分 1

顺便问一下逍遥
你的推理里面设的是3进制且每个3种状态
那为什么算的时候又要（3-1)^XX呢?Top

26 楼thuers（我什么都不会，所以我想多看看）回复于 2005-04-23 21:19:39 得分 1

Mark

学习～！Top

27 楼fidelf（笨笨猪）回复于 2005-04-23 22:22:53 得分 1

对阿，我也不懂，为什么要（3－1)^XX呢Top

28 楼ect2（利爪）回复于 2005-04-23 23:55:34 得分 2

这样做可以使数据分布更为平均，那3来说如果没有（3-1)^XX那数据分布应如此1,3,9,27,81,243,636
很显然数据产生了分布上的不均，如712就不可能从以上得出，不可能再满足题目的要求。
这是我的理解，没有严密的数学推导，希望有人能给出严密的数学过程
Top

29 楼inlin（）回复于 2005-04-24 02:17:52 得分 0

xue xiTop

30 楼musin1（并合）回复于 2005-04-24 18:37:30 得分 1

有1024个小球放入10个容器内,随意说出一个数字,要使得挑出几个容器中的小球数目加起来就等于这个数字,问改怎么放改小球

题目改了一点可以吗?Top

31 楼nuttang（果壳）回复于 2005-04-24 18:42:31 得分 0

学习！Top

32 楼stephenli（翔）回复于 2005-04-24 19:10:36 得分 1

任何整数都可以用2进制的0和1表示，所以可以用2的幂相加得到Top

33 楼spider104537（蜘蛛）回复于 2005-04-24 21:49:57 得分 1

恩，又学了一种思想！呵呵！Top

34 楼ariel_521（Ariel）回复于 2005-04-25 08:40:52 得分 1

同意 ect2(利爪) 的说法
虽然说以2的结成来分是正确的思想，但是我认为这道题本身就不严谨！有漏洞！！

Top

35 楼zzxenjoy（朝）回复于 2005-04-25 09:24:23 得分 0

接分接分！
我很快乐。。
Top

36 楼yhb7805（codingMouselet）回复于 2005-04-25 09:25:24 得分 1

这个应该属于《离散数学》还是《概率与统计》？Top

37 楼superwyf（++）回复于 2005-04-25 09:28:57 得分 1

说实在的，这个题目我见过，不过是一个卖小菜的来考我的，幸好半个小时侯我才搞定了```Top

38 楼jlkzzh（一阵风）回复于 2005-04-25 09:37:54 得分 1

最重要的是分析各种情况
情况的个数即为进制位数
使用OR解决问题Top

39 楼lbaby（春天来了...）回复于 2005-04-25 10:34:08 得分 1

倘若是20个容器，那么可选的进制就多了
Top

40 楼ariel_521（Ariel）回复于 2005-04-26 10:21:56 得分 1

三进制中有“2”的情况，这就需要有两个1，两个3，两个9，两个27……这样就能说几个就取几个了。
我上面说的不对。昨天晚上没睡好觉，光想这个问题了。我更正一下，这道题没有问题。Top

41 楼kceiw（无名）回复于 2005-04-26 10:37:55 得分 0

学习Top

42 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2005-04-26 12:59:38 得分 0

upTop

43 楼sumless（void）回复于 2005-04-26 13:22:24 得分 1

可以说二进制在计算机学习过程中每天都要用到，可是这么熟悉的思想，在我们要用的时候偏偏想不到Top

44 楼flying_dancing（小混混-_-）回复于 2005-04-26 16:28:57 得分 0

好知识...............接受了Top

45 楼hunanlion（湖南雄狮）回复于 2005-04-26 16:42:42 得分 1

任何整数都可以用2进制的0和1表示，所以可以用2的幂相加得到

这是最好的回答拉楼上说的因为无论一个什么数（用二进制表示）他上面的每个位数都可以用一个小的二进制表示啊而二进制数又是2的多少次方啊所以就是2的次方Top

46 楼cao12m（★草上飞★）回复于 2005-04-26 17:02:16 得分 1

晕点
基本的二进制都不会
这是考你能不能灵活的知道计算机怎么处理数字的
1 2 4 8 16 32 。。。。。。。489
初拉最后一个全是2的N次方Top

47 楼haiyan2004（编程）回复于 2005-04-26 17:28:35 得分 1

晕这对于初学者....Top

48 楼xuewanlong（国家最高机密）回复于 2005-04-26 18:54:52 得分 1

晕Top

49 楼ysb007（宇飞）回复于 2005-04-26 19:42:03 得分 1

太强了
我还要拼命学阿Top

50 楼Sachegirl（Fly-Plume-angel.....）回复于 2005-04-26 20:37:14 得分 1

太强了~~~~~~~~~偶汗Top

51 楼jihanzhong（逍遥）回复于 2005-04-26 20:49:02 得分 1

顺便问一下逍遥
你的推理里面设的是3进制且每个3种状态
那为什么算的时候又要（3-1)^XX呢?

--------------------------------

记数一定要等差的！你看2-1=3-2=4-3=5-4。。。。。
明白了？？？Top

52 楼jihanzhong（逍遥）回复于 2005-04-26 20:53:09 得分 2

3进制的时候，一位最大值是不是(3-1)?大了就要进位了啊！
同理10进制 10-1=9Top

53 楼jihanzhong（逍遥）回复于 2005-04-26 20:57:57 得分 2

这种思路第i个容器放的数量是k进制下[（k-1）0 0 0...] = （k-1）*k*k*...k = (k-1)*k^(i-1)个球!

[（k-1）0 0 0...] :模拟十进制表示法，比如十进制的9000.., 4进制的3000..Top

54 楼cao12m（★草上飞★）回复于 2005-04-26 22:50:36 得分 2

证明：共有10个箱子代表二进制数字的位数 10 位二进制的最大数是1023
9 位的最大数字是511 要是大于911 要用到最高位数字
上面的1 2 4 8 。。。。。。。分别代表每位上的权值
任意一个1--1000内的数字都能用十位以内的二进制表示确切的说把489 也看成权值代替512 没什么影响。
证毕。Top