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

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

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

例えば、

ｎが5
ｘが9

であれば

1+3+5＝9
2+3+4＝9

で
カウントが2です。

Java
1import java.io.*;
2 
3class Main {
4    public static void main(String[] args) {
5        BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
6        try {
7          
8            int n, x;
9            int cnt, ave3, ave2;
10            String[] tmpArray;  
11            while( true ) {
12                String str = kb.readLine();
13                tmpArray = str.split( " " );
14                n = Integer.parseInt( tmpArray[0] );
15                x = Integer.parseInt( tmpArray[1] );
16             
17                if( 0 == n && 0 == x ) {  break; }
18             
19                cnt = 0;
20                ave3 = x / 3;
21                int i, j, k;
22                for( i=1; i<ave3; i++ ) {
23                    ave2 = ( x-i ) / 2;
24                    for( j=i+1; j<=ave2; j++ ) {
25                        k = x - i - j;
26                        if( j < k && k <= n ) {
27                            cnt++;
28                        }
29                    }
30                }
31                System.out.println( cnt );    
32            }
33        } catch( IOException e ) {
34            System.err.println( e );
35        }
36    }
37}
38
39

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

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

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

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

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

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

行動規範の内容に同意します

回答3件

ベストアンサー

例えば「足して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 02:02

swordone

総合スコア20651

退会済みユーザー

2017/09/21 02:26

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

行動規範の内容に同意します

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

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

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

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

java
1k = x - i - j;
2if( j < k && k <= n ) {
3    cnt++;
4}

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

また、

java
1for( i=1; i<ave3; i++ ) {
2    ave2 = ( x-i ) / 2;
3    for( j=i+1; j<=ave2; j++ ) {
4        k = x - i - j;
5        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も同様です。

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