Dynamic Programming di Python

Ini adalah salah satu materi yang ada di buku Pemrograman Kompetitif. Buku ini bisa di download di https://tlx.toki.id/courses/competitive/chapters/07/lessons/A. Seharusnya penjelasannya diketik ulang , tapi maaf belum sempat... 

Dalam buku dijelaskan konsep dan Pseudocode dari soal. Keduanya diterjemahkan dalam bahasa Python versi saya.

Soalnya seperti ini:

Diberikan M jenis koin, masing-masing jenis bernilai a₁,a₂, ....aₘ rupiah. Asumsikan banyaknya koin  yang ada tak terbatas. Tentukan banyaknya koin paling sedikit untuk membayar tepat sebesar N rupiah!

Solusinya bisa diselesaikan dalam dua cara: Bottom up dan Top down.

1. Bottom-up: (ubah variabel M dan N untuk mengubah input)

1. def solve(a, N):
2.     f = [0] * (N + 1)
3.     for x in range(1, N + 1):
4.         best = float('inf')
5.         for k in range(len(a)):
6.             if a[k] <= x:
7.                 best = min(best, f[x - a[k]] + 1)
8.         f[x] = best
9.     return f[-1]
10. 
    
11. def main():
12.     M = 1, 6, 10
13.     N = 12
14.     print(solve(M, N))
15. 
    
16. if __name__ == '__main__':
17.     main()

2. Top-down:

1. def solve(x):
2.     if x == 0: return 0
3. 
   
4.     best = float('inf')
5.     for k in range(len(M)):
6.         if M[k] <= x:
7.             best = min(best, solve(x - M[k]) + 1)
8.     return best
9. 
   
10. def main():
11.     global M
12.     M = 1000, 2000, 5000
13.     N = 12000
14.     print(solve(N))
15. 
    
16. if __name__ == '__main__':
17.     main()

Menyelesaikan Soal Cerita Berbasis Aljabar (Matematika SD)

https://id.pngtree.com/freepng/cartoon-watermelon-score-clipart_6030316.html

 

Belum belajar persamaan aljabar, sudah ada soal cerita aljabar. Seperti yang kita ketahui soal Aljabar sederhana biasa membuat perumpamaan dan perbandingan beberapa bilangan utnuk mendapatkan hasil. cara ini agak sulit untuk anak usia sekolah SD kelas 1,2,3. Tapi apakah ada cara lain untuk menyelesaikan soal seperti ini?

Saya menemukan soal cerita ini di buku Matematika SD kelas 3.(diterjemahkan dengan sedikit modifikasi)

Soal ke 1

Kathy berkata kepada ayahnya: "Guru memuji saya hari ini karena memecahkan masalah." Adiknya mendengar ini dan berkata kepada Kathy: "Saya tidak tahu mengapa Anda dipuji, tetapi sayalah siswa nomor satu dalam aritmatika." Sang ayah lalu memberi soal untuk siswa siswa jago matematika. 

Kathy membaca soal ayahnya: "Jika Anda menambahkan setengah bagiannya ke uang saya, Anda mendapatkan 81 Dolar. Berapa banyak uang yang saya miliki?" 

Dan Adiknya membaca ini: "Jika ibu memasukkan sepertiga dari uang di dompetnya ke dompetnya, maka akan ada 68 Dolar di dompetnya. Berapa banyak uang di dompetnya?" 

Anak anak menjadi malu karena kesulitan mengerjakan soal itu. Bisakah kamu membantu mereka? 

 

Ada banyak cara dan jawaban yang dapat diberikan oleh anak anak. 

Cara 1

Cara paling gampang adalah cara coba coba (Brute Force). 

Kita bisa menebak terlebih dulu berapa uang milik ayah. Dari sana kita akan periksa apakah perhitungannya sudah betul atau belum. Jika belum kita akan menambah atau mengurangi tebakan seusai dengan hasil yang sudah ada.  

Cara 2

Anak kelas 3 banyak yang belum belajar pecahan dan masih kesulitan membuat persamaan aljabar. namun soal ini bisa diselesaikan dengan membuat model dan membandingkan.

