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

問題

下の図のようにリング状に１－８の数字が並んでいます。

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

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

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

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

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

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

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

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

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

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

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

■RingNumber.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace RingNumberGcdSL {
	public class RingNumberGcd {
        private int _baseNumber;

// ８ケタの整数から得られる16個の数の最大公約数は
		public int Solve(int baseNumber, Action<int> callBack) {
			int gcd = 0;
            int a = baseNumber;
            callBack(a);
			foreach (var b in GetNumbers(a).Skip(1)) {
                callBack(b);
				gcd = Gcd(a, b);
				a = gcd;
			}
			return gcd;
		}

// ８桁の整数から、１６個の８ケタの整数を列挙する。
		private IEnumerable<int> GetNumbers(int num) {
			string s = num.ToString();           	        // 右回り用
			string rs = new string(s.Reverse().ToArray());  // 左回り用
			return _GetNumbers(s).Concat(_GetNumbers(rs));
		}

// GetNumbersの下請けメソッド 右回りの８つの数を列挙する
		private IEnumerable<int> _GetNumbers(string s) {
			yield return int.Parse(s);
			for (int i = 0; i < 7; i++) {
				s = RotateShift(s);
				yield return int.Parse(s);
			}
		}

// 右へローテートシフト
		private string RotateShift(string s) {
			string s1 = new string(s.Skip(1).ToArray());
			return s1 + s[0];
		}

// ユークリッドの互除法によるGCD 
		static int Gcd(int a, int b) {
			if (a < b)
				return Gcd(b, a);  // 引数を入替えて自分を呼び出す  
			int d = 0;
			do {
				d = a % b;
				a = b;
				b = d;
			} while (d != 0);
			return a;
		}
	}
}

■MainPage.cs

using System.Windows;
using System.Windows.Controls;

namespace RingNumberGcdSL {
    public partial class MainPage : UserControl {
        public MainPage() {
            InitializeComponent();
        }

private void button1_Click(object sender, RoutedEventArgs e) {
            listBox1.Items.Clear();
            RingNumberGcd dng = new RingNumberGcd();
            textBlock1.Text = dng.Solve(GetNumber(), Action).ToString();
        }

// 8桁の数が求められるたびに呼び出される。
        private void Action(int n) {
            listBox1.Items.Add(n.ToString());
        }

// ８つのTextBoxの値から８桁の整数を得る。
        private int GetNumber() {
            string s = "";
            for (int i = 1; i < 9; i++) {
                string name = "baseNum" + i.ToString();
                TextBox obj = this.FindName(name) as TextBox;
                s += obj.Text;
            }
            return int.Parse(s);
        }

private void baseNum_GotFocus(object sender, RoutedEventArgs e) {
            TextBox tb = sender as TextBox;
            tb.SelectAll();
        }
        
    }
}

■MainPage.xaml

Gushwell's C# Programming Page

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

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