Rabu, 06 April 2011

Tugas

ARRAY

PENGERTIAN

            Array atau larik di definisikan sebagai pemesanan alokasi memory berurutan.definisi ini kurang tepat, karena terjadi kerancuan antara struktur data dan representasinya. Memang benar array hampir selalu di implementasikan menggunakan memory berurutan tapi tidak selalu demikian.
Semua elemem array bertipe sama. Array cocok untuk organisasi kumpulan data homogen yang ukuran atau jumlah elemen maksimumnya telah diketahui dari awal.
Homogen adalah bahwa setiap elemen dari sebuah array tertentu haruslah mempunyai tipe data yang sama.
 KARAKTERISTIK ARRAY
a)      Mepunyai batasan dari pemesanan alokasi memori (bersifat statis)
b)      Mempunyai tipe data sama (bersifat homogen)
c)      Dapat diakses secara acak.

DEKLARASI ARRAY
Ada tiga hal yang harus di ketahui dalam mendeklarasikan array, yaitu :
a)      Type data array
b)      Nama variable array
c)      Subkrip / index array.
Contoh deklarasi dari array adalah sebagai berikut :
int A[5] ; artinya variabel A adalah kumpulan data sebanyak 5 bilangan bertipe
integer.






 JENIS ARRAY
1.      ARRAY DIMENSI SATU
Deklarasi         : Type_Data Nama_Variabel [index]
Rumus untuk menentukan jumlah elemen dalam array adalah :


n
p (Index Array)
i = 1


 
 




p = Perkalian dari index sebelumnya (untuk arraybdimensi dua dan tiga).

PEMETAAN (MAPPING) ARRAY DIMENSI SATU KE STORAGE
Rumus             :  @A[i] = B + (i – 1) * L
Dimana            :  @A[i]           :  Posisi array yang dicari
                                    B         :  Posisi awal index di memori computer
                                    i           :  Subkrip atau index array yang di cari
                                    L          :  Ukuran atau besar memori suatu tipe data
2.      ARRAY DIMENSI DUA
Deklarasi         : Type_Data Nama_Variabel [index1] [index2]
            Menentukan jumlah elemen dalam array dimensi dua :


n
p (Index Array)
i = 1


 
 




p = Perkalian dari statemen sebelumnya

PEMETAAN (MAPPING) ARRAY DIMENSI DUA KE STORAGE
Terbagi dua cara pandang (representasi) yang berbeda :
·         Secara kolom per kolom (coloumn major order / CMO)


@M[i][j] = M[0][0] + {(j – 1) * K + (i – 1)} * L
 
 


·         Secara baris per baris (row major order / RMO)


@M[i][j] = M[0][0] + {(i – 1) * N + (j – 1)} * L
 
 


