内容纲要
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、问题与总结
问题:以上题目对分支限算法,即数学思想有较高要求,花了一定时间
总结:对分支限算法的了解更加熟悉
Comments NOTHING