Laporan Akhir Lab TI Perancangan & Analisis Algoritma Pertemuan 4 Algoritma BFS dan DFS

Listing Program

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];

int del();

void add(int item);

void bfs(int s, int n);

void dfs(int s, int n);

void push(int item);

int pop();

main(){

int n,i,s,ch,j;

clrscr();

printf("masukkan angka ");

scanf("%d",&n);

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

printf("masukkan %d jika mempunyai simpul %d selain itu 0",i,j);

scanf("%d",&a[i][j]);

}

}

printf("matriks adjasensi\n");

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

printf("%d ",a[i][j]);

}

printf("\n");}

for(i=1;i<=n;i++)

a:

vis[i]=0;

printf("\nmenu");

printf("\n1. bfs");

printf("\n2. dfs");

printf("\npilihan:");

scanf("%d",&ch);

printf("\nmasukan simpul sumber:");

scanf("%d",&s);

switch(ch)

{

case 1:bfs(s,n);

goto a ;

case 2:dfs(s,n);

goto a ;

case 3:

break;

}

return(0);

}

void bfs(int s,int n){

int p,i;

add(s);

vis[s]=1;

p=del();

if(p!=0)

printf("%d ",p);

while(p!=0){

for(i=1;i<=n;i++)

if((a[p][i]!=0)&&(vis[i]==0)){

add(i);

vis[i]=1;

}

p=del();

if(p!=0)

printf("%d ",p);

}

for(i=1;i<=n;i++)

if (vis[i]==0)

bfs(i,n);

}

void add(int item){

if (rear==19)

printf("antrian full");

else

if (rear==-1){

q[++rear]=item;

front++;

}

else

q[++rear]=item;

}

int del(){

int k;

if((front>rear)||(front==-1))

return(0);

else {

k=q[front++];

return(k); } }

void dfs(int s, int n){

int i,k;

push(s);

vis[s]=1;

k=pop();

if(k!=0)

printf("%d ",k);

while(k!=0){

for(i=1;i<=n;i++)

if((a[k][i]!=0)&&(vis[i]==0)){

push(i);

vis[i]=1;

}

k=pop();

if (k!=0)

printf("%d ",k);

}

for(i=1;i<=n;i++)

if (vis[i]==0)

dfs(i,n); }

void push(int item) {

if(top==19)

printf("stack overflow");

else

stack[++top]=item;

}

int pop() {

int k;

if (top==-1)

return(0);

else {

k=stack[top--];

return(k); }}

Logika Program

#include<stdio.h>

#include<conio.h>

#include <stdlib.h>

Fungsi perintah diatas digunakan sebagai standard library yang berfungsi untuk I/O  package. Maksudnya agar pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita. library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat.

void add(int item);

Fungsi perintah diatas digunakan untuk mendefinisikan prosedur antrian penuh.

void bfs(int s, int n);

void dfs(int s, int n);

Fungsi perintah piatas digunakan untuk perhitungan bfs dan perhitungan dfs.

void push(int item);

Fungsi perintah diatas digunakan untuk jika terjadi kelebihan data .

main() {

Fungsi perintah diatas digunakan untuk prosedur utama dalam program.

clrscr();

Fungsi perintah diatas digunakan untuk membersihkan layar ketika program dieksekusi.

int n,i,s,ch,j;

Fungsi perintah diatas digunakan untuk mendeklarasikan variable n, i, s, ch dan j yang bertipe data integer (bilangan bulat).

printf("matriks adjasensi\n ");

Fungsi perintah diatas digunakan untuk mencetak tulisan matriks adjasensi. Pernyataan \n digunakan agar tulisan utama yang dicetak ada jedanya (enter) pada saat program dieksekusi.

scanf("%d",&n);

Fungsi perintah diatas digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %d yang mengartikan data inputan akan ditampilkan dalam bentuk decimal.

switch(ch){

Fungsi perintah diatas digunakan untuk kondisi percabangan.

case 1:bfs(s,n);

Fungsi perintah diatas digunakan untuk pilihan pertama dari percabangan, dimana program akan mengeksekusi blok procedure bfs.

case 2:dfs(s,n);

Fungsi perintah diatas digunakan untuk pilihan kedua dari percabangan, dimana program akan mengeksekusi blok procedure dfs.

case 3: break;  }

Fungsi perintah diatas digunakan untuk pilihan ketiga jika angka yang kita masukkan bukan 1 atau 2, maka program akan berhenti mengeksekusi.

return(0); }

