質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.20%

2つのn桁の数字の積から作られる最大の回文数を求めたい

解決済

回答 5

投稿

  • 評価
  • クリップ 0
  • VIEW 1,084

opyon

score 987

 やりたいこと

2つのn桁の数字の積から作られる最大の回文数を求めたい

 やったこと

例題
2つの2桁の数字の積から作られる最大の回文数は、9009 = 91×99です。
2つの3桁の数字の積から作られる最大の回文数を求めよ。


上記課題は解けたので学習のためにn桁対応させようとしたところ、4桁までは約15秒で結果が出るように作れました。
しかし5桁になると処理が重すぎて途中で中断せざるを得ない状況です。

何かしら改善出来そうなアドバイスなど頂ければ幸いです。


    public static void main(String[] args) {

        //        func(2);//1秒以内
        //        func(3);//1秒以内

        func(4);//約15秒

        //        func(5);//????秒//2桁分増加の単純計算で15*100=1500秒=25分??

    }
    static void func(int length) {

        String a = "";//文字列操作用:桁A
        String b = "";//文字列操作用:桁B
        String s = "";//文字列操作用:回文数

        int maxA = 0;//暫定最大数:桁A
        int maxB = 0;//暫定最大数:桁B
        int maxS = 0;//暫定最大数:回文数

        //ループ範囲用
        int iMax = (int) Math.pow(10, (length)) - 1;//4桁なら=9999
        int iMin = (int) Math.pow(10, (length - 1));//4桁なら=1000

        //文字列操作用
        int n = 0;

        for (int i = iMax; i >= iMin; i--) {

            for (int j = iMax; j >= iMin; j--) {

                s = String.valueOf(i * j);

                //対象外をスルー
                if (s.length() % 2 == 1 || s.length() < length*2) {
                    continue;
                }

                n = s.length();

                a = s.substring(0, n / 2);//前半桁を文字列で取得//123321なら123

                b = "";

                //後半桁を文字列で取得//123321なら321
                for (int k = 0; k < n / 2; k++) {
                    b += s.substring(n - (k + 1), n - k);
                }

                //回文数か判定
                if (a.equals(b)) {

                    //暫定最大回文数発見時
                    if (maxS < i * j) {

                        maxA = i;
                        maxB = j;
                        maxS = i * j;

                        //途中経過
                        System.out.println(maxA + " * " + maxB + " = " + maxS);
                    }
                }
            }
        }
        //最終結果
        System.out.println("最終結果");
        System.out.println(maxA + " * " + maxB + " = " + maxS);
    }

 出力例 func(3);の場合

995 * 583 = 580085
993 * 913 = 906609
最終結果
993 * 913 = 906609


  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+2

質問の読み替えが重要です。

3桁の数の積で表される回文数の最大値を求める処理を、プログラミングで完結させたい。
の raccy さんと私の回答が参考になるかと。

ざっくりというと、回文数を先に作って、最大数値の方から割っていくと良いです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/10 06:21

    ありがとうございます
    今は総当たりループで回してるのでかなりスッキリしそうな予感がします
    なるほど!目から鱗って感じがしました
    時間出来たら作り直してみます

    キャンセル

  • 2018/08/10 14:50

    とても参考になりました!最初のものに比べたら爆速です!
    自己回答にも書きましたがやはりPCの限界なのでしょう6桁出力後の7桁で10分後でも結果出ませんでした。

    キャンセル

+1

とりあえず変数jの方のfor文の初期値の設定をint j = iMaxからint j=iに変えるだけでループ回数半減できるのでまずそのあたりから変更してみては?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/10 06:19

    ありがとうございます
    掛け算だからなんとなくAB半分に出来そうだなと思っていたのですが
    手を入れたら壊れそうで試せなかったですが思ったことから試すべきですね。

    キャンセル

+1

te2jiさんの回答のリンク先を参考に作り直してみました。
とても参考になりましたありがとうございました。

