以前、カプレカ数を計算しました。
ネタ元の動画。最大から最小を引いて元通り
カプレカ数は桁を並び替えて最大にしたものから最小にしたものを引くと元の値に等しくなる数です。前回の方法は実際にひとつずつ桁を並び替えて最大値と最小値を求めて計算しました。桁を並び替えて最大値から最小値をひくと9の倍数になるという性格を利用しても時間がかかりました。
しかし！ ここにヒントがあります。
Contents
重複組み合わせをつかって時間短縮
時間がかかっていたのは無駄な処理をしていたからでした。123も231も321も桁を並び替えて最大値から最小値を引いたときの値は同じです。にもかかわらず全部を処理していたわけですから時間もかかるでしょう。
そこで今回は、0～9までの重複組み合わせを作成してさきに両者の差を求めてしまいます。そしてその値を並べ替えて最大にしたものが最初の最大値と同じならカプレカ数とみて間違いないということになります。
では、さっそくやってみましょう。
まずn桁の0～9までの重複組み合わせを取得するメソッドを作成します。
最初に0～9までの整数が入ったリストを用意します。そして左に0～9までの整数を付加していきます。このときに付加する値は左の値よりも小さなもの以外の整数にします。これで重複組み合わせの完成です。
|
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 { List<List<int>> GetOverlapCombination(int keta) { List<List<int>> list = new List<List<int>>(); for(int i = 0; i < 10; i++) { List<int> vs = new List<int>(); vs.Add(i); list.Add(vs); } return GetOverlapCombination2(list, keta); } List<List<int>> GetOverlapCombination2(List<List<int>> list, int keta) { if(list[0].Count > keta -1) return list; List<List<int>> ret = new List<List<int>>(); foreach(List<int> vs in list) { for(int i= vs[0]; i< 10; i++) { List<int> vs1 = vs.ToList(); vs1.Insert(0, i); ret.Add(vs1); } } return GetOverlapCombination2(ret, keta); } } |
次に数字のリストを入れ替えることで最大にしたり最小にするメソッドを作成します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public partial class Form1 : Form { long GetMax(List<int> vs) { vs = vs.OrderByDescending(x => x).ToList(); string str = ""; foreach(int i in vs) { str += i.ToString(); } return long.Parse(str); } long GetMin(List<int> vs) { vs = vs.OrderBy(x => x).ToList(); string str = ""; foreach(int i in vs) { str += i.ToString(); } return long.Parse(str); } } |
あとは最大値から最小値を引いて得られた値を並べ変えて最大値と一致するかどうか確認します。
|
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 34 |
public partial class Form1 : Form { List<long> GetKaprekars(int keta) { // keta桁の0～9までの重複組み合わせを取得する List<List<int>> lists = GetOverlapCombination(keta); List<long> rets = new List<long>(); foreach(List<int> list in lists) { long val = GetMax(list) - GetMin(list); // 0は除外する if(val == 0) continue; // valが GetMax(list)と同じか確認する string str = val.ToString(); char[] vs = str.ToArray(); vs = vs.OrderByDescending(x => x).ToArray(); string newstr = new string(vs); // 指定した桁と違うものは取得しない if(newstr.Length != keta) continue; // 大きい順に並べ変えて最大値と一致するならカプレカ数 if(long.Parse(newstr) == GetMax(list)) rets.Add(val); } // 小さい順に並べ変えて結果を返す return rets.OrderBy(x => x).ToList(); } } |
ではやってみましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public partial class Form1 : Form { private void button1_Click(object sender, EventArgs e) { string str = ""; // 8桁までならすぐに終わります。12桁まで調べてみました。 for(int i =1; i<= 12; i++) { List<long> rets = GetKaprekars(i); str += i.ToString() + "桁のカプレカ数\n"; if(rets.Count == 0) str += "なし\n"; foreach(long value in rets) str += value.ToString("#,0") + "\n"; str += "\n"; } richTextBox1.Text = str; } } |
実行結果
なし
2桁のカプレカ数
なし
3桁のカプレカ数
495
4桁のカプレカ数
6,174
5桁のカプレカ数
なし
6桁のカプレカ数
549,945
631,764
7桁のカプレカ数
なし
8桁のカプレカ数
63,317,664
97,508,421
9桁のカプレカ数
554,999,445
864,197,532
10桁のカプレカ数
6,333,176,664
9,753,086,421
9,975,084,201
11桁のカプレカ数
86,431,976,532
12桁のカプレカ数
555,499,994,445
633,331,766,664
975,330,866,421
997,530,864,201
999,750,842,001
12桁だけずいぶんたくさんありますね。では13桁はもっとあるのかと思って調べてみると・・・
8,643,319,766,532
1個だけでした。
