1. Sekolah Dasar
  2. Sekolah Menengah Pertama
  3. Sekolah Menengah Atas
  4. Mata Pelajaran
  5. Programming

Buat sebuah algoritma menggunakan pseudocode atau flowchart untuk menentukan sebuah

Berikut ini adalah pertanyaan dari Ahmadlunox1244 pada mata pelajaran TI untuk jenjang Sekolah Menengah Atas

Buat sebuah algoritma menggunakan pseudocode atau flowchart untuk menentukan sebuah deret fibonacci, kemudian coba buktikan dengan menggunakan induksi matematika!

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Asumsi:
Yang dimaksud dengan “menentukan sebuah deret Fibonacci”adalah menentukann bilangan Fibonacci pertama beserta jumlahnya, dengan masukan/input n ∈ bilangan asli.
Misalkan: n = 5, maka algoritma menghasilkan 1, 1, 2, 3, 5 dengan jumlah deret = 12.
______________

Pseudocode

Algoritma Deret Fibonacci (Iteratif)
Input: Bilangan bulat positif.
Output: n bilangan Fibonacci pertama, dan jumlahnya.

read n
jumlah ← 0
if n < 1 then
   print “n harus lebih dari atau sama dengan 1”
else if n = 1 then
   print 1   # bilangan Fibonacci
   print 1   # jumlah deret bilangan Fibonacci
else
   fib ← [1, 1]
   jumlah ← 2
   for i ← 3 to n, do
       fib[i] ← fib[i–1] + fib[i–2]
       jumlah ← jumlah + fib[i]
   print fib  # mencetak isi array fib
    print jumlah
______________

Pembuktian dengan Induksi Matematika

Sebelum membuktikan, kita perhatikan definisi barisan/deret bilangan Fibonacci.

Sepengetahuan saya, ada 2 versi dalam penjabaran bilangan Fibonacci, yaitu:

  • Versi 1: dimulai dengan indeks 0, barisan = 0, 1, 1, 2, 3, 5, ...
  • Versi 2: dimulai dengan indeks 1, barisan = 1, 1, 2, 3, 5, ...

Di sini saya gunakan versi 2, di mana bilangan Fibonacci ke-n dinyatakan oleh F_n yang memenuhi definisi:
\begin{aligned}F_n=\begin{cases}1\,,&{\sf jika\ }n \le 2\,,\ n\in\mathbb{N}\\F_{n-1}+F_{n-2}\,,&{\sf jika\ }n > 2\,,\ n\in\mathbb{N}\\\end{cases}\end{aligned}

Maka, pembuktian terhadap blangan Fibonacci ke-n tidak perlu dilakukan, karena merupakan bagian dari definisinya.

Menurut saya, yang perlu dibuktikan adalah jumlah deret bilangan Fibonacci.

Penelusuran algoritma di atas dengan input n = 5 (tanpa eksekusi print) adalah sebagai berikut.

  • fib = [1, 1], jumlah = 2
  • i = 3: fib = [1, 1, 2], jumlah = 2+2 = 4
  • i = 4: fib = [1, 1, 2, 3], jumlah = 4+3 = 7
  • i = 5: fib = [1, 1, 2, 3, 5], jumlah = 7+5 = 12

Jika kita teruskan iterasinya tanpa menghitung jumlahnya, maka diperoleh:

  • i = 6: fib = [1, 1, 2, 3, 5, 8]
  • i = 7: fib = [1, 1, 2, 3, 5, 8, 13]

Jadi, jumlah 5 bilangan Fibonacci pertama, yaitu 12, sama dengan F_7-1, atau dengan kata lain, sama dengan F_{5+2}-1.

Jadi, pernyataan yang ingin dibuktikan adalah:

Jumlah deret n bilangan Fibonacci pertama dinyatakan oleh:
\begin{aligned}\sum_{i=1}^nF_i=F_{n+2}-1\end{aligned}
untuk n ∈ bilangan asli.

Basis Induksi

Untuk n = 1:

\begin{aligned}\sum_{i=1}^1F_i&=F_{3}-1\\F_1&=F_2+F_1-1\\&=1+1-1\\&=1\end{aligned}

Sesuai definisi, F_1 = 1. Maka basis induksi terbukti benar.

Asumsi/Hipotesis

Untuk n = k, diasumsikan benar bahwa:

\begin{aligned}\sum_{i=1}^kF_i=F_{k+2}-1\end{aligned}

Langkah Induksi

Berdasarkan asumsi tersebut dan definisi bilangan Fibonacci di atas, perlu dibuktikan bahwa untuk n = k+1, berlaku:

\begin{aligned}\sum_{i=1}^{k+1}F_i=F_{k+3}-1\end{aligned}

Pembuktian Langkah Induksi:

\begin{aligned}&{\sf Ruas\ kiri}=\sum_{i=1}^{k+1}F_i\\&{=\ }\sum_{i=1}^{k}F_i+F_{k+1}\\&{=\ }\left(F_{k+2}-1\right)+F_{k+1}\\&{=\ }\left(F_{k+2}+F_{k+1}\right)-1\\&{=\ }\left(F_{(k+3)-1}+F_{(k+3)-2}\right)-1\\\vphantom{\big|}&\quad\to \textsf{Berdasarkan d{ef}inisi:}\\&\qquad\ \:F_{(k+3)-1}+F_{(k+3)-2}=F_{k+3}\\\vphantom{\Big|}&{=\ }F_{k+3}-1=\sf Ruas\ kanan\\\end{aligned}

⇒ Langkah induksi terbukti benar.

Kesimpulan

∴  Dengan induksi matematika, pernyataan bahwa jumlah deret n bilangan Fibonacci pertama dinyatakan oleh:
\begin{aligned}\sum_{i=1}^nF_i=F_{n+2}-1\end{aligned}
untuk n ∈ bilangan asli, terbukti benar.

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Sat, 24 Dec 22
<< Previous Post
Next Post >>