Showing posts with label Logika dan Pemrograman Sistem II. Show all posts
Showing posts with label Logika dan Pemrograman Sistem II. Show all posts

Monday, May 3, 2010

IMPROVING QUICKSORT(HOURS 14)


Quicksort emang dapat mengurutkan data dengan cepat namun quicksort akan kurang efisien jika dihadapkan pada data yang ter-invers(terbalik) ataupun dengan data yang jumlahnya sedikit, karena itu diperlukan peningkatan kinerja dari quicksort agar dapat menangani masalah tersebut serta mempercepat kinerja quicksort.
Data terbalik

Masalah pada data terbalik adalah pada pivot. Pada bab sebelumnya pivot yang dipilih adalah indeks terbesar dari array data, masalah ini dapat ditangani dengan memilih pivot pada median(tengah) data. Sehingga diperoleh 2 bagian yang lebih mudah dalam pembagian selanjutnya.
Median-of-Three Partitioning
  • Pilih nilai indeks awal, tengah, dan akhir
  • Urutkan ketiga nilai tersebut
  • Pilih median dari 3 nilai tersebut sebagai pivot
  • Lakukan quicksort
Implementasinya dalam c++

//quickSort2.cpp

//demonstrates quick sort with median-of-three partitioning

#include <iostream>

#include <vector>

#include <cstdlib> //for random numbers

#include <ctime> //for random numbers

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double>(theVect); //vector of doubles

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) : nElems(0) //constructor

