具体数学第三章笔记及习题解答

离散数学是跟整数有关的数学，也是计算机科学的基础，本章就着重于讲述如何将分数转化为整数的技巧

底和顶

我们使用以下标记
$\lfloor x\rfloor=$ 小于或等于 $x$ 的最大整数
$\lceil x\rceil=$ 大于或等于 $x$ 的最小整数

下面是一个函数的示意图

image.png

我们可以得出一个恒等式
$\lceil x\rceil- \lfloor x\rfloor=[x不是整数]$
这是因为当 $x$ 为整数时， $\lceil x\rceil=\lfloor x\rfloor=x$ ，当 $x$ 不为整数时， $\lceil x\rceil-\lfloor x\rfloor=1$
同样的很明显有
$x-1<\lfloor x\rfloor\leq x\leq \lceil x\rceil<x+1$
$\lfloor -x\rfloor=-\lceil x\rceil，\lceil -x\rceil=-\lfloor x\rfloor$

为了更直观的理解底和顶，可以通过以下不等式（其实就是上面不等式的变形，n表示一个整数）
$\lfloor x\rfloor=n \Leftrightarrow x-1<n\leq x<n+1\tag{1}$
$\lceil x\rceil=n \Leftrightarrow n-1<x\leq n<x+1\tag{2}$

同时像 $\lfloor x+n\rfloor=\lfloor x\rfloor+n，\lceil x+n\rceil=\lceil x\rceil+n$ ，可以将整数项挪入和挪出底或顶，但像 $\lceil nx\rceil\neq n\lceil x\rceil，\lfloor nx\rfloor\neq n\lfloor x\rfloor$ 则不可以

同样可以总结出以下几个不等式
$x<n\Leftrightarrow \lfloor x\rfloor<n\tag{3}$
$n<x\Leftrightarrow n<\lceil x\rceil\tag{4}$
$x\leq n\Leftrightarrow \lfloor x\rfloor\leq n\tag{5}$
$n\leq x\Leftrightarrow n\leq \lceil x\rceil\tag{6}$

我们把 $x,\lfloor x\rfloor$ 间的差称为 $x$ 的分数部分 $\{x\}=x-\lfloor x\rfloor$ ，同时称 $\lfloor x\rfloor$ 为 $x$ 的整数部分

对 $x=\lfloor x\rfloor+\{x\}$ ， $y=\lfloor y\rfloor+\{y\}$ ，有
$\lfloor x+y\rfloor=\lfloor x\rfloor+\lfloor y\rfloor+\lfloor {\{x\}}+{\{y\}}\rfloor$
且 $0\leq{\{x\}} +{\{y\}}<2$ ，故有

$\lfloor x+y\rfloor$ 等于 $\lfloor x\rfloor+\lfloor y\rfloor$ 或 $\lfloor x\rfloor+\lfloor y\rfloor+1$
$\lceil x+y\rceil$ 等于 $\lceil x\rceil+\lceil y\rceil$ 或 $\lceil x\rceil+\lceil y\rceil-1$

底和顶的应用

任意一个整数写成二进制表示需要多少位？
经过简单的验证，我们可以通过 $\lfloor \lg n\rfloor+1$ 或 $\lceil \lg(n+1)\rceil$ 两种位数表示（这里默认的底显然是2）

而对于多个底或者顶的表达式，形如 $\lfloor \lceil x\rceil \rfloor$ 这样的内层是底或者顶外层多个底或者顶的表达式，可以把外层的底或者顶省略掉而不改变表达式的值

我们尝试证明以下命题
$\lfloor \sqrt{\lfloor x\rfloor} \rfloor=\lfloor \sqrt x\rfloor,x\geq 0$

在证明其存在或不存在时，我们可以首先猜测一个可能的值，试图找一个反例去否定命题，一是因为否定更加容易，二是因为在寻找反例中，我们会有机会寻找到证明的方法。这个例子中，无论怎么尝试，是找不出反例来的。

如果我们借助微积分来证明，首先将 $x$ 分解为整数和分数部分，用牛顿二项式定理将其展开，但展开后过于复杂不好处理

我们换一种方式，先去掉原式左部分中外部的底和根号，然后去掉内层的底，最后将外层的符号还原回去最后得到右部分