最初に投稿したものよりかなり速度up出来ました。
5桁までは1秒以内で、6桁でも約20秒です。
7桁だと10分経過しても結果が出ませんでしたのでここで打ち止めとしました。
7桁=14桁の99999999999999から10000000000000までループですから仕方ないでしょう。

ここが限界のようです。

    public static void main(String[] args) {

        for(int i=2;i<=5;i++) {

        long start = System.currentTimeMillis();

        func((long)i);

//        func((long)2);//1ms
//        func((long)3);//1ms
//        func((long)4);//7ms
//        func((long)5);//288ms
//        func((long)6);//20235ms

//        func((long)7);//※10分経過しても結果出ず強制終了※

        long end = System.currentTimeMillis();
        System.out.println(i + "桁 " + (end - start)  + "ms");
        System.out.println();
        }

    }
    static void func(long num){

        long maxA = 0;//暫定最大数:整数A
        long maxB = 0;//暫定最大数:整数B
        long maxS = 0;//暫定最大数:回文数

        //3桁の整数A:ループ範囲:999>>>100
        long iMax = (long) Math.pow(10, num)-1 ;
        long iMin =  iMax-(long) Math.pow(10, num-1)+1;

        for(long i=iMax;i>=iMin;i--) {

            //回文数範囲:999999>>>900009
            long pd = getPalindrome(i);

            //3桁の整数B:ループ範囲:i>>>最小値√回分数
            long jMax = iMax;
            long jMin = (long)Math.sqrt(pd);

            for(long j = jMax; j >= jMin; j--) {

                //整数で割り切れ且つ3桁の整数
                if(pd % j == 0 && pd / j < j) {

                    //暫定最大数として更新
                    if(maxS < pd) {

                        //maxA=i;//ご指摘あり修正
                        maxA=pd/j;
                        maxB=j;
                        maxS=pd;

//                        //途中経過:デバッグ用
//                        System.out.println("途中経過 " + maxA +" * "+ maxB +" = "+ maxS);
                        break;
                    }
                }
            }
        }
        System.out.println("最終経過 " + maxA + " * " + maxB + " = " + maxS);

    }
    static long getPalindrome(long num){

        String str = String.valueOf(num) + new StringBuilder(String.valueOf(num)).reverse().toString();

        return Long.parseLong(str);
    }

出力結果

最終経過 90 * 99 = 9009
2桁 0ms

最終経過 906 * 993 = 906609
3桁 0ms

最終経過 9900 * 9999 = 99000099
4桁 15ms

最終経過 99660 * 99979 = 9966006699
5桁 282ms

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/12 17:31

    ごめんなさいコメントに気づかず、ずっと他の問題解いていました
    コメント頂いた内容を読んで改善出来るところを探してみます

    キャンセル

  • 2018/08/12 19:20

    途中報告です
    下一桁が9,3,1になる条件だけを先に配列に格納して、
    それをループで回してみたのですが逆に処理が遅くなりました。
    999,993,991,989,983,981...
    こうすれば計算対象が3/10になるのかと思いましたがうまくいきませんでした。
    別の方法など考え直してみます。

    キャンセル

  • 2018/08/12 19:41

    長くなっているので別の回答に書きます。

    キャンセル

+1

処理見切れていませんが、気づいた点だけ。

1,ヘビーなループ内でStringの生成を頻繁を行うことを避ける。
文字列はint/long型と比較してコストが重いです。(※)
ヘビーなループ内で生成を頻繁に行うと顕著にGC(Garbage Collection)の影響を受けます。

数字で扱うか、HashMapなどを使って生成内容をキャッシュしてくださいな。
今回の場合は数字を反転させたいので、以下のような形にできるかと。