Uang yang ditambahkan adalah sesuatu = x

Uang itu adalah setengah dari uang saya. Jadi uang saya 2 kalinya. = 2x

Jumlah uang saya dan yang ditambahkan untuk saya adalah x+ 2x. 

Hasilnya adalah 81 Dolar. 

3 bagian x hasilnya 81, kalau 1 bagian adalah 81/3 = 27. Uang saya adalah 2 kalinya yaitu: 27 x 2 = 54 Dolar. 

Cara 3

Soal ini juga dapat diselesaikan dengan cara membuat garis bilangan, atau membuat model gambar. Dan tentu saja untuk anak yang lebih besar bisa menyelesaikannya dengan persamaan aljabar. 

 Soal ke 2

Seorang pria bertemu dengan keluarga yang terdiri dari kakek, ayah dan anak, dan bertanya berapa usia mereka. "Kita semua umurnya100 tahun," jawab kakek. (maksudnya jumlah umur semua anggota adalah 100). 

Kemudian pria itu bertanya kepada ayahnya: "Nah, katakan padaku, berapa umurmu?" - "Bersama dengan putra saya, saya berusia 45 tahun," jawab sang ayah, "dan putranya 25 tahun lebih muda dari saya."  

Jadi pria yang penasaran itu tidak perlu mencari tahu berapa usia mereka masing-masing.  Apakah kamu juga sudah tahu? 

Cara menyelesaikannya hampir sama dengan soal ke 1.

Soal Ke 3

Yang ini adalah soal yang aneh tapi lucu.. 'thinking out of the box'. 

Tugas lelucon  

a) Berapa banyak ujung yang dimiliki 4 batang, 5 batang, 5 setengah batang? 

Cara ini dapat diselesaikan denagn membuat model atau menggambar secara visual. Berapa ujung yang dimiliki oleh 1 batang.

b) Bagilah dua belas menjadi dua bagian yang sama di atas kertas sehingga setengah dari angka ini adalah tujuh.  

c) Bagaimana cara membagi 188 menjadi dua bagian yang sama sehingga masing-masing menjadi 100?

Soal b dan c lebih sulit. Kita  pasti membayangkan dua-belas itu adalah besaran atau jumlah. Padahal yang dimaksud di sini adalah angka. Dan format angka bukan hanya format arabic, tapi bisa bentuk lain.

Gasing Permainan Tradisional

Sejarah Gasing

gambar dari: https://pixabay.com/th/photos

Gasing, permainan berputar ini adalah permainan yang ada di Indonesia sejak sebelum zaman penjajahan Belanda.  Kata gasing berasal dari dua suku kata yaitu, Gang yang berarti Lorong atau lokasi lahan dan Sing yang berarti suara. Dari dua kata suku itu, gasing adalah sebuah permainan yang dimainkan di sebuah tempat yang kosong dan mengeluarkan bunyi.

 

Permainan ini dapat dimainkan sendiri atau bersama sama. Gasing akan diputar dan tentunya gasing yang terbaik adalah gasing yang berputar paling lama. Permainan ini dapat dimainkan bersama dengan mengadu gasing. Pihak lawan akan berusaha menjatuhkan gasing musuhnya. Siapa yang bertahan paling lama, dia yang menang. 

 

Konon, permainan gasing dikatakan berasal dari tanah Melayu dan menyebar ke Riau lalu ke seluruh Indonesia. Di Nusantara, nama sebutan dan bahan gasing berbeda beda. Jawa Barat dan Jakarta menyebut permainan ini dengan Gangsing atau Panggal, Lampung dengan Pukang, Kalimantan Timur dengan Begasing, Maluku dengan Apiong, Sulawesi Selatan dan Nusa Tenggara Barat dengan Maggasing, Lombok dengan Gansing, Bolaang Mongondow Sulawesi Selatan dengan Paki, Jawa Timur dengan Kekehan, dan lain lain.

 

Mainan gasing ini sempat populer di Indonesia beberapa tahun yang lalu melalui serial anime Jepang yang cukup terkenal di Indonesia: Beyblade. Dalam serial tersebut gasing digambarkan sebagai permainan yang bisa mengeluarkan kekuatan khusus untuk mengalahkan lawan-lawannya. 

 

