ネタに困ったので他人様の動画から。
プログラミングでカプレカ数を計算してみる
この動画によると桁を並び替えて最大にしたものから最小にしたものを引くと元の値に等しくなる数をカプレカ数というそうです。
そこでその数がカプレカ数であるかどうかを調べるメソッドを作成しました。
考え方は数を一旦Charの配列に変換して大きい順または小さい順に並べ替えて差を計算すればカプレカ操作ができます。
桁を並び替えて最大になるものと最小になるものは以下の方法で求めることができます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int GetMin(int i) { string str = i.ToString(); // 文字列に変換 char[] chars = str.ToArray(); // 配列に変換 char[] chars2 = chars.OrderBy(x => x).ToArray(); // 小さい順に並べ替える string str2 = new string(chars2); // 文字列に変換 return int.Parse(str2); // 整数に変換 } int GetMax(int i) { string str = i.ToString(); char[] chars = str.ToArray(); char[] chars2 = chars.OrderByDescending(x => x).ToArray(); string str2 = new string(chars2); return int.Parse(str2); } |
あとは i == GetMax(i)-GetMin(i) かどうか調べるだけです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { List<int> rets = new List<int>(); for(int i = 100; i<= 999999; i++) { if(IsKaprekar(i)) { rets.Add(i); } } foreach(int i in rets) MessageBox.Show(i.ToString()); } bool IsKaprekar(int i) { if(i == GetMax(i) - GetMin(i)) return true; else return false; } // 以下は上記のとおり // int GetMax(i) // int GetMin(i) } |
どのくらい存在するのか?
2桁(ただし0は除く)の場合、カプレカ数は存在しません。3桁と4桁はそれぞれひとつだけです。5桁になるとたくさんあるのかなと思ったらひとつも存在しません。6桁は2つ存在します。
桁数を増やすと当然処理にかかる時間は長くなります。6桁ならまだなんとかなりますが、7桁になるとすぐには終わりません。
処理を速くするには?
たとえば6桁の任意の整数について考えると、最大の整数は
100000a + 10000b + 1000c + 100d + 10e + f(ただし 9≧a≧b≧c≧d≧e≧f≧0)
最小の整数は
100000f + 10000e + 1000d + 100c + 10b + a
になります。
その差は
99999a + 9990b + 900c – 900d – 9990e – 99999f
となります。
これは
= 9(11111a + 1110b + 100c + 100d + 1110e + 11111f)
と変形できるので9の倍数であることがわかります。
それ以外の桁数でも同じように考えると同様の結果になるので、カプレカ数が存在するとすればそれは9の倍数です。
そこでIsKaprekarメソッドを以下のように改良すれば処理速度が速くなります。
1 2 3 4 5 6 7 8 9 10 |
bool IsKaprekar(int i) { if(i % 9 != 0) return false; if(i == GetMax(i) - GetMin(i)) return true; else return false; } |