纯数学的算法题(1)

那些需要数学知识的算法题，第一波

斐波那契数列

常见的题目如爬楼梯，本质上是求f(n)=f(n-1)+f(n-2)的值

public int climbStairs(int n) {
    int a = 1, b = 1, c = 1;
    while(--n != 0) {
        c = a + b;
        b = c;
        a = c - a;
    }
    return c;
}

注意，在另一道题求斐波那契数列中初始值是从0开始的，并且要求对结果取模

public int fib(int n) {
    if(n == 0) return 0;
    int a = 0, b = 0, c = 1;
    while(--n > 0) {
        a = b;
        b = c;
        c = (a + b)  % 1000000007;
    }
    return c;
}

实际写代码时需要注意：

1. 交替赋值顺序不能搞错，比如写成c=a+b, b=c, a=b
2. while的退出条件是--n > 0，一定是--在前面
3. 取模这里比较坑，一开始按照爬楼梯的解题代码就写成了c = (a+b)%1000000007, b=c, a=b，导致部分测试用例没有通过 总结起来还是第二段代码更为全面，能够处理f(0)的情况，直接背下来吧

灯泡开关

原题描述：

初始时有n个灯泡处于关闭状态。对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。
第 1 轮，每个灯泡切换一次开关。即，打开所有的灯泡。
第 2 轮，每两个灯泡切换一次开关。 即，每两个灯泡关闭一个。
第 3 轮，每三个灯泡切换一次开关。
第 i 轮，每 i 个灯泡切换一次开关。 而第 n 轮，你只切换最后一个灯泡的开关。
找出 n 轮后有多少个亮着的灯泡。

一开始试图对1,2,3,4几种较小情况分析出结果然后判断结果是否是某种规则的数列，实际上没有，接着又上头想着能不能转成动态规划，还是不行。看了题解，从1开始对灯泡编号，对于灯泡k，它在什么时候切换开关呢？从第1,2,3,4到i，发现当k能整除i时灯泡k切换一次开关，并且只需要关注切换次数的奇偶性，那切换几次呢？由于轮数从1到k，那切换次数就是k的所有因子的个数，到了这里就需要引入一个重要的数学理论

因数个数的奇偶性

当整数k为完全平方数时，其因数个数为奇数，否则为偶数

所以，对于灯泡k，当k为完全平方数时，此时它切换开关奇数次，最后为点亮状态，否则为熄灭状态。因此问题即转换为求1到n中完全平方数的个数：

public int bulbSwitch(int n) {
    int ans = 0;
    for(int i = 1; i * i <= n; ++i) {
        ++ans;
    }
    return ans;
}

用rand7生成rand10

原题描述：

已有方法rand7可生成1到7范围内的均匀随机整数，试写一个方法rand10生成1到10范围内的均匀随机整数。不要使用系统的Math.random()方法。

一开始是有点懵逼的，冷静分析后是要对rand7()进行一些加减乘除运算后返回一个数。那怎么进行四则运算随机产生1到10的数呢？这里引出3个重要概率公式

公式1

令Rand_N表示随机生成1到N的方法，那么有:
Rand_XY = (Rand_X - 1) * Rand_Y + Rand_Y
其中Rand_XY中的XY表示X乘以Y

公式2

如果X整除N，那么(Rand_N) % X + 1= Rand_X

拒绝采样

Rand_Y() = (X > Y) ? Rand_X - Y : Rand_X;

先根据公式1，可以用两个rand7()方法得到rand49()，通过拒绝采样，只要rand49()的返回值大于10就继续采样，否则直接返回。这里得到了49个随机数但是却只要10个，丢弃概率太大。由于49内10的最大公倍数是40，根据公式2，将条件改为大于40才拒绝采样，这样只需要丢弃9个数。9个还是太多，用rand49()减去40得到rand(9)，根据公式1继续得到rand63()，还不够，减60得到rand3()，最后得到rand21()，此时只需要丢弃1个数

public int rand10() {
    while(true) {
        int a = rand7();
        int b = rand7();
        int sum = (a - 1) * 7 + b;

        if(sum <= 40)   return sum % 10 + 1;

        a = sum - 40;
        b = rand7();
        sum = (a - 1) * 7 + b;
        if(sum <= 60)   return sum % 10 + 1;

        a = sum - 60;
        b = rand7();
        sum = (a - 1) * 7 + b;
        if(sum <= 20)   return sum % 10 + 1;
    }
}