問題 サイコロが３つある。3個同時にふる場合の目の組み合わせを列挙せよ。
今回はまずこの問題を考える。前回と違うのは1,1,1という目の重複が許される点だ。
for(int i=1;i<=6;i++) {
for(int j=i;j<=6;j++) {
for(int k=j;k<=6;k++) {
System.out.println("["+i+j+k+"]");
}
}
}３つの目を作るので３重ループを回すところまでは前回と同じだが、重複を許すので基本はすべての目の組み合わせを考える。この際、内側のループの開始を外のループと一致させることで[1,1,2]に対する[1,2,1]などの同じ組み合わせの登場を防ぐことができる。(i<=j<=kの関係となっている)
実行例
[111] [112] [113] [114] [115] [116] [122] [123] [124] [125] [126] [133] [134] [135] [136] [144] [145] [146] [155] [156] [166] [222] [223] [224] [225] [226] [233] [234] [235] [236] [244] [245] [246] [255] [256] [266] [333] [334] [335] [336] [344] [345] [346] [355] [356] [366] [444] [445] [446] [455] [456] [466] [555] [556] [566] [666]
確認問題
Q1
以下のお菓子の中から2つを選択する（重複可)。ただし、合計金額は200円以内でなければならない。 アメ:30円 チョコ:120円 ガム:100円 ポテチ:80円 ビスケット:90円 条件を満たす組み合わせをすべて列挙せよ。 出力フォーマットは以下のようにすること [アメ(30),アメ(30)] [アメ(30),チョコ(120)] . . .
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;i++){
for(int j=i;j<snacks.length;j++){
if(snacks[i].price+snacks[j].price<=200){
System.out.printf("[%s,%s]%n",snacks[i],snacks[j]);
}
}
}
}
}
class Snack{
String name;
int price;
Snack(String name,int price){
this.name=name;
this.price=price;
}
@Override
public String toString() {
return String.format("%s(%d)", this.name,this.price);
}
}選ぶ個数が増えてきたら・・・
問題
赤、緑、青のボールがたくさんある。5個選ぶ場合の組み合わせを列挙せよ。
ではこの問題はどうだろうか？確かにこの問題も5重forを使って先ほどと同じように解くことができる。
public class Main {
public static void main(String[] args) {
String[] colors= {"R","G","B"};
for(int i=0;i<3;i++) {
for(int j=i;j<3;j++) {
for(int k=j;k<3;k++) {
for(int l=k;l<3;l++) {
for(int m=l;m<3;m++) {
System.out.printf("[%s,%s,%s,%s,%s]%n",
colors[i],
colors[j],
colors[k],
colors[l],
colors[m]
);
}
}
}
}
}
}
}[R,R,R,R,R] [R,R,R,R,G] [R,R,R,R,B] [R,R,R,G,G] [R,R,R,G,B] [R,R,R,B,B] [R,R,G,G,G] [R,R,G,G,B] [R,R,G,B,B] [R,R,B,B,B] [R,G,G,G,G] [R,G,G,G,B] [R,G,G,B,B] [R,G,B,B,B] [R,B,B,B,B] [G,G,G,G,G] [G,G,G,G,B] [G,G,G,B,B] [G,G,B,B,B] [G,B,B,B,B] [B,B,B,B,B]
ただもし、10個選ぶとなったら10重forだろうか？この方法では限界がありそうだ。
取りうる値の可能性から考える
こういった時は取りうる値の可能性からのループを組む方法がある。
for(int i=5;i>=0;i--) {
for(int j=5-i;j>=0;j--) {
System.out.printf("[%d,%d,%d]%n",i,j,5-i-j);
}
}まず、赤の個数の可能性を考え(5~0)次に内側のループでは緑の個数の可能性について考える。その際に赤のボールに使った個数は初期値設定の際に減らすのがポイントだ。２つの数がわかれば残りが青ということになる。
確認問題
500円、100円、50円、10円を組み合わせは自由に10枚使ってできる金額の種類と総数を求める処理を作成せよ
100 140 180 . . . 4550 4600 5000 244種類
public class Main {
public static void main(String[] args) {
Set<Integer> moneys=new TreeSet<>();
for(int i=10;i>=0;i--) {
for(int j=10-i;j>=0;j--) {
for(int k=10-i-j;k>=0;k--) {
//System.out.printf("[%d,%d,%d,%d]%n", i,j,k,10-i-j-k);
moneys.add(i*500+j*100+k*50+(10-i-j-k)*10);
}
}
}
for(int m:moneys) {
System.out.println(m);
}
System.out.println(moneys.size()+"種類");
}
}応用
先程のお菓子の問題は２つを選んだがこれを予算以内ならばいくつでもOKという問題にしてみよう。
以下のお菓子の中から自由に選択する（重複可)。ただし、合計金額は200円以内でなければならない。 アメ:30円 チョコ:120円 ガム:100円 ポテチ:80円 ビスケット:90円 条件を満たす組み合わせをすべて列挙せよ。 出力フォーマットは以下のようにすること(出力順は任意) [ビスケット(90),] [ビスケット(90),ビスケット(90),] [ポテチ(80),] [ポテチ(80),ビスケット(90),] [ポテチ(80),ポテチ(80),] [ガム(100),] . . .
解法1
この程度ならfor文ですべての組み合わせをとってもどうにかなる。
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),
};
int maxMoney=200;//この金額を超えてはいけない
//アメは0~6個の可能性
for(int i=0;i<=maxMoney/snacks[0].price;i++){
//チョコは0~1個の可能性
for(int j=0;j<=maxMoney/snacks[1].price;j++){
for(int k=0;k<=maxMoney/snacks[2].price;k++){
for(int l=0;l<=maxMoney/snacks[3].price;l++){
for(int m=0;m<=maxMoney/snacks[4].price;m++){
boolean isCountOK=i+j+k+l+m >=1;
boolean isPriceOK=i*snacks[0].price+j*snacks[1].price+k*snacks[2].price+l*snacks[3].price+m*snacks[4].price <=maxMoney;
if(isCountOK && isPriceOK){
System.out.printf("[%s%s%s%s%s]%n",
snacks[0].showInfoTimes(i),
snacks[1].showInfoTimes(j),
snacks[2].showInfoTimes(k),
snacks[3].showInfoTimes(l),
snacks[4].showInfoTimes(m));
}
}
}
}
}
}
}
}
class Snack {
String name;
int price;
Snack(String name, int price) {
this.name = name;
this.price = price;
}
@Override
public String toString(){
return String.format("%s(%d)", this.name,this.price);
}
String showInfoTimes(int times){
String ret="";
for(int i=0;i<times;i++){
ret+=toString()+",";
}
return ret;
}
}
実現はできたが力技感がすごい、しかもお菓子が増えたときの修正が面倒だ。
こういったときには再帰処理を検討してみるとよい。
解法2(再帰)
import java.util.*;
public class Main {
static final List<Map<Snack,Integer>> data=new ArrayList<>();
public static void main(String[] args) {
List<Snack> snacks=new ArrayList<>();
snacks.add(new Snack("アメ", 30));
snacks.add(new Snack("チョコ", 120));
snacks.add(new Snack("ガム", 100));
snacks.add(new Snack("ポテチ", 80));
snacks.add(new Snack("ビスケット", 90));
Map<Snack,Integer> map=new LinkedHashMap<>();
getSnack(200,snacks,map);
}
static void getSnack(int money, List<Snack> snacks, Map<Snack,Integer> map) {
//探索するお菓子がなくなったら終わり
if(snacks.size()==0){
//結果出力
for(Snack key:map.keySet()) {
for(int i=0;i<map.get(key);i++) {
System.out.print(key+",");
}
}
System.out.println();
}else {
//着目するお菓子（リストの先頭から取り出す(リストは短くなる))
Snack snack = snacks.remove(0);
//アメだったら0~6個の可能性がある
for (int i = 0; i <= money / snack.price; i++) {
if(i !=0) {
map.put(snack, i);
}
//アメの個数ごとに再帰処理（残金,一つ短くなったリスト,更新されたMap)
getSnack(money - snack.price * i, new ArrayList<Snack>(snacks), new LinkedHashMap<Snack,Integer>(map));
}
}
}
}
class Snack {
String name;
int price;
Snack(String name, int price) {
this.name = name;
this.price = price;
}
@Override
public String toString() {
return String.format("%s(%d)", this.name,this.price);
}
}
再帰はロマンだ。ソースを見たときに処理が分かりづらいという弱点はあるが時として超絶なパワーを発揮する。プログラミング上級者を目指すならば必ずマスターしていかなければならない項目だ。
おまけ
1セント，10セント，25セントのコインを好きな枚数使う事ができる． 1234セントを支払う時最低何枚で払うことが出来るか？再帰を用いて求めよ。
import java.util. *;
public class Main {
static int min=1000000; //答えとなる最小枚数（初期値として適当に大きな数字をいれておく)
public static void main(String[] args){
List<Integer> list=new ArrayList<>();
list.add(25);
list.add(10);
list.add(1);
change(1234,list,0,"");
System.out.println("最小は"+min+"枚");
}
static void change(int money,List<Integer> list,int num,String result){
if(list.size()==0){
if(money==0){
if(num<min){
min=num;
}
System.out.printf("%d枚%s%n", num,result);
}
}else{
int coin=list.remove(0);
for(int i=0;i<=money/coin;i++){
change(money-coin*i,new ArrayList<Integer>(list),num+i,result+coin+"("+i+")");
}
}
}
}
コメント