マクロツイーター

はてダから移行したばかりなので表示が崩れてますが、そのうちに直せればいいのに(えっ)

TeX での末尾再帰 (5)

これまで、「再帰」を中心として TeX における実行制御について色々と述べている。実行制御というのはプログラミング言語の知識の中で基礎を成すものであるが、TeX 言語においては、その使われ方の特殊性ゆえに、相当な TeX のコーディングの経験がある人でも「実行制御が苦手」という人が多いと私は思っている。「自分は TeX 言語をある程度使い慣れている」と思っている人は、ここで改めて「実行制御をどこまで使いこなせるか」を確かめてみるのもいいであろう。そこで、FizzBuzz や NabeAzz のような「できて当然」の問題ではなく、やや難しめあるいはかなり難しい問題をいくつか挙げておく。

さて、あなたはどこまで TeX を使えますか……?

問題 1

以下の条件を満たすマクロ \doFibonacci を実装せよ。

  • \doFibonacci{<整数n>}(n > 0 を仮定してよい)を実行すると、n 番目のフィボナッチ数 F(n) を整数レジスタ \countResult に代入する。
  • F(n) の定義は以下の通り: F(1) = F(2) = 1; F(n) = F(n−1) + F(n−2) (n > 2)
  • n の線形時間(O(n))で完了する計算方法を用いること。*1

実行例:

\doFibonacci{10}
\showthe\countResult %=> 55
\doFibonacci{40}
\showthe\countResult %=> 102334155

問題 2

以下の条件を満たすマクロ \kanjinumber を実装せよ。

  • \kanjinumber{<整数n>} は n の日本語での数詞を漢字で出力する。
  • 1 ≦ n ≦ 9999 を仮定してよい。

実行例:

\kanjinumber{2011} % 「二千十一」を出力
\kanjinumber{1999} % 「千九百九十九」を出力

(発展問題) 完全展開可能になるように実装せよ。

実行例:

\edef\test{\kanjinumber{2011}}
\show\test %=> macro:->二千十一

問題 3

以下の条件を満たすマクロ \reverse を実装せよ。

  • \reverse{<文字列>} は文字列を逆順にしたものを出力する。
  • 文字列は英字(A〜Z、a〜z)のみからなると仮定してよい。

実行例:

\reverse{live} % 「evil」を出力
\reverse{a} % 「a」を出力

(発展問題 1) 文字列に空白を含めても正しく動作するようにせよ。

(発展問題 2) さらに完全展開可能になるように実装せよ。

実行例:

\edef\test{\reverse{live saw nametag}}
\show\test %=> macro:->gateman was evil

問題 4

葉のラベルに整数をもつ二分木(内部節点は必ず 2 つの子を持ちラベルを持たない)を以下のような文字列で表す。

  • 整数 n をラベルとする葉を n(の 10 進表記)で表す。
  • 2 つの節点(内部節点または葉)AB を子とする内部節点を [A|B] で表す。

例えば、下の図のような木 T は以下の文字列で表される。

[[[9|2]|6]|[4|[15|[2|4]]]]

このような木の文字列表現を引数にとって以下の動作をするマクロを実装せよ。(「葉の深さ」とはその葉と根の間にある枝の個数、「木の深さ」は「葉の深さ」の最大値。)

  • (1) \sumLeaves{<木T>}T の葉のラベルの総和を \countResult に代入する。
  • (2) \treeDepth{<木T>}T の深さを \countResult に代入する。
  • (3) \sumLeavesWithin{<木T>}{<整数d>}T がもつ深さが d 以下の葉のラベルの総和を \countResult に代入する。

例に挙げた木の場合、以下のようになるはずである。

\sumLeaves{[[[9|2]|6]|[4|[15|[2|4]]]]}
\showthe\countResult %=> 42
\treeDepth{[[[9|2]|6]|[4|[15|[2|4]]]]}
\showthe\countResult %=> 4
\sumLeavesWithin{[[[9|2]|6]|[4|[15|[2|4]]]]}{2}
\showthe\countResult %=> 10

〔追記:2012-01-16〕 よく考えると、上記の表現形式では実装が複雑になるのであった。従って、[A|B] の形式の代わりに {A|B} (波括弧)を用いてもよいことにする。

問題 5

整数のリスト [a1, a2, ..., an] を「/a1/a2//an/」という形で表すことにする。以下の動作をするマクロを実装せよ。

  • \sortList{<リスト>} は引数のリストを昇順にソートしたリスト(の表現)をマクロ \result として定義する。
\sortList{/3/1/4/1/5/9/}
\show\result %=> macro:->/1/1/3/4/5/9/

*1:要するに、F() の再帰的定義(指数時間かかる)をそのまま使ってはいけないということ。実際の実行時間は TeX の実装を知らないと解析できないであろう。