Menghitung Akar Kuadrat Menggunakan Iterasi (Dengan Gambar)

Sedikit Aljabar & Geometri

Bagaimana cara menghitung √10 itu?

Coba lihat gambar berikut:

Pada gambar di atas, luas gabungan dari kotak hitam, merah, dan biru adalah 10, dan luas kotak hitam adalah 9. sedangkan panjang sisi kotak hitam adalah √9 = 3, dan panjang sisi kotak hitam + x adalah √10.

Sekarang, kita perlu menghitung x (karena √10 - √9 = x).

Kita sudah tahu bahwa gabungan dari kotak merah, biru, dan hitam tertumpuk (overlap) dengan kotak hitam, maka total  luas kotak merah dan biru adalah 10 - 9 = 1

luas 1 kotak merah = x ⋅ 3. namun karena jumlah kotak merah adalah 2, maka luas total kotak merah = x ⋅ 3 ⋅ 2.

total luas kotak merah dan biru = x ⋅ 3 ⋅ 2 + x² = 1

1 - x² = x ⋅ 6

x = (1 - x²) ÷ 6

6 = (1 - x ⋅ x) ÷ x

6 = 1 ÷ x - x

x = 1 ÷ (6 + x)

Nah, persamaan ini tidak bisa diselesaikan karena nilai x bergantung dengan angka x itu sendiri(kecuali menggunakan akar-kuadrat. ini tidak bisa karena kita ingin membuat fungsi akar-kuadrat itu sendiri).

 

Maka untuk menghitungnya, kita bisa menggunakan iterasi (iteration).

Kita bisa mensubstitusi sebuah persamaan dengan persamaan itu sendiri.

Coba lihat:

x = 1 ÷ (6 + x)

   = 1 ÷ (6 + (1 ÷ (6 + x)))

   = 1 ÷ (6 + (1 ÷ (6 + (1 ÷ (6 + x)))))

   = 1 ÷ (6 + (1 ÷ (6 + (1 ÷ (6 + (1 ÷ (6 + x)))))))

 

Memprogram iterasi perhitungan √10

Ketika kita menggunakan metode iterasi (untuk menghitung sebuah angka), kita tidak bisa menghitung angka dengan persis, tapi kita bisa menghitung aproksimasi angka. semakin banyak iterasi yang dilakukan, semakin akurat kita dengan angka sebenarnya.

Pada iterasi ke-0, kita bisa mengatur x = 0 (sebagai placeholder):

Iterasi ke-0:

x₀ ≈ 0

Pada iterasi ke-1, baru kita memasukkan persamaan:

Iterasi ke-1:

x₁ ≈ 1 ÷ (6 + x₀) = 1 ÷ 6

Iterasi ke-2:

x₂ ≈ 1 ÷ (6 + x₁) = 1 ÷ (6 + 1 ÷ 6)

Iterasi ke-3:

x₃ ≈ 1 ÷ (6 + x₂) = 1 ÷ (6 + 1 ÷ (6 + 1 ÷ 6))

Perhatikan angka 'kecil'-nya (₀, ₁, ₂, dsb) di variabel x.

Nah sekarang kita bisa membuat program-nya dengan Python.

sqrt_10.py

Menyelesaikan Maze Secara Otomatis Menggunakan Algoritma Dijkstra

Ini adalah tulisan anak ke 1 usia 16 tahun yang sedang mempelajari Algoritma Komputer.

Algoritma Dijkstra adalah algoritma untuk mencari jalur tersingkat dari satu titik ke satu titik lainnya. Algoritma ini dapat digunakan untuk menyelesaikan sebuah maze.

Ini adalah salah satu gambar "maze sederhana" yang sudah diselesaikan oleh program yang menggunakan algoritma dijkstra:

Gambar asli berukuran 10px x 20px

Pada waktu itu, teknik yang digunakan adalah teknik rekursi dari sini, Memang berhasil, tetapi, ketika dicoba dengan maze yang lebih besar, program tewas dan tak mampu menyelesaikan maze.

Teknik lainpun dicoba, kali ini yang digunakan adalah teknik loop dari buku Competitive Programmers Handbook. Teknik ini mudah ditulis, singkat, dan mudah dimengerti, tidak seperti kebanyakan algoritma dijkstra yang lain. Kebanyakan algoritma pada umumnya susah dimengerti dan menggunakan banyak baris code, walaupun sama sama menggunakan teknik looping.

Teknik ini berhasil menyelesaikan maze yang lebih besar. Ini adalah hasilnya:

Kemudian dicoba lagi dengan maze yang lebih besar:

Pada maze ini, program memilih untuk tidak melewati maze, tetapi ia "memotong jalan" (lewat sebelah kiri):

Setelah jalur untuk memotong jalan tersebut ditutup:

Akhirnya jalur maze diberi warna:

Kemudian program dibuat supaya bisa bergerak secara diagonal:

Mulai mencoba maze yang lebih rumit:

Maze yang jauh lebih rumit:

Maze diatas diselesaikan dalam waktu kurang dari 2 menit.

Maze ini diselesaikan dalam waktu kurang dari 17 detik:

Kilas Balik Menyelesaikan Maze. 

Pada tahun 2009 ketika berumur 7 tahun saya menyelesaikan maze secara manual dan 8 tahun kemudian menyelesaikan maze yang sama dengan Algoritma Dijkstra. Cerita di tahun 2009 dapat dilihat di sini.

Source code ada di github (mungkin akan dikembangkan kemudian) .

Kredit maze: krazydad.com, fun-stuff-to-do.com dan littlebadwolf.com .