Laporan mengenai mikro instruksi dalam level ISA dapat didownload disini
READ MORE - Laporan ISA(Instruction Set Architecture)
Tuesday, May 25, 2010
Thursday, May 20, 2010
Mikroinstruksi ISA (MIC-1)
Dalam mikro instruksi ini kita dapat memahami prinsip dan cara kerja mikro instruksi pada level arsitektur mikro, dalam sebuah mikroprosesor.
Level arsitektur mikro berada diatas level logika digital, arsitektur ini akan mengimplementasikan level ISA(Instruction Set Architecture). Pada level ISA akan ditemukan kumpulan register yang membentuk memori lokal, serta rangkaian ALU(Aritmethmetic Logic Unit) yang mampu menjalankan operasi-operasi aritmatika sederhana.
Secara umum bentuk dari data flow arsitektur mikro adalah
Untuk mengetahui langkah-langkah dalam ISA dapat digunakan simulasi dengan java platform yaitu mic-1
untuk pemakaiannya:
- Extract file rar
- Atur posisi dari folder mic-1 dan folder JVM pada directory C:
- Buka folder mic-1 dan jalankan simulator-mic1win.exe
- Setelah extrack buka file env.bat dengan notepad
- Edit isi file untuk directorinya seperti berikut:
@echo off
rem
rem env.bat
rem
rem This batch file sets the environment variables necessary for running
rem the mic1 software.
rem 1) comment out the following 4 commands
echo NOTE: YOU NEED TO EDIT THE FILE ENV.BAT BEFORE YOUR mic1
echo SOFTWARE will WORK CORRECTLY.
pause
goto end
rem 2) Set the path to point to the bin directory of the JDK
path c:\JVM\bin;%path%
rem 3) Set the classpath to point to the classes.zip file from the mic1
rem distribution
set CLASSPATH=c:\mic-1\classes.zip
:end
Download mic-1
Java development kit 1.1.8
READ MORE - Mikroinstruksi ISA (MIC-1)
Level arsitektur mikro berada diatas level logika digital, arsitektur ini akan mengimplementasikan level ISA(Instruction Set Architecture). Pada level ISA akan ditemukan kumpulan register yang membentuk memori lokal, serta rangkaian ALU(Aritmethmetic Logic Unit) yang mampu menjalankan operasi-operasi aritmatika sederhana.
Secara umum bentuk dari data flow arsitektur mikro adalah
untuk pemakaiannya:
- Extract file rar
- Atur posisi dari folder mic-1 dan folder JVM pada directory C:
- Buka folder mic-1 dan jalankan simulator-mic1win.exe
- Setelah extrack buka file env.bat dengan notepad
- Edit isi file untuk directorinya seperti berikut:
@echo off
rem
rem env.bat
rem
rem This batch file sets the environment variables necessary for running
rem the mic1 software.
rem 1) comment out the following 4 commands
echo NOTE: YOU NEED TO EDIT THE FILE ENV.BAT BEFORE YOUR mic1
echo SOFTWARE will WORK CORRECTLY.
pause
goto end
rem 2) Set the path to point to the bin directory of the JDK
path c:\JVM\bin;%path%
rem 3) Set the classpath to point to the classes.zip file from the mic1
rem distribution
set CLASSPATH=c:\mic-1\classes.zip
:end
Download mic-1
Java development kit 1.1.8
Sunday, May 16, 2010
Laporan Memori (1)
Laporan Organisasi dan Arsitektur Komputer tentang memori (1)
download
READ MORE - Laporan Memori (1)
download
Monday, May 10, 2010
Know your Self To Get What you Want
Emotion is created by motion
– anthony robbius
Emosi yang ada pada manusia dan tergambarkan dalam perilaku sehari-hari merupakan hasil dari aktivitas yang dilakukan. Dan untuk mengendalikan dan mengatur emosi maka kita juga perlu untuk mengatur dan mengendalikan aktivitas sehari-hari agar dapat membuat emosi yang positif.
Your outer world is the reflection of your inner world
– joe vitule
– joe vitule
Sesuatu yang terlihat dari seseorang(perilaku, sikap, sifat) adalah cerminan pribadi diri yang telah terbentuk akibat aktivitas dan informasi yang telah masuk ke dalam pikiran.
Cara kerja pikiran manusia
RAS(reticular activating system) adalah filter dari informasi yang masuk ke pikiran sehingga tidak semua informasi masuk begitu saja ke dalam pikiran.
Pikiran manusia mampu memilah informasi yang masuk memalui filter yaitu moral dan kesadaran diri. Sehingga tidak semua informasi dapat masuk begitu saja ke dalam otak, sehingga kadang kita begitu mudahnya melupakan suatu hal. Selain itu pikiran memiliki kapasitas memori bawah sadar yang lebih besar dibandingkan memori sadar. Sering kali kita belajar untuk melakukan sesuatu dengan menggunakan pikiran sadar kita namun amat mudah untuk terlupakan. Namun begitu informasi tentang apa yang kita pelajari itu masuk ke dalam memori pikiran bawah sadar kita maka informasi itu akan tersimpan dan kita tanpa sadar dapat menggunakan informasi itu begitu saja tanpa perlu berpikir terlebih dahulu. Contoh saat belajar mengendarai motor/ mobil akan sangat sulit tapi begitu bisa maka akan sangat mudah dilakukan.
The most important part of your prayer is what you fell not is what you say
–pence pillgrim
Saat berdoa dan menginginkan sesuatu kita harus benar-benar menginginkannya dan bersungguh-sungguh disertai perasaan yang kuat sehingga akan menimbulkan semangat untuk dapat benar-benar mendapatkan apa yang kita ingikan
Fokus pada solusi bukan fokus pada masalah
Untuk dapat menyelesaikan suatu permasalahan yang terjai haruslah fokus pada solusi bukan pada masalah. Pikirkan bagaimana mengatasi masalah bukannya berpikir masalah yang semakin berlarut-larut dan akan menjerumuskan diri.
The law of attract = like attract like
Dalam kehidupan manusia berlaku hukum diatas dimana sesuatu yang sama akan cenderung bersama-sama atau menarik yang sama untuk berkumpul dan berinteraksi.
FEAR = False Evidence Appear Real
Khawatir terhadap sesuatu yang tidak terjadi(tidak nyata). Khawatir seperti ini hendaknya dihilangkan agar dapat berpikir cerah untuk masa depan tanpa menghawatirkan sesuatu yang tidak nyata/ hanya kekhawatiran semata. Orang akan berhasil jika mampu dan berani mengalahkan ketakutan dan kekhawatiran dalam dirinya.
Untuk mencapai tujuan/ keinginan
Do'a + yakin
Do'a disertai usaha(inspire action), ikhlas, dan tawakal
Yakin yaitu tenang, sabar, fokus, dan bersyukur
Source : kuliah kewirausahaan
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 terbalikMasalah 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
//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()
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:
- Quicksort dilanjutkan insertion sort untuk data sedikit
- Quicksort kemudian sort dihentikan untuk data sedikit( mencapai cutoff point). Lalu dilakukan insertion sort secara keseluruhan
//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
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
- bagi data menjadi 2 dengan jumlah sama
- urutkan masing-masing bagian
- lakukan penggabungan(merge)
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.
- tentukan pivot sebagai index bagain terbesar
- Ki(data bagian terkiri) digeser ke kanan sampai ki > pivot
- Ka(data bagian terkanan) digeser ke kiri sampai ka < pivot
- Jika ka > ki maka nilai di ka dan ki ditukar
- pivot array 70, data dibandingkan
- diambil bagian kiri pivot 50, data dibandingkan
- diambil pivot 40, data dibandingkan
- diambil pivot 20, data dibandingkan
- diambil bagian kanan
- diambil pivot 110, data dibandingkan
- diambil pivot 100, data dibandingkan
- diambil pivot 80, data dibandingkan
- didapatkan array yang terurut
//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
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
Sunday, May 2, 2010
Applied Recursion(Hours 12) part 1
Pemakaian rekursi pada bab ini ada 2 macam yaitu
Langkah untuk menyelesaikan puzzle ini adalah
Urutan pemindahan disk
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
- The Towers of Hanoi puzzle
- Mergesort
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.
Urutan pemindahan disk
- Disk 1: A ke B
- Disk 2: A ke C
- Disk 1: B ke C
- Disk 3: A ke B
- Disk 1: C ke A
- Disk 2: C ke B
- Disk 1: A ke B
- Disk 4: A ke C
- Disk 1: B ke C
- Disk 2: B ke A
- Disk 1: C ke A
- Disk 3: B ke C
- Disk 1: A ke B
- Disk 2: A ke C
- Disk 1: B ke C
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 adalahjumlah 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
