リングナンバーの最大公約数

 問題

下の図のようにリング状に1-8の数字が並んでいます。

 1から8までの任意の数字からはじめ、右回りあるいは左回りに数字を取り出し8ケタの数字を作ります。 全部で、16個の数字が得られますが、この最大公約数を求めてください。


結局、この問題は、
 12345678
 23456781
 34567812
 ...
 87654321
 76543218
 ...

の16個の数字の最大公約数を求める問題です。

Gcd(a, b, c) = Gcd(Gcd(a, b), c)  

が成り立つので、8ケタの数字を求めるメソッドと2つの値の最大公約数を求めるメソッドを 作成できれば、この問題を解くことができます。なので、これを解くプログラムはそれほど難しくありませんね。

この問題は、答えが9の倍数であることは簡単にわかるのですが、はたして、それが何倍なのかは、僕にはすぐにはわかりませんでした。 上記のプログラムを実行すれば、答えは、9であることが分かります。紙と鉛筆だけで、 簡単に 9 であることを証明できそうな気もするのですが....

簡単にプログラムの説明をします。整数を受け取り、そこから、16個の数を 生成するGetNumbers メソッドを作成しました。汎用性を持たせるために、12345678 という数値以外の 値も受け取れるようにしています。

上記プログラムでも、TextBoxの数値を変更することで、12345678 以外の値にすることができます。重複のチェックはしていません。

この16個の数値を得るのに、右回りで得られる8個の数を求めるメソッドを作り、左まわりは、これに反転した値を与えることで、求めています。 随所でLINQ to Objectの拡張メソッドを 利用しています。

最大公約数を求める Gcdメソッドは、「最大公約数」のページで示したものと同じです。

以下、C#+Silverlightのコードです。

■RingNumber.cs
 

■MainPage.cs


■MainPage.xaml