Q&A
あまりスマートではないですが暫定的に9桁まで出してみました。
全対象を計算させずに推測に基づくループ範囲の抽出とカットとで速くはなりましたが本当に正しいかは微妙です。
どちらにしてもこれ以上の桁数増加や速度upは限界なのかなと思います。
やりたいこと
2つのn桁の数字の積から作られる最大の回文数を求めたい
やったこと
例題
2つの2桁の数字の積から作られる最大の回文数は、9009 = 91×99です。
2つの3桁の数字の積から作られる最大の回文数を求めよ。
上記課題は解けたので学習のためにn桁対応させようとしたところ、4桁までは約15秒で結果が出るように作れました。
しかし5桁になると処理が重すぎて途中で中断せざるを得ない状況です。
何かしら改善出来そうなアドバイスなど頂ければ幸いです。
java
1 public static void main(String[] args) { 2 3 // func(2);//1秒以内 4 // func(3);//1秒以内 5 6 func(4);//約15秒 7 8 // func(5);//????秒//2桁分増加の単純計算で15*100=1500秒=25分?? 9 10 } 11
java
1 static void func(int length) { 2 3 String a = "";//文字列操作用：桁A 4 String b = "";//文字列操作用：桁B 5 String s = "";//文字列操作用：回文数 6 7 int maxA = 0;//暫定最大数：桁A 8 int maxB = 0;//暫定最大数：桁B 9 int maxS = 0;//暫定最大数：回文数 10 11 //ループ範囲用 12 int iMax = (int) Math.pow(10, (length)) - 1;//4桁なら=9999 13 int iMin = (int) Math.pow(10, (length - 1));//4桁なら=1000 14 15 //文字列操作用 16 int n = 0; 17 18 for (int i = iMax; i >= iMin; i--) { 19 20 for (int j = iMax; j >= iMin; j--) { 21 22 s = String.valueOf(i * j); 23 24 //対象外をスルー 25 if (s.length() % 2 == 1 || s.length() < length*2) { 26 continue; 27 } 28 29 n = s.length(); 30 31 a = s.substring(0, n / 2);//前半桁を文字列で取得//123321なら123 32 33 b = ""; 34 35 //後半桁を文字列で取得//123321なら321 36 for (int k = 0; k < n / 2; k++) { 37 b += s.substring(n - (k + 1), n - k); 38 } 39 40 //回文数か判定 41 if (a.equals(b)) { 42 43 //暫定最大回文数発見時 44 if (maxS < i * j) { 45 46 maxA = i; 47 maxB = j; 48 maxS = i * j; 49 50 //途中経過 51 System.out.println(maxA + " * " + maxB + " = " + maxS); 52 } 53 } 54 } 55 } 56 //最終結果 57 System.out.println("最終結果"); 58 System.out.println(maxA + " * " + maxB + " = " + maxS); 59 } 60
出力例 func(3);の場合
995 * 583 = 580085
993 * 913 = 906609
最終結果
993 * 913 = 906609
回答5件
0
ベストアンサー
質問の読み替えが重要です。
３桁の数の積で表される回文数の最大値を求める処理を、プログラミングで完結させたい。
の raccy さんと私の回答が参考になるかと。
ざっくりというと、回文数を先に作って、最大数値の方から割っていくと良いです。
投稿2018/08/09 19:26
退会済みユーザー
総合スコア0
0
主な変更点
- ループ範囲の桁を半分にする
変更前：999999>>>900000
変更後：999999>>>999000
- 1つ目の発見が最大数と仮定し、そこで処理中断することで大幅に改善
出力結果
最終結果 91 * 99 = 9009
2桁 1ms
最終結果 913 * 993 = 906609
3桁 0ms
最終結果 9901 * 9999 = 99000099
4桁 1ms
最終結果 99681 * 99979 = 9966006699
5桁 1ms
最終結果 999001 * 999999 = 999000000999
6桁 6ms
最終結果 9997647 * 9998017 = 99956644665999
7桁 66ms
最終結果 99990001 * 99999999 = 9999000000009999
8桁 249ms
最終結果 999920317 * 999980347 = 999900665566009999
9桁 20197ms
10桁以上への課題
- 10桁以上は未対応
- 桁数が増えると指数倍的に計算量が増え限界が浅い
java
1 for (int i = 2; i <= 9; i++) { 2 3 long start = System.currentTimeMillis(); 4 5 func((long) i); 6 7 long end = System.currentTimeMillis(); 8 System.out.println(i + "桁 " + (end - start) + "ms"); 9 System.out.println(); 10 } 11
java
1 2 static void func(long num) { 3 4 int maxA = 0;//暫定最大数：整数A 5 int maxB = 0;//暫定最大数：整数B 6 long maxS = 0;//暫定最大数：回文数 7 8 //ループ範囲最大数：3桁例：999999 9 final long iMax = (long) Math.pow(10, num) - 1; 10 11 //ループ範囲最小数：3桁例：999000 12 //※900000まで回さなくとも最大数に近いところで発見出来るので 13 //※暫定的に半分にしてみる 14 15 final long iMin = iMax - (long) Math.pow(10, num - (num * 50 / 100)) + 1; 16 17 for (long i = iMax; i >= iMin; i--) { 18 19 //回文数生成 20 final long pd = getPalindrome(i); 21 22 //3桁の整数B：ループ範囲：i>>>最小値√回分数 23 long jMax = iMax; 24 long jMin = (long) Math.sqrt(pd); 25 26 for (long j = jMax; j >= jMin; j--) { 27 28 //整数で割り切れ且つ3桁の整数 29 if (pd % j == 0 && pd / j < j) { 30 31 //最初の発見が最大数と仮定する 32 if (maxS < pd) { 33 34 maxA = (int) (pd / j); 35 maxB = (int) j; 36 maxS = pd; 37 System.out.println("最終結果 " + maxA + " * " + maxB + " = " + maxS); 38 39 //発見と同時に処理中断で大幅に改善 40 return; 41 } 42 } 43 } //j 44 } //i 45 } 46 47 //回文数生成 48 static long getPalindrome(long num) { 49 50 String str = String.valueOf(num) + new StringBuilder(String.valueOf(num)).reverse().toString(); 51 52 return Long.parseLong(str); 53 } 54
投稿2018/08/12 11:35
編集2018/08/12 12:56総合スコア1009
修正完了。
結局配列は使わずに、最初の発見で`return;`することで大幅に改善しました。
func(10)で10桁x2=20桁の回文数となりlong型の最大値19桁を超える為10桁以上は未対応。
0
処理見切れていませんが、気づいた点だけ。
1,ヘビーなループ内でStringの生成を頻繁を行うことを避ける。
文字列はint/long型と比較してコストが重いです。(※)
ヘビーなループ内で生成を頻繁に行うと顕著にGC(Garbage Collection)の影響を受けます。
数字で扱うか、HashMapなどを使って生成内容をキャッシュしてくださいな。
今回の場合は数字を反転させたいので、以下のような形にできるかと。
ある桁数で数値の内容を反転させたいので、こんな感じに。
Java
1 final long div = (long) Math.pow(10, num); 2 for (long i = iMax; i >= iMin; i--) { 3 final long pd = getPalindrome(i, div); // 値が変わらないならfinal宣言を 4 // 中略 5 }
Java
1 static long getPalindrome(final long num, final long div) { 2 long number = num; 3 long reverse = 0; // 数字としては桁数が半分なので、longで扱うかどうかは悩みどころです。 4 while (number > 0) { 5 reverse *= 10; 6 reverse += number % 10; // 剰余演算は他の四則演算と比較して遅いので、高速化できそうな気も。 7 number /= 10; 8 } 9 return num * div + reverse; 10 }
使用メモリStringを参考に
int 4 Byte long 8 Byte System.out.println("99999999999999".getBytes().length); // 14Byte
2, 経過時間を測定する時はSystem.currentTimeMillis();ではなく
System.nanoTime()を使うと精度が良くなります。
投稿2018/08/12 05:30
編集2018/08/12 05:36
総合スコア5846
0
te2jiさんの回答のリンク先を参考に作り直してみました。
とても参考になりましたありがとうございました。
最初に投稿したものよりかなり速度up出来ました。
5桁までは1秒以内で、6桁でも約20秒です。
7桁だと10分経過しても結果が出ませんでしたのでここで打ち止めとしました。
7桁=14桁の99999999999999から10000000000000までループですから仕方ないでしょう。
ここが限界のようです。
java
1 public static void main(String[] args) { 2 3 for(int i=2;i<=5;i++) { 4 5 long start = System.currentTimeMillis(); 6 7 func((long)i); 8 9// func((long)2);//1ms 10// func((long)3);//1ms 11// func((long)4);//7ms 12// func((long)5);//288ms 13// func((long)6);//20235ms 14 15// func((long)7);//※10分経過しても結果出ず強制終了※ 16 17 long end = System.currentTimeMillis(); 18 System.out.println(i + "桁 " + (end - start) + "ms"); 19 System.out.println(); 20 } 21 22 } 23
java
1 static void func(long num){ 2 3 long maxA = 0;//暫定最大数：整数A 4 long maxB = 0;//暫定最大数：整数B 5 long maxS = 0;//暫定最大数：回文数 6 7 //3桁の整数A：ループ範囲：999>>>100 8 long iMax = (long) Math.pow(10, num)-1 ; 9 long iMin = iMax-(long) Math.pow(10, num-1)+1; 10 11 for(long i=iMax;i>=iMin;i--) { 12 13 //回文数範囲：999999>>>900009 14 long pd = getPalindrome(i); 15 16 //3桁の整数B：ループ範囲：i>>>最小値√回分数 17 long jMax = iMax; 18 long jMin = (long)Math.sqrt(pd); 19 20 for(long j = jMax; j >= jMin; j--) { 21 22 //整数で割り切れ且つ3桁の整数 23 if(pd % j == 0 && pd / j < j) { 24 25 //暫定最大数として更新 26 if(maxS < pd) { 27 28 //maxA=i;//ご指摘あり修正 29 maxA=pd/j; 30 maxB=j; 31 maxS=pd; 32 33// //途中経過：デバッグ用 34// System.out.println("途中経過 " + maxA +" * "+ maxB +" = "+ maxS); 35 break; 36 } 37 } 38 } 39 } 40 System.out.println("最終経過 " + maxA + " * " + maxB + " = " + maxS); 41 42 } 43
java
1 static long getPalindrome(long num){ 2 3 String str = String.valueOf(num) + new StringBuilder(String.valueOf(num)).reverse().toString(); 4 5 return Long.parseLong(str); 6 } 7
出力結果
最終経過 90 * 99 = 9009
2桁 0ms
最終経過 906 * 993 = 906609
3桁 0ms
最終経過 9900 * 9999 = 99000099
4桁 15ms
最終経過 99660 * 99979 = 9966006699
5桁 282ms
投稿2018/08/10 05:45
編集2018/08/12 04:02総合スコア1009
すみませんが、
90 * 99 -> 91 * 99
906 * 993 -> 913 * 993
9900 * 9999 -> 9901 * 9999
99660 * 99979 -> 99681 * 99979
ではないでしょうか?
ご指摘ありがとうございます、見直してみます
途中経過 91 * 99 = 9009
最終経過 91 * 99 = 9009
2桁 0ms
途中経過 913 * 993 = 906609
最終経過 913 * 993 = 906609
3桁 0ms
途中経過 9901 * 9999 = 99000099
最終経過 9901 * 9999 = 99000099
4桁 8ms
途中経過 99681 * 99979 = 9966006699
最終経過 99681 * 99979 = 9966006699
5桁 238ms
//maxA=i;
maxA=pd/j;
回答も修正しました、ありがとうございました。
修正ありがとうございます。コメントで追記してもよかったですが、回答を編集してもいいと思います。
自分もこの問題について考えていました。
考察ですが、どうやら答えに規則性があると思います。
偶数桁の場合は 9009 -> 99000099 となるので
また、これらの回文数はすべて11の倍数になるのでそこらへんも考慮すれば処理速度がもっと
速くなるかもしれません。
(私も、コードを作成しましたが、まだ５桁から処理速度が遅いのでもう少し考えます。
完成したら、載せるつもりです。)
おそらく偶数桁の場合の回文数の最大値は
{10 ^ n - 10 ^ (n / 2) + 1} * (10 ^ n - 1) になると思います。
他に気づいた点として、回分数の最大値を作る２つの整数の１の位の組み合わせは
(1,9),(3,3)の２つだと思います。おそらく最大値の最高位の数は9なので
ごめんなさいコメントに気づかず、ずっと他の問題解いていました
コメント頂いた内容を読んで改善出来るところを探してみます
途中報告です
下一桁が9,3,1になる条件だけを先に配列に格納して、
それをループで回してみたのですが逆に処理が遅くなりました。
999,993,991,989,983,981...
こうすれば計算対象が3/10になるのかと思いましたがうまくいきませんでした。
別の方法など考え直してみます。
長くなっているので別の回答に書きます。
0
とりあえず変数jの方のfor文の初期値の設定をint j = iMaxからint j=iに変えるだけでループ回数半減できるのでまずそのあたりから変更してみては？
投稿2018/08/09 19:02
総合スコア50
ありがとうございます
掛け算だからなんとなくAB半分に出来そうだなと思っていたのですが
手を入れたら壊れそうで試せなかったですが思ったことから試すべきですね。
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/08/09 21:21
2018/08/10 05:50