分支限界算法的设计与分析

1、专题名称

分支限界算法的设计与分析

2、实践内容

2.1 实践内容 1

（1）题目要求

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:

输入: 1
输出: [2]

示例 2:

输入: 2
输出: [2,8]

示例 3:

输入: 3
输出: [3,8,10]

提示:

• 1 <= n <= 10^5^

（2）算法设计

只要把小的数7映射到一个大的数10即可,注意要求是等概率的

（3）代码实现

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int a = (rand7() - 1) * 7 + rand7();
        while(a>10)
        a = (rand7() - 1) * 7 + rand7();
        return a;
    }
};

（4）算法分析

时间复杂度：O(1)

空间复杂度：O(1)

算法优点：时间复杂度和空间复杂度都低。

缺点：要把题目转换为数学问题来解决。

2.2 实践内容 2

（1）题目要求

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

示例 1：

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解释:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint ();//返回[-0.02493，-0.38077]
solution.randPoint ();//返回[0.82314,0.38945]
solution.randPoint ();//返回[0.36572,0.17248]

提示：

• 0 < radius <= 10^8^
• -10^7^ <= x_center, y_center <= 10^7^
• randPoint 最多被调用 3 * 10 ^4^ 次

（2）算法设计

根据数学思想设计解决问题

（3）代码实现

class Solution {
private:
    mt19937 gen{random_device{}()};
    uniform_real_distribution<double> dis;
    double xc, yc, r;

public:
    Solution(double radius, double x_center, double y_center): dis(-radius, radius), xc(x_center), yc(y_center), r(radius) {}

    vector<double> randPoint() {
        while (true) {
            double x = dis(gen), y = dis(gen);
            if (x * x + y * y <= r * r) {
                return {xc + x, yc + y};
            }
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */

（4）算法分析

时间复杂度：O(1)

空间复杂度：O(1)

算法优点：空间复杂度低，时间复杂度较低。

缺点：对数学要求非常高，非常难想。

3、问题与总结

问题：以上题目对分支限算法，即数学思想有较高要求，花了一定时间

总结：对分支限算法的了解更加熟悉

4、完成情况证明