- マックナゲット数を説明した。
- マックナゲット数の判定ロジックをEmacs Lispで実装した。
- 現在のマックナゲットのピースの数とは異なるため、そのままロジックを適応することはできない。
O’Reilly Japanから出版されているアルゴリズムパズルを読んでいる。 この書籍ではたくさんのアルゴリズムを紹介/解説している。 その中でマックナゲット数というものがあった。
マクドナルドで販売しているマックナゲットのメニューの組み合わせで出来る ナゲットの個数の総和として表現できる数をマックナゲット数という。
書籍内ではマックナゲット数の素となる数は以下となっていた。
- 4 (4個入り)
- 6 (6個入り)
- 9 (9個入り)
- 20 (20個入り)
マックナゲット判定のロジックは再帰を使う方法と使わない方法の2種類がある。 詳しくはアルゴリズムパズルの書籍を読んでもらいたい。
今回はを再帰を使う方法をEmacs Lispで実装してみた。
(defvar mcdonald-primitive-nugget-number-list '(4 6 9 20))
(defvar mcdonald-well-known-non-nugget-number-list '(1 2 3 5 7 11))
(defvar mcdonald-well-known-non-nugget-number-limit 15)
(defun mcdonald-is-mcd-nugget-number (num)
(interactive "nNumber: ")
(if (<= num mcdonald-well-known-non-nugget-number-limit)
(not (member num mcdonald-well-known-non-nugget-number-list))
(mcdonald-is-mcd-nugget-number (- num 4))))あまりエレガントではない。 mcdonald-primitive-nugget-number-listで指定している20は、4個入り5箱注文すれば良いので省略していいかもしれない。 Emacs Lispは末尾再帰最適化がないので引数に2000などを渡すと以下のような再帰エラーが発生してしまう。
Lisp nesting exceeds ‘max-lisp-eval-depth’
mcdonald-primitive-nugget-number-list に任意の自然数のリストを指定した時に
ある数xがナゲット数かどうかを判定できるようなアルゴリズムにしておきたい。
そういうアルゴリズムはあるのだろうか。
2020年05月16日現在に日本マクドナルドによって販売されている マックナゲット(チキンマックナゲット)は以下となる。
- チキンマックナゲット5ピース
- チキンマックナゲット15ピース
そのため書籍に書かれていた条件とは異なる。 上で定義した関数は書籍を元にしている。 そのため現在のマックナゲット数の判定はできない。