首先设 $m=\lfloor \sqrt{\lfloor x\rfloor} \rfloor$ ，根据性质1，有 $m\leq \sqrt{\lfloor x \rfloor}<m+1$ ，
由于不等式三个值都是正的，将其平方，得 $m^2\leq \lfloor x \rfloor<(m+1)^2$
对这个不等式左边使用性质6，右边使用性质3，则有 $m^2\leq x <(m+1)^2$
再同时开方得 $m\leq \sqrt x<m+1$ ，利用性质1， $\lfloor \sqrt x\rfloor=m$
即左式等于右式，命题得证

在以上证明中，并没有严重依赖平方根的性质，我们把这个命题推广:
设 $f(x)$ 是任意一个具有如下性质且在实数区间连续的单调递增函数
$f(x)=整数\quad \Rightarrow\quad x=整数$

只要 $f(x),f(\lfloor x\rfloor),f(\lceil x\rceil)$ 都有定义，则有
$\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor)\rfloor,\lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil$

下面是对顶的证明，底的证明类似

当 $x=\lceil x\rceil$ ，显然是成立的，否则 $x<\lceil x\rceil$ ，由于 $f(x)$ 单调递增， $\lceil \rceil$ 非减，于是 $f(x)<f(\lceil x\rceil),\lceil f(x)\rceil\leq \lceil f(\lceil x\rceil)\rceil$

如果 $\lceil f(x)\rceil<\lceil f(\lceil x\rceil)\rceil$ ，因为 $f(x)$ 的连续性以及其必备的性质，必然存在一个整数 $y$ ，使得 $x\leq y<\lceil x\rceil,f(y)=\lceil f(x)\rceil$ 成立，但显然这样的数并不存在，于是命题得证

这个定理有如下一个应用特例
如果 $m,n$ 为整数且分母 $n$ 为正，则有
${\left\lfloor\frac{x+m}{n}\right\rfloor}={{\left\lfloor\frac{\lfloor x\rfloor+m}{n}\right\rfloor}}, {\left\lceil\frac{x+m}{n}\right\rceil}={{\left\lceil\frac{\lceil x\rceil+m}{n}\right\rceil}}$
例如令 $m=0$ ，则 $\Big\lfloor\big\lfloor\lfloor x/10\rfloor/10\big\rfloor/10\Big\rfloor=\lfloor x/1000 \rfloor$ ，三次用10来除并抛弃个位数字，与用1000来除并抛弃余数，结果是一样的
$\lfloor x/1000 \rfloor=\lfloor \frac{x/100}{10} \rfloor=\Big\lfloor\frac{\lfloor x/100 \rfloor}{10}\Big\rfloor=\cdots$ 重复下去即可得到左式结果

image.png

在了解上面对于数学问题水平的定义之上，我们研究一下以下等式等号成立的条件
$\lceil \sqrt{\lfloor x\rfloor}\rceil{\stackrel{?}{=}} \lceil \sqrt x \rceil ,x\geq 0$
我们在尝试几个数后发现，有时等号成立，有时不成立，以水平4的角度去寻找等号成立的条件会发现：
当 $m^2<x<m^2+1$ 时，等号左边为 $m$ ，右边则为 $m+1$ ，等号不成立
当 $m^2+1\leq x \leq (m+1)^2$ 时，等号成立
因此我们可以说等号成立的充要条件为： $x$ 为整数或者 $\sqrt{\lfloor x\rfloor}$ 不为整数

现在我们从区间的角度数一数其中的整数个数。我们知道开区间 $(a,b)$ 表示满足 $a<x<b$ 的所有 $x$ 取值，闭区间 $[a,b]$ 表示满足 $a\leq x\leq b$ 的所有 $x$ 取值，而半开半闭区间同理。事实上，两个同类型的半开半闭区间可以很方便的相加，但显然开区间和闭区间不能随便这么做。于是我们先从半开半闭区间研究。

当 $a,b$ 都为整数时，显然在区间 $[a,b)$ 内的整数有 $a,a+1,\dots,b-1$ 共 $b-a$ 个；区间 $(a,b]$ 内的整数有 $a+1,\dots,b$ 共 $b-a$ 个。
当 $a,b$ 为任意实数时，根据我们之前了解到的底和顶的性质，有
$a\leq n<b \Leftrightarrow \lceil a\rceil\leq n<\lceil b\rceil$
$a< n\leq b \Leftrightarrow \lfloor a\rfloor< n\leq\lfloor b\rfloor$

从而得出 $[a,b)$ 包含 $\lceil b\rceil-\lceil a\rceil$ 个整数， $(a,b]$ 包含 $\lfloor b\rfloor-\lfloor a\rfloor$ 个整数，类似的 $[a,b]$ 包含 $\lfloor b\rfloor-\lceil a\rceil+1$ 个整数， $(a,b)$ 包含 $\lceil b\rceil-\lfloor a\rfloor-1$ 个整数