Fungsi perintah diatas digunakan untuk mengambil data masukkan untuk melanjutkan eksekusi ke baris program berikutnya.

for(i=1;i<=n;i++)    {

Fungsi perintah diatas digunakan untuk kondisi perulangan, dimana mengeksekusi dimulai dari bilangan 1, program akan berhenti mengeksekusi jika variable i telah lebih besar daripada variable n, dan variable i akan bertambah satu setiap terjadi perulangan.

if(p!=0)

Fungsi perintah diatas digunakan untuk kondisi percabangan jika hasil bagi variable p tidak sama dengan 0.

getch();

Fungsi perintah diatas digunakan untuk membaca sebuah karakter, menampilkan karakter dari tombol yang ditekan, dan menunggu sembarang tombol ditekan.

BFS dan DFS merupakan jenis dari metode pencarian solusi. BFS merupakan metode pencarian solusi dimana semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan. DFS merupakan metode pencarian solusi dimana Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.

Dalam program ini, kita akan membuat pencarian BFS dan DFS dengan bantuan matriks. Program akan meminta inputan ordo dari matriks. Jika angka 2 dimasukkan, maka program akan memproses matriks 2 X 2. Setelah memasukan 2, maka program akan meminta elemen dari matriks tersebut, apabila kita memasukan 1 2 3 dan 4, program akan berlanjut pada proses percabangan, apakah akan memilih menu DFS atau BFS, ketika kita memilih DFS, program akan meminta simpul sumber, simpul sumber ini merupakan solusi yang akan dicari, ketika kita memasukan angka 2, maka yang tercetak 1 dan 2, secara BFS pun demikian, namun apabila kita memasukan angka 1, maka program tak akan memproses, ini dikarenakan program tidak menemukan solusi karena kita memasukan angka 2.

Output

Laporan Akhir Lab TI Perancangan & Analisis Algoritma Pertemuan 3 Algoritma Brute Force

Listing Program

#include <stdio.h>

#include <conio.h>

void prima(){

            int bil,j;

            printf("\n\t\tPencarian Bilangan Prima\n\n\n");

            printf("Masukan Bilangan Yang Ingin Diinput : ");

            scanf("%d",&bil);

            for(j=2;j<=bil;j++){

                        if((j%2>0)&&(j%3>0)&&(j%5>0)&&(j%7>0)||

                        (j==2)||(j==3)||(j==5)||(j==7))

                        printf("%i ",j);}

                        getch();

            }

void faktorial(){

            int hasil=1,i,bil;

            printf("\n\t\tPencarian Bilangan Faktorial\n\n");

            printf("Masukan Jumlah Faktorial Yang Ingin Diinput : ");

            scanf("%d",&bil);

            printf("\nAngka Faktorial : ");

            for(i=1;i<=bil;i++){

                        printf(" %d",i);

                        hasil=i*hasil;

                        }

            printf("\n\n\nJumlah Hasil Perkaliannya Adalah = %d",hasil);

}

main(){

            int pilihan;

            printf("\t\t\tMasukan Menu Pilihan Anda\n\n");

            printf("1. Bilangan Prima\n\n");

            printf("2. Bilangan Faktorialnya\n\n");

            printf("Masukan Nomor Pilihan : ");

            scanf("%i",&pilihan);

            switch(pilihan){

                        case 1:

                                    prima();

                                    break;

                        case 2:

                                    faktorial();

                                    break;

                        default:

                                    printf("Pilihan Tidak Tersedia");

                                    break;

                        }

            }

Logika Program

#include<stdio.h>

Dalam c++ jika kita menginginkan penggunaan input dan output, atau bisa diartikan sebagai standard library yang berfungsi untuk I/O  package maksudnya digunakan jika kita ingin pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita.

#include<conio.h>

Pernyataan conio.h adalah library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat. Tanpa menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti: gotoxy(), clrscr(), clreol(). Dan juga file header ini berfungsi untuk menampilkan hasil antarmuka kepada pengguna.

void prima(){

int bil,j;

Fungsi perintah diatas mendeklarasikan method bilangan prima yang bersifat void dan mendeklarasikan variable bilangan dan j memiliki tipe data integer.

printf("\n\t\tPencarian Bilangan Prima\n\n\n");

printf("Masukan Bilangan Yang Ingin Diinput : ");

scanf("%d",&bil);

Fungsi diatas adalah untuk menampilkan beberapa teks pada perintah printf atau cetak dan membuat perintah untuk menginput nilai yang diinputkan oleh user sendiri ke dalam variable bil.

for(j=2;j<=bil;j++){

Fungsi diatas adalah untuk melakukan perulangan pada variable j dengan kondisi nilai awalnya 2, nilai variable j lebih kecil dari nilai variable bil, dan j adalah increment.

if((j%2>0)&&(j%3>0)&&(j%5>0)&&(j%7>0)||

(j==2)||(j==3)||(j==5)||(j==7))

printf("%i ",j);}

getch();

}

Fungsi diatas adalah untuk percabangan maka jika nilai j mod 2 lebih besar dari 0 dan nilai j mod 3 lebih besar dari 0 dan nilai j mod 5 lebih besar dari 0 dan nilai j mod 7 lebih besar dari 0 atau nilai j sama dengan 2 atau nilai j sama dengan 3 atau nilai j sama dengan 5 atau nilai j sama dengan 7 lalu menampilkan nilai j. Dan jika menekan tombol enter maka akan kembali ke method utama.

void faktorial(){

int i,j,temp,n,bil[100];

int hasil=1,i,bil;

Fungsi diatas adalah untuk mendeklarasikan method faktorial yang bersifat void dan mendeklarasikan variable hasil=1,i,bil yang bertipe data integer.

printf ("\n \t\Pencarian Bilangan Faktorial \n \n" );

printf ("Masukkan Jumlah Faktorial Yang ingin Diinput: " );

scanf ("%d",&bil);

Fungsi diatas adalah untuk mencetak tulisan yang berada didalam kurung setelah perintah printf, memberi perintah input yang dilakukan oleh user sendiri, dan memasukan nilai yang akan diinputkan ke dalam nilai variabel bil.

printf("\nAngka Faktorial : ");

for(i=1;i<bil;i++){

printf(" %d",i);

hasil=i*hasil;

}

}

printf("\n\n\nJumlah Hasil Perkaliannya Adalah = %d",hasil);

}

