分类目录归档:Mathematics

There is only one problem to solve——汉诺塔问题

汉诺塔问题的描述如下,汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘,只能移动在最顶端的圆盘。

那么这里我们也先来思考最简单的情况(变量当然是盘子的个数\(n\)啦),那么最简单的就是\(n=1\)了(当然,\(n=0\)也可以算是一种情况,不过没必要分析了)

不妨假设原始的柱子为\(A\),目标柱子为\(C\),

hanoi-tower-1

此时直接将盘子从\(A\)柱移动到\(C\)柱即可。

继续阅读There is only one problem to solve——汉诺塔问题

There is only one problem to solve——\(2^k\times 2^k\)棋盘覆盖问题

\(2^k\times 2^k\)棋盘覆盖问题描述如下,给出\(k\)的值,得到一块\(2^k\times 2^k\)大小的棋盘,棋盘上有一格是特殊方格。随后给出如下4种L型的骨牌,要求使用这四种L型的骨牌覆盖给定棋盘上的,除特殊方格以外的所有格子,并且任何两个L型骨牌不得重叠覆盖。

L

继续阅读There is only one problem to solve——\(2^k\times 2^k\)棋盘覆盖问题

从百鸡问题到数学思维

鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、母、雏各几何?

——张丘建《算经》

这里从最最简单的算法开始一步一步讲如何优化,主要涉及的还是数学,Roger Bacon曾在《Opus Majus》写到

It is impossible to know things of this world unless you know mathematics.

——Roger Bacon《Opus Majus》

虽然这篇 post 会一直讲百鸡问题,但是主要还是想以此记录一些在解决某些问题是可能用到的数学思维,并不是只为了做百鸡问题。当然,我的数学也不怎么样qwq不过至少在这道题上,应用数学之后的算法在时间上的减少是比较明显的。

这篇 post 由以下几个部分构成

继续阅读从百鸡问题到数学思维

Congested network笔记(4)

第二个谬误的思考方式是在估计和进度安排中使用的工作量单位: 人月。成本的确随开发产品的人数和时间的不同有着很大的变化, 进度却不是如此。因此我认为用人月作为衡量一项工作的规模是一个危险和带有欺骗性的神话。 它暗示着人员数量和时间是可以相互替换的。……从而,添加更多的人手,实际上是延长了而不是缩短了时间。

——人月神话

继续阅读Congested network笔记(4)

Congested network笔记(3)

上一篇 Congested network笔记(2) 的最后,我们把问题变成了变分不等式的求解,那么这两个变分不等式在什么情况下存在解,且解唯一呢?