这里规定一个习惯，对 $[a,b)$ 用顶来表示，对 $(a,b]$ 用底来表示，用表格来总结一下

区间	包含整数的个数	条件
$[a,b]$	$\lfloor b\rfloor-\lceil a\rceil+1$	$a\leq b$
$[a,b)$	$\lceil b\rceil-\lceil a\rceil$	$a\leq b$
$(a,b]$	$\lfloor b\rfloor-\lfloor a\rfloor$	$a\leq b$
$(a,b)$	$\lceil b\rceil-\lfloor a\rfloor-1$	$a<b$

下面我们看一个具体的例子来验证我们所总结的内容
计算1~1000中（包含两端）的整数个数，其满足 $\lfloor \sqrt[3]{n}\rfloor \Big|n$ ，也就是一个数n能被它的立方根的底整除的条件
我们把个数设为 $S$ ，则有
$\begin{align}S&=\sum_{1\leq n\leq 1000}[\lfloor \sqrt[3]{n}\rfloor \Big|n]\\&=\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][1\leq n\leq 1000]\\ &=1+\sum_{k,m}[k^3\leq km<(k+1)^3][1\leq k<10]\quad\text{这里将n=1000的情况单独列出}\\ &=1+\sum_{k,m}[m\in[k^2,\frac{(k+1)^3}{k})][1\leq k<10]\\ &=1+\sum_{1\leq k<10}(\lceil k^2+3k+3+\frac{1}{k}\rceil-\lceil k^2\rceil)\\ &=1+\sum_{1\leq k<10}\lceil 3k+3+\frac{1}{k}\rceil\\ &=1+\sum_{1\leq k<10}(3k+4)\\ &=1+\frac{7+31}{2}\times 9=172 \end{align}$
注意到注释部分，之所以这么做是想要使得 $k$ 的取值范围变成一个半开半闭的区间，把 $n=1000$ 单独列出来后，就可以做到这一点，之后使用上面表格中的性质就很方便了。

下面我们把1000这个具体的数字变成代数 $N$ ，同样的条件，我们来计算一下结果

我们设 $K^3\leq N<(K+1)^3$ ，也就是说 $K=\lfloor \sqrt[3]{N}\rfloor$ ， $K$ 是小于或等于 $N$ 的立方根最大的整数，则根据上面我们计算的经验
$\begin{align}S'&=\sum_{1\leq k<K}(3k+4)+\sum_m [K^3\leq Km\leq N]\\ &=\frac{(7+3K+1)(K-1)}{2}+\sum_m\big[m\in[K^2,\frac{N}{K}]\big]\\ &=\frac{3}{2}K^2+\frac{5}{2}K-4+\sum_m\big[m\in[K^2,\frac{N}{K}]\big] \end{align}$
后面的和式等于 $\lfloor \frac{N}{K}\rfloor-\lceil K^2\rceil +1=\lfloor \frac{N}{K}\rfloor-K^2+1$
故最后的答案为
$S'=\lfloor \frac{N}{K}\rfloor+\frac{1}{2}K^2+\frac{5}{2}K-3,K=\lfloor \sqrt[3]{N}\rfloor$

这样就得出了一个一般性的答案

观察这个公式前两项近似于 $N^\frac{2}{3}+\frac{1}{2}N^\frac{2}{3}=\frac{3}{2}N^\frac{2}{3}$ ，而其余项可记做 $O(N^\frac{1}{3})$ ，在 $N$ 足够大的情况下，是可以忽略的，但在取一些不够大的值时，如果需要精确的数据，不可以随便忽略

下面我们讲一个新的概念：谱

一个实数 $a$ 的谱是整数组成的一个无限多重(元素可重复，数论里有讲)集合
$Spec(a)=\{\lfloor a\rfloor,\lfloor 2a\rfloor,\lfloor 3a\rfloor,\dots\}$
例如 $1 \over 2$ 的谱就是 $\{0,1,1,2,2,3,3,\dots\}$
谱有一个基本的性质，就是当 $a\neq b$ 时， $Spec(a)\neq Spec(b)$ ，其证明如下：

