编程语言与算法设计







[编程之美]N个鸡蛋放到M个篮子的方法

今天看到一个面试题目,题目大意:将n个鸡蛋放到m个篮子,同时保证不能有空篮子,且对于任意小于等于n的数,都能保证有几个篮子的鸡蛋数等于这个数

题目分析

第一眼看到这个题目时,感觉像是整数拆分问题,但是有两个限制:1. 不能有空篮子 2.保证能够针对任意<=n的数,都可以用几个篮子的鸡蛋的和来表示,所以应该不是整数拆分问题。

首先想到是就是穷举,也就是深度搜索,但是如何判断搜索的一个结果是否满足第二个条件呢?

这里可以通过归纳的方法,假设当前的前n个数为Sn,同时任意<=Sn的数都可以用前n个数某些数的和来表示,那么第n+1个数的范围是什么呢?

这里应该可以想到,如果第n+1个数>(Sn) + 1 的话,相当于有间隔,那么(Sn) + 1这个就无法表示,所以第n+1个数应该是<= Sn + 1,这样就可以满足

任意的<=S(n+1) 的数都可以用前n+1个数来表示;

同时在搜索的过程中保证序列是非降序的,而且会有剪枝的方法,实现具体看代码

代码实现

更多 >













C++沉思录读书笔记:句柄类的实现

对于某些类来说,能够避免复制是很有好处的,比如某些对象会很大,复制起来消耗太大,这时就可以通过 句柄(Handler)的类来实现,它允许在保持类的多态的行为的同时,还可以避免不必要的复制。

句柄类的实现方法

为了避免不必要的对象复制,也就是说允许多个句柄绑定到单个对象上,否则就很难把句柄作为参数传递函数,因为那要求复制句柄而不复制对象。因此我们必须了解有多少个句柄绑定在同一个对象上,只有这样才能确定应当在何时删除对象,通常使用“引用计数(use count)”来达到这个目的。

引用计数应该放到何处呢?

1.不能作为句柄的一部分,因为这样的话,每个句柄都必须知道跟它一起被绑定到同一个对象的其他句柄的位置,唯有如此才能更新其他句柄的引用计数数据;

2.作为对象的一部分,这样就要求我们重写已经存在的对象类;

3.定义一个新的类,来保存对象和引用计数(可以考虑);

4.在句柄类中保存引用计数的指针地址,绑定到同一个对象的句柄指向同一个引用计数值;

5.单独抽象出引用计数类,为句柄类提供接口(终极方案);

使用句柄类时还必须关注一个问题,当对句柄所绑定的对象进行修改时,句柄的语义就分为值语义和指针语义:

值语义:修改句柄绑定的对象,但是不影响其他句柄 (使用写时复制copy-on-write)

指针语义:修改句柄绑定的对象,其他绑定到该对象的句柄也同样修改 (指针的作用)

具体实现请参考C++沉思录