流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【マトリックス】変数aとbを入れ替えるのに、cは要るのか問題!?【増殖するb】

変数abの入れ替えとエージェントスミスについて

 変数abに異なる値が入っていて、それを入れ替えるアルゴリズムを書きましょう……というのは、プログラミングの入門書にありがちな問題で、ついさっきあるプログラミング言語の本を見ていたら、また書いてあった。

では、この問題の模範的な"間違え方"から紹介しよう。それが、
 ①abに値を入力
 ②a=b
 ③b=a
 ④abを出力
という解答*1。この間違え方をすると、本の著者や解答を知っている人にニヤニヤされるかもしれないので要注意だ!
 落とし穴は②でabの値を代入しているところで、代入した瞬間にabも全部bの値になってしまい、aの値が跡形もなくなっている。いわば、このbマトリックスのエージェントスミスなのだ。
 このようなスミスの無限増殖を防ぐ方法として、たぶん一番よく書いてある解法は、余分な変数cを用意して、
 ①abに値を入力
 ②c=a
 ③a=b
 ④b=c
 ⑤abを出力
として、aの値が上書きされる前にcに避けておけばいい。要は、cがネオである。
さて、このcないしネオは常に必要なのだろうか?そんなことを何となく考えていたら、cを使わない第2の解答が存在することに気づいた。ただし、a,bが整数や実数等の数値である場合に限るけど。この解答は、厚めの本とか開けるとたぶん書いてありそうだけど……あえて紹介してみる!

cを使わない解法とネオの休日

cを使わないでabを入れ替えるには、どうしたらいいか?
それには、aを完全にbに置き換えるのではなく、abの両方の情報を持つようにしておけばいい。つまり、aに半分だけスミス分bを入れる。
 a=a+b
ここまで来ればもう簡単なので、解答を書いてみる。わかりやすくするため、abに最初に入っている値をA,Bとして、各ステップでa,bに入っている値もカッコで囲って書いておく。
 ①a(=A),  b(=B)
 ②a=a+b(=A+B),  b(=B)
 ③a(=A+B),  b=a-b(=A+B-B =A)
 ④a=a-b(=A+B-A =B),  b(=A)
 ⑤abを出力
という風に、変数c(ネオ)が休んでいても、abの値は無事に入れ替えられた(Mission complete!)

*1:プログラミングで=は左辺の変数に右辺の変数の値を代入するという意味。