问题描述

要求从N个元素中随机的抽取k个元素，其中N无法确定(N是个流，可能无穷大)。

这种应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的；但又要保持随机性，于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”，怎么才能是随机的抽取元素呢？我们设想，买彩票的时候，由于所有彩票的中奖概率都是一样的，所以我们才是“随机的”买彩票。那么要使抽取数据也随机，必须使每一个数据被抽样出[......]

继续阅读

DAG和概念
有向无环图：顾名思义，有向图，且不含环，directed acycline graph，简称DAG图。

无向图检查环：若深度优先遍历过程遇到回边（先前访问过的顶点的边），则必定存在环。

有向图检查环：从某个顶点v出发，在dfs(v)结束前，出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图必定存在包含顶点v和u之间的环。

DAG图是描述工程的有效工具。一个工程可以用一个DAG图表示，每一个顶点是一个子工程，工程的先后关系用弧表示。

围绕着[......]

继续阅读

用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的（条件是y个球中y-1个重量相等，其他一个轻），
使用x 次天平，最多可以从y 个小球中找出较轻的那个，求y 与x 的关系式。

其实，这是一个“三分查找问题”。

当y=3时，x=1（一次称重即可）：

3个球中任选两个放到天平两端，若相等，则没称的那个是轻球。

若有一个轻，则轻的就是。

递归可以分析出来x = log3(y)。

 [......]

继续阅读

1、瀑布开发模型(Waterfall Model)

将软件生命周期划分为制定计划、需求分析、软件设计、程序编写、软件测试和运行维护等六个活动。一个阶段完成后再将其输出作为下一个阶段的输入，逐层开发。缺点是难以适应业务需求变化，风险管控不够。

2、快速原型模型(Rapid Prototype Model )

迅速建造一个可以运行的软件原型 ，以便理解和澄清问题，使开发人员与用户达成共识，最终在确定的客户需求基础上开发客户满意的软件产品。优点是可以快速摸清客户需求且成本低风险低。缺[......]

继续阅读