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

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

ただいまの
回答率

90.85%

  • Java

    12499questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

3桁の数の積で表される回文数の最大値を求める処理を、プログラミングで完結させたい。

解決済

回答 8

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 215

chicken-a_s.

score 25

お世話になっております。
ネットでプログラミング数学というサイトの問題を解いてたときの話なのですが、

**問題**

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数の最大値を求めよ.

という問題があり、プログラミングを使って解いていて、解けはしたのですが、プログラミングを上手く生かしきれず、最終的には出力結果とにらめっこしてマッチする値を探すという手段で答えを出したのですが、プログラミング的にはどうなのかと思い質問しました。

値が6桁の場合、[1][2][3][3][2][1]のような関係があるのは気付いたのですが、プログラミングでの記述方法がわかりませんでした。

↓は私が書いたコードなのですが、プログラミングでこの問題の処理を完結させて、答えを出力させることはできるのでしょうか?

public class hoge {
    public static void main( String[] args ){
        int a = 0;
        int c = 0;
        for( int i = 0; i < 90; i++ ){
            for( int j = 0; j < 90; j++ ){
                a = (999-j)*(999-i);
                String b = String.valueOf( a );
                if( b.matches( "^9.*" ) ){
                    if( b.matches( ".*9$" ) ){
                        c++;
                        System.out.println( "【j=" + j + "】【i=" + i + "】" + a );
                    }
                }else if( b.matches( "^8.*" ) ){
                    if( b.matches( ".*8$" ) ){
                        c++;
                        System.out.println(  "【j=" + j + "】【i=" + i + "】" + a );
                    }
                }
            }
        }
        System.out.println( "出力結果は" + c + "通りです。" );
    }
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 8

+2

整数 n が回文数かどうかは以下の関数で判別することができます。

public static boolean isPalindrome(int n) {
    String string = String.valueOf(n);
    String reverse = new StringBuilder(string).reverse().toString();
    return string.equals(reverse);
}

これを使ってこんな風に求めることができます。

int max = -1, max1 = -1, max2 = -1;
for (int i = 100; i <= 999; ++i) {
    for (int j = i; j <= 999; ++j) {
        if (isPalindrome(i * j)) {
            if (i * j > max) {
                max = i * j;
                max1 = i;
                max2 = j;
            }
        }
    }
}
System.out.printf("max: %d = (%d * %d)%n", max, max1, max2);
-> 
max: 906609 = (913 * 993)

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/26 21:38

    結果に影響はないですが、3桁どうしの掛け算なので i < 999, j < 999 のところは
    i <= 999, j <= 999 または i < 1000, j < 1000にすべきだと思います。

    キャンセル

  • 2018/05/27 04:59

    @Stars1024 さん ありがとうございます。

    キャンセル

  • 2018/05/27 14:26

    @game-overさんへ
    ソースコードを変更して頂き、ありがとうございました。

    キャンセル

+1

「3桁の数の積」の最大値は
(1000-1)^2=998001
なので、これ以下で回分数になる数を求めるなり作るなりして、
回分数を素因数分解などして3桁×3桁にできるかチェックしていくというのはどうでしょう?

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/26 16:22

    回答ありがとうございます。
    回文数の部分はプログラムで求めることはできないのでしょうか?

    キャンセル

  • 2018/05/27 09:07

    [1][2][3][3][2][1]のようになっているということは、
    (100000+1)*[1]+(10000+10)*[2]+(1000+100)*[3]のような計算で求められるということになります。この考えで順次ループさせて作ることができます。

    キャンセル

checkベストアンサー

0

まあ 回文数になるプログラム(コピペを避けるために別言語で)

<?php

$k = 0;
for ( $i = 101; $i < 1000; $i++) {
    for ( $j = 101; $j < 1000; $j++) {
        $x = $i * $j;

        $str = ($x."");
        $rev = strrev($x.""); // 文字列反転

        if ($str == $rev) { // 反転結果と一致してるかどうか
            // echo sprintf("%4d", $i);
            // echo sprintf("%4d", $j);
            // echo " ";
            echo $str . PHP_EOL;
            $k++; // 件数を確認
             // ここで最大値判定をする
        }
    }
}
// echo $k . "件" .PHP_EOL;

というように文字列反転して比較してしまえばいいのです。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/27 12:27