$$\left\{\begin{align}\frac{\partial\mathcal{Z(F)}}{\partial\underline{\mathcal{F}}}\cdot(\mathcal{F}-\underline{\mathcal{F}})&\ge 0&\forall \mathcal{F}\in S&\text{  最优解}\\
\mathcal{C}(\mathcal{F}^*)\cdot(\mathcal{F}-\mathcal{F}^*)&\ge 0&\forall \mathcal{F}\in S&\text{ 均衡解}\end{align}\right.$$

继续阅读Congested network笔记(3)

Congested network笔记(1)

人类天性是自私的,而经济行为植根于此"事实"之上。博弈论看似也反映了此种假设。在博弈论最初的形式中,博弈论数学描述"理性的"行为,本质上是将"理性"和"自私"当作同义词。但按照今天的解释,博弈论并非假设人类总是表现得自私——或理性。博弈论告诉你如果人类确实表现得自私或理性,会是怎么样的情形。

——A BEAUTIFUL MATH
John Nash, Game Theory
AND THE MODERN QUEST FOR A CODE OF NATURE

继续阅读Congested network笔记(1)

Using generating functions to solve recurrence relations

前几天在《Discrete Mathematics and its Applications》上看到了这三道题,均要求使用生成函数求解,题目如下:

  1. ak = ak-1 + 2ak-2 + 2k, a0 = 4, a1 = 12
  2. ak = 4ak-1 - 4ak-2 + k2, a0 = 2, a1 = 5
  3. ak = 2ak-1 - 3ak-2 + 4k + 6, a0 = 20, a1 = 60

昨天在StackExchange[1]上询问之后,今天花了一早上的时间做了一遍,下面就是完整的步骤和总结。

  • Problem 1

 ak=ak-1+2ak-2+2k a0=4 a1=12

我们首先令f(x)为序列{ak}的生成函数,即

fx=k0akxk

然后我们对递推关系式(也就是上面大括号中的第一个式子)中的每一项都乘以xk,得

akxk=ak-1xk+2ak-2xk+2kxk

接着对每一项都取k从2开始的和

k2akxk=k2ak-1xk+k22ak-2xk+k22kxk

= k2ak-1xk+2k2ak-2xk+k22kxk

在这之后我们将对每一项都进行变形,变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

k2akxk=k2akxk+a1x+a0-a1x-a0

=k0akxk-a1x-a0

= fx-4x-12


k2ak-1xk=xk2ak-1xk-1

= xk1akxk

= xk0akxk-a0

= xfx-4


k2ak-2xk=x2k2ak-2xk-2

= x2k0akxk

= x2fx


k22kxk=k02kxk-2x

=11-2x-1-2x-1

现在我们将变形后的式子替换回去

fx-4x-12=xfx-4+2x2fx+11-2x-2x-1
合并同类项,然后分解分式多项式得

fx=23·11-2x2+389·11-2x-89·11+x

根据生成函数与序列{ak}的关系,可得

ak=23C2+k-12-12k+389·2k-89·-1k

=231+k2k+389·2k-89·-1k

=449·2k+23k·k3-89·-1k
至此,我们解出了满足递推关系和初始条件的解
  • Problem 2

 ak=4ak-1-4ak-2+k2 a0=2 a1=5

我们首先令f(x)为序列{ak}的生成函数,即

fx=k0akxk

然后我们对递推关系式(也就是上面大括号中的第一个式子)中的每一项都乘以xk,得

akxk=4ak-1xk-4ak-2xk+k2xk

接着对每一项都取k从2开始的和

k2akxk=k24ak-1xk-k24ak-2xk+k2k2xk

= 4k2ak-1xk-4k2ak-2xk+k2k2xk

在这之后我们将对每一项都进行变形,变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

k2akxk=k2akxk+a1x+a0-a1x-a0

=k0akxk-a1x-a0

= fx-5x-2


k2ak-1xk=xk2ak-1xk-1

= xk1akxk

= xk0akxk-a0

= xfx-2


k2ak-2xk=x2k2ak-2xk-2

= x2k0akxk

= x2fx

最后的这个k2的和式处理稍微复杂一些

k2k2xk=k0k2xk-x

=xk0k2xk-1-x

=xk0kkxk-1-x

化简到这一步之后,下面我们对和式积分,然后再求导

=xk0kxk'-x

=xxk0kxk-1'-x

再来一次

=xxk0xk''-x

到了这一步之后就简单了

=xx11-x''-x

=xx1-x2'-x

=x1+x1-x3-x

现在我们将变形后的式子替换回去

fx-5x-2=4xfx-2-4x2fx+x1+x1-x3-x

合并同类项,然后分解分式多项式得

fx=21-x3+51-x2+131-x+61-2x2-241-2x

根据生成函数与序列{ak}的关系,可得

ak=2C3+k-13-1+5C2+k-12-1+13+6C2+k-12-12k-24·2k

=22+k1+k2+51+k+13+61+k2k-24·2k

展开、合并同类项

=2+13+5+6·2k-24·2k+3k+5k+6k·2k+k2

=20-18·2k+8k+6k·2k+k2

至此,我们解出了满足递推关系和初始条件的解
  • Problem 3

Problem 3的和处理方式前面的Problem 1十分相似,这里不再给出解答。
  • 总结

一般来讲,使用生成函数求解递推关系第一步是在递推关系式的各项上乘以xk,然后取k>=m(m为递推关系式的阶数,即如果是二阶递推关系式m就取2)时的和式并分别变形,最后通过生成函数f(x)与序列ak的关系解出。

  • References

[1]: How to solve these recurrence relations bu using generating function