算术

上一个帖子《没有重复的全排列》中的算法虽然有效，但是不能处理字符串中有重复的情形。这回我们考虑给定的字符串中包含重复的字符。如何能够有效的生成它所有不同的排列。要求不可使用递归，而且生成的排列必须按照字典顺序。例如输入字符串bac，我们有

bac
bca 升序
cab 升序
cba 升序，最大值
abc 最小值
acb 升序
bac 升序

给定一个字符串，每个字符在其中都不重复出现。每当改变字符出现的顺序，我们就得到这个字符串的一个排列。请设计一个算法，最有效的生成其所有不同的排列？

例如给定abc，生成 acb, bac, bca, cab, cba。

提示：此算法基于自然数和排列之间的一一映射关系 。

一个娱乐电视节目中，主持人要一个嘉宾从三道门中选择一道。其中的一个后面放着一辆崭新的轿车，如果猜对了就会赢取这辆车。无论嘉宾做出什么选择，主持人总会打开另外一个门，当然门后什么也不会有。然后主持人会问嘉宾，是否想改变选择。请问嘉宾应该怎么做才有较大的机会赢取轿车。

如何最有效的检查单向链表中是否包含了环。请避免使用额外的内存。下面有一个含有环的链表的例子：

假设你有两枚硬币，其中一枚两面都是国徽，另一枚是正常的。某日，你随便拿了其中一枚到了办公室。你连续抛了三次硬币，结果三次都是国徽。请问再抛一次还是国徽的概率是多少？

假设鸡蛋壳的硬度是随机分布，从0到1。现在我们随便找两个鸡蛋对敲(PK),选其中没有被敲破的那个（A）和随便挑出来的另一个鸡蛋对敲，此鸡蛋（A）仍然不破的概率是多大？

在早期的赛马比赛中，裁判没有秒表，只能靠每场比赛中大家的先后顺序来判断谁快谁慢。如果每场比赛只能同时跑5匹马，总共有25匹马参赛的情况下，最少需要多少场比赛才能保证赛出前三名？

一间古老的寺庙中住着一群和尚。所有的和尚都非常的聪明，精于算术和逻辑，同时也都严格遵守这庙里的各项戒律。以下是一些比较重要戒律：

1. 所有的和尚都不准照镜子
2. 和尚之间不准说话或进行其他方式的交流
3. 除了在午饭时间，其他时候一律不得来往，安心修行
4. 每天午饭必须准时到食堂，这也是大家每天唯一能相互看见的机会。

一 天，外面来了一个医生，说本地区出现了一种疾病，可能是之前供应的不干净的食物带来的。现在食物的问题已经解决了，这个疾病也不会传染，他们在呼吁患者赶 快去医院看病。这个病最明显的症状就是病患的前额会长一个明显的大红斑。医生说完“我已经看到有的和尚得病了”就急匆匆离开了。

寺院很快就制定了新的章程，要求和尚一旦发现自己发病就立刻离开去医院住院治疗。问题是和尚们如何确定自己是否发病，需要多长时间得病的和尚才会发觉并去医院进行治疗。

为了讨论方便，我们假设共有N个和尚得病了，当然和尚自己是不知道有多少的。

这次实际上是两个问题：

有一台高配置的PC服务器，包含8个CPU和4G的内存。服务器用于统计一个字符流中的词频信息。字符流是实时产 生的，比如搜索引擎用户输入的查询关键字，数量大、速度快。假设当前使用的算法不能有效的利用所有的CPU，计算性能已经成为了系统的瓶颈(就是说IO不 是问题)。如何设计一个有效并行算法统计字符流中每个单词的词频（出现次数）？

使用你设计的算法，我们生成了一个关于词频统计信息的表 格。表格的第一列是单词的ID，第二列是每个单词的词频。为了训练一个人工智能算法，现在需要根据单词的词频生成一个很大的样本。请设计一个方案，每次 （根据词频统计信息）随机的返回一个单词给人工智能算法。你可以使用一个随机数生成函数，但必须保证样本和原有数据有相似的词频分布。

设计一个程序，找出所有位于X和Y之间的素数。这是一个老题了，但是真正做起来才会知道有很多地方可以进一步优化。先把最常见的程序放在这里，看你能想到多少可以改进的地方。注：这里使用数组只是为了方便，别无他意。

这里是优化后的程序，解释见后面。

至少有三个可以改进的地方：

1. 首先所有的素数除了2以外都是奇数，所以循环中应该跳过所有的偶数。
2. 当i小于X时，第14行的比较操作永远是失败的。为了避免无效的比较，我们可以把循环分成两部分，小于X的一部分，X到Y另一部分。
3. 为了检查一个数是不是素数，只需要检查小于它的平方根的那些因子即可。