    回答ありがとうございます。
    一番シンプルでわかりやすかったです。
    件数は出力とにらめっこできるレベルか見るために表示してたものなんですが、
    丁寧にありがとうございますw

    キャンセル

0

3桁の数の積で表される可能性のある回文は
[1][0][0]/[0][0][1]
から
[9][9][9]/[9][9][9]
つまり100-999の組み合わせで記述できます。

ので、先に全回文を作って、それを3桁の数字で割ってみるのがワリと手っ取り早い気がします。3桁の数字のでかい方から割れば、最大値はサクッと見つかるのでは?

追記
php で書いてみました。
上記以外に、ちょっと条件が必要でした^^;

<?php
function make_palindrome_array(){
    $palindrome_array = [];
    for ($i = 999; $i >= 100; --$i){
        $palindrome = (string)$i . strrev((string)$i);
        $palindrome_array[] = (int)$palindrome;
    } 
    return $palindrome_array;
}
$palindrome_array = make_palindrome_array();
foreach($palindrome_array as $palindrome){
    for($j = 999; $j >= 100; --$j){
        if($palindrome % $j === 0){
            if($palindrome / $j <= 999){
                echo '最大の回文は'.$palindrome.PHP_EOL;
                echo '組み合わせは ' . $j . ' と ' . $palindrome / $j . PHP_EOL;
                break 2;
            }
        }
    }
}

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

値が6桁の場合、[1][2][3][3][2][1]のような関係があるのは気付いたのですが、プログラミングでの記述方法がわかりませんでした。

この部分ですが、複数の問題に分割すれば簡単に記述可能かと思います。
コードそのものを書くと考える余地が無くなってしまいますので、問題分割の概要のみの回答とさせて頂きます。

  1. 数値の桁数を求める。
  2. 各桁の数値を取り出す。
  3. 回文数かどうか判定する。

まず1.ですが、これは10を底とするlogを計算し、結果を切り上げれば実現可能です。java.lang.Mathクラスにはlog10(double)メソッドとceil(double)メソッドが有りますので、これを使えば簡単かと。

2.に関しては、簡単な数学の問題です。例えば数値aの3桁目の値は「aを100で割って、その値を10で割った余り」です。

3.に関しては、特に解説は不要かと思います。先頭と末尾から順番に判定すれば良いだけですので。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/26 16:56

    難しい(*_*)

    キャンセル

  • 2018/05/26 17:02

    一個一個の問題は比較的簡単なので、まずは手計算で概要を掴んで、それから実装してみてはどうでしょうか?

    他の方の回答にある様に文字列に変換して比較するのが「楽」ではありますが。
    ただ、今後のスキルアップを目標にするなら、頑張って実装してみてはどうかと思います。

    キャンセル

  • 2018/05/26 17:23

    ありがとうございます。
    他の方もわかりやすく書いてくださっているので参考にうまくいくまでやって見ます。