Fungsi diatas adalah untuk mencetak tulisan yang ada pada tanda kurung setelah printah printf, perulangan pada variabel i dengan kondisi nilai awal i yaitu 1, nilai i lebih kecil dari bil, nilai i increment lalu mencetak nilai i, hasil yang dikeluarkan dari hasil perhitungan i*hasil setalah itu mencetak teks yang ada didalam kurung dengan mencetak hasil yang telah diinputkan dari perhitungan hasil pada kodingan sebelumnya.

main(){

int pilihan;

Fungsi diatas adalah untuk mengawali program method utama dan mendeklarasikan variabel pilihan yang menggunakan tipe data integer

printf("\t\t\tMasukan Menu Pilihan Anda\n\n");

printf("1. Bilangan Prima\n\n");

printf("2. Bilangan Faktorialnya\n\n");

printf("Masukan Nomor Pilihan : ");

scanf("%i",&pilihan);

Fungsi diatas adalah untuk menampilkan beberapa teks yang ada pada kodingan tersebut dan scanf untuk memberikan perintah input data yang dilakukan oleh user sendiri dan diinputkan kedalam nilai variable pilihan

switch(pilihan){

case 1:

prima();

break;

case 2:

faktorial();

break;

default:

printf("Pilihan Tidak Tersedia");

break;

}

}

