組み合わせ問題をJavaで

Java

問題
袋に9つのボールが入っていてそのひとつひとつに1〜9の番号がついている。ちょうどビリヤードの球が9つ入っている様子を想像してもらえればよい。
その袋から3つ取り出してその番号の合計が10になる組み合わせを列挙せよ。


プログラム問題を解いていて中級くらいになってくると登場する順列や組み合わせ。
上のような問題がでて「詰んで」しまう人も多いのではないだろうか?
それはそうだこの手の問題を一から考えていたら日が暮れてしまう。
この手の問題は「解き方を知ってるか知ってないか」が全てなのだ。(プログラミングの問題にはそういった物が多く存在する)

まずは一番簡単と思われる組み合わせ(Combination)からやっていこう。
今回の場合だと9個の中から3個を取り出す組み合わせなので9C3で84通り。
この9C3のCはCombinationのCだ。9×8×7を3×2×1で割るという計算方法をなんとなく覚えている人もいるだろう。

すべて列挙すると以下となる。

123 124 125 126 127 128 129 134 135 136 137 138 139 145 146 147 148 149 156 157 158 159 167 168 169 178 179 189 
234 235 236 237 238 239 245 246 247 248 249 256 257 258 259 267 268 269 278 279 289 
345 346 347 348 349 356 357 358 359 367 368 369 378 379 389 
456 457 458 459 467 468 469 478 479 489 
567 568 569 578 579 589 
678 679 689 
789 

この問題をJavaで解いてみよう。
3桁の数字をつくるので3重forを作成する。
最初のループでは1つ目(百の位)なので1~7まで回せばよさそうだ。この際、8、9まで回さなくてよいことに注意する。(789が最大)
2桁目のループでは1桁目でとりだした値+1から8まで回せば良い。
3桁目のループでは2桁目でとりだした値+1から9まで回せば良い。

[解答例]

public static void main(String[] args) {
			
		for(int i=1;i<=7;i++){
			System.out.println();
			for(int j=i+1;j<=8;j++){
				for(int k=j+1;k<=9;k++){
					System.out.print(""+i+j+k+" ");				
				}
			}
		}
		
	}

これで上記の組み合わせがすべて得られる。見やすくするため最初のforのあとで改行処理をいれた。

今回の問題ではこの中から桁の合計が10になるものをピックアップすればよいので以下のように変更する。

public static void main(String[] args) {		
		for(int i=1;i<=7;i++){
			for(int j=i+1;j<=8;j++){
				for(int k=j+1;k<=9;k++){
					if(i+j+k==10){
						System.out.printf("[%d,%d,%d]%n",i,j,k);	
					}				
				}
			}
		}
	}

[結果]

[1,2,7]
[1,3,6]
[1,4,5]
[2,3,5]

答えが得られた。

最後に汎用性を持たせるためにマジックナンバーを定数化しよう。

public static void main(String[] args) {	
		final int MIN=1,MAX=9,TOTAL=10;
		for(int i=MIN;i<=MAX-2;i++){
			for(int j=i+1;j<=MAX-1;j++){
				for(int k=j+1;k<=MAX;k++){
					if(i+j+k==TOTAL){
						System.out.printf("[%d,%d,%d]%n",i,j,k);	
					}				
				}
			}
		}
	}

以上で終了だ。「やはり知ってるか知ってないか」と言わざるをえない。
プログラミングによる組み合わせ,組み合わせ問題の第一歩としてまずは今回の多重forによる組み合わせを理解しよう。

[確認問題]
以下のお菓子の中から2つを選択する。ただし、合計金額は200円以内でなければならない。
アメ:30円
チョコ:120円
ガム:100円
ポテチ:80円
ビスケット:90円
条件を満たす組み合わせをすべて列挙せよ。
出力フォーマットは以下のようにすること
[アメ(30),チョコ(120)]
[アメ(30),ガム(100)]
.
.
.

[解答例]

public class Main {
	public static void main(String[] args) {
		Snack[] snacks={
				new Snack("アメ",30),
				new Snack("チョコ",120),
				new Snack("ガム",100),
				new Snack("ポテチ",80),
				new Snack("ビスケット",90),
		};
		
		for(int i=0;i<snacks.length-1;i++){
			for(int j=i+1;j<snacks.length;j++){
				if(snacks[i].price+snacks[j].price <=200){
					System.out.printf("[%s(%d),%s(%d)]%n",snacks[i].name,snacks[i].price,snacks[j].name,snacks[j].price);
				}
			}
		}	
	}	
}
class Snack{
	String name;
	int price;
	Snack(String name,int price){
		this.name=name;
		this.price=price;
	}
}

[組み合わせ問題をJavaで(重複組合せ)はこちら]

コメント

タイトルとURLをコピーしました