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()

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

Aplikasi Pengingat Jadwal Belajar di Waktu Pandemi Gratis

Aplikasi Pengingat Jadwal

Selama pandemi, kita memang banyak belajar dari rumah.. Tapi kadang kita suka lupa waktu, ketika sedang ada di rumah, ternyata ada banyak sekali yang ingin dilakukan, tapi waktu selalu terbatas, dan kita harus menyelesaikan jadwal belajar kita setiap hari.. Maka dari itu, saya ingin membuat aplikasi "Pengingat Jadwal". 

Aplikasi pengingat waktu ini saya buat dalam bahasa python, dengan bantuan modul tkinter.

Download:

Kamu juga bisa menggunakan aplikasi Pengingat Jadwal. Caranya:

1. Pastikan python sudah terinstall di komputermu. jika belum, kamu bisa menginstallnya di: python.org

2. Download file zip dengan cara menekan tombol download berikut:

download

3. extrak zip yang baru didownload.

    a. klik kanan pada file zip dan pilih "Extract All..."

    b.  klik tombol "Extract"

Menjalankan aplikasi

run program "schedule-controller2.py", sebuah window akan muncul. tekan tombol Add untuk menambahkan jadwal.

Kalau kamu sudah mencobanya, tolong beri ide-ide yang bagus ya di kolom komentar, saya ingin membuat aplikasi ini menjadi lebih bagus. agar aplikasi ini bermanfaat bagi anak anak yang sedang belajar di masa Pandemi. 

Catatan:

untuk sementara aplikasi ini TIDAK bisa digunakan di android

Cara kerja script (Jika kamu penasaran):

import time, tkinter

from tkinter.messagebox import showerror

from tkinter import font

1. kita "mengimpor" modul yang kita akan gunakan:

  a. modul time untuk mengetahui waktu sekarang.

  b. modul tkinter untuk membuat window di OS.

  c. selain itu, tkinter.messagebox untuk membuat message di OS.

class Entry(tkinter.Entry):

    def __init__(self, master = None, colors = None, **kw):

        super().__init__(master, **kw)

       

        self.var = tkinter.StringVar()

        self['bd'] = 0

        self['textvariable'] = self.var

        setup_border(self, colors['outlinebox'], colors['focus'])

        self['selectbackground'] = colors['focus']

        self['selectforeground'] = colors['foregroundbox']

        self['bg'] = colors['box']

        self['fg'] = colors['foreground']

       

class Spinbox(tkinter.Spinbox):

    def __init__(self, master = None, colors = None, **kw):

        super().__init__(master, **kw)

        self.var = tkinter.StringVar()

        self['bd'] = 0

        self['wrap'] = True

        self['textvariable'] = self.var

        setup_border(self, colors['outlinebox'], colors['focus'])

        self['selectbackground'] = colors['focus']

        self['selectforeground'] = colors['foregroundbox']

[......] (dipotong)

2. karena GUI tkinter kurang cocok untuk aplikasi ini, maka saya membuat GUI sendiri, menggunakan class. supaya lebih modern.

Saya juga menambahkan GUI yang belum ada, seperti: notification, scrollview, dll.

[in-progress]

-- MNA --