ある桁数で数値の内容を反転させたいので、こんな感じに。

    final long div = (long) Math.pow(10, num);
    for (long i = iMax; i >= iMin; i--) {
        final long pd = getPalindrome(i, div); // 値が変わらないならfinal宣言を
                // 中略
        }
    static long getPalindrome(final long num, final long div) {
        long number = num;
        long reverse = 0; // 数字としては桁数が半分なので、longで扱うかどうかは悩みどころです。
        while (number > 0) {
            reverse *= 10;
            reverse += number % 10;  // 剰余演算は他の四則演算と比較して遅いので、高速化できそうな気も。
            number /= 10;
        }
        return num * div + reverse;
    }

使用メモリStringを参考に

int  4 Byte
long 8 Byte
System.out.println("99999999999999".getBytes().length); // 14Byte

2, 経過時間を測定する時はSystem.currentTimeMillis();ではなく
System.nanoTime()を使うと精度が良くなります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/12 17:32

    ありがとうございます 内容を読んでから何かしら改善してみます

    キャンセル

  • 2018/08/12 19:28

    finalやlongをintに出来る限り変更してみましたが特に速度変化は無いようです。
    どちらかというと処理速度というより使用メモリ量の削減なのかなと思いました。
    final化などのGC抑制による恩恵はこの小さなプログラムでは軽微なようです。
    Stringをなるべく使わない意識はした方が良いのは分かるのですが、使わない実装だと逆に冗長になる気もしています。
    コストを意識する考え方などとても参考になりました。
    ありがとうございます。

    キャンセル

+1

主な変更点

  • ループ範囲の桁を半分にする
    変更前: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桁以上は未対応
  • 桁数が増えると指数倍的に計算量が増え限界が浅い

        for (int i = 2; i <= 9; i++) {

            long start = System.currentTimeMillis();

            func((long) i);

            long end = System.currentTimeMillis();
            System.out.println(i + "桁 " + (end - start) + "ms");
            System.out.println();
        }
    static void func(long num) {

        int maxA = 0;//暫定最大数:整数A
        int maxB = 0;//暫定最大数:整数B
        long maxS = 0;//暫定最大数:回文数

        //ループ範囲最大数:3桁例:999999
        final long iMax = (long) Math.pow(10, num) - 1;

        //ループ範囲最小数:3桁例:999000
        //※900000まで回さなくとも最大数に近いところで発見出来るので
        //※暫定的に半分にしてみる

        final long iMin = iMax - (long) Math.pow(10, num - (num * 50 / 100)) + 1;

        for (long i = iMax; i >= iMin; i--) {

            //回文数生成
            final long pd = getPalindrome(i);

            //3桁の整数B:ループ範囲:i>>>最小値√回分数
            long jMax = iMax;
            long jMin = (long) Math.sqrt(pd);

            for (long j = jMax; j >= jMin; j--) {

                //整数で割り切れ且つ3桁の整数
                if (pd % j == 0 && pd / j < j) {

                    //最初の発見が最大数と仮定する
                    if (maxS < pd) {

                        maxA = (int) (pd / j);
                        maxB = (int) j;
                        maxS = pd;
                        System.out.println("最終結果 " + maxA + " * " + maxB + " = " + maxS);

                        //発見と同時に処理中断で大幅に改善
                        return;
                    }
                }
            } //j
        } //i
    }

    //回文数生成
    static long getPalindrome(long num) {

        String str = String.valueOf(num) + new StringBuilder(String.valueOf(num)).reverse().toString();

        return Long.parseLong(str);
    }

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/12 20:43

    あまりスマートではないですが暫定的に9桁まで出してみました。
    全対象を計算させずに推測に基づくループ範囲の抽出とカットとで速くはなりましたが本当に正しいかは微妙です。
    どちらにしてもこれ以上の桁数増加や速度upは限界なのかなと思います。

    キャンセル

  • 2018/08/12 21:04 編集

    修正完了。
    結局配列は使わずに、最初の発見で`return;`することで大幅に改善しました。
    func(10)で10桁x2=20桁の回文数となりlong型の最大値19桁を超える為10桁以上は未対応。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.20%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる