Simulasi dan brute force

Brute force: coba semua kemungkinan

Brute force mencoba semua kemungkinan jawaban dan memeriksa mana yang benar. Cara ini sering cukup, asalkan banyak kemungkinannya tidak terlalu besar.

Soal: tuliskan semua pasangan bilangan bulat positif (a, b) dengan a ≤ b dan a² + b² = 50.

1n = 502a = 13while a * a <= n:4    b = a5    while a * a + b * b <= n:6        if a * a + b * b == n:7            print(a, b)8        b += 19    a += 1

1 7
5 5

Perulangan berhenti begitu a² + b² melewati n, sehingga tidak ada pemeriksaan yang sia-sia.

Memperkirakan apakah brute force cukup cepat

Sebagai perkiraan kasar, program C++ bisa menjalankan sekitar seratus juta operasi sederhana per detik, sedangkan Python jauh lebih lambat, sekitar sepuluh juta. Hitung dulu banyak kemungkinannya:

• Mencoba semua pasangan dari 1.000 data: sekitar 500 ribu. Aman.
• Mencoba semua pasangan dari 100.000 data: sekitar 5 miliar. Terlalu lambat, butuh cara lain.
• Mencoba semua susunan 10 benda: 10! = 3.628.800. Masih bisa.
• Mencoba semua susunan 15 benda: lebih dari satu triliun. Mustahil.

Simulasi: permainan hitung lompat

Soal: n anak duduk melingkar, bernomor 1 sampai n. Mulai dari anak nomor 1, setiap hitungan ke-k keluar dari lingkaran. Siapa yang keluar berturut-turut, dan siapa yang tersisa terakhir?

1def hitung_lompat(n, k):2    lingkaran = list(range(1, n + 1))3    keluar = []4    i = 05    while lingkaran:6        i = (i + k - 1) % len(lingkaran)7        keluar.append(lingkaran.pop(i))8    return keluar910urutan = hitung_lompat(7, 3)11print("Urutan keluar:", urutan)12print("Terakhir:", urutan[-1])

Urutan keluar: [3, 6, 2, 7, 5, 1, 4]
Terakhir: 4

Program menirukan permainannya persis. Operasi % len(lingkaran) membuat hitungan berputar kembali ke awal lingkaran. Simulasi seperti ini sangat andal untuk n yang kecil sampai sedang.

1data = [12, 3, 7, 20, 5, 8]2n = len(data)3for i in range(n):4    for j in range(i + 1, n):5        for k in range(j + 1, n):6            if data[i] + data[j] + data[k] == 20:7                print(data[i], data[j], data[k])

12 3 5
7 5 8