假设 $a<b$ ，则存在一个正整数 $m$ 使得 $m(b-a)\geq 1$ ，即 $mb-ma\geq 1$ 且 $\lfloor mb\rfloor>\lfloor ma\rfloor$ ，显然 $Spec(b)$ 有少于 $m$ 个元素 $\leq \lfloor ma\rfloor$ ，而 $Spec(a)$ 至少有 $m$ 个这样的元素

下面我们看一下谱一个有趣的性质，比如观察下面两个谱
$\begin{align}Spec(\sqrt 2)&=\{1,2,4,5,7,8,9,11,12,14,15,16,18,19,21,22,24,\dots\}\\ Spec(2+\sqrt 2)&=\{3,6,10,13,17,20,23,27,30,34,37,40,44,47,51,\dots\} \end{align}$

观察到 $Spec(2+\sqrt 2)$ 的第 $n$ 个元素恰好比 $Spec(\sqrt 2)$ 的第 $n$ 个元素大 $2n$ ，同时更惊人的是全体正整数是 $Spec(2+\sqrt 2)$ 和 $Spec(\sqrt 2)$ 的不相交并集，我们称这两个谱构成了正整数的一个划分

其证明思路就是对任意正整数 $n$ ，我们计算 $Spec(\sqrt 2)$ 中有多少个元素是 $\leq n$ 的，以及 $Spec(2+\sqrt 2)$ 中有多少个元素是 $\leq n$ 的，然后将两个值相加，如果等于 $n$ ，则命题得证

设 $\alpha$ 是正数， $Spec(\alpha)$ 中 $\leq n$ 的元素个数是
$\begin{align}N(\alpha,n)&=\sum_{k>0}\big[\lfloor k\alpha \rfloor\leq n\big]\\ &=\sum_{k>0}\big[\lfloor k\alpha \rfloor< n+1\big]\\ &=\sum_{k>0}\big[ k\alpha < n+1\big]\\ &=\sum_k [0<k<\frac{n+1}{\alpha}]\\ &=\lceil \frac{n+1}{\alpha}\rceil-1 \end{align}$
在上面的推导中，有两处值得注意，首先有
$m\leq n \Leftrightarrow m<n+1，m,n$ 均为整数
这一步将 $\leq$ 改为 $<$ ，根据性质3，可以将底去掉
同时我们限定 $k>0$ 求和而非 $k\geq 1$ ，这是因为 $(0,\frac{n+1}{\alpha})$ 与 $[1,\frac{n+1}{\alpha})$ 区别的地方是 $\frac{n+1}{\alpha}$ 有可能小于1，前者更加准确

下面我们套用这个公式，计算 $N(\sqrt 2,n)+N(2+\sqrt 2,n)$ 的结果
$\Bigg\lceil\frac{n+1}{\sqrt 2}\Bigg\rceil-1+\Bigg\lceil\frac{n+1}{2+\sqrt 2}\Bigg\rceil-1$
注意到 $\frac{n+1}{\sqrt 2}$ 在n为整数时必定不为整数，于是顶减1正好为底，于是可以化为
$\Bigg\lfloor\frac{n+1}{\sqrt 2}\Bigg\rfloor+\Bigg\lfloor\frac{n+1}{2+\sqrt 2}\Bigg\rfloor$

进一步化为
$\frac{n+1}{\sqrt 2}-\{ \frac{n+1}{\sqrt 2} \}+\frac{n+1}{2+\sqrt 2}-\{\frac{n+1}{2+\sqrt 2}\}$
由于有恒等式
$\frac{1}{\sqrt 2}+\frac{1}{2+\sqrt 2}=1$
所以原式可以化为
$n+1-\{ \frac{n+1}{\sqrt 2} \}-\{\frac{n+1}{2+\sqrt 2}\}$
也就是说只要我们证明
$\{ \frac{n+1}{\sqrt 2} \}+\{\frac{n+1}{2+\sqrt 2}\}=1$
原式也就等于n了
我们设两个非整数 $a=\frac{n+1}{\sqrt 2},b=\frac{n+1}{2+\sqrt 2}$ ，显然有 $a+b=n+1$ ，这两个数的整数部分的和显然是 $n$ ，分数部分的和显然就是1了，故命题得证

底和顶的递归式

