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

发布于 2023-11-08  266 次阅读


内容纲要

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、完成情况证明

世界のネズミは彼らが望むものに依存し、彼らは彼ら自身から誰も求めません
最后更新于 2023-11-08