Keterangan      :
@M[i][j] = Posisi array yang di cari, M[0][0 = Posisi alamat awal index array, i = Baris, j = Kolom, L = Ukuran memory type data, K = Banyaknya elemen per kolom, N = Banyaknya elemen per baris.

3.      ARRAY DIMENSI TIGA
Deklarasi         : type_Data Nama_Variabel [index1][index2][index3]
Menentukan jumlah elemen dalam array dimensi tiga :
n
p (Index Array)
i = 1


 
 




p = Perkalian dari statemen sebelumnya

PEMETAAN (MAPPING) ARRAY DIMENSI TIGA KE STORAGE


Rumus : @M[n][m][p] = M[0][0][0] + {((n – 1) * (index1)) + ((m – 1) *     (index2)) + ((p – 1) * (index3)} * L
 
 




TRIANGULAR ARRAY (ARRAY SEGI TIGA)
Triangular array dapat merupakan Upper Triangular (seluruh elemen di bawah diagonal utama = 0), ataupun Lower Triangular (seluruh elemen di atas diagonal utama = 0).
Dalam array Lower Triangular dengan N baris, jumlah maksimum elemen <> 0, tidak lebih dari  
N
          I = N (N+1)/2
I = 1

 
 





SPERSE ARRAY (ARRAY JARANG)
Suatu array yang sangat banyak elemen nol-nya.

 OPERASI DASAR PADA ARRAY
Operasi terhadap elemen di array dilakukan dengan pengaksesan langsung. Nilai
di masing-masing posisi elemen dapat diambil dan nilai dapat disimpan tanpa melewati
posisi-posisi lain.
Terdapat dua tipe operasi, yaitu :
1. Operasi terhadap satu elemen / posisi dari array
2. Operasi terhadap array sebagai keseluruhan

Dua operasi paling dasar terhadap satu elemen / posisi adalah
1. Penyimpanan nilai elemen ke posisi tertentu di array
2. Pengambilan nilai elemen dari posisi tertentu di array

Operasi-operasi dasar terhadap array secara keseluruhan adalah :
1. Operasi penciptaan
2. Operasi penghancuran
3. Oparasi pemrosesan traversal
4. Operasi pencarian (table look-up)
5. Operasi sorting

                                    Rekursif & Itertif
Pengertian
Rekursif berarti bahwa suatu proses bisa memanggil dirinya sendiri. Menurut definisi dalam Microsoft Bookshelf,  Rekursif adalah kemampuan suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir.
penjelasan Rekursif & Iteratif
Kelebihan perulangan rekursif:
• Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar.
• Dapat melakukan perulangan dengan batasan fungsi.
Kekurangan perulangan rekursif:
• Tidak bisa melakukan nested loop atau looping bersarang.
• Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan         tertentu saja.
• Trace error sulit.
• Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack dan ada kalanya akan menyebabkan stack tak cukup lagi (Stack Overrun).
• Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk.
jika pada program 1, diubah kedalam bentuk
Dalam bentuk rekursif :          
#include <cstdlib>
#include <iostream>


using namespace std;                                                                                                                               int jumlah(int n) {
if(n==0) return (0);
else return (n-2 + jumlah(n-2));
}
void cetak(int n) {                                                                                                                          if(n!=0){
cetak(n-2);
cout << n-2 << ” “;
}
}
int main(int argc, char *argv[])
{
int n = 10;
cout << jumlah(n);
cetak(n);
system(“PAUSE”);
return EXIT_SUCCESS;
}
Rekursif  Versus  Iteratif
            Dalam beberapa situasi, pemecahan secara rekursif maupun secara iteratif mempunyai keuntungan dan kekurangan yang bisa saling diperbandingkan. Adalah cukup sulit untuk menentukan mana yang paling sederhana, paling jelas, paling efisien dan paling mudah disbanding yang lain. Boleh dikatakan pemilihan cara iterative maupun rekursif merupakan kesenangan seorang programmer dan tergantung konteks permasalahan yang akan dipecahkan sesuai dengan kesanggupan yang bersangkutan.
Persamaan antara perulangan iteratif dan rekursif:
• Iteratif dan rekursif merupakan metode atau teknik di dalam perulangan (looping).
• Sama-sama mengalami perulangan kondisi.




String dan Rekursi
1. Metode perulangan rekursif dan contoh program aplikasi perulangan rekursif:
Perulangan rekursif merupakan salah satu metode didalam pemrograman yang mana dalam sebuah fungsi terdapat intruksi yang memanggil fungsi itu sendri, atau lebih sering disebut memanggil dirinya sendiri.
2. Metode perulangan iteratif dan contoh program aplikasi perulangan iteratif:
Perulangan iteratif merupakan perulangan yang melakukan proses perulangan terhadap sekelompok intruksi. Perulangan dilakukan dalam batasan syarat tertentu. Ketika syarat tersebut tidak terpenuhi lagi maka perulangan aka terhenti.
Contoh aplikasinya:
Berikut merupakan contoh program faktorial yang mana inputan akan dikalikan dengan nilai inputan itu sendiri dikurangi satu hingga mencapai nilai satu.
a. Implementasi
#include
Main()
{
Int i;
For (i=1;i<10;i++)
{
Printf(“Ini perulangan iteratif\n”);
}
}
b. Hasil
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
Ini perulangan iteratif
1. Persamaan antara perulangan iteratif dan rekursif
• Iteratif dan rekursif merupakan metode atau teknik didalam perulangan(looping)
• Sama-sama memiliki bagian yang berfungsi sebagai batas dalam sebuah perulangan.
Perbedaan antara perulangan iteratif dan rekursif
• Iteratif dapat berjalan pada program yang terdiri dari prosedur (Tidak terdapat fungsi) sedangkan rekursif merupakan fungsi.
• Iteratif dalam melakukan perulangan membutuhkan suatu instruksi program seperti for, while dan while do, sedangkan rekursi tidak memakai instruksi program seperti itu.

Kelebihan perulangan iterative :
• Mudah dipahami dan mudah dilakukan debuging ketika ada perulangan yang salah.
• Dapat melakukan nested loop atau yang disebut dengan looping bersarang.
• Proses lebih singkat karena perulangan terjadi pada kondisi yang telah disesuaikan.
• Jarang terjadi overflow karena batasan dan syarat perulangan yang jelas.

Kelemahan perulangan iterative :
• Tidak dapat menggunakan batasan berupa fungsi.
• Perulangan dengan batasan yang luas akan menyulitkan dalam pembuatan program perulangan itu sendiri.
Kelebihan perulangan rekursif :
• Sangat mudah untuk melakukan perulangan dengan batasan yang luas dalam artian melakukan perulangan dalam skala yang besar.
• Dapat melakukan perulangan dengan batasan fungsi.
Kekurangan perulangan rekursif :
• Tidak bisa melakukan nested loop atau looping bersarang.
• Biasanya membuat fungsi sulit untuk dipahami, hanya cocok untuk persoalan tertentu saja
• Memerlukan stack yang lebih besar, sebab setiap kali fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack dan ada kalaya akan menyebabkan stack tak cukup lagi (Stack Overum);
• Proses agak berbelit-belit karena terdapat pemangilan fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk..
1. Base case dan rekursive case:
• Base case merupakan bagian dari perulangan rekursif yang berfungsi sebagai batasan, dengan demikian suatu fungsi akan terus melakukan pemanggilan terhadap dirinya sendiri selama syarat pada bagian basecase masih terpenuhi.
• Rekursif case merupakan bagian dimana fungsi tersebut memanggil dirinnya sendiri. Prosesnya dapat digambarkan seperti:
funsi(fungsi(fungsi(fungsi())))
 



           
Contohnya:
int perkalian(int bilangan1, int bilangan2)
{
If(bilangan2==1)return bilangan1;
else return bilangan1+perkalian(bilangan1,bilangan2-1);
}
Baris 1=Base Case
Baris 2=Recursive Case
Jika program diatas diberi input Bilangan1=7 dan Bilngan2=6 maka outputnya:
42
Program diatas dapat diubah kedalam bentuk iteratif menjadi:
int perkalian(int bilangan1, int bilangan2)
{
int i,hasil=bilangan1;
for(i=1; i
{
hasil=bilangan1+hasil;
}
return hasil;
}

1. Defenisi fungsi Ackermen function:
A(0,n)=n+1 untuk n>=0
A(m,0)=A(m-1,1) untuk m>=0
A(m,n)=A(m-1,A(m,n-1)) untuk m,n>0
Maka apabila diinputkan A(3,3), dengan menggunkan call trace didapatkan hasil berupa nilai 61 dengan uraian sebagai berikut:
   program faktorial dengan rekursif:           
methode rekursif adalah perulangan dengan menggunakan teknik memanggil methode itu sendiri. reskursif tidak mengunakan teknik perulangan iteratif (misalnya for atau while).