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

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

ただいまの
回答率

90.75%

  • Java

    13116questions

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

組み合わせの数のプログラムの意味が分からないです。

解決済

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 526

szk24

score 70

アルゴリズムの勉強をしているのですが、他の方が書いたコードの意味が分からなくて困っています。

1からnまでの数から重複しない3つの数を選び出し、足してxとなる数をカウントするプログラムです。

例えば、

nが5
xが9

であれば

1+3+5=9
2+3+4=9


カウントが2です。

import java.io.*;

class Main {
    public static void main(String[] args) {
        BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
        try {

            int n, x;
            int cnt, ave3, ave2;
            String[] tmpArray;  
            while( true ) {
                String str = kb.readLine();
                tmpArray = str.split( " " );
                n = Integer.parseInt( tmpArray[0] );
                x = Integer.parseInt( tmpArray[1] );

                if( 0 == n && 0 == x ) {  break; }

                cnt = 0;
                ave3 = x / 3;
                int i, j, k;
                for( i=1; i<ave3; i++ ) {
                    ave2 = ( x-i ) / 2;
                    for( j=i+1; j<=ave2; j++ ) {
                        k = x - i - j;
                        if( j < k && k <= n ) {
                            cnt++;
                        }
                    }
                }
                System.out.println( cnt );    
            }
        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

わからないのは、ave3 = x / 3;と3で割っている部分と
for文のave2 = ( x-i ) / 2;とx-iを2で割っている部分と
for文以下です。

何故、これで、組み合わせの数がでるのかがわかりません。

教えて頂けると有り難いです。

あと、こういったアルゴリズムの考え方の勉強に役に立つ本やサイトとかあれば、教えて下さると助かります。

(Amazonで本を検索したのですが、どれが良いのかわかりませんでした。)

よろしくお願い致します。

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

checkベストアンサー

+5

例えば「足して9」という3数の組み合わせを重複を避けて探すため、1つ目より2つ目が大きく、2つ目より3つ目を大きくというように、数字を小さいほうから順に選ぼうという狙いです。
この時、最初の数字を目的の数の1/3以上にしてしまうと、そのあとに選ばれる数字が2つとも1/3より大きな数確定なので、合計が目的の数を確実に超えます。9の1/3である3を最初に選ぶと、そのあとに選べる数字は最小でも4と5なので、合計12となり条件に合いません。
2つ目を選ぶ際も同様です。(残り2つの合計)=9-(1つ目の数字)であり、かつ2つ目より3つ目が大きくなるようにとるので、2つ目が(残り2つの合計)の半分未満である必要があります。

具体的にn=5,x=9でプログラムの流れを追います。
まず最初の数としてi=1を選びます。残りは8です。
その次の数として1より大きいj=2を選びます。
残りが9-1-2=6で、これが3番目の数として使えれば条件達成ですが、
今使える最大数はn=5なので合いません。

2番目の数を選びなおしてj=3にします。
9-1-3=5で、これは3より大きく5以下であるため、3番目の数として使えます。
これで、1組目発見です。

2番目の数を選びなおし、j=4です。
9-1-4=4ですが、2番目の4と重複するためカウントしません。

次のj=5は残り数8の半分を超えるため、i=1に対しての組み合わせはこれ以上ありません。
実際、この場合9-1-5=3で、(1,3,5)の組み合わせはすでに出ています。

iを次に移動して、i=2とします。以下同じような処理になります。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/21 11:26

    丁寧な回答ありがとうございます。
    1/3の意味が分かりました。

    ありがとうございました。

    キャンセル

+1

その二つは最適化のために使用しているだけで、この問題を解くためには必要ないものです。
i < ave3j <= ave2は、それぞれi <= nj <= nを最適化したものになります。

まずは、最適化していない状態でアルゴリズムを理解してみることです。
頭のなかで考えるだけではなく、紙なりテキストなりに変数の値を書き出してみるといいですよ。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/21 11:29 編集

    回答ありがとうございます。
    紙等に書き出して、やってみたいと思います。

    ありがとうございました。

    キャンセル

+1

まず求める「カウント」がなんという変数名か確認します。
これはprintln()や変数名からしてcntだと想像つきます。

次に、どうやってcntを求めているか調べるために、cntを操作しているところを探します。

初期値は0で、他にはcnt++;以外の操作はないので、
組み合わせを見ていって、条件を満たすものを見つけたら数えるという方法を取っていることがわかります。

では、実際にcnt++;している直接の条件をみてみます。

k = x - i - j;
if( j < k && k <= n ) {
    cnt++;
}

nは足し合わせる数の最高値で、それをkと比較しているということは、
kは3つ組み合わせる数の候補の一つと推定できます。
また、xは「3つ足してxになる数」のxなので、
k = x - i - j;から、i,jも同様に組み合わせ候補だと推定できます。

また、

for( i=1; i<ave3; i++ ) {
    ave2 = ( x-i ) / 2;
    for( j=i+1; j<=ave2; j++ ) {
        k = x - i - j;
        if( j < k && k <= n ) {


この部分の、i,jの初期値、kの条件から、
i < j < k というような組み合わせを得ようとしていることがわかります。

まとめると、
i + j + k = n ただし 1 < i < j < k < n となる(i, j ,k)の組を探そうとしているコードになってます。

だいたいがわかったので、i,jについている上限値について考えます。
こういう組み合わせを求めるアルゴリズムで、単なる総当たりではなく、
上限、下限値の指定や途中でループを抜けるなど、何らかの範囲指定が付いている場合、
計算量削減のための指定です。

その筋で考えると、
まず、i < ave3 = x/3ですが、
仮にi = x/3 だったら、i + j + k > x/3 + x/3+1 + x/3 +2 = x + 3 > xになってしまうので、i >= x/3は計算するだけ無駄とわかります。
j < ave2も同様です。

こういうコードを読むときは、

  • とりあえず自分でも組んでみて違いや共通部分がどうなるか
  • 不可解な条件があったらそれを破ってどうなるか
  • とりあえず適当な値入れて具体的にどういう処理になるか

を見てみるといいと思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/09/21 12:12

    詳しく回答して頂き、ありがとうございました。
    考え方の順番まで教えて頂き、参考になりました。

    ありがとうございました。

    キャンセル

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

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

関連した質問

  • 受付中

    10進数から16進数に変換

    10進数を入力すれば16進数に変換されるというプログラムを作っているのですがいまいちうまくいきませんどこがまちがっているのでしょうか? import java.io.IOExce

  • 解決済

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

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

  • 解決済

    javaでデータを読み込んでソートしたいのですがうまく来ません

    コンパイルするとエラーになって 「シンボルが見つかりません」と表示されます。 他にも問題があれば教えてください import java.io.File; import

  • 解決済

    Javaでマス当てゲームを作りたい

    前提・実現したいこと Javaで5*5のマス目から当たりを見つけるプログラムを作りたいと考えています。 インターネットで下記のプログラムを見つけ応用できないかと思っています。

  • 受付中

    3つの整数が

    public class Main { public static void main(String[] args) throws Exception { //3つの整数が入力

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

  • Java

    13116questions

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