全探索とは
全探索とは、問題の解を見つけるためにすべての可能性を試すアプローチのことです。
この方法は、計算量が多くなる可能性がありますが、確実に正確な解を見つけることができます。
全探索は、特に問題の規模が小さい場合や、他の効率的なアルゴリズムが明らかでない場合に有用です。
JavaScriptで全探索はforを使用する
JavaScriptで全探索はforを使用すると高速かつ簡単にできます。
もし「500円玉が2枚、100円玉が3枚、50円玉が4枚の組み合わせでできる金額は何通りか」という一見難しそうな問題も、全探索を使えばすぐに解けます。
やり方はまず各枚数の定数と何通りかを保存するための変数を用意して、以下のようにforで入れ子にしてcountに加算していくだけです。
const yen500 = 2
const yen100 = 3
const yen50 = 4
let count = 0
for (let x = 0; x <= yen500; x++) {
for (let y = 0; y <= yen100; y++) {
for (let z = 0; z <= yen50; z++) {
count++
}
}
}
console.log(`結果は${count}通り`)
// 結果は60通り
もしすべての組み合わせの金額を知りたい場合はtotalの配列を作成して結果をpushします。
const yen500 = 2
const yen100 = 3
const yen50 = 4
const total = []
let count = 0
for (let x = 0; x <= yen500; x++) {
for (let y = 0; y <= yen100; y++) {
for (let z = 0; z <= yen50; z++) {
total.push(500 * x + 100 * y + 50 * z)
count++
}
}
}
console.log(`結果は${count}通り`)
// 結果は60通り
console.log(total)
// [
// 0, 50, 100, 150, 200, 100, 150, 200,
// 250, 300, 200, 250, 300, 350, 400, 300,
// 350, 400, 450, 500, 500, 550, 600, 650,
// 700, 600, 650, 700, 750, 800, 700, 750,
// 800, 850, 900, 800, 850, 900, 950, 1000,
// 1000, 1050, 1100, 1150, 1200, 1100, 1150, 1200,
// 1250, 1300, 1200, 1250, 1300, 1350, 1400, 1300,
// 1350, 1400, 1450, 1500
// ]
for文は入れ子になっている場合は内側から処理されるので、小さい金額が先に追加されています。
「500円玉が2枚、100円玉が3枚、50円玉が4枚の組み合わせでできる、1000円の金額は何通りか」というケースの場合は、if文を追加して条件に一致した場合にcountに加算します。
const yen500 = 2
const yen100 = 3
const yen50 = 4
const target = 1000
let count = 0
for (let x = 0; x <= yen500; x++) {
for (let y = 0; y <= yen100; y++) {
for (let z = 0; z <= yen50; z++) {
if (target === 500 * x + 100 * y + 50 * z) {
count++
}
}
}
}
console.log(`${target}円になる組み合わせは${count}通り`)
// 1000円になる組み合わせは2通り
全探索はプログラミングで頻繁に使用されるアルゴリズムなので、まだ知らない場合は必ず習得したほうが良いでしょう。