    キャンセル

0

Problem 4 - Project Euler の問題ですね。

汎用性を持たせるなら任意のN桁について解けるようなロジックを考えるべきでしょう。

最大の数と言うことから、一番大きい数、999 * 999 = 998001から探していくというのが早いだろうということがわかります。しかし、二つの積の部分、999999の二つを減らしていくとなると、組合せが膨大で、かつ、片方だけを減らしていっても、ちょうどうまい具合のものを見逃してしまいそうです。ですので、減らしていくのは9998001の方です。

9998001の減らしていくと言っても回文になるパターンは非常に少ないです。6桁の場合は1000分の1個しか回文になりません。それもそのはずです。単純に前の3桁が決まれば、対応する回文が決定されるからです。

998 -> 998899
997 -> 997799
996 -> 996699
...

という感じにです。つまり、減らしていくのは前3桁だけが必要です。前3桁さえ決まれば、後3桁も自動的に決まります。そして、重要なことは、前3桁の大小は回文になったときの大小と一致すると言うことです。つまり、998から減らしていって、条件を満たす数がみつかれば、その数が最大となるというわけです。(減らす限界は100までである。それ以下の場合は5桁になるため、この方法では回文が得られない。)

こうして、回文候補は大きい方から順に上げることが出来るようになりました。次は、それらが3桁同士の積になるかどうかです。

条件を満たすのであればn = a * b(nは回文になる数、a ≧ b)となる3桁の整数abが存在することになります。このときaは3桁なので999以下です。では逆にあり得る最小はいくつでしょうか?それは√nです。もし、a√nより小さい場合、ba以下であるため、a * b√n * √n = nより小さくなってしまいます。つまり、もしaが存在するなら、a999から√nの間の数となります。

後はわかりますよね。999から√nまでの整数に対して、回文の数nが割り切れるかどうかを確認するだけです。もし、割り切れれば、bが存在し、その数はa以下であるため、3桁以内になります。(bが2桁以下であることは確認しなくても良い。最大のパターンでも999 * 99 = 98901と5桁になるため、6桁を前提しているときには2桁以下になることはない)

桁数を増やしても最大の数が999999999と増えていくだけ、同じ考え方で解くことが出来ます。

稚拙ですが、参考までにRubyでの実装例です。

def int2list(n)
  list = []
  while (n > 0)
    n, r = n.divmod(10)
    list << r
  end
  list
end

def list2int(list)
  list.each_with_index.map { |n, i| n * (10 ** i) }.sum
end

def palindrome(n)
  list = int2list(n)
  n * (10 ** list.size) + list2int(list.reverse)
end

def search_palindrome(digit)
  max_n = 10 ** digit - 1
  n = max_n ** 2 / 10 ** digit
  n.downto(10 ** (digit - 1)) do |i|
    pn = palindrome(i)
    max_n.downto(Integer.sqrt(pn)) do |j|
      if pn % j == 0
        return pn, j, pn / j
      end
    end
  end
  nil
end

printf("%d = %d * %d\n", *search_palindrome(2))
printf("%d = %d * %d\n", *search_palindrome(3))
printf("%d = %d * %d\n", *search_palindrome(4))
printf("%d = %d * %d\n", *search_palindrome(5))
printf("%d = %d * %d\n", *search_palindrome(6))
printf("%d = %d * %d\n", *search_palindrome(7))
printf("%d = %d * %d\n", *search_palindrome(8))

計算量は桁数の指数関数オーダー以上のようです(正確なものはよくわからない)。9桁は時間がかかりすぎてRubyでは求められませんでした。C++あたりで書き直せばできるかとも思います。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/26 18:15 編集

    回答ありがとうございます。
    そうです、そのサイトです。 英語が読めないので和訳版ですが。