含有底或顶的递归关系经常在计算机科学中出现，因为很多以分而治之为基础的算法，会把一个大小为 $n$ 的问题转化为 $n$ 的几分之一(取整)的多个小问题。例如给 $n$ 个记录排序的一种方法是把它们分为两个近乎相等的部分，一部分大小为 $\lceil \frac{n}{2}\rceil$ ，另一部分大小为 $\lfloor \frac{n}{2}\rfloor$ ，显然我们知道 $n=\lceil \frac{n}{2}\rceil+\lfloor \frac{n}{2}\rfloor$ 。在每一部分被分别排序后（切分过的部分自然也可以循环的切分为两部分），通过每一步做至多 $n-1$ 次比较，最后将这些记录合并成最后的排序，这样一来，我们设最终的比较次数最多为 $f(n)$ ，则有

$f(1)=0$
$f(n)=f(\lceil \frac{n}{2}\rceil)+f(\lfloor \frac{n}{2}\rfloor)+n-1,n>1$

这里稍微解释一下为什么两个已排序的几乎等长（其实以最坏情况考虑，等长不等长结果是一样的）数组（为了叙述的习惯，叫数组比较顺口）需要至多 $n-1$ 次比较才能将两者合并为一个已排序的数组。我们惯用的方法是将两个数组两端（或者是最大或者是最小，这里举例用最小的）的元素进行比较，较小的放入新的存储结果的数组并改变这个数组的端点（角标向后移一位），较大的其数组端点保持不变，重复以上步骤直至两个数组中有一个没有元素，将另一个的数组中所有剩余的元素依次序放入新数组，结束整个步骤。显然每次比较会在新数组中填入一个元素，至多 $n-1$ 次比较后，一定会有一个数组元素为空，此时不再需要比较，直接将最后的元素填入新数组就结束了。

这个递归式的解在习题34中，我们提前把答案写出来
$f(n)=\sum_{k=1}^{n}\lceil \lg k\rceil$
其封闭形式的计算如下：
我们设 $m=\lceil \lg n\rceil$ ，则 $f(2^m)=\sum_{k=1}^{2^m}\lceil \lg k\rceil$ ，显然当 $k\in(2^{i-1}+1,2^i]$ 时， $\lceil \lg k\rceil=i$ ，这个区间有 $2^{i-1}$ 个整数，故和式可改写为
$f(2^m)=\sum_{k=1}^{2^m}\lceil \lg k\rceil=\lceil \lg 1\rceil+\lceil \lg 2\rceil+\sum_3^4\lceil \lg k\rceil+\cdots+\sum_{2^{m-1}+1}^{2^m}\lceil \lg k\rceil$
对 $\sum_{2^{m-1}+1}^{2^m}\lceil \lg k\rceil$ 可以化为 $m\times 2^{m-1}$ ，故原式可进一步化为
$f(2^m)=\sum_{k=1}^{m}k2^{k-1}$
这个和式我们第二章有讲，这里直接给出答案
$f(2^m)=\sum_{k=1}^{m}k2^{k-1}=(m-1)2^m+1$

现在我们反过来计算 $f(n)$
要知道 $2^m\geq n$ 的，所以我们有
$f(n)=f(2^m)-(2^m-n)m$
注意这里 $(2^m-n)m$ 式中的 $(2^m-n)$ 表示我们多计算了多少次， $m$ 代表此时对应的 $\lceil \lg k\rceil$ 值
所以最后化简得到
$f(n)=mn-2^m+1,m=\lceil \lg n\rceil$
也就是说最终是一个比较次数为 $n\lg n$ 复杂度的算法

如果感兴趣的话，我们再来看一下如何证明这个答案就是我们需要的答案

image.png

绕了这么大一圈，我们回头看一下第一章的约瑟夫问题

$J(1)=1$
$J(2n)=2J(n)-1,n>0$
$J(2n+1)=2J(n)+1,n>0$

此时我们可以更准确的将最基本的情况归纳为以下递归式

$J(1)=1$
$J(n)=2J(\lfloor \frac{n}{2}\rfloor)-(-1)^n,n>1$

同时如果我们把条件变成每隔2人杀死一人，那么我们最终得到递归式

$J_3(n)=\Bigg(\bigg\lceil\frac{3}{2}J_3\Big(\Big\lfloor \frac{2}{3}n\Big\rfloor\Big)+a_n\bigg\rceil \mod n\Bigg)+1$
当 $n\mod 3=0,1,2$ 时 $a_n=-2,1,-\frac{1}{2}$
这个递归式有着分数、底和顶，想要化简不是一件容易的事，我们在下面给出一种更好的解决方案，同时附上其相应的java代码

