Head Pic: Absolute Duo, heavenly ass, barefoot / おやすみなさい - pixiv

从两个分数$(\frac{0}{1},\frac{1}{0})$出发,在相邻两个分数$\frac{m}{n},\frac{m'}{n'}$之间插入$\frac{m+m'}{n+n'}$,便可以构造出满足$m\perp n$的全部非负分数$\frac{m}{n}$的集合。

例如:

$\frac{0}{1},\frac{1}{1},\frac{1}{0}$

$\frac{0}{1},\frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0}$

$\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1},\frac{3}{2},\frac{2}{1},\frac{3}{1},\frac{1}{0}$

画成树状便是$SBT$。

约定与命名

用字母$L$和$R$表示从某一子树向左或向右走一步,这样每一个位置都有一串$LR$字符唯一对应。

比如:$LRRL:\frac{1}{1}->\frac{1}{2}->\frac{2}{3}->\frac{3}{4}->\frac{5}{7}$。

并将$\frac{1}{1}$记作$I$。

问题

  • 甲:对于$\forall m,n\in N^+,m\prod n$,则与$\frac{m}{n}$对应字符串$S$是什么?
  • 乙:甲的逆命题:对于给定字符串$S$,则与它对应的分数是什么?

求解

对乙:

不妨令$f(s)=$与$s$对应的分数,比如$f(LRRL)=\frac{5}{7}$

可以发现在计算过程中需要保持两个分数共计$4$个变量,那么最好的方式就是构造$2\times2$矩阵:

$$ M(S)=\left[ \begin{matrix} n & n' \\ m & m' \end{matrix} \right] $$

显然

$$ M(I)=\left[ \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right] $$

则向左一步就是用$n+n'$替换$n'$,$m+m'$替换$m'$。(记住$\frac{m}{n},\frac{m+m'}{n+n'},\frac{m'}{n'}$)

$$ M(SL)=\left[ \begin{matrix} n & n+n' \\ m & m+m' \end{matrix} \right]=\left[ \begin{matrix} n & n' \\ m & m' \end{matrix} \right]\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right]=M(S)\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right] $$

透过$2\times2$矩阵乘法

$$ \left[\begin{matrix}a&b\\c&d\end{matrix}\right]\left[\begin{matrix}w&x\\y&z\end{matrix}\right]=\left[\begin{matrix}aw+by&ax+bz\\cw+dy&cx+dz\end{matrix}\right] $$

便有上述结论

同理

$$ M(SR)=\left[ \begin{matrix} n+n' & n \\ m+m' & m \end{matrix} \right]=M(S)\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right] $$

不妨令

$$ L=\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right],R=\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right] $$

则$M(S)=S$,例如

$$ M(LRRL)=LRRL=\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right]\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right]\left[ \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right]\left[ \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right]=\left[ \begin{matrix} 3 & 4 \\ 2 & 3 \end{matrix} \right] $$

故$f(S)=f(M(S))=\frac{m+m'}{n+n'}$

对甲:

这棵树去除$\frac{1}{0},\frac{0}{1}$后就是一棵标准的二叉搜索树(Binary Search Tree,BST)​,直接跑一个二叉查询即可。

S=I
while(m / n != f(s))
    if(m / n < f(s)) S += L
    else S += R

参考文献

Ronald L. Graham, 《具体数学》(2017),96-101

最后修改:2020 年 01 月 29 日 05 : 05 PM