Fungsi diatas  yaitu perintah switch case yang terdiri dari 3 pilihan, jika memilih case 1 maka akan memanggil method prima, kemudian jika memilih case 2 maka akan memanggil method factorial, dan jika tidak memilih salah satu dari pilihan case tersebut maka akan mencetak teks ”Pilihan Tidak Tersedia”. Fungsi dari break untuk menghentikan perintah dari switch atau menghentikan suatu loop.

Output

Laporan Akhir Lab TI Perancangan & Analisis Algoritma Pertemuan 2 Divide and Conquer

Listing Program

#include <stdio.h>

#include <conio.h>

int a[100];

int max,min;

void maxmin(int i, int j){

     int max1,min1,mid;

     if(i==j) {

              max=min=a[i]; }

              else if(i==j-1) {

                   if(a[i] > a[j]) {

                           max=a[i];

                           min=a[j];}

                                                                           else {max=a[j];

                                                                           min=a[i];}}

                           else {mid = (i+j)/2;

                           maxmin(i,mid);

                           max1 = max;

                           min1 = min;

                           maxmin(mid+1,j);

                           if(max < max1)

                           max = max1;

                           if(min > min1)

                           min = min1;

                           }}

int main(){

    int i,num;

    printf("\n\t\t\tMaximum Dengan Minimum\n\n");

    printf("Masukan Banyak Angka: ");

    scanf("%i", &num);

    printf("\nMasukan Angka-Angkanya: \n");

    for(i=0; i<num; i++) {

             scanf("%i", &a[i]);

             }

             printf("\nAngka-Angkanya adalah: \n");

             for(i=0; i<num; i++) {

                      printf("%i", a[i]);

                      }

                      max = a[0];

                      min = a[0];

                      maxmin(0,num-1);

                      printf("\n\nMaksimum Angka: %i\n", max);

                      printf("Minimum Angka: %i", min);

                      getch();

                      return 0;

                      }

Logika Program

Pada pertemuaan kali ini saya akan membuat program divide and conquer dan saya logika dar program yang saya buat. Disini saya menggunakan bahasa C++. Berikut adalah logikanya.

#include<stdio.h>

Dalam c++ jika kita menginginkan penggunaan input dan output, atau bisa diartikan sebagai standard library yang berfungsi untuk I/O  package maksudnya digunakan jika kita ingin pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita.

#include<conio.h>

Pernyataan conio.h adalah library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat. Tanpa menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti: gotoxy(), clrscr(), clreol(). Dan juga file header ini berfungsi untuk menampilkan hasil antarmuka kepada pengguna.

int a[100];

Fungsi diatas untuk mendeklarasikan a sebagai integer dan berbentuk aray.

int max,min;

Fungsi diatas untuk mendeklarasikan max, min sebagai  integer.

void maxmin(int i, int j)

Fungsi diatas adalah untuk melakukan perhitungan maxmin dengan variable utamanya i dengan tipe data integer dan j dengan tipe datanya integer. Void karena fungsi tersebut tidak mengembalikan suatu nilai keluaran yang didapat dari hasil proses fungsi tersebut.

int max1,min1,mid;

Fungsi diatas mempunyai ukuran nilai bilangan bulat (integer).

if(i==j) {

Fungsi diatas adalah untuk melakukan kondisi percabangan dalam suatu program.

max=min=a[i]; }

else if(i==j-1) {

Fungsi diatas adalah kondisi kedua (alternative) sebuah percabangan dalam suatu program, pernyataan ini akan dieksekusi jika kondisi dalam pernyataan utama tidak terpenuhi.

if(a[i] > a[j]) {

Fungsi diatas jika variable i lebih besar dari variable j maka lakukan perintah selanjutnya.

max=a[i];

min=a[j];}}

