Buatlah aplikasi rekursif dalam bahasa
pemograman tentang :
a. Faktorial
b. Perkalian
c. Fibonacci
d. Binary search
a. Faktorial
b. Perkalian
c. Fibonacci
d. Binary search
Rekursif
Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.
Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:
def kali(a, b):
return a if b == 1 else a + kali(a, b - 1)
Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintah a + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:
kali(2, 4)
-> 2 + kali(2, 3)
-> 2 + (2 + kali(2, 2))
-> 2 + (2 + (2 + kali(2, 1)))
-> 2 + (2 + (2 + 2))
-> 2 + (2 + 4)
-> 2 + 6
-> 8
Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.
Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:
def kali(a, b):
return a if b == 1 else a + kali(a, b - 1)
Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintah a + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:
kali(2, 4)
-> 2 + kali(2, 3)
-> 2 + (2 + kali(2, 2))
-> 2 + (2 + (2 + kali(2, 1)))
-> 2 + (2 + (2 + 2))
-> 2 + (2 + 4)
-> 2 + 6
-> 8
Perhatikan
bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi
rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti
(\(2\)). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru
dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir. Mari
kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan
perhitungan faktorial:
def
faktorial(n):
return n if n == 1 else n * faktorial(n -
1)
Fungsi
faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil
dan lihat langkah pemanggilannya:
faktorial(5)
-> 5 * faktorial(4)
-> 5 * (4 * faktorial(3))
-> 5 * (4 * (3 * faktorial(2)))
-> 5 * (4 * (3 * (2 * faktorial(1))))
-> 5 * (4 * (3 * (2 * 1)))
-> 5 * (4 * (3 * 2))
-> 5 * (4 * 6)
-> 5 * 24
-> 120
Dengan
melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita
dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:
1.Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2.Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.
Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.
1.Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2.Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.
Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.
Fungsi Rekursif dan Iterasi
Pembaca yang jeli akan menyadari bahwa kedua contoh fungsi rekursif yang diberikan sebelumnya, faktorial dan kali, dapat diimplementasikan tanpa menggunakan fungsi rekursif. Berikut adalah contoh kode untuk perhitungan faktorial tanpa menggunakan rekursif:
def faktorial_iterasi(n):
hasil = 1
for i in range(1, n + 1):
hasil = hasil * i
return hasil
Dalam menghitung nilai faktorial menggunakan iterasi, kita meningkatkan nilai hasil terus menerus, sampai mendapatkan jawaban yang tepat. Yang perlu kita pastikan benar pada fungsi ini adalah berapa kali kita harus meningkatkan nilai hasil. Jika jumlah peningkatan salah, maka hasil akhir yang didapatkan juga akan salah.
Pendekatan iteratif berbeda dengan rekursif dalam hal ini: jika pendekatan rekursif memecah-mecah masalah untuk kemudian menyelesaikan masalah sedikit demi sedikit, pendekatan iteratif justru langsung mencoba menyelesaikan masalah, tanpa memecah-mecahkan masalah tersebut menjadi lebih kecil terlebih dahulu. Untungnya, baik teknik iterasi maupun rekursi sama-sama memiliki tingkat ekspresi yang sama: segala hal yang dapat diselesaikan dengan itearsi akan dapat diselesaikan dengan rekursif. Lalu, kapan dan kenapa kita harus menggunakan rekursif?
Pembaca yang jeli akan menyadari bahwa kedua contoh fungsi rekursif yang diberikan sebelumnya, faktorial dan kali, dapat diimplementasikan tanpa menggunakan fungsi rekursif. Berikut adalah contoh kode untuk perhitungan faktorial tanpa menggunakan rekursif:
def faktorial_iterasi(n):
hasil = 1
for i in range(1, n + 1):
hasil = hasil * i
return hasil
Dalam menghitung nilai faktorial menggunakan iterasi, kita meningkatkan nilai hasil terus menerus, sampai mendapatkan jawaban yang tepat. Yang perlu kita pastikan benar pada fungsi ini adalah berapa kali kita harus meningkatkan nilai hasil. Jika jumlah peningkatan salah, maka hasil akhir yang didapatkan juga akan salah.
Pendekatan iteratif berbeda dengan rekursif dalam hal ini: jika pendekatan rekursif memecah-mecah masalah untuk kemudian menyelesaikan masalah sedikit demi sedikit, pendekatan iteratif justru langsung mencoba menyelesaikan masalah, tanpa memecah-mecahkan masalah tersebut menjadi lebih kecil terlebih dahulu. Untungnya, baik teknik iterasi maupun rekursi sama-sama memiliki tingkat ekspresi yang sama: segala hal yang dapat diselesaikan dengan itearsi akan dapat diselesaikan dengan rekursif. Lalu, kapan dan kenapa kita harus menggunakan rekursif?
Meskipun dapat menyelesaikan masalah yang
sama, terdapat beberapa permasalahan atau solusi yang lebih tepat diselesaikan
dengan menggunakan fungsi rekursif. Salah satu contoh dari masalah ini adalah
penelurusan data di dalam sebuah binary tree. Sebuah binary tree, yang dapat didefinisikan
sebagai sebuah pohon dengan jumlah cabang yang selalu dua, secara alami adalah
struktur data rekursif.
Faktorial adalah perkalian suatu bilangan bulat N dengan N-1, N-2, dan
seterusnya hingga 0.
Kalau begitu hasilnya selalu 0 dong, khan semua bilangan jika dikalikan dengan 0 adalah 0. Pada faktorial yang terjadi tidaklah demikian, karena ada perjanjian bahwa nilai faktorial 0 adalah 1, bukan 0.
Suatu faktorial dilambangkan dengan tanda seru (!) dan mengikuti rumus sebagai berikut:
N! = N x (N-1) x (N-2) x … x 0
Dalam bentuk lain, rumus di atas bisa dituliskan sebagai berikut:
N! = N x (N-1)!
Nah, program bahasa C yang digunakan untuk menghitung faktorial diberikan pada listing 2.
Listing 2. Menghitung faktorial
#include <stdio.h>
long int faktorial(int N);
Kalau begitu hasilnya selalu 0 dong, khan semua bilangan jika dikalikan dengan 0 adalah 0. Pada faktorial yang terjadi tidaklah demikian, karena ada perjanjian bahwa nilai faktorial 0 adalah 1, bukan 0.
Suatu faktorial dilambangkan dengan tanda seru (!) dan mengikuti rumus sebagai berikut:
N! = N x (N-1) x (N-2) x … x 0
Dalam bentuk lain, rumus di atas bisa dituliskan sebagai berikut:
N! = N x (N-1)!
Nah, program bahasa C yang digunakan untuk menghitung faktorial diberikan pada listing 2.
Listing 2. Menghitung faktorial
#include <stdio.h>
long int faktorial(int N);
Deklarasi variabel. Input bilangan yang akan
difaktorial.
Pemeriksaan kondisi, jika bilangan kurang dari nol, maka muncul peringatan, jika bilangan lebih besar atau sama dengan nol, maka fungsi faktorial() dipanggil.
Sementara itu di dalam fungsi faktorial() sendiri alurnya adalah sebagai berikut:
Deklarasi variabel.
Pemeriksaan kondisi, jika nilai bilangan kurang dari atau sama dengan 1, maka fungsi faktorial() akan menghasilkan nilai balik 1, jika nilai bilangan lebih dari 1, maka dihitung nilai faktorialnya. Perhitungan nilai faktorial mengikuti rumus N! = N x (N-1)!. Karena itu di dalam fungsi faktorial() ini dipanggil lagi fungsi faktorial() namun sekarang nilai argumennya adalah N-1.
Untuk membantu Anda dalam membayangkan alur tersebut, lihat bagan seperti terlihat pada gambar di bawah ini :
Menghitung Faktorial Dengan Bahasa C - Gambar2
Dengan memanfaatkan program faktorial di atas, kita bisa membuat suatu program lain yang juga bermanfaat, seperti misalnya program untuk menghitung permutasi dan kombinasi. Permutasi dan kombinasi merupakan proses perhitungan yang kerap dilakukan di bidang ilmu statistik. Rumus perhitungan permutasi dan kombinasi dapat dilihat pada gambar di bawah ini :
Pemeriksaan kondisi, jika bilangan kurang dari nol, maka muncul peringatan, jika bilangan lebih besar atau sama dengan nol, maka fungsi faktorial() dipanggil.
Sementara itu di dalam fungsi faktorial() sendiri alurnya adalah sebagai berikut:
Deklarasi variabel.
Pemeriksaan kondisi, jika nilai bilangan kurang dari atau sama dengan 1, maka fungsi faktorial() akan menghasilkan nilai balik 1, jika nilai bilangan lebih dari 1, maka dihitung nilai faktorialnya. Perhitungan nilai faktorial mengikuti rumus N! = N x (N-1)!. Karena itu di dalam fungsi faktorial() ini dipanggil lagi fungsi faktorial() namun sekarang nilai argumennya adalah N-1.
Untuk membantu Anda dalam membayangkan alur tersebut, lihat bagan seperti terlihat pada gambar di bawah ini :
Menghitung Faktorial Dengan Bahasa C - Gambar2
Dengan memanfaatkan program faktorial di atas, kita bisa membuat suatu program lain yang juga bermanfaat, seperti misalnya program untuk menghitung permutasi dan kombinasi. Permutasi dan kombinasi merupakan proses perhitungan yang kerap dilakukan di bidang ilmu statistik. Rumus perhitungan permutasi dan kombinasi dapat dilihat pada gambar di bawah ini :
Listing 3. Menghitung permutasi dan kombinasi
#include <stdio.h>
long int faktorial(int N);
main()
{
long int hasil;
int n,r;
char proses;
clrscr();
printf("Program Menghitung Permutasi atau Kombinasi \n");
printf("nPr atau nCr \n \n");
printf("Masukkan nilai n : ");
scanf("%d",&n);
printf("Masukkan nilai r : ");
scanf("%d",&r);
if (n<r) {
printf("Nilai n tidak boleh lebih kecil dari r");
} else {
printf("Pilih P (permutasi) atau C (kombinasi) : ");
proses = getche();
if (proses=='p' | proses=='P')
{
hasil = faktorial(n)/faktorial(n-r);
printf("\n \n");
printf("%dP%d = %ld",n,r,hasil);
}
#include <stdio.h>
long int faktorial(int N);
main()
{
long int hasil;
int n,r;
char proses;
clrscr();
printf("Program Menghitung Permutasi atau Kombinasi \n");
printf("nPr atau nCr \n \n");
printf("Masukkan nilai n : ");
scanf("%d",&n);
printf("Masukkan nilai r : ");
scanf("%d",&r);
if (n<r) {
printf("Nilai n tidak boleh lebih kecil dari r");
} else {
printf("Pilih P (permutasi) atau C (kombinasi) : ");
proses = getche();
if (proses=='p' | proses=='P')
{
hasil = faktorial(n)/faktorial(n-r);
printf("\n \n");
printf("%dP%d = %ld",n,r,hasil);
}
Berikut
outoutnya :
Aplikasi
rekursif dalam bahasa pemograman tentang perkalian.
Tutorial ini menjelaskan tentang penggunaan
rekursif dalam menghitung perkalian array matrix 2 dimensi. Sebelum dikalikan user
menginputkan dahulu baris dan kolom matrix pertama dan matrix kedua. Jika kolom
matrix pertama sama dengan baris matrix kedua maka akan terjadi proses
penghitungan, jika tidak maka saat proses ditampilkan “Perkalian matrix tidak
mungkin dilakukan.
#include<stdio.h>
#define MAX 10
void multiplyMatrix(int [MAX][MAX],int [MAX][MAX]);
int m,n,o,p;
int c[MAX][MAX];
int main(){
int a[MAX][MAX],b[MAX][MAX],i,j,k;
printf("Masukkan baris dan kolom matrix pertama (*beri spasi): ");
scanf("%d %d",&m,&n);
printf("Masukkan baris dan kolom matrix kedua (*beri spasi): ");
scanf("%d %d",&o,&p);
if(n!=o)
{
printf("Perkalian matrik tidak mungkin dilakukan");
printf("\nKolom pada matrix pertama harus sama dengan baris kolom kedua");
}
else{
printf("Masukkan nilai matrix pertama (*beri spasi): ");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
#define MAX 10
void multiplyMatrix(int [MAX][MAX],int [MAX][MAX]);
int m,n,o,p;
int c[MAX][MAX];
int main(){
int a[MAX][MAX],b[MAX][MAX],i,j,k;
printf("Masukkan baris dan kolom matrix pertama (*beri spasi): ");
scanf("%d %d",&m,&n);
printf("Masukkan baris dan kolom matrix kedua (*beri spasi): ");
scanf("%d %d",&o,&p);
if(n!=o)
{
printf("Perkalian matrik tidak mungkin dilakukan");
printf("\nKolom pada matrix pertama harus sama dengan baris kolom kedua");
}
else{
printf("Masukkan nilai matrix pertama (*beri spasi): ");
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&b[i][j]);
printf("\nMatrik pertama adalah: \n");
for(i=0;i<m;i++){
printf("\n");
for(j=0;j<n;j++){
printf("%d\t",a[i][j]);
}
}
printf("\nMatrik kedua adalah: \n");
for(i=0;i<o;i++){
printf("\n");
for(j=0;j<p;j++){
printf("%d\t",b[i][j]);
}
}
multiplyMatrix(a,b);
}
printf("\nPerkalian kedua matrix menghasilkan: \n");
for(i=0;i<m;i++){
printf("\n");
for(j=0;j<p;j++){
printf("%d\t",c[i][j]);
}
}
printf("\nMatrik pertama adalah: \n");
for(i=0;i<m;i++){
printf("\n");
for(j=0;j<n;j++){
printf("%d\t",a[i][j]);
}
}
printf("\nMatrik kedua adalah: \n");
for(i=0;i<o;i++){
printf("\n");
for(j=0;j<p;j++){
printf("%d\t",b[i][j]);
}
}
multiplyMatrix(a,b);
}
printf("\nPerkalian kedua matrix menghasilkan: \n");
for(i=0;i<m;i++){
printf("\n");
for(j=0;j<p;j++){
printf("%d\t",c[i][j]);
}
}
}
}
printf("\n\n");
return 0;
}
void multiplyMatrix(int a[MAX][MAX],int b[MAX][MAX]){
static int sum,i=0,j=0,k=0;
if(i<m){ //row of first matrix
if(j<p){ //column of second matrix
if(k<n){
sum=sum+a[i][k]*b[k][j];
k++;
multiplyMatrix(a,b);
}
c[i][j]=sum;
sum=0;
k=0;
j++;
multiplyMatrix(a,b);
}
j=0;
i++;
multiplyMatrix(a,b);
}
}
}
printf("\n\n");
return 0;
}
void multiplyMatrix(int a[MAX][MAX],int b[MAX][MAX]){
static int sum,i=0,j=0,k=0;
if(i<m){ //row of first matrix
if(j<p){ //column of second matrix
if(k<n){
sum=sum+a[i][k]*b[k][j];
k++;
multiplyMatrix(a,b);
}
c[i][j]=sum;
sum=0;
k=0;
j++;
multiplyMatrix(a,b);
}
j=0;
i++;
multiplyMatrix(a,b);
}
}
Berikut
outputnya :
Deret
fibonacci dengan fungsi rekursif.
Di
dalam deret fibonacci, angka ke(n) adalah penjumlahan dari angka ke(n-1) dengan
angka ke(n-2). sebagai contoh:
7
angka dalam deret fibonacci pertama adalah:
1,
1, 2, 3, 5, 8, 13
angka 13 adalah bilangan fibonacci dalam deret ke-7.
angka 13 di dapat dari penjumlahan angka 8 (yang merupakan bilangan
fibonacci deret ke-6) dengan angka 5
(yang merupakan bilangan fibonacci deret ke-5)
maka deret fibonacci dapat dipetakan sebagai
berikut:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
dengan pembatasan fib(2) dan fib(1) bernilai
1.
maka dari penjelasan di atas kita dapat
membuat coding programnya di dalam bahasa python seperti dibawah ini:
Data hosted with ♥ by Pastebin.com - Download
Raw - See Original
#deret fibonacci akan ditampilkan sebanyak
"x" kali
#contoh: jika x = 4, maka akan ditampilkan: 1, 1, 2, 3
# : jika x = 6, maka akan ditampilkan: 1, 1, 2, 3, 5, 8
#fungsi ini adalah FUNGSI REKURSIF
def fib(n):
if (n <= 2):
return 1
else:
return (fib(n-1)+fib(n-2))
print ("fungsi untuk menampilkan deret fibonacci sebanyak x buah")
n = int (input("masukkan x:"))
Deret fibonacci dengan fungsi non-rekursif
dengan fungsi iterasi (pengulangan) program dapat dibuat dengan lebih mudah. kita hanya tinggal melakukan perulangan dengan batas tertentu, dan menjumlahkan 2 bilangan sebelumnya di setiap perulangan. coding program:
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
#deret fibonacci akan ditampilkan sebanyak "x" kali
#contoh: jika x = 4, maka akan ditampilkan: 1, 1, 2, 3
# : jika x = 6, maka akan ditampilkan: 1, 1, 2, 3, 5, 8
#fungsi ini BUKAN fungsi rekursif
def fibonacci(x):
bil1=1
bil2=1
print ("|", bil1, end = " | ")
for i in range (1,x):
print(bil2,end = " | ")
if ((i+1) % 5 == 0):
print()
print ("| ",end="")
c = bil2
bil2 = bil2 + bil1
bil1 = c
print ("fungsi untuk menampilkan deret fibonacci sebanyak x buah")
x = int (input("masukkan x:"))
fibonacci(x)
#contoh: jika x = 4, maka akan ditampilkan: 1, 1, 2, 3
# : jika x = 6, maka akan ditampilkan: 1, 1, 2, 3, 5, 8
#fungsi ini adalah FUNGSI REKURSIF
def fib(n):
if (n <= 2):
return 1
else:
return (fib(n-1)+fib(n-2))
print ("fungsi untuk menampilkan deret fibonacci sebanyak x buah")
n = int (input("masukkan x:"))
Deret fibonacci dengan fungsi non-rekursif
dengan fungsi iterasi (pengulangan) program dapat dibuat dengan lebih mudah. kita hanya tinggal melakukan perulangan dengan batas tertentu, dan menjumlahkan 2 bilangan sebelumnya di setiap perulangan. coding program:
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
#deret fibonacci akan ditampilkan sebanyak "x" kali
#contoh: jika x = 4, maka akan ditampilkan: 1, 1, 2, 3
# : jika x = 6, maka akan ditampilkan: 1, 1, 2, 3, 5, 8
#fungsi ini BUKAN fungsi rekursif
def fibonacci(x):
bil1=1
bil2=1
print ("|", bil1, end = " | ")
for i in range (1,x):
print(bil2,end = " | ")
if ((i+1) % 5 == 0):
print()
print ("| ",end="")
c = bil2
bil2 = bil2 + bil1
bil1 = c
print ("fungsi untuk menampilkan deret fibonacci sebanyak x buah")
x = int (input("masukkan x:"))
fibonacci(x)
#include
<iostream>
//ini adalah yang si sebut liblary. dalam c++ kita juga dapat
//membuat liblary sendiri sesuai dengan yang di perlukan
using namespace std;
//tidak semua kompiler menggunakan ini, taoi jika anda menggunakan
//devc++ maka anda harus menggunakanya agar dapat terkompile.
int fibonacci(int suku) //Definisi fungsi , tanpa titik koma
{
if (suku == 0) return 0; //nilai awal 0
if (suku == 1) return 1; //nilai selanjutnya 1
return (fibonacci(suku-1) + fibonacci(suku-2));
//fungsi untuk menambahkan 2 suku sebelumnya, dan begitu seterusnya
}
int main(){ //main program mengembalikan nilai int secara default
int suku; // Deklarasi suku bertipe integer
cout << "Masukkan nilai suku ke-: ";
// Output pada layar untuk perintah memasukkan nilai suku
cin >> suku; // Menginputkan data suku oleh user
cout<<"\nBilangan fibonaccinya untuk "<<suku<<" adalah ";
cout<< fibonacci ( suku); //pemanggilan fungsi iteratif()
return 0;//memberitahu kepada sistem operasi bahwa program telah berakhir
}
//Penjelasan fibonacci rekursif :
//suku Fibonacci didapatkan dengan cara menjumlahkan
//kedua suku Fibonacci sebelumnya.
//dengan rumus (fib(num-1)+fib(num-2))
//ini adalah yang si sebut liblary. dalam c++ kita juga dapat
//membuat liblary sendiri sesuai dengan yang di perlukan
using namespace std;
//tidak semua kompiler menggunakan ini, taoi jika anda menggunakan
//devc++ maka anda harus menggunakanya agar dapat terkompile.
int fibonacci(int suku) //Definisi fungsi , tanpa titik koma
{
if (suku == 0) return 0; //nilai awal 0
if (suku == 1) return 1; //nilai selanjutnya 1
return (fibonacci(suku-1) + fibonacci(suku-2));
//fungsi untuk menambahkan 2 suku sebelumnya, dan begitu seterusnya
}
int main(){ //main program mengembalikan nilai int secara default
int suku; // Deklarasi suku bertipe integer
cout << "Masukkan nilai suku ke-: ";
// Output pada layar untuk perintah memasukkan nilai suku
cin >> suku; // Menginputkan data suku oleh user
cout<<"\nBilangan fibonaccinya untuk "<<suku<<" adalah ";
cout<< fibonacci ( suku); //pemanggilan fungsi iteratif()
return 0;//memberitahu kepada sistem operasi bahwa program telah berakhir
}
//Penjelasan fibonacci rekursif :
//suku Fibonacci didapatkan dengan cara menjumlahkan
//kedua suku Fibonacci sebelumnya.
//dengan rumus (fib(num-1)+fib(num-2))
Outptnya
:
PROGRAM
BINARY SEARCH
Binary Search merupakan metode pencarian dimana data harus diurutkan terlebih dahulu sebelum dilakukan proses pencarian. Pada metode pencarian ini, data dibagi menjadi dua bagian untuk setiap tahap pencarian.
Algoritma binary search :
Data diambil dari posisi 1 sampai posisi akhir n
Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
Jika data sama, berarti ketemu.
#include <iostream>
using namespace std;
#include <conio.h>
#include <iomanip>
int data[7] = {1, 8, 2, 5, 4, 9, 7};
int cari;
void selection_sort()
{
int temp, min, i, j;
for(i=0; i<7;i++)
{
min = i;
for(j = i+1; j<7; j++)
{
if(data[j]<data[min])
{
min=j;
}
Binary Search merupakan metode pencarian dimana data harus diurutkan terlebih dahulu sebelum dilakukan proses pencarian. Pada metode pencarian ini, data dibagi menjadi dua bagian untuk setiap tahap pencarian.
Algoritma binary search :
Data diambil dari posisi 1 sampai posisi akhir n
Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
Jika data sama, berarti ketemu.
#include <iostream>
using namespace std;
#include <conio.h>
#include <iomanip>
int data[7] = {1, 8, 2, 5, 4, 9, 7};
int cari;
void selection_sort()
{
int temp, min, i, j;
for(i=0; i<7;i++)
{
min = i;
for(j = i+1; j<7; j++)
{
if(data[j]<data[min])
{
min=j;
}
}
temp = data[i];
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
void binarysearch()
{
//searching
int awal, akhir, tengah, b_flag = 0;
awal = 0;
akhir = 7;
while (b_flag == 0 && awal<=akhir)
{
tengah = (awal + akhir)/2;
if(data[tengah] == cari)
{
b_flag = 1;
break;
data[min] = temp;
}
}
void binarysearch()
{
//searching
int awal, akhir, tengah, b_flag = 0;
awal = 0;
akhir = 7;
while (b_flag == 0 && awal<=akhir)
{
tengah = (awal + akhir)/2;
if(data[tengah] == cari)
{
b_flag = 1;
break;
}
else if(data[tengah]<cari)
awal = tengah + 1;
else
akhir = tengah -1;
}
if(b_flag == 1)
cout<<"\nData ditemukan pada index ke-"<<tengah<<endl;
else
cout<<"\nData tidak ditemukan\n";
}
int main()
else if(data[tengah]<cari)
awal = tengah + 1;
else
akhir = tengah -1;
}
if(b_flag == 1)
cout<<"\nData ditemukan pada index ke-"<<tengah<<endl;
else
cout<<"\nData tidak ditemukan\n";
}
int main()
Outputnnya:
Tidak ada komentar:
Posting Komentar