    応用は聞かないのを書き直して見たらめちゃくちゃ処理が重く、pc的に無理そうなのができました(´o`;

    public class hoged {
    public static void main( String[] args ){
    int a = 999 * 999 / 1000;
    for( int i = 0; i < 10; ){
    for( int j = 0; j < 10; j++ ){
    int b = ( 999 - i ) * ( 999 - j );
    String aa = String.valueOf( b );
    for( int l = 0; l < 100; l++ ){
    int c = a - l;
    String bb = String.valueOf( c );
    if( aa.matches( "^bb.*" ) ){
    System.out.println( bb );
    }
    }
    }
    }
    }
    }

    キャンセル

  • 2018/05/26 18:17

    二つの積の両方をループで回せば最大値に対する2乗のオーダーの計算量になるので遅くなりますよ。いかに片方だけをいくつまで回せば確認が完了できるか考えるのかが重要です。

    キャンセル

  • 2018/05/26 18:51

    あ、重いのは無限ループでした。
    んー、難しい。

    キャンセル

  • 2018/05/27 09:19

    > いかに片方だけをいくつまで回せば確認が完了できるか考えるのかが重要です。

    ん?最も重要なのは、いかに回文を作り出すかでは?

    キャンセル

  • 2018/05/27 09:49

    > ん?最も重要なのは、いかに回文を作り出すかでは?

    え?引っかかる所ってそっちなの?私が競プロに毒されているだけ?

    キャンセル

  • 2018/05/27 10:13

    > 重要なことは、前3桁の大小は回文になったときの大小と一致すると言うことです。

    回文が作れることに気がつくことと、上記が最重要かなぁと思ったので。
    でも言い換えると、`いかに片方だけを回せば`ってことになるから、あんまり意味のない指摘でしたね。失礼^^;

    キャンセル

0

回答してくださった皆様、ありがとうございます。
拙いコードですが、一発で結果を出力することができました。

public class hoged {
    public static void main( String[] args ){
        for( int i = 1000; i > 900; i-- ){
            for( int j = 1000; j > 900; j-- ){
                int a = i * j;
                String str = String.valueOf( a );
                StringBuffer sb = new StringBuffer( str );
                String str_2 = sb.reverse().toString();
                if( str.matches( str_2 ) ){
                    System.out.println( str + " =    " + i +" x " + j );
                    return;
                }                
            }
        }
    }
}

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

今更ですが、答えが6桁であることを前提にすると、abccbaと表すことができて、
abccba = 100001 * a + 10010 * b + 1100 * c

ここで100001、10010、1100はすべて11の倍数です。なので6桁の回文数は11の倍数であると分かります。

回文数を生成して3桁の数の積であらわせるかをチェックする戦略と、3桁の数の積を生成して回文数であるかをチェックする戦略が考えられますが、どちらにおいても、この「11の倍数である」であるという性質を利用すれば多少高速化できると思います(計算量のオーダーは変わりませんが)。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

  • 解決済

    100になる直前の加算結果出力

    javaで開始値と終了値を入力してその間の偶数を加算していき、合計が100を超えたら「数値が100を超えたため、処理を中止します。」とメッセージを出し、かつ合計が100になる前の加

  • 解決済

    入力した値を表示させない方法

    初めまして。現在JAVAを学んでいる初心者です。 現在、配列に格納している値を表示させるプログラムを作っています。 ユーザーから入力があった場合、次に配列の値を表示させるとき、

  • 解決済

    javaで作れる学習プログラムってどのようなものが作れますか

    意図 javaを使って学習プログラムを作成してほしいといわれました。 しかし、イメージがわきません。 どんなものが作れるのでしょうか

  • 解決済

    以下のコードでエラーになる原因を教えて下さい。

    import java.util.*; public class Main { public static void main(String[] args) { Sc

  • 解決済

    javaについて

    javaについて質問です。情報処理検定第53回のプログラミング部門1級のjavaの問題をやっているんですけど、そのjavaに平均値を追加したいです。どのように追加すれば良いのでしょ

  • 解決済

    改行区切りでの出力

    ランダムな整数を改行区切りで3個出力したくて以下のコードを打ってみたんですが間違いといわれました。どこが違うのか指摘お願いします  public class Main {  p

  • 解決済

    偶数だけ出したい

    public class Main { public static void main(String[] args) throws Exception { for (int

  • 解決済

    javaの配列に文字を格納して処理する方法

     疑問、質問 javaについての質問です。 キーボードから文字を一字ずつ入力し配列に格納する。 その後配列に格納されていた文字によってそれぞれ順番に処理していくというプログラ

同じタグがついた質問を見る

  • Java

    12499questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • トップ
  • Javaに関する質問
  • 3桁の数の積で表される回文数の最大値を求める処理を、プログラミングで完結させたい。