{

theVect.resize(max); //size the vector

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theVect[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theVect[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort array

{

recQuickSort(0, nElems-1); //call recursive sort

}

//--------------------------------------------------------------

void recQuickSort(int left, int right) //recursive sort

{

int size = right-left+1;

if(size <= 3) //manual sort if smallmanualSort(left, right);

else //quicksort if large

{

double median = medianOf3(left, right);

int partition = partitionIt(left, right, median);

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

} //end recQuickSort()

//--------------------------------------------------------------

double medianOf3(int left, int right)

{

int center = (left+right)/2;

//order left & center

if( theVect[left] > theVect[center] )

swap(left, center);

//order left & right

if( theVect[left] > theVect[right] )

swap(left, right);

//order center & right

if( theVect[center] > theVect[right] )

swap(center, right);

swap(center, right-1); //put pivot on right

return theVect[right-1]; //return median value

} //end medianOf3()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theVect[dex1]; //A into temp

theVect[dex1] = theVect[dex2]; //B into A

theVect[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

//partition a range

int partitionIt(int left, int right, double pivot)

{

int leftMark = left; //right of first elem

int rightMark = right - 1; //left of pivot

while(true)

{

while( theVect[++leftMark] < pivot ) //find bigger

; // (nop)

while( theVect[--rightMark] > pivot ) //find smaller

; // (nop)

if(leftMark >= rightMark) //if pointers cross, break; // partition done

else //not crossed, so

swap(leftMark, rightMark); //swap elements

} //end while(true)

swap(leftMark, right-1); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void manualSort(int left, int right)

{

int size = right-left+1;

if(size <= 1)

return; //no sort necessary

if(size == 2)

if( theVect[left] > theVect[right] )

swap(left, right);

return;

}

else //size==3, so 3-sort left, center (right-1) & right

{

if( theVect[left] > theVect[right-1] )

swap(left, right-1); //left, center

if( theVect[left] > theVect[right] )

swap(left, right); //left, right

if( theVect[right-1] > theVect[right] )

swap(right-1, right); //center, right

}

} //end manualSort()

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

time_t aTime;

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create the array

srand( static_cast<unsigned>(time(&aTime)) ); //seed randoms

for(int j=0; j<maxSize; j++) //fill array with

{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main()

Handling Small Partitions

Algoritma quicksort standar tidak dapat bekerja mengurutkan bagian dengan 3 data atau lebih sedikit dari itu. Dalam hal ini jumlah tersebut disebut dengan cutoff point


Menggunakan insertion sort untuk bagian data yang kecil

Insertion sort dapat dipakai untuk menangani bagian data yang kecil dimana insertion sort akan dipakai saat bertemu dengan cutoff point.
  • Insertion sort dilakukan sebagai bagian dari quicksort setelah mencapai data sedikit(cutoff point)
  • Metode:
  1. Quicksort dilanjutkan insertion sort untuk data sedikit
  2. Quicksort kemudian sort dihentikan untuk data sedikit( mencapai cutoff point). Lalu dilakukan insertion sort secara keseluruhan
Listing untuk mengangani data kecil

//quickSort3.cpp

//demonstrates quick sort; uses insertion sort for cleanup

#include <iostream>

#include <vector>

#include <cstdlib> //for rand()

#include <ctime> //for rand()

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double> theArray; //array theArray

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) //constructor

{

theArray.reserve(max); //change size of vector

nElems = 0; //no items yet

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theArray[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theArray[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort the array

{

recQuickSort(0, nElems-1);

// insertionSort(0, nElems-1); //(another option)

}

//--------------------------------------------------------------

void recQuickSort(int left, int right) //recursive quicksort

{

int size = right-left+1;

if(size < 10) //insertion sort if small

insertionSort(left, right);

else //quicksort if large

{

double median = medianOf3(left, right);

int partition = partitionIt(left, right, median);

recQuickSort(left, partition-1);

recQuickSort(partition+1, right);

}

} //end recQuickSort()

//--------------------------------------------------------------

double medianOf3(int left, int right)

{

int center = (left+right)/2;

//order left & center

if( theArray[left] > theArray[center] )

swap(left, center);

//order left & right

if( theArray[left] > theArray[right] )

swap(left, right);

//order center & right

if( theArray[center] > theArray[right] )

swap(center, right);

swap(center, right-1); //put pivot on right

return theArray[right-1]; //return median value

} //end medianOf3()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theArray[dex1]; //A into temp

theArray[dex1] = theArray[dex2]; //B into A

theArray[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

int partitionIt(int left, int right, double pivot)

{

int leftMark = left; //right of first elem

int rightMark = right - 1; //left of pivot

while(true)

{

while( theArray[++leftMark] < pivot ) //find bigger

; // (nop)

while( theArray[--rightMark] > pivot ) //find smaller; // (nop)

if(leftMark >= rightMark) //if pointers cross,

break; // partition done

else //not crossed, so

swap(leftMark, rightMark); //swap elements

} //end while(true)

swap(leftMark, right-1); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void insertionSort(int left, int right) //insertion sort

{

int in, out;

//sorted on left of out

for(out=left+1; out<=right; out++)

{

double temp = theArray[out]; //remove marked item

in = out; //start shifts at out

//until one is smaller,

while(in>left && theArray[in-1] >= temp)

{

theArray[in] = theArray[in-1]; //shift item to right

--in; //go left one position

}

theArray[in] = temp; //insert marked item

} //end for

} //end insertionSort()

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create array

time_t aTime; //seed random numbers

srand(static_cast<unsigned>( time(&aTime) ));

for(int j=0; j<maxSize; j++) //fill array with

{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main() 


Sumber : Kuliah Logika dan Pemrograman Sistem II

READ MORE - IMPROVING QUICKSORT(HOURS 14)

QUICKSORT (HOURS13)


Pada bab sebelumnya telah dibahas mergesort dimana dapat mengurutkan dengan cepat namun memerlukan ruang lebih banyak untuk melakukan pengkopian array-array yang akan diurutkan. Sehingga memerlukan banyak memori. Sementara quicksort sama cepat dengan mergesort hanya keunggulannya memerlukan sedikit memori.
Inti dari quicksort

  • data dibagi 2 bagian dengan 1 titik bagi
  • mengulangi pembagian pada masing masing bagian
Proses mengurutkan(mergesort)

  • bagi data menjadi 2 dengan jumlah sama
  • urutkan masing-masing bagian
  • lakukan penggabungan(merge)
Partition

quicksort bekerja dengan membagi data menjadi bagian-bagian(partition) dan proses ini dilakukan berulang-ulang pada masing-masing bagian. Untuk melakukan partition dimulai dengan memilih titik/nilai acuan(pivot) untuk kemudian membandingkan data dengan pivot tersebut sehingga diperoleh 2 bagian data yaitu data yang lebih besar dari pivot dan data yang lebih kecil dari pivot.


Setelah didapat 2 bagian seperti pada gambar diatas maka masing-masing bagian akan dibagi lagi dengan menentukan pivot pada masing masing bagian sehingga data akan terurut.

Proses program dasar quicksort

  1. tentukan pivot sebagai index bagain terbesar
  2. Ki(data bagian terkiri) digeser ke kanan sampai ki > pivot
  3. Ka(data bagian terkanan) digeser ke kiri sampai ka < pivot
  4. Jika ka > ki maka nilai di ka dan ki ditukar
Proses jalannya quicksort
  1. pivot array 70, data dibandingkan
  2. diambil bagian kiri pivot 50, data dibandingkan
  3. diambil pivot 40, data dibandingkan
  4. diambil pivot 20, data dibandingkan
  5. diambil bagian kanan
  6. diambil pivot 110, data dibandingkan
  7. diambil pivot 100, data dibandingkan
  8. diambil pivot 80, data dibandingkan
  9. didapatkan array yang terurut
listing quicksort

//quickSort1.cpp

//demonstrates simple version of quick sort

#include <iostream>

#include<vector>

#include<cstdlib> //for random numbers

#include<ctime> //for random numbers

using namespace std;

////////////////////////////////////////////////////////////////

class ArrayIns

{

private:

vector<double>(theVect); //vector of doubles

int nElems; //number of data items

public:

//--------------------------------------------------------------

ArrayIns(int max) : nElems(0) //constructor

{

theVect.resize(max); //size the vector

}

//--------------------------------------------------------------

void insert(double value) //put element into array

{

theVect[nElems] = value; //insert it

nElems++; //increment size

}

//--------------------------------------------------------------

void display() //displays array contents

{

cout << "A=";

for(int j=0; j<nElems; j++) //for each element,

cout << theVect[j] << " "; //display it

cout << endl;

}

//--------------------------------------------------------------

void quickSort() //sort array

{

recQuickSort(0, nElems-1); //call recursive sort

}

//-------------------------------------------------------------- void

recQuickSort(int left, int right) //recursive sort

{

if(right-left <= 0) //if size <= 1, return; // already sorted

else //size is 2 or larger

{

double pivot = theVect[right]; //rightmost item

//partition range

int partition = partitionIt(left, right, pivot);

recQuickSort(left, partition-1); //sort left side

recQuickSort(partition+1, right); //sort right side

}

} //end recQuickSort()

//--------------------------------------------------------------

int partitionIt(int left, int right, double pivot)

{

int leftMark = left-1; //left (after ++)

int rightMark = right; //right-1 (after --)

while(true)

{ //find bigger item

while( theVect[++leftMark] < pivot )

; // (nop)

//find smaller item

while(rightMark > 0 && theVect[--rightMark] > pivot)

; // (nop)

if(leftMark >= rightMark) //if pointers cross,

break; // partition done

else //not crossed, so

swap(leftMark, rightMark); // swap elements

} //end while(true)

swap(leftMark, right); //restore pivot

return leftMark; //return pivot location

} //end partitionIt()

//--------------------------------------------------------------

void swap(int dex1, int dex2) //swap two elements

{

double temp = theVect[dex1]; //A into temp

theVect[dex1] = theVect[dex2]; //B into A

theVect[dex2] = temp; //temp into B

} //end swap(

//--------------------------------------------------------------

}; //end class ArrayIns

////////////////////////////////////////////////////////////////

int main()

{

time_t aTime;

int maxSize = 16; //array size

ArrayIns arr(maxSize); //create array

srand( static_cast<unsigned>(time(&aTime)) ); //seed randoms

for(int j=0; j<maxSize; j++) //fill array with{ //random numbers

double n = rand() % 99;

arr.insert(n);

}

arr.display(); //display items

arr.quickSort(); //quicksort them

arr.display(); //display them again

return 0;

} //end main()

Output

A=69 0 70 6 38 38 24 56 44 26 73 77 30 45 97 65

A=0 6 24 26 30 38 38 44 45 56 65 69 70 73 77 97


 

sumber : Kuliah Logika dan Pemrograman Sistem II
READ MORE - QUICKSORT (HOURS13)

Applied Recursion(Hours 12) part 2

Mergesort
Teknik pengurutan mergesort lebih cepat dan efisien dibandingkan dengan bubble sort dan insertion sort. Insertion sort dan bubble sort memerlukan waktu O(N2) sedangkan mergesort memerlukan waktu O(N*logN). Sebagai contoh jika N adalah 10.000 data yang diurutkan maka N2 adalah 100.000.000 sementara N*logN hanya 40.000. jika sorting data ini memerlukan waktu 40 detik dengan mergesort maka dengan insertion sort akan memerlukan waktu hampir 28 jam.
Penggabungan 2 array
Inti dari mergesort adalah menggabungkan 2 buah array yang telah terurut dimana array A dan B akan digabungkan menjadi array C dengan data yang telah terurut
Langkah-langkah mergesort
Langkah ke 9 dan ke 10 kosong karena array B telah habis untuk dibandingkan dengan array A. Maka setelahnya sisa array A hanya langsung dipindah ke array C.

Listing mergesort
//merge.cpp
//demonstrates merging two arrays into a third
#include <iostream>
using namespace std;
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void merge( int[], int, int[], int, int[] );
void display(int[], int); //prototypes
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
int main()
{
int arrayA[] = {23, 47, 81, 95}; //source A
int arrayB[] = {7, 14, 39, 55, 62, 74}; //source B
int arrayC[10]; //destination
merge(arrayA, 4, arrayB, 6, arrayC); //merge A+B––>C
display(arrayC, 10); //display result
return 0;
} //end main()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void merge( int arrayA[], int sizeA, //merge A and B into C
int arrayB[], int sizeB,
int arrayC[] )
{
int aDex=0, bDex=0, cDex=0;
while(aDex < sizeA && bDex < sizeB) //neither array empty
if( arrayA[aDex] < arrayB[bDex] )
arrayC[cDex++] = arrayA[aDex++];
else
arrayC[cDex++] = arrayB[bDex++];
while(aDex < sizeA) //arrayB is empty,
arrayC[cDex++] = arrayA[aDex++]; //but arrayA isn't
while(bDex < sizeB) //arrayA is empty,
arrayC[cDex++] = arrayB[bDex++]; //but arrayB isn't
} //end merge()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––-
void display(int theArray[], int size) //display array
{
for(int j=0; j<size; j++)
cout << theArray[j] << " ";
cout << endl;
}
Output
7 14 23 39 47 55 62 74 81 95

Sorting dengan penggabungan
Ide dari mergesort adalah membagi array menjadi 2 bagian, kemudian tiap bagian diurutkan lalu dilakukan merge atau penggabungan sehingga didapatkan array terurut
Pada gambar diatas array dibagi menjadi masing-masing 2 bagian untuk kemudian urutkan dan digabungkan menjadi 4 bagian kemudian array terurut 4 bagian tersebut digabungkan kembali menjadi array yang terurut. dengan kata lain cara diatas adalah menggunakan pembagian kelipatan 2 yaitu dengan urutan 2,4,8,...dst hingga pada akhirnya array akhir terurut dengan N data.

Program mergesort dengan rekursif
//mergeSort.cpp
//demonstrates recursive merge sort
#include <iostream>
#include <vector>
using namespace std;
////////////////////////////////////////////////////////////////
class DArray
{
private:
vector<double>(theVect); //vector of doubles
int nElems; //number of data items
void recMergeSort(vector<double>, int, int);
void merge(vector<double>, int, int, int);
public:
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
DArray(int max) : nElems(0) //constructor
{
theVect.resize(max); //size vector
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void insert(double value) //put element into array
{
theVect[nElems] = value; //insert it
nElems++; //increment size
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void display() //displays array contents
{
for(int j=0; j<nElems; j++) //for each element,
cout << theVect[j] << " "; //display it
cout << endl;
}
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void mergeSort() //called by main()
{ //provides workspace
vector<double>(workSpace);
workSpace.resize(nElems);
recMergeSort(workSpace, 0, nElems-1);
}
}; //end class DArray
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void DArray::recMergeSort(vector<double> workSpace,
int lowerBound, int upperBound)
{
if(lowerBound == upperBound) //if range is 1,
return; //no use sorting
else
{ //find midpoint
int mid = (lowerBound+upperBound) / 2;
//sort low half
recMergeSort(workSpace, lowerBound, mid);
//sort high half
recMergeSort(workSpace, mid+1, upperBound);
//merge them
merge(workSpace, lowerBound, mid+1, upperBound);
} //end else
} //end recMergeSort()
//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
void DArray::merge(vector<double> workSpace, int lowPtr,
int highPtr, int upperBound)
{
int j = 0; //workspace index
int lowerBound = lowPtr;
int mid = highPtr-1;
int n = upperBound-lowerBound+1; //# of items
while(lowPtr <= mid && highPtr <= upperBound)
if( theVect[lowPtr] < theVect[highPtr] )
workSpace[j++] = theVect[lowPtr++];
else
workSpace[j++] = theVect[highPtr++];
while(lowPtr <= mid)
workSpace[j++] = theVect[lowPtr++];
while(highPtr <= upperBound)
workSpace[j++] = theVect[highPtr++];
for(j=0; j<n; j++)
theVect[lowerBound+j] = workSpace[j];
} //end merge()
////////////////////////////////////////////////////////////////
int main()
{
const int maxSize = 100; //array size
DArray arr(maxSize); //create "array"
arr.insert(64); //insert items
arr.insert(21);
arr.insert(33);
arr.insert(70);
arr.insert(12);
arr.insert(85);
arr.insert(44);
arr.insert(3);
arr.insert(99);
arr.insert(0);
arr.insert(108);
arr.insert(36);
arr.display(); //display items
arr.mergeSort(); //merge-sort the array
arr.display(); //display items again
return 0;
} //end main()

Output
64 21 33 70 12 85 44 3 99 0 108 36
0 3 12 21 33 36 44 64 70 85 99 108

Jumlah operasi yang dilakukan jika N adalah kelipatan dari 2











Jumlah maksimum dan minimum pembandingan jika digunakan array yang sudah terurut dan array yang tidak terurut dalam mergesort
sumber : Kuliah Logika dan Pemrograman Sistem II
READ MORE - Applied Recursion(Hours 12) part 2

Sunday, May 2, 2010

Applied Recursion(Hours 12) part 1

Pemakaian rekursi pada bab ini ada 2 macam yaitu

  • The Towers of Hanoi puzzle
  • Mergesort
The Towers of Hanoi puzzle

Adalah sebuah puzze kuno dimana terdiri dari piringan silinder(disk) yang berbeda diameter yang disusun menjadi piramid dalam 1 kolom. Diharuskan untuk memindahkan kolom disk ke kolom lain dengan syarat bahwa disk yang lebih besar tidak boleh berada diatas disk yang lebih kecil. Pada gambar ditunjukkan semua disk berawal dari kolom A. Diharuskan memindahkan semua disk ke kolom C. Hanya 1 disk yang dapat di pindah dalam 1 waktu dan tidak boleh ada menempatkan disk yang lebih besar diatas disk yang lebih kecil.
Langkah untuk menyelesaikan puzzle ini adalah

Urutan pemindahan disk

  1. Disk 1: A ke B
  2. Disk 2: A ke C
  3. Disk 1: B ke C
  4. Disk 3: A ke B
  5. Disk 1: C ke A
  6. Disk 2: C ke B
  7. Disk 1: A ke B
  8. Disk 4: A ke C
  9. Disk 1: B ke C
  10. Disk 2: B ke A
  11. Disk 1: C ke A
  12. Disk 3: B ke C
  13. Disk 1: A ke B
  14. Disk 2: A ke C
  15. Disk 1: B ke C
Jadi untuk memindah 4 disk dari kolom A ke C diperlukan 15 langkah

Setelah diketahui untuk memindahkan 4 disk diperlukan 15 langkah maka untuk memindahkan 5 disk dapat dilakukan seperti pada gambar diatas yaitu dengan memindahkan 4 disk ke kolom B(15 langkah) lalu memindahkan disk terbesar(disk ke 5) ke kolom C (1 langkah) lalu memindahkan 4 disk dari kolom B ke kolom C(15 langkah). Jadi untuk memindahkan 5 disk dari kolom A ke kolom C diperlukan 15+1+15 = 31 langkah
 
rumus umum jumlah langkah yang diperlukan untuk menyelesaikan puzzle ini adalah

jumlah langkah = 2n-1

dengan n adalah jumlah piringan disk



implementasi dalam pemrograman C++

//towers.cpp

//solves Towers of Hanoi puzzle

#include <iostream>

using namespace std;

void doTowers(int, char, char, char); //prototype

//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

int main()

{

int nDisks; //number of disks

cout << "Enter number of disks: "; //get # of disks

cin >> nDisks;

doTowers(nDisks, 'A', 'B', 'C'); //solve it

return 0;

}

//––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

void doTowers(int topN, char src, char inter, char dest)

{

if(topN==1) //display

cout << "Disk 1 from " << src << " to " << dest << endl;

else

{

doTowers(topN-1, src, dest, inter); //src to inter

cout << "Disk " << topN //display

<< " from " << src << " to " << dest << endl;

doTowers(topN-1, inter, src, dest); //inter to dest

}

}


 

Output

Enter (3 disks): s=A, i=B, d=C

Enter (2 disks): s=A, i=C, d=B

Enter (1 disk): s=A, i=B, d=C

Base case: move disk 1 from A to C

Return (1 disk)

Move bottom disk 2 from A to B

Enter (1 disk): s=C, i=A, d=B

Base case: move disk 1 from C to B

Return (1 disk)

Return (2 disks)

Move bottom disk 3 from A to C

Enter (2 disks): s=B, i=A, d=C

Enter (1 disk): s=B, i=C, d=A

Base case: move disk 1 from B to A

Return (1 disk)

Move bottom disk 2 from B to C

Enter (1 disk): s=A, i=B, d=C

Base case: move disk 1 from A to C

Return (1 disk)

Return (2 disks)

Return (3 disks)

Disk 1 from A to C

Disk 2 from A to B

Disk 1 from C to B

Disk 3 from A to C

Disk 1 from B to A

Disk 2 from B to C

Disk 1 from A to C


 

Berlanjut ke part 2

sumber : Kuliah Logika dan Pemrograman Sistem II
READ MORE - Applied Recursion(Hours 12) part 1

Thursday, April 29, 2010

Flowchart Searching Data

Flowchart Searching data dengan metode biner dan sequensial
READ MORE - Flowchart Searching Data

Program Searching Data

Program untuk serching data dengan metode biner dan sequensial. dibuat dengan delphi 7
source codenya dapat didownload disini
READ MORE - Program Searching Data

Monday, April 26, 2010

REKURSI (HOURS 11)


Rekursi adalah teknik pemrograman dimana sebuah fungsi atau anggota yang dapat memanggil dirinya sendiri untuk menyelesaikan sebuah permasalahan.
 

Contoh rekursi dalam penggunaan penambahan segitiga phytagoras dimana didapatkan hasil berupa deret 1, 3, 6, 10, 15, 21, …dst

Digunakan loop atau perulangan untuk mendapatkan nilai jumlah dari setiap segitiga
int triangle(int n) {
int total = 0;
while(n > 0) // until n is 1
{
total = total + n; // add n (column height) to total
--n; // decrement column height
}
return total;
}
Dengan menggunakan rekursi rumusnya dapat disederhanakan menjadi
int triangle(int n) {
if(n==1)
return 1;
else
return( n + triangle(n-1) );
}
Secara matematis dapat dihitung nilai dari hasil return fungsi triangle yaitu dengan rumus (n2+n)/2

Cara kerja fungsi triangle
Listing
int triangle(int n){
cout << "Entering: n=" << n << endl;
if(n==1){
cout << "Returning 1" << endl;
return 1;
}
Else {
int temp = n + triangle(n-1);
cout << "Returning " << temp << endl;
return temp;
}
}

Output
Enter a number: 5
Entering: n=5
Entering: n=4
Entering: n=3
Entering: n=2
Entering: n=1
Returning 1
Returning 3
Returning 6
Returning 10
Returning 15
Triangle = 15

Analisa
Terlihat jelas urutan saat fungsi triangle memproses input dan memulai rekursi dengan memanggil dirinya sendiri hingga nilai yang dikembalikan(return) terus berubah hingga didapat nilai akhir yaitu nilai yang sebenarnya
Karakteristik dari fungsi rekursif
- memanggil dirinya sendiri
- ketika memanggil dirinya sendiri maka akan menyelesaikan masalah yang lebih kecil/sederhana terlebih dahulu
- ada beberapa versi dari rekursi dimana proses yang dilakukan terlalu mudah sehingga tidak perlu melakukan pemanggilan fungsi diri sendiri dan langsung memberikan nilai return

Rekursi dipakai bukan karena efisien
tapi karena kemudahan dalam listing serta sederhana. Rekursi memakan banyak memori dan dapat mengakibatkan overflow jika permasalahan yang diberikan terlalu banyak

Pembuatan program anagram/kombinasi dengan rekursi
Konsepnya adalah menyimpan 1 karakter dan menukar-nukar posisi karakter yang lain sehingga didapat kombinasi yang berbeda-beda
Listing anagram
//anagram.cpp
//creates anagrams
#include <iostream>
#include <string>
using namespace std;
////////////////////////////////////////////////////////////////
class word {
private:
int size; //length of input word
int count; //numbers in display
string workStr; //workspace
void rotate(int); //rotate part of workStr
void displayWord(); //display workStr
public:
word(string); //constructor
void anagram(int); //anagram ourselves
};
//--------------------------------------------------------------
//constructor
word::word(string inpStr) : workStr(inpStr), count(0) { //initialize workStr
size = inpStr.length(); //number of characters
}
//--------------------------------------------------------------
void word::anagram(int newSize) {
if(newSize == 1) //if too small,
return; //go no further
for(int j=0; j<newSize; j++) //for each position,
{
anagram(newSize-1); //anagram remaining
if(newSize==2) //if innermost,
displayWord(); // display it
rotate(newSize); //rotate word
}
}
//--------------------------------------------------------------
//rotate left all chars from position to end
void word::rotate(int newSize) {
int j;
int position = size - newSize;
char temp = workStr[position]; //save first letter
for(j=position+1; j<size; j++) //shift others left
workStr[j-1] = workStr[j];
workStr[j-1] = temp; //put first on right
}
//--------------------------------------------------------------
void word::displayWord() {
if(count < 99) //spaces before onecout
<< " "; //or two-digit numbers
if(count < 9)
cout << " ";
cout << ++count << " "; //number
cout << workStr << " ";
if(count%6 == 0)
cout << endl;
}
////////////////////////////////////////////////////////////////
int main() {
string input;
int length;
cout << "Enter a word: "; //get word
cin >> input;
length = input.length(); //get its length
word theWord(input); //make a word object
theWord.anagram(length); //anagram it
return 0;
} //end main()
Output
Enter a word: cats
1 cats     2 cast     3 ctsa     4 ctas     5 csat     6 csta
7 atsc     8 atcs     9 asct     10 astc     11 acts     12 acst
13 tsca     14 tsac     15 tcas     16 tcsa     17 tasc     18 tacs
19 scat     20 scta     21 satc     22 sact     23 stca     24 stac

Pembuatan fungsi rekursif
  1. Menentukan nilai henti(terminate)
  2. Melakukan penyederhanaan pada langkah rekursi
Contoh
Program faktorial dengan fungsi fak(n)
  1. Nilai henti 1!=1 fak(1)=1
  2. Penyederhanaan n! = n*(n-1)!
Program fibonacci dengan fungsi fib(n)
  1. Nilai henti fib(1) = 1

        fib(2) = 1
  2. Penyederhanaan fib(n) = fib(n-1) + fib(n-2)
Program pangkat an dengan fungsi pangkat(a,n)
  1. Nilai henti pangkat(a,n) n=0;a=1
  2. Penyederhanaan return(a*pangkat(a,n-1))
Program tes 1
Int tes(int n) {
If (n>0) {
Cout <<n<<" ";
Tes(n-1);
}
}
Int main(){
Tes(5);
Cout<<endl;
Return 0;
}
Output 54321

Program tes 2
Int tes(int n) {
If (n>0) {
Tes(n-1);
Cout <<n<<" ";
}
}
Int main(){
Tes(5)
Cout<<endl;
Return 0;
}
Output 12345





sumber : kuliah logika dan pemrograman sistem II
READ MORE - REKURSI (HOURS 11)