具体数学-第8课 - WeiYang Bloggodweiyang.com
今天主要讲了取整与递归式的结合,还有取模的相关知识。
给出下列递归式:
现在不要求你求解,要你证明:
首先想到的就是数学归纳法,假设对于任意
,都有
,那么:
如果
,那么
。 如果
,那么
,这时不成立。
所以数学归纳法无法证明,今后我们会用其他方法来证明这个式子。
还记得约瑟夫环问题吗?详见第一节课。
这里我们继续推广到一般情况,如果有
个人,每隔
个人踢掉一个人,最后剩下的是几号?
初始编号为
,现在考虑一种新的编号方式。
第一个人不会被踢掉,编号加
,变成
,然后第二个人编号变为
,直到第
个人,他被踢掉了。
然后第
个人编号继续加
,变成了
,依次下去。
考虑当前踢到的人编号为
,那么此时已经踢掉了
个人,所以接下去的人新的编号为
。
所以编号为
的人编号变成了
,其中
。
直到最后,可以发现活下来的人编号为
,问题是怎么根据这个编号推出他原来的编号?
以
,
为例,下图就是每个人新的编号:
令
所以他上一次的编号是
因为
所以上一次编号可以写为
因此最后存活的人编号可以用如下的算法计算:
N = qn
while N > n:
N = k + N - n
ans = N
其中
如果我们用
替代
,将会进一步简化算法:
算法伪代码如下:
D = 1
while D <= (q-1)n:
D = k
ans = qn + 1 - D
其中
模定义如下:
特别的
与此类似,定义一个与模类似的运算:
形象理解如下图所示:
圆的周长是
,一共走过的路长(红色+绿色部分)是
,所以
就是绿色部分,
就是一圈长度减去绿色部分。
模有一些性质:
考虑如下问题,怎么平均分配
个东西给
个人?
很容易想到,首先分给每个人
个东西,剩下
件东西分给前
个人,一人多一件就行。
概括起来就是,前
个人,每人
件,剩下的人,每人
件。
那有没有办法统一表示呢?有的,每个人分到的件数为
为什么呢?假设
那么
当
时,
当
时,
得证,因此可以得到如下等式:
由
可以进一步将其转换为下取整形式:
令
我们得到了一个令人惊奇的等式:
最后用今天介绍的约瑟夫环算法来解决一道经典的ACM题!题目链接:杭电3089。
C++代码如下:
#include<bits/stdc++.h>using namespace std;
typedef long long LL;
LL Ceil(LL x, LL y) {
if (x % y == 0) return x / y;
return x / y + 1;
}
LL J(LL n, LL q) {
LL D = 1, end = (q - 1) * n;
while (D <= end) {
D = Ceil(q * D, q - 1);
}
return q * n + 1 - D;
}
int main() {
LL n, q;
while (~scanf("%lld%lld", &n, &q)) {
printf("%lld\n", J(n, q));
}
return 0;
}
比网上各种快速算法还要快哦,理论时间复杂度是
的。