Fungsi diatas berfungsi untuk mengeksekusi nilai i akan masuk sebagai max dan j sebagai min.

else {max=a[j];

min = a[j]; }}

else {mid = (i+j)/2;

maxmin(i,mid);

max1 = max;

min1 = min;

maxmin(mid+1,j);

if(max < max1)

max = max1;

if(min > min1)

min = min1;

Fungsi diatas apabila perintah yang sebelumnya tidak terpenuhi maka lakukan perintah diatas. jika kondisi yang sebelumnya sudah terpenuhi maka perintah yang diatas tidak di jalankan.

int main(){

Fungsi diatas merupakan badan dari program.

int i,num;

printf("\n\t\t\tMaximum Dengan Minimum\n\n");

Fungsi diatas untuk mendeklarasikan i dan num sebagai integer. Dan pernyataan printf di atas digunakan untuk mencetak tulisan yang ada diantara tanda kutip , yaitu Maximum dan Minimum. Pernyataan \n digunakan untuk memberikan jeda (enter) pada saat program dieksekusi, sedangkan pernyataan \t digunakan agar tulisan utama yang

dicetak menjorok kedalam (tab) pada saat dieksekusi.

printf("Masukan Banyak Angka: ");

Fungsi diatas untuk mencetak kalimat yang berada di dalam tanda kutip, lalu kita akan mulai menginputkan angka.

scanf("%i", &num);

Fungsi diatas scanf digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %i yang mengartikan data inputan akan ditampilkan dalam bentuk integer decimal , dan &num mengartikan data inputan akan disimpan sementara pada variable num.

printf("\nMasukan Angka-Angkanya: \n");

Fungsi diatas adalah untuk mencetak kalimat yang berada dalam tanda kutip, \n adalah untuk memberikan jeda ke perintah selanjutnya. Lalu kita inputkan data sesuai dengan banyaknya jumlah data yang tadi kita input.

for(i=0; i<num; i++) {

scanf("%i", &a[i]); }

Fungsi for di atas digunakan sebagai kondisi perulangan pada program, program akan mengeksekusi dimulai dari 0 hingga terpenuhi kondisi i<num , dan variable i akan terus bertambah 1 jika terpenuhi kondisi i<num. Hasil dari eksekusi perulangan di atass akan tersimpan kedalam baris pernyataan scanf(“%i”,&a[ i ]).

printf("\nAngka-Angkanya adalah: \n");

Fungsi diatas akan mencetak kalimat yang berada di dalam tanda kutip pada layar.

for(i=0; i<num; i++) {

printf("%i", a[i]);}

program akan mengeksekusi dimulai dari 0 hingga terpenuhi kondisi i<num , dan variable i akan terus bertambah 1 jika terpenuhi kondisi i<num. lalu akan mencetak hasil dari pernyataan ("%i", a[i])

max = a[0];

min = a[0];

maxmin(0,num-1);

Fungsi diatas nilai max dan min diisi nilai array indeks 0. Perintah maxmin(0,num-1) adalah untuk menjalankan perintah diatas.

printf("\n\nMaksimum Angka: %i\n", max);

Fungsi diatas untuk mencetak kalimat yang berada di dalam tanda kutip, yang dimana angka tersebut dalam bentuk integer decimal, lalu akan muncul nilai yang maksimum dari data yang kita inputkan.

printf("Minimum Angka: %i", min);

Fungsi diatas untuk mencetak kalimat yang berada di dalam tanda kutip, yang dimana angka tersebut dalam bentuk integer decimal, lalu akan muncul nilai yang minimum dari data yang kita inputkan.

getch();

Fungsi diatas getch() untuk membaca sebuah karakter dengan sifat karakter yang dimasukkan tidak perlu diakhiri dengan menekan tombol enter, dan karakter yang dimasukan tidak akan ditampilkan di layar.

return 0;

Fungsi diatas angka 0 ini akan dikembalikan kepada sistem operasi. Nilai ini digunakan oleh sistem operasi untuk disimpan dimana 0 artinya ‘sukses’.

Output