Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1022765
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类:

2010-05-18 14:07:42

面试题——n个小孩拿n个苹果

有n个苹果,n个小孩排队一个个地去拿苹果,每一个小孩在剩下的苹果中至少拿1个,至多全拿光。编程输出所有可能的拿法。百度2008年面试题

我一看到这个问题就想到了0-1背包问题:每个小孩可以拿1到n个,看成n种规格的物品放入大小为n的背包,用递归方法解出。但事实上,这道题没有这么复杂,让我们以n=4为例,按一定顺序列出所有的拿法:

4 0 0 0
3 1 0 0
2 2 0 0
2 1 1 0
1 3 0 0
1 2 1 0
1 1 2 0
1 1 1 1

可以得出这样一个规律:第n+1行的数列可以在第n行的基础上用如下的算法计算出:从右至左找到第一个大于1的数字,将它减1,然后将这个数字右边的数字赋为苹果总数减去左边所有数字后剩下的值,其余更右边的数全赋为0。

阅读(805) | 评论(0) | 转发(0) |
0

上一篇:面试题 赛马 转载

下一篇: 子数组 最大和

给主人留下些什么吧!~~