我们规定每当循环中，一个人幸存了，就把他的号码替换为最大的号码加1，这样1号，2号跳过，于是变成了 $n+1,n+2$ 号，3号被杀，4号5号变成了 $n+3,n+4$ ，以此类推... $3k+1$ 和 $3k+2$ 号变成 $n+2k+1,n+2k+2$ 号。最终是 $3n$ 号被处死，比如当 $n=10$ 时，有下图

image.png

所以如果我们能算出标号为的人最初的号码，就可以获得我们想要的答案

当某时刻任意一个还活着的人的号码为 $N$ 时，如果 $N>n$ ，则他必定有一个以前的号码，则根据我们上文的规定，有 $N=n+2k+1$ 或者 $N=n+2k+2$ ，于是有 $k=\lfloor (N-n-1)/2\rfloor$ ，而这个人之前的号码分别可能为 $3k+1$ 或 $3k+2$ ，用一个式子来表示这两种情况可以通过 $3k+(N-n-2k)=k+N-n$
再把 $k$ 用 $N,n$ 表示，则上式可以写做 $\lfloor (N-n-1)/2\rfloor+N-n$ ，之后只需要不断把这个之前的号码以如上步骤循环迭代下去，直至这个号码 $\leq n$ ，则这个号码就是最后活下去的人刚开始的编号
综上我们可以写出伪代码

$\begin{split}&N=3n;\\ &while \quad &N>n\\ &do\quad &N=\lfloor (N-n-1)/2\rfloor+N-n\\ &J_3(n)=N \end{split}$

虽然我们以上面的方式去设计算法，肯定是可以解出最后的答案的，但这个式子还是太复杂，我们尝试去简化这个算法
我们用 $D=3n+1-N$ 来替换 $N$ 作为迭代的值，有 $N=3n+1-D$ ，则我们根据上文中 $N$ 的迭代式从而写出 $D$ 的迭代式
$D=3n+1-\bigg(\bigg\lfloor\frac{(3n+1-D)-n-1}{2}\bigg\rfloor+(3n+1-D)-n\bigg)\\=n+D-\bigg\lfloor\frac{2n-D}{2}\bigg\rfloor=D-\bigg\lfloor\frac{-D}{2}\bigg\rfloor=D+\bigg\lceil\frac{D}{2}\bigg\rceil=\bigg\lceil\frac{3}{2}D\bigg\rceil$

此时我们将算法改写为：
$\begin{split}&D=1;\\ &while &D\leq 2n\\ &do &D=\bigg\lceil\frac{3}{2}D\bigg\rceil\\ &J_3(n)=3n+1-D \end{split}$

在上一种算法中， $N$ 从 $3n$ 迭代减到小于等于 $n$ ，算法结束
而现在这种算法， $D$ 从1迭代增到大于 $2n$ ，算法结束

事实上，我们可以通过类似的推理获得一个结论：
当每隔 $q-1$ 个人就杀掉一人，幸存者 $J_q(n)$ 可以使用以下方式计算
$\begin{split}&D=1;\\ &while &D\leq (q-1)n\\ &do &D=\bigg\lceil\frac{q}{q-1}D\bigg\rceil\\ &J_3(n)=qn+1-D \end{split}$
注意到这种算法的复杂度为
$\log_{\frac{q}{q-1}}(q-1)n$
使用换底公式可以化为
$\frac{\ln(q-1)n}{\ln\frac{q}{q-1}}=\frac{\ln(q-1)+\ln n}{\ln q-\ln (q-1)}$
显然除了 $\ln n$ 之外，其余都是常数，所以复杂度是 $\ln n$

下面我们看一下常见的解约瑟夫问题的算法，同时我们对其复杂度进行分析
这里我们用 $m$ 表示数到几的人被杀， $n$ 表示一共多少人
先看一种最普通的解法：通过对环形单向链表的节点进行删除获得最后结果，其具体步骤如下：

如果链表节点数为1，或者m的值小于1，则直接返回
在环形单向链表中不断循环遍历每个节点，在此过程中，让节点报数
当报数从1到m时，删除报数为m的节点
删除节点后，注意要保持链表的环形状态

我们看一下具体的代码实现

最后编辑于：2019.09.28 21:24:49

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,012评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,628评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,653评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,485评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,574评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,590评论 1赞 293
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,596评论 3赞 414
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,340评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,794评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,102评论 2赞 330
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,276评论 1赞 344
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,940评论 5赞 339
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,583评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,201评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,441评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,173评论 2赞 366
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,136评论 2赞 352

具体数学第三章笔记及习题解答

底和顶

底和顶的应用

底和顶的递归式

推荐阅读更多精彩内容