编程语言与算法设计

问题描述

已知random3()这个随机数产生器生成[1, 3]范围的随机数，请用random3()构造random5()函数，生成[1, 5]的随机数？

问题分析

如何从[1-3]范围的数构造更大范围的数呢？同时满足这个更大范围的数出现概率是相同的，可以想到的运算包括两种：加法和乘法

考虑下面的表达式：

3 * (random3() – 1) + random3();

可以计算得到上述表达式的范围是[1, 9]  而且数的出现概率是相同的，即1/9

下面考虑如何从[1, 9]范围的数生成[1, 5]的数呢？

可以想到的方法就是 rejection sampling 方法，即生成[1, 9]的随机数，如果数的范围不在[1, 5]内，则重新取样

解决方法

int random5()
{
    int val = 0;
    do {
        val = 3 * (random3() - 1) + random3();
    } while (val > 5);
    return val;
}

归纳总结

将这个问题进一步抽象，已知random_m()随机数生成器的范围是[1, m] 求random_n()生成[1, n]范围的函数，m < n && n <= m *m
一般解法：

int random_n()
{
    int val = 0 ;
    int t; // t为n最大倍数，且满足 t <= m * m     
    do {         
        val = m * (random_m() - 1) + random_m();     
    } while (val > t);
    return val;
}

参考资料：

http://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7

好久没更新blog，都快荒废了，今天发个算法问题

题目介绍：

输入为不断地数字流，实时显示出当前已经输入的数字序列的中位数

解答：

求中位数的方法很多，对于大数据量最经典是桶的计数方法，但是对于这个问题不适用，因为数据是不断变化的

可以用最大堆和最小堆来解答这个问题：

1.假设当前的中位数为m，其中最大堆维护的是<=m的数字序列，最小堆维护的是>=m的数字序列，但是两个堆都不包含m

2.当新的数字到达时，比如为a，将a与m进行比较，若a<=m 则将其加入到最大堆中，否则将其加入到最小堆中

3.如果此时最小堆和最大堆的元素个数的差值>=2 ，则将m加入到元素个数少的堆中，然后从元素个数多的堆将根节点赋值到m，最后重建两个最大堆和最小堆，返回到2

今天看编程之美，看到求平面中两点的最近距离，书中给出了O(nlogn)算法，主要是采用分治的方法来做的，首先将平面的点按x坐标分为两部分，分别求最近点对，然后是合并；合并过程中对于两个点分别在两个区域的分析非常巧妙，有效地减少了需要比较的点对的个数。

在poj中对应的题目3714

然后又看到了扩展问题：如何求平面中最远的两个点的距离

这个就不能继续套用“最近距离点对”的分治策略，上网查了下，原来是使用凸包算法+旋转卡壳算法，poj中对应的题目是2187和3608

这里简单记录下，明天做下这两个题目

关于凸包算法和旋转卡壳算法的介绍：

http://yishan.cc/blogs/gpww/archive/2011/02/16/graham-s-scan.aspx

http://www.cppblog.com/staryjy/archive/2010/09/25/101412.html

http://yishan.cc/blogs/gpww/archive/2011/02/15/1787.aspx