咖啡时间

我们工作生活中的很多问题都是优化问题。在本文中，我们给出几个典型的例子，并尝试使用现有的求解器进行求解，作为参照。在后续文章中，我们将介绍一些启发式算法，并对本文中的问题进行求解。

定义

$$ min \ f_{0}(x) $$
$$ subject \ to \ f_{i}(x) \leqslant b_{i} \ i=1,…,m $$

• 目标函数和限制函数都是凸的，即
  $$ f_{i}(\alpha x + \beta y) \leqslant \alpha f_{i}(x) + \beta f_{i}(y) \ \alpha + \beta = 1, \alpha \geq 0, \beta \geq 0 $$
• 最小二乘问题和线性规划问题都是凸优化问题的特例

问题1: 拒绝采样

leetcode 470: Implement Rand10() Using Rand7()

Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn’t call any other API. Please do not use a language’s built-in random API.

Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

Follow up:
What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Example 1:
Input: n = 1
Output: [2]

Example 2:
Input: n = 2
Output: [2,8]

Example 3:
Input: n = 3
Output: [3,8,10]

Constraints:
1 <= n <= 105

最近对“算法”有了新的理解，对于普通程序员来说，算法功底的好坏对于简洁而高质量的代码至关重要，因此决定从一些经典的ACM算法开始，扎实的学习一下这些算法和编程技巧，以期能有更好的将来。从网上搜索了一些资料，发现“@制糕神的算法工坊”整理的比较全面，这里借用他的一张图片，后续将从他的这个图片开始学习。