Bahan Gasing 

 

Bahan gasing bervariasi seperti kayu, paku berindu, buah parah, bambu, biji pinang,  aluminium dan plastik.

Gasing kayu adalah gasing yang paling lama. Ada bambu dari Jawa tengah, kayu bahkan biji pakis dari Bengkulu. Di Jawa Barat, terdapat dua jenis gasing yaitu gasing kalangenan dan gasing untuk aduan. Gasing kalangenan dibuat dari jenis kayu yang ringan dan empuk. Dengan jenis kayu ini, suara yang dihasilkan pun lebih nyaring. Sementara, untuk gasing aduan, mereka menggunakan kayu dari pohon jambu batu dan pete cina. Jenis kayu lain yang dapat dipakai adalah kayu pohon asam, kayu pohon kembang sepatu, mahoni, dan jengkol.

Ada juga gasing plastik. Beberapa gerai makanan yang menjual makanan anak anak bahkan memberi gasing plastik sebagai bonus ketika membeli makanan tersebut (Kids Meal). Gasing jenis ini cukup mudah dimainkan, seimbangdenagn cepat dan dapat diputar dengan mudah.

 

Belajar Ilmu Alam Lewat Gasing

 

Ketika membuat atau memilih gasing atau memainkannya, kita dapat belajar tentang ilmu alam seperti kesetimbangan, gaya berat dan gaya putar benda. Kalau kita sudah tahu tentang sedikit ilmu kinematika, kita dapat membuat atau memilih gasing yang baik agar berputar lebih lama. Beberapa hal yang harsu diperhatikan dalam memilih atau membuat gasing adalah: bentuk gasing, berat gasing, titik tumpuan. Tempat gasing berputar juga akan berpengaruh pada perputaran gasing. Itu sebabnya ketika mengadu gasing, perlu disediakan alas khusus dengan batas yang jelas.

 

Bentuk gasing

 

Kalau kita perhatikan hampir semua gasing berbentuk bulat, tidak ada yang kotak atau persegi panjang. 

Mungkin kalau kita memutar sebuah benda berbentuk kotak atau bulat dengan ukuran yang sama, kita akan mendapatkan jawabannya. Benda berbentuk bulat atau kotak dengan jarak yang sama akan memiliki waktu putar yang berbeda.  

 

Pada video di bawah kamu akan melihat beberapa gasing dengan bentuk yang berbeda akan  memiliki waktu putar yang berbeda.

Bagaimana dengan gasing dengan bentuk yang agak rumit? Bisakah kita membuat gasing berbentuk kincir? apakah ada pengaruhnya dengan waktu putar? 

Bagaimana dengan ukuran panjang dan lebar gasing, apakah semakin besar ukurannya akan semakin lama atau semakin singkat waktu putarnya? 

 

Lebar gasing akan berpengaruh pada momen inersia gasing sementara panjang gasing akan berpengaruh pada pusat massa gasing. 

 

Tumpuan

Bagaimana dengan luas permukaan tumpuan gasing? semakin besar luasnya apakah akan semakin stabil atau justru memperlambat perputarannya? 

Berat Gasing

Bagaimana dengan berat gasing? mana yang lebih banyak pengaruhnya, berat atau ukuran lebar gasing? 

(kalau kita sudah tahu rumus momen inersia, mungkin kita dapat menjawabnya dengan cepat) tapi sejauh mana rumus tersebut dapat diterapkan? kita perlu mencobanya sendiri.

Tempat Gasing berputar

Jangan lupa, kita juga harus memperhatikan masalah gesekan baik pada lantai ataupun gesekan udara. Coba saja kalau kita memainkan gasing di atas lantai dan di atas aspal.. apakah ada perbedaan?  Gesekan udara juga bisa memberi pengaruh pada waktu putar. Benda berbentuk batang atau berbentuk kincir akan dipengaruhi gesekan udara. 

Di bawah ini adalah video yang mencoba membuat beberapa benda berputar seperti gasing dan mengukur waktu perputarannya. Semua dibuat dengan LEGO 9686. 

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