Tampilkan postingan dengan label Algoritma Pemrogaman. Tampilkan semua postingan
Tampilkan postingan dengan label Algoritma Pemrogaman. Tampilkan semua postingan

Selasa

Array Unik


Not really long post on my favorite blog. Miss all of you equally. This time I will share about the unique array. What I mean by an array of unique? I mean that is an array that is displayed is the number that has no similarity of numbers in the input data. Sorry if my language covered. Hehehe ...
Immediately, at its core. As an illustration,
for example we will enter 4 data arrays of 1,3,3,5. Then the numbers will be displayed at only 1 and 5. It is called with an array of unique.
Have now towards the crime scene. We will make the function sebegai follows:


Here I use the variable C to help detect an array of unique. At each examination found no similar array data then the value of c will be increased by one. So we get that if the value of C == 0 then the data is a unique data. After that it will be directly printed.
You all can develop a program with better. This is just for reference only. For programs running that are ready can more clearly let you download memalui link below:
C + + program
 Java Program
A few old friends, hopefully be able to let go of the miss. Hopefully useful!

Kamis

c++ Array 2 dimensi

Struktur array yang dibahas di bawah, mempunyai satu dimensi, sehingga
variabelnya disebut dengan variabel array berdimensi satu. Pada bagian ini,
ditunjukkan array berdimensi lebih dari satu, yang sering disebut dengan array
berdimensi dua.

Sering kali digambarkan/dianalogikan sebagai sebuah matriks. dimana
indeks pertama menunjukan baris dan indeks kedua menunjukan kolom


ILUSTRASI ARRAY 2 DIMENSI
Gambar array berdimensi (baris x kolom = 3 x 4):

contoh program 1

#include
#include
void main

int matrix[3][4] = {{5,10,1,11},{4,7,67,-9},{9,0,45,3}};
for int i = 0; i<3; i++ { for (int j=0;j<4; j++) { cout<
#include
void main()
{
int i,j,kola,kolb,bara,barb;
int data1[25][25],data2[25][25],hasil[25][25];
char jawab;
do
{
do
{
clrscr();
cout<<"Program Penjumlahan Matrix"<>bara;
cout<<"Jml kolom Matrix A: "; cin>>kola;
cout<>barb;
cout<<"Jml kolom Matrix B: "; cin>>kolb;
}
while ((kola!=kolb) || (bara!=barb));
cout<>data1[i][j];
}
}
cout<>data2[i][j];
}
}
for (i=1; i<=bara; i++) { for (j=1; j<=kola; j++) { hasil[i][j]=data1[i][j] + data2[i][j]; } } cout<

c++ Array 1 Dimensi

Array merupakan kumpulan dari nilai-nilai data yang bertipe sama dalam
urutan tertentu yang menggunakan nama yang sama. Dengan menggunakan
array, sejumlah variabel dapat memakai nama yang sama. Letak atau posisi dari
elemen array ditunjukkan oleh suatu index. Dilihat dari dimensinya array dapat
dibagi menjadi Array dimensi satu, array dimensi dua dan array multi-dimensi.
Bentuk Umum pendeklarasian array :

Contoh :

int nil[5];


Nilai suatu variabel array dapat juga diinisialisasi secara langsung pada saat
deklarasi, misalnya:

int nil[5] = { 1,3,6,12,24 };

Maka di penyimpanan ke dalam array dapat digambarkan sebagai berikut:


Mengakses nilai array
Untuk mengakses nilai yang terdapat dalam array, mempergunakan sintak:

nama_array[index];

Pada contoh di atas, variabel nil memiliki 5 buah elemen yang masing-masing
berisi data. Pengaksesan tiap-tiap elemen data adalah:

Misal, untuk memberikan nilai 75 pada elemen ke 3, maka pernyataannya
adalah:

nil[2] = 75;

atau jika akan memberikan nilai array kepada sebuah variabel a, dapat ditulis:

a = nil[2];

Contoh Penerapan:

Misalkan kita memiliki sekumpulan data ujian seorang siswa, ujian
pertama bernilai 90, kemudian 95,78,85. Sekarang kita ingin menyusunnya
sebagai suatu data kumpulan ujian seorang siswa. Dalam array kita
menyusunnya sebagai berikut:

ujian[0] = 90;
ujian[1] = 95;
ujian[2] = 78;
ujian[3] = 85;

Empat pernyataan diatas memberikan nilai kepada array ujian. Tetapi
sebelum kita memberikan nilai kepada array, kita harus mendeklarasikannya
terlebih dahulu, yaitu :

int ujian[4];

Perhatikan bahwa nilai 4 yang berada didalam tanda kurung menujukkan
jumlah elemen larik, bukan menunjukkan elemen larik yang ke-4. Jadi elemen
larik ujian dimulai dari angka 0 sampai 3. Pemrogram juga dapat
menginisialisasi larik sekaligus mendeklarasikannya, sebagai contoh :

int ujian[4] = {90,95,78,85};


contoh progaram 1

#include
#include
void main

int ujian[5]
for(int k=0;k<5;k++) cout<<"masukkan data nilai ujian["<>ujian[k];
}
//tampil data array
for (int j=0;j<5;j++) { cout<<"data nilai ujian["<
#include
void main()
{
float data[5];
float rata, total = 0;
//input data ke array
for (int k=0;k<5;k++) { cout<<"masukkan data["<>data[k];
}
//menghitung total nilai pada array
for (int j=0;j<5;j++) { total = total + data[j]; } //menghitung rata - rata rata = total / 5; cout<<"rata - rata data pada array = "<
#include
void main()
{
int data[10] = {4, 1, 0, -9, 8, 5, -1, 2, 3, -7};
int elemen, ketemu, x;
cout << "Data yang dicari : "; cin >> x;
ketemu = 0;
for(elemen=0; elemen<= 9; elemen++)
{
if (data[elemen] == x)
{
ketemu = !ketemu;
break;
}
}
if (ketemu == 0)
cout << "Data tidak ditemukan ";
else
cout << "Data ada di elemen : " << elemen;
getch();
}

c++ Array 2 Dimensi dan MultiDimensi

ARRAY DUA DIMENSI
Singkatnya, Array dua dimensi merupakan array yang terdiri dari m buah baris dan n buah kolom. Bentuknya dapat berupa matriks atau tabel.

Bentuk umum pendeklarasian variabel array dua dimensi di Java adalah:
tipeData[][]nama_variabel[=new tipeData[jumlah_baris][jumlah_kolom]];


Untuk memudahkan pemahaman, bentuk array dua dimensi bisa dihambarkan dalam bentuk petak-petak sebagai berikut:

N adalah nilai yang menyatakan jumlah baris dari array, sedangkan M menyatakan jumlah kolom dari array. Sama seperti array satu dimensi, penomoran indeks untuk array dua dimensi juga dimulai dari 0 untuk baris maupun kolomnya. Tidak ada aturan yang mengatakan bahwa urutan untuk nomor indeks adalah baris dulu baru kolom.

Contoh array 2 dimensi:
int x[3][4];

ARRAY MULTIDIMENSI
Array multidimensi merupakan array yang terdiri dari array yang tidak terbatas hanya dua dimensi saja. Kita dapat menggunakan kode berikut untuk mendapatkan array tiga dimensi :
int[][][]array dimensi=new int[5][10][5]


Dan pada array multidimensi, kita dapat menentukan ukuran array yang berbeda pada tiap array. Misalnya :
int[][][]array dimensi=new int[5][][]


Dari kode diatas, kita mendapatkan array pertama dengan 5 elemen, tetapi kita belum mendefinisikan ukuran array dimensi kedua dan ketiga.
Selain berdimensi tiga, kita juga dapat membuat array berdimensi empat, lima dan seterusnya. Hal ini dapat dilakukan karena pada bahasa Java

c++ Mengubah "for-loop" berikut menjadi "while-loop"

for (x=1000;x<=10000;x++){
if(x%5==0)continue;
else{
if(x%8==0)continue;
else{
if(x%13==0)continue;
else printf(“%5d”,x);
}
}
}


Lalu bagaimana jika di ganti ke "while-loop"?
untuk mengganti ke "while-loop" kode programnya adalah sebagai berikut:

#include
main ()
{
int i;
i=1000;
while (i<=10000)
{ if(i%5!=0 && i%8!=0 && i%13!=0)
printf("%5d", i);
i+=1;
}
getchar();
getchar();
return 0;
}

Selasa

Mengenal Sistem Koordinat
Thursday, 23/04/2009 14:00 WIB | email | print

Allah SWT menciptakan alam semesta ini dalam keadaan yang teratur rapi. Keteraturan gerakan bintang termasuk matahari, planet, satelit, komet dan benda langit lainnya menyebabkan gerakan benda-benda tersebut dapat dipelajari dengan seksama. Dengan memahami gerakan benda-benda langit tersebut, manusia dapat memperkirakan peristiwa-peristiwa yang terjadi di masa depan dengan akurat. Kapan matahari terbenam, kapan terjadi bulan purnama, kapan terjadi gerhana matahari dapat dihitung dengan ketelitian tinggi.

Untuk memudahkan pemahaman terhadap posisi benda-benda langit, diperkenalkan beberapa sistem koordinat. Setiap sistem koordinat memiliki koordinat masing-masing. Posisi benda langit seperti matahari dapat dinyatakan dalam sistem koordinat tertentu. Selanjutnya nilainya dapat diubah ke dalam sistem koordinat yang lain melalui suatu transformasi koordinat.

Sistem Koordinat 2 dan 3 dimensi

Untuk menyatakan posisi sebuah benda di dalam ruang, dibutuhkan suatu sistem koordinat yang memiliki pusat koordinat (origin) dan sumbu koordinat (axis). Sistem koordinat yang paling dasar/sederhana adalah Kartesian (Cartesian). Jika kita berbicara ruang 2 dimensi, maka koordinat Kartesian 2 dimensi memiliki pusat di O dan 2 sumbu koordinat yang saling tegaklurus, yaitu x dan y. Dalam Gambar 1, titik P dinyatakan dalam koordinat x dan y.

Gambar 1. Koordinat Kartesian 2 dimensi (x, y)

Selanjutnya koordinat Kartesian 2 dimensi dapat diperluas menjadi Kartesian 3 dimensi yang berpusat di O dan memiliki sumbu x, y dan z. Pada Gambar 2, titik P dapat dinyatakan dalam x, y dan z. OP adalah jarak titik P ke pusat O.

Gambar 2. Koordinat Kartesian 3 dimensi (x, y, z)

Koordinat Kartesian 3 dimensi (x, y, z) pada Gambar 2 dapat diubah menjadi Koordinat Bola (Spherical Coordinate) 3 dimensi (r, Alpha, Beta) seperti pada Gambar 3. Dalam koordinat Kartesian 3 dimensi, seluruh koordinat (x, y dan z) berdimensi panjang. Sedangkan dalam koordinat bola, terdapat satu koordinat yang berdimensi panjang (yaitu r) dan dua koordinat lainnya berdimensi sudut (yaitu Alpha dan Beta). Titik P masih tetap menyatakan titik yang sama dengan titik P pada Gambar 2. Jarak titik P ke pusat O sama dengan r. Jika titik P diproyeksikan ke bidang datar xy, maka sudut antara garis OP dengan bidang datar xy adalah Beta. Selanjutnya sudut antara proyeksi OP pada bidang xy dengan sumbu x adalah Alpha.

Gambar 3. Koordinat Bola tiga dimensi (r, Alpha, Beta)

Hubungan antara (x, y, z) dengan (r, Alpha, Beta) dinyatakan dalam transformasi koordinat berikut.

Sebagai contoh, jika titik P terletak di koordinat x = 3, y = 4 dan z = 12, maka diperoleh r = 13, Alpha = 53,13 derajat dan Beta = 67,38 derajat.

Di atas telah dibahas transformasi dari koordinat Kartesian ke koordinat bola. Berikut ini dibahas beberapa sistem koordinat yang penting dalam ilmu hisab, yaitu:

Sistem Koordinat Ekliptika Heliosentrik (Heliocentric Ecliptical Coordinate).
Sistem Koordinat Ekliptika Geosentrik (Geocentric Ecliptical Coordinate).
Sistem Koordinat Ekuator Geosentrik (Geocentric Equatorial Coordinate).
Sistem Koordinat Horison (Horizontal Coordinate).

Keempat sistem koordinat di atas termasuk ke dalam koordinat bola. Sebenarnya masih ada sistem koordinat lainnya, seperti Sistem Koordinat Ekuator Toposentrik (Topocentric Equatorial Coordinate) namun Insya Allah dibahas pada kesempatan lain.

Sekilas, banyaknya sistem koordinat di atas bisa membuat rumit. Namun pembagian sistem koordinat di atas berasal dari benda langit manakah yang dijadikan pusat koordinat, apakah bidang datar sebagai referensi serta bagaimana cara mengukur posisi benda langit lainnya. Penting pula untuk diketahui bahwa seluruh benda langit dapat dianggap seperti titik. Bisa pula dianggap seperti benda yang seluruhnya terkonsentrasi di pusat benda tersebut. Jika kita memperoleh jarak bumi-bulan, maka yang dimaksud adalah jarak antara pusat bumi dengan pusat bulan.

Sistem Koordinat Ekliptika Heliosentrik dan Sistem Koordinat Ekliptika Geosentrik sebenarnya identik. Yang membedakan keduanya hanyalah manakah yang menjadi pusat koordinat. Pada Sistem Koordinat Ekliptika Heliosentrik, yang menjadi pusat koordinat adalah matahari (helio = matahari). Sedangkan pada Sistem Koordinat Ekliptika Geosentrik, yang menjadi pusat koordinat adalah bumi (geo = bumi). Karena itu keduanya dapat digabungkan menjadi Sistem Koordinat Ekliptika. Pada Sistem Koordinat Ekliptika, yang menjadi bidang datar sebagai referensi adalah bidang orbit bumi mengitari matahari (heliosentrik) yang juga sama dengan bidang orbit matahari mengitari bumi (geosentrik).

Sistem Koordinat Ekliptika Heliosentrik (Heliocentric Ecliptical Coordinate)

Pada koordinat ini, matahari (sun) menjadi pusat koordinat. Benda langit lainnya seperti bumi (earth) dan planet bergerak mengitari matahari. Bidang datar yang identik dengan bidang xy adalah bidang ekliptika yatu bidang bumi mengitari matahari.

Gambar 4. Sistem Koordinat Ekliptika Heliosentrik

Pusat koordinat: Matahari (Sun).
Bidang datar referensi: Bidang orbit bumi mengitari matahari (bidang ekliptika) yaitu bidang xy.
Titik referensi: Vernal Ekuinoks (VE), didefinisikan sebagai sumbu x.
Koordinat:
r = jarak (radius) benda langit ke matahari
l = sudut bujur ekliptika (ecliptical longitude), dihitung dari VE berlawanan arah jarum jam
b = sudut lintang ekliptika (ecliptical latitude), yaitu sudut antara garis penghubung benda langit-matahari dengan bidang ekliptika.

Sistem Koordinat Ekliptika Geosentrik (Geocentric Ecliptical Coordinate)

Pada sistem koordinat ini, bumi menjadi pusat koordinat. Matahari dan planet-planet lainnya nampak bergerak mengitari bumi. Bidang datar xy adalah bidang ekliptika, sama seperti pada ekliptika heliosentrik.

Gambar 5. Sistem Koordinat Ekliptika Geosentrik

Pusat Koordinat: Bumi (Earth)
Bidang datar referensi: Bidang Ekliptika (Bidang orbit bumi mengitari matahari, yang sama dengan bidang orbit matahari mengitari bumi) yaitu bidang xy.
Titik referensi: Vernal Ekuinoks (VE) yang didefinisikan sebagai sumbu x.
Koordinat:
Jarak benda langit ke bumi (seringkali diabaikan atau tidak perlu dihitung)
Lambda = Bujur Ekliptika (Ecliptical Longitude) benda langit menurut bumi, dihitung dari VE.
Beta = Lintang Ekliptika (Ecliptical Latitude) benda langit menurut bumi yaitu sudut antara garis penghubung benda langit-bumi dengan bidang ekliptika

Sistem Koordinat Ekuator Geosentrik

Ketika bumi bergerak mengitari matahari di bidang Ekliptika, bumi juga sekaligus berotasi terhadap sumbunya. Penting untuk diketahui, sumbu rotasi bumi tidak sejajar dengan sumbu bidang ekliptika. Atau dengan kata lain, bidang ekuator tidak sejajar dengan bidang ekliptika, tetapi membentuk sudut kemiringan (epsilon) sebesar kira-kira 23,5 derajat. Sudut kemiringan ini sebenarnya tidak bernilai konstan sepanjang waktu. Nilainya semakin lama semakin mengecil. Masalah ini Insya Allah akan dibahas pada kesempatan lain.

Gambar 6. Sistem Koordinat Ekuator Geosentrik

Pusat koordinat: Bumi
Bidang datar referensi: Bidang ekuator, yaitu bidang datar yang mengiris bumi menjadi dua bagian melewati garis khatulistiwa
Koordinat:
jarak benda langit ke bumi.
Alpha = Right Ascension = Sudut antara VE dengan proyeksi benda langit pada bidang ekuator, dengan arah berlawanan jarum jam. Biasanya Alpha bukan dinyatakan dalam satuan derajat, tetapi jam (hour disingkat h). Satu putaran penuh = 360 derajat = 24 jam = 24 h. Karena itu jika Alpha dinyatakan dalam derajat, maka bagilah dengan 12 untuk memperoleh satuan derajat. Titik VE menunjukkan 0 h.
Delta = Declination (Deklinasi) = Sudut antara garis hubung benda langit-bumi dengan bidang ekliptika.Nilainya mulai dari -90 derajat (selatan) hingga 90 derajat (utara). Pada bidang ekuator, deklinasi = 0 derajat.

Seringkali, Alpha (right ascension) dinyatakan dalam bentuk H (hour angle). Hubungan antara Alpha dengan H adalah H = LST - Alpha.

Disini, LST adalah Local Sidereal Time, yang sudah penulis bahas sebelumnya pada tulisan tentang Macam-Macam Waktu (http://www.eramuslim.com/syariah/ilmu-hisab/macam-macam-waktu.htm)

Sistem Koordinat Horison

Pada sistem koordinat ini, pusat koordinat adalah posisi pengamat (bujur dan lintang) yang terletak di permukaan bumi. Kadang-kadang, ketinggian pengamat dari permukaan bumi juga ikut diperhitungkan. Bidang datar yang menjadi referensi seperti bidang xy adalah bidang horison (bidang datar di sekitar pengamat di permukaan bumi).

Gambar 7. Sistem Koordinat Horison

Pusat koordinat: Pengamat di permukaan bumi
Bidang datar referensi: Bidang horison (Horizon plane)
Koordinat:
Altitude/Elevation = sudut ketinggian benda langit dari bidang horison. h = 0 derajat berarti benda di bidang horison. h = 90 derajat dan -90 derajat masing-masing menunjukkan posisi di titik zenith (tepat di atas kepala) dan nadir (tepat di bawah kaki).
A (Azimuth) = Sudut antara arah Utara dengan proyeksi benda langit ke bidang horison.

Jarak benda langit ke pengamat dalam sistem koordinat ini seringkali diabaikan, karena telah dapat dihitung sebelumnya dalam sistem koordinat ekliptika.

Catatan penting: Dalam banyak buku referensi, azimuth seringkali diukur dari arah selatan (South) yang memutar ke arah barat (West). Gambar 7 di atas juga menunjukkan bahwa azimuth diukur dari arah Selatan. Namun demikian, dalam pemahaman umum, orang biasanya menjadikan arah Utara sebagai titik referensi. Karena itu dalam tulisan ini penulis menjadikan sudut azimuth diukur dari arah Utara. Untuk membedakannya, lambang untuk azimuth dari arah selatan dinyatakan sebagai As, sedangkan azimuth dari arah utara dinyatakan sebagai A saja. Hubungan antara As dan A adalah A = As - 180 derajat. Jika As atau A negatif, tinggal tambahkan 360 derajat.

Suatu sistem koordinat dengan sistem koordinat lainnya dapat dihubungkan melalui transformasi koordinat. Misalnya, dari algoritma untuk menghitung posisi bulan menurut sistem koordinat ekliptika geosentrik, kita dapat menentukan jarak bulan dari pusat bumi, sudut lambda dan beta. Selanjutnya, sudut lambda dan beta ditransformasi untuk mendapat sudut alpha dan delta dalam sistem koordinat ekuator geosentrik. Dari alpha dan beta, serta memperhitungkan posisi pengamat (bujur dan lintang) dan waktu saat pengamatan/penghitungan, maka sudut ketinggian (altitude) dan azimuth bulan menurut sistem koordinat horison dapat diketahui dengan tepat. Rumus-rumus transformasi koordinat yang membutuhkan pengetahuan trigonometri Insya Allah akan dibahas pada tulisan mendatang.

Rinto Anugraha

Referensi:

Jean Meeus: Astronomical Algorithm, Willmann-Bell, Virginia, 1991.
Oliver Montenbruck: Practical Ephemeris Calculations, Springer-Verlag, 1999.

c++ menghitung 2 buah titik koordinat

Kali ini menentukan koordinat 2 buah titik yang nanti kita tentukan inputannya,
algoritmanya:

Kita inputkan data koordinat titik pertama => x1
titik kedua => x2
titik ketiga = y1
titik keempat => y2
Kemudian nilai-nilai tersebut akan kalikan & dijumlah untuk selanjutnya diakarkan, datanya sebagai berikut :
(((x1-x2).(x1-x2))+((y1-y2).(y1-y2))) => tidak lupa untuk diakarkan
Dan hasil pengakaran tersebut adalah jarak koordinat yang kita cari.

source kodenya :
#include
#include
class jarak
{
friend istream& operator>>(istream&, jarak&);
public:
int proses();
private:
float hasil,x1,x2,y1,y2;
};
istream& operator>>(istream& in, jarak& masukan)
{
cout << " ============================================= " << endl; cout << " --Program penghitung 2 buah titik koordinat-- " << endl; cout << " =============================================\n" << endl; cout<<" Masukkan Nilai x1 : "; in>>masukan.x1;
cout<<" Masukkan Nilai x2 : "; in>>masukan.x2;
cout<<" Masukkan Nilai y1 : "; in>>masukan.y1;
cout<<" Masukkan Nilai y2 : "; in>>masukan.y2;
return in;
}
jarak::proses()
{
hasil=sqrt (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)));
cout<<" Jarak kedua titik adalah : "< }
int main
{
jarak x
in x
x.prosses
return
}

Senin

c++ Binary search

Binary search algorithm

Generally, to find a value in unsorted array, we should look through elements of an array one by one, until searched value is found. In case of searched value is absent from array, we go through all elements. In average, complexity of such an algorithm is proportional to the length of the array.

Situation changes significantly, when array is sorted. If we know it, random access capability can be utilized very efficiently to find searched value quick. Cost of searching algorithm reduces to binary logarithm of the array length. For reference, log2(1 000 000) ≈ 20. It means, that in worst case, algorithm makes 20 steps to find a value in sorted array of a million elements or to say, that it doesn't present it the array.
Algorithm

Algorithm is quite simple. It can be done either recursively or iteratively:

get the middle element;
if the middle element equals to the searched value, the algorithm stops;
otherwise, two cases are possible:
searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Now we should define, when iterations should stop. First case is when searched element is found. Second one is when subarray has no elements. In this case, we can conclude, that searched value doesn't present in the array.
Examples

Example 1. Find 6 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.

Step 1 (middle element is 19 > 6): -1 5 6 18 19 25 46 78 102 114

Step 2 (middle element is 5 < 6): -1 5 6 18 19 25 46 78 102 114 Step 3 (middle element is 6 == 6): -1 5 6 18 19 25 46 78 102 114 Example 2. Find 103 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}. Step 1 (middle element is 19 < 103): -1 5 6 18 19 25 46 78 102 114 Step 2 (middle element is 78 < 103): -1 5 6 18 19 25 46 78 102 114 Step 3 (middle element is 102 < 103): -1 5 6 18 19 25 46 78 102 114 Step 4 (middle element is 114 > 103): -1 5 6 18 19 25 46 78 102 114

Step 5 (searched value is absent): -1 5 6 18 19 25 46 78 102 114
Complexity analysis

Huge advantage of this algorithm is that it's complexity depends on the array size logarithmically in worst case. In practice it means, that algorithm will do at most log2(n) iterations, which is a very small number even for big arrays. It can be proved very easily. Indeed, on every step the size of the searched part is reduced by half. Algorithm stops, when there are no elements to search in. Therefore, solving following inequality in whole numbers:

n / 2iterations > 0

resulting in

iterations <= log2(n). It means, that binary search algorithm time complexity is O(log2(n)). Code snippets. You can see recursive solution for Java and iterative for C++ below. Java /** * searches for a value in sorted array * * @param array * array to search in * @param value * searched value * @param left * index of left boundary * @param right * index of right boundary * @return position of searched value, if it presents in the array or -1, if * it is absent */ int binarySearch(int[] array, int value, int left, int right) { if (left > right)

return -1;

int middle = (left + right) / 2;

if (array[middle] == value)

return middle;

else if (array[middle] > value)

return binarySearch(array, value, left, middle - 1);

else

return binarySearch(array, value, middle + 1, right);

}
C++

/*

* searches for a value in sorted array

* arr is an array to search in

* value is searched value

* left is an index of left boundary

* right is an index of right boundary

* returns position of searched value, if it presents in the array

* or -1, if it is absent

*/

int binarySearch(int arr[], int value, int left, int right) {

while (left <= right) { int middle = (left + right) / 2; if (arr[middle] == value) return middle; else if (arr[middle] > value)

right = middle - 1;

else

left = middle + 1;

}

return -1;

}

c++ Bubble Sort

Bubble Sort

Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.
Algorithm

Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
If at least one swap has been done, repeat step 1.

You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.

Example. Sort {5, 1, 12, -5, 16} using bubble sort.




Bubble sort example
Complexity analysis

Average and worst case complexity of bubble sort is O(n2). Also, it makes O(n2) swaps in the worst case. Bubble sort is adaptive. It means that for almost sorted array it gives O(n) estimation. Avoid implementations, which don't check if the array is already sorted on every step (any swaps made). This check is necessary, in order to preserve adaptive property.
Turtles and rabbits

One more problem of bubble sort is that its running time badly depends on the initial order of the elements. Big elements (rabbits) go up fast, while small ones (turtles) go down very slow. This problem is solved in the Cocktail sort.

Turtle example. Thought, array {2, 3, 4, 5, 1} is almost sorted, it takes O(n2) iterations to sort an array. Element {1} is a turtle.




Turtle example

Rabbit example. Array {6, 1, 2, 3, 4, 5} is almost sorted too, but it takes O(n) iterations to sort it. Element {6} is a rabbit. This example demonstrates adaptive property of the bubble sort.




Rabbit example
Code snippets

There are several ways to implement the bubble sort. Notice, that "swaps" check is absolutely necessary, in order to preserve adaptive property.
Java

public void bubbleSort(int[] arr) {

boolean swapped = true;

int j = 0;

int tmp;

while (swapped) {

swapped = false;

j++;

for (int i = 0; i < arr.length - j; i++) { if (arr[i] > arr[i + 1]) {

tmp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = tmp;

swapped = true;

}

}

}

}
C++

void bubbleSort(int arr[], int n) {

bool swapped = true;

int j = 0;

int tmp;

while (swapped) {

swapped = false;

j++;

for (int i = 0; i < n - j; i++) { if (arr[i] > arr[i + 1]) {

tmp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = tmp;

swapped = true;

}

}

}

}

c++ Merge Sort

Merge Sort



The merge sort combines two sorted arrays into
one larger sorted array.
As the diagram at the left shows,
Array A and Array B merge to form Array C.

Arrays to be merged MUST be SORTED FIRST!!

Be sure to declare Array C in main( ) and establish its size.

Example: Ascending Order
Array A: {7. 12}
Array B: {5, 7, 8}
Array C: {5, 7, 7, 8, 12} after merge

Here is how it works: The first element of array A is compared with the first element of array B. If the first element of array A is smaller than the first element of array B, the element from array A is moved to the new array C. The subscript of array A is now increased since the first element is now set and we move on.

If the element from array B should be smaller, it is moved to the new array C. The subscript of array B is increased. This process of comparing the elements in the two arrays continues until either array A or array B is empty. When one array is empty, any elements remaining in the other (non-empty) array are "pushed" into the end of array C and the merge is complete.

//Function to merge two pre-sorted arrays
void MergeSort(apvector &arrayA, apvector &arrayB, apvector &arrayC)
{
int indexA = 0; // initialize variables for the subscripts
int indexB = 0;
int indexC = 0;

while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
{
if (arrayA[indexA] < arrayB[indexB])
{
arrayC[indexC] = arrayA[indexA];
indexA++; //increase the subscript
}
else
{
arrayC[indexC] = arrayB[indexB];
indexB++; //increase the subscript
}
indexC++; //move to the next position in the new array
}
// Move remaining elements to end of new array when one merging array is empty
while (indexA < arrayA.length( ))
{
arrayC[indexC] = arrayA[indexA];
indexA++;
indexC++;
}
while (indexB < arrayB.length( ))
{
arrayC[indexC] = arrayB[indexB];
indexB++;
indexC++;
}
return;
}

c++ Insertion Sort

Insertion Sort

Insertion sort belongs to the O(n2) sorting algorithms. Unlike many sorting algorithms with quadratic complexity, it is actually applied in practice for sorting small arrays of data. For instance, it is used to improve quicksort routine. Some sources notice, that people use same algorithm ordering items, for example, hand of cards.
Algorithm

Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into two parts - sorted one and unsorted one. At the beginning, sorted part contains first element of the array and unsorted one contains the rest. At every step, algorithm takes first element in the unsorted part and inserts it to the right place of the sorted one. When unsorted part becomes empty, algorithm stops. Sketchy, insertion sort algorithm step looks like this:




Insertion sort sketchy, before insertion

becomes




Insertion sort sketchy, after insertion

The idea of the sketch was originaly posted here.

Let us see an example of insertion sort routine to make the idea of algorithm clearer.

Example. Sort {7, -5, 2, 16, 4} using insertion sort.




Insertion sort example
The ideas of insertion

The main operation of the algorithm is insertion. The task is to insert a value into the sorted part of the array. Let us see the variants of how we can do it.

"Sifting down" using swaps

The simplest way to insert next element into the sorted part is to sift it down, until it occupies correct position. Initially the element stays right after the sorted part. At each step algorithm compares the element with one before it and, if they stay in reversed order, swap them. Let us see an illustration.

insertion sort, sift down illustration

This approach writes sifted element to temporary position many times. Next implementation eliminates those unnecessary writes.
Shifting instead of swapping

We can modify previous algorithm, so it will write sifted element only to the final correct position. Let us see an illustration.

insertion sort, shifting illustration

It is the most commonly used modification of the insertion sort.
Using binary search

It is reasonable to use binary search algorithm to find a proper place for insertion. This variant of the insertion sort is called binary insertion sort. After position for insertion is found, algorithm shifts the part of the array and inserts the element. This version has lower number of comparisons, but overall average complexity remains O(n2). From a practical point of view this improvement is not very important, because insertion sort is used on quite small data sets.
Complexity analysis

Insertion sort's overall complexity is O(n2) on average, regardless of the method of insertion. On the almost sorted arrays insertion sort shows better performance, up to O(n) in case of applying insertion sort to a sorted array. Number of writes is O(n2) on average, but number of comparisons may vary depending on the insertion algorithm. It is O(n2) when shifting or swapping methods are used and O(n log n) for binary insertion sort.

From the point of view of practical application, an average complexity of the insertion sort is not so important. As it was mentioned above, insertion sort is applied to quite small data sets (from 8 to 12 elements). Therefore, first of all, a "practical performance" should be considered. In practice insertion sort outperforms most of the quadratic sorting algorithms, like selection sort or bubble sort.
Insertion sort properties

adaptive (performance adapts to the initial order of elements);
stable (insertion sort retains relative order of the same elements);
in-place (requires constant amount of additional space);
online (new elements can be added during the sort).

Code snippets

We show the idea of insertion with shifts in Java implementation and the idea of insertion using swaps in the C++ code snippet.
Java implementation

void insertionSort(int[] arr) {

int i, j, newValue;

for (i = 1; i < arr.length; i++) { newValue = arr[i]; j = i; while (j > 0 && arr[j - 1] > newValue) {

arr[j] = arr[j - 1];

j--;

}

arr[j] = newValue;

}

}
C++ implementation

void insertionSort(int arr[], int length) {

int i, j, tmp;

for (i = 1; i < length; i++) { j = i; while (j > 0 && arr[j - 1] > arr[j]) {

tmp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = tmp;

j--;

}

}

}

c++ Quicksort

Quicksort

Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely applied in practice. On the average, it has O(n log n) complexity, making quicksort suitable for sorting big data volumes. The idea of the algorithm is quite simple and once you realize it, you can write quicksort as fast as bubble sort.
Algorithm
The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:

Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn't present in the array.
Partition. Rearrange elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Notice, that array may be divided in non-equal parts.
Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.

Partition algorithm in detail

There are two indices i and j and at the very beginning of the partition algorithm i points to the first element in the array and j points to the last one. Then algorithm moves i forward, until an element with value greater or equal to the pivot is found. Index j is moved backward, until an element with value lesser or equal to the pivot is found. If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j - 1). Algorithm stops, when i becomes greater than j.

After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.
Example. Sort {1, 12, 5, 26, 7, 14, 3, 7, 2} using quicksort.




Quicksort example

Notice, that we show here only the first recursion step, in order not to make example too long. But, in fact, {1, 2, 5, 7, 3} and {14, 7, 26, 12} are sorted then recursively.
Why does it work?
On the partition step algorithm divides the array into two parts and every element a from the left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤ b inequality. After completion of the recursion calls both of the parts become sorted and, taking into account arguments stated above, the whole array is sorted.
Complexity analysis

On the average quicksort has O(n log n) complexity, but strong proof of this fact is not trivial and not presented here. Still, you can find the proof in [1]. In worst case, quicksort runs O(n2) time, but on the most "practical" data it works just fine and outperforms other O(n log n) sorting algorithms.
Code snippets

Partition algorithm is important per se, therefore it may be carried out as a separate function. The code for C++ contains solid function for quicksort, but Java code contains two separate functions for partition and sort, accordingly.
Java

int partition(int arr[], int left, int right)

{

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];



while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot)

j--;

if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } }; return i; } void quickSort(int arr[], int left, int right) { int index = partition(arr, left, right); if (left < index - 1) quickSort(arr, left, index - 1); if (index < right) quickSort(arr, index, right); } C++ void quickSort(int arr[], int left, int right) { int i = left, j = right; int tmp; int pivot = arr[(left + right) / 2]; /* partition */ while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};



/* recursion */

if (left < j)

quickSort(arr, left, j);

if (i < right)

quickSort(arr, i, right);

}

Rabu

Linear search

Sequential search / pencarian beruntun atau banyak pula yang menyebutnya linear search (pencarian lurus), adalah salah satu metode algoritma pencarian yang paling sederhana. Para programmer pemula pasti akan menggunakan algoritma ini saat menghadapi kasus pencarian untuk pertama kali. Konsep dari algoritma ini tak terlalu sulit, yakni seluruh data akan dicek satu persatu sampai data yang dicari ditemukan

konversi Fungsi Iteratif Menjadi Fungsi Rekursif

program 1

Bentuk fungsi iteratif :
Algoritma :
Deklarasi
x,i : integer
Deskripsi
Iteratif
read x
for i <- 1 to x do write i end for end Rekursif read x if (x >= 1) then
rekursif (x - 1)
write x
end if
end

#include
#include

using namespace std;

int jumlah(int n) {
int hasil = 0;
for (int i=0; i
#include

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;
}

Persamaan antara perulangan iteratif dan rekursif:
• Iteratif dan rekursif merupakan metode atau teknik di dalam perulangan (looping).
• Sama-sama mengalami perulangan kondisi.

c++ rekursif dan iteratif

fungsi rekursif yang mempunyai design dan konsep yang sangat elegan, akan tetapi iterasi lebih simple daripada proses rekursi dengan melakukan pengulangan sederhana terhadap blok kode dengan variabel lokal yang mengontrol jumlah eksekusi. Didalam C terdapat konstruksi for, while, and do untuk kontrol iterasi loop. Dibawah ini diberikan perbandingan antara fungsi rekursif yang sudah ada diatas dengan bentuk kontrol iterasi.

Iteratif adalah proses perulangan dalam suatu prosedur atau fungsi.

Algoritma iteratif

-Teknik Iteratif merupakan suatu teknik pembuatan algoritma dengan pemanggilan procedure beberapa kali atau hingga suatu kondisi tertentu terpenuhi.

-Tidak ada variabel lokal baru

-Program tidak sederhana

Contoh:

BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .

Teknik Iteratif pada algoritma untuk menentukan suku ke-n dari barisan bilangan Fibbonaci, adalah sebagai berikut :

1. Set x, y, n, i, f : integer

2. x ← 1 ; y ← 1

3. If n ⟩ 2 then

begin

4. for i ← 3 to n do

begin

5. F ← x + y

6. x ← y

7. y ← F

end

else

8. F ← x

9. Write(F)

End

Algoritma rekursif

-Teknik Rekursif merupakan salah satu cara pembuatan algoritma dengan pemanggilan procedure atau function yang sama

-Ada variabel lokal baru

-Program menjadi lebih sederhana

Contoh:

BARISAN BILANGAN FIBBONACI → 1, 1, 2, 3, 5, 8, 13, 21, . . .

Teknik Rekursif pada algoritma untuk menentukan suku ke-n dari barisan bilangan Fibbonaci, adalah sebagai berikut :

Procedure F(n : integer) : integer

1. If n ≤ 2 then F(n) = 1

else F(n) = F(n-1) + F(n-2)

Endif

End

#include

#include

int Perkalian(int bilangan1, int bilangan2)

{

int pro=0;

for (int i=bilangan2;i>=1;i–)

{

pro+=bilangan1;

}

return (pro);

}

int main(void)

{

int x,y,N;

scanf(“%d %d”,&x,&y);

N = Perkalian(x,y);

printf(“Hasil : %d”,N);

getch();

return (0);

}

Rekursif merupakan sebuah proses yang terjadi apabila dalam sebuah fungsi terdapat sebuah instruksi yang memanggil (calling) fungsi itu sendiri.

Contoh program:

#include

void hitung(int n);

main()

{

int N, fact;

scanf(“%i”, &N);

fact= hitung(N);

printf(“%i”, fact);

}

void hitung()

{

int x,y;

if(n==0);

return(1);

x=n-1;

y=hitung(x);

return(n*y);

}


Perbedaan dan Persamaan Rekursif dan Iteratif :

a. Persamaan

Sama-sama merupakan bentuk perulangan.

Dilakukan pengecekan kondisi terlebih dahulu sebelum mengulang.

b. Perbedaan

1) Iteratif menggunakan FOR, WHILE, DO-WHILE sedangkan rekursif hanya menggunakan IF.

Kelebihan metode rekursif:

Solusi sangatlah efisien.

Dapat memecahkan masalah yang sulit dengan tahapan yang mudah dan singkat.

Kekurangan metode rekursif:

Sulit dipahami.

Perlu stack besar (stack overflow).

Kamis

fungsi rekursif c++

Dalam dunia pemrograman, rekursi
diimplementasikan dalam sebuah fungsi yang
memanggil dirinya sendiri.
Contoh fungsi rekursif misalnya adalah fungsi pangkat,
faktorial, dan barisan fibonacci.
Dalam fungsi pangkat xy , kita tahu bahwa semua
bilangan selain 0, jika dipangkatkan dengan 0 nilainya
sama dengan 1.
Jika x dipangkatkan dengan y, dengan y lebih dari 0,
maka hasilnya sama dengan x dikalikan dengan x
dipangkatkan y – 1.
xy = 1, jika y = 0
xy = x * x(y-1)
, jika y > 0
Untuk x = 10 dan y = 0, hasil dari xy adalah 1.
Untuk x = 10 dan y = 3

contoh program
fungsi fibonachi

#include

int fibonacci (int n)
{ if ((n == 1) || (n == 2)) return(1);
else return(fibonacci(n-1) + fibonacci(n-2));
}

main() {
int i, n;
cout << "Sampai suku ke : "; cin >> n;
for (i = 1; i <= n; i++) cout << fibonacci(i) << " ";
return 0;
}

Dimana n,i=integer
n-1 = Pemanggil rekursi
i <= n= sebagai Penyetop

Senin

C++ Loop Invariant

C++ Loop Invariant

Loop invariants are critical tools for the proof of correctness of algo-
rithms; they represent the “inductive step” in a proof by induction that
the configuartion of the variables satisfies certain conditions throughout the
algorithm.
To formalize this concept, we introduce some terminology.
Let x1, . . . , xm denote the variables on which an algorithm operates;
let Ai be the domain of xi (set of possible values of xi). A configuration
a = (a1, . . . , am) is an assignment of values to each variable (ai ∈ Ai). The
set of all conceivable configurations is C = A1 × . . . × Am; we call C the
configuration space. A feasible configuration is a configuration which can
actually occur in the course of an execution of the algorithm. Note that in
general, not all configurations are feasible.

Example: the variables in Dijkstra’s algorithm are the priority queue L and
for each vertex i ∈ V , the variables status(i), c(i), and p(i) (the current
status, cost, and parent of vertex i), a total of 3n + 1 variables where n is
the number of vertices. The domain of status(i) is {white, grey, black }; the
domain of c(i) is R+ ∪{∞} (the nonnegative reals and infinity); the domain
of p(i) is V ∪ {NIL }. The domain of L can be thought of as 2V (the set of
all subsets of V ).
An example of an infeasible configuration that nevertheless belongs to
the configuration space is a configuration where some vertex i belongs to
the queue while status(i) =black.

A predicate over C is a function P : C → {0, 1} where 0 indicates “FALSE”
and 1 indicates “TRUE.” A transformation of C is a function S : C → C.
If P is a predicate and a ∈ C a configuration then instead of writing
P(a) = 1, we just write “P(a),” meaning “the statement P(a) is TRUE”;
i. e., the configuration a satisfies the predicate P. For P(a) = 0 we may
write “¬P(a),” meaning the negation of P(a) holds, i. e., a does not satisfy
P. In other words, P is false on a.
The effect of a sequence S of instructions in the code is a change of the
values of the variables and therefore S can be thought of as a transformation
S : C → C.

Definition. Let P and Q be predicates over the configuration space and
let S be a sequence of instructions, viewed as a transformation of the con-
figuration space. Consider the loop
while P do S.
We call Q a loop-invariant for this loop if for all configurations a it is true
that
(∀a ∈ C)( if P(a)&Q(a) then Q(S(a))).

Algorithm:

GetMiddle (List l){
pSlow = pFast = l;
while ((pFast->next)&&(pFast->next->next)){
pFast = pFast->next->next
pSlow = pSlow->next
}
return pSlow
}

#include
#include

int main()
{
int n, min;
cout<<"Masukkan bilangan positif(0 untuk selesai): "; cin>>n;
for(min=n;n>0;)
{
if(n>n;
}
cout<<"min = "< getch();
return 0;
}

c++ Bilangan berpangkat

Kasus 4.7.
c++ Bilangan berpangkat
#include
#include
main() {
int x, y, i;
int pangkat = 1;
cout<<"Menghitung hasil perpangkatan\n"; cout<<"Tulis sebuah bilangan : "; cin >> x;
cout<<"Mau dipangkat berapa : "; cin >> y;
for(i = 1; i<=y; i++)
pangkat *= x;
cout<

C++ Sentinel

C++ Sentinel
#include
#include
main() {
int n = 1, jumlah = 0, x;
float rata;
cout<<"Data ke-1 : "; cin>>x;
while(x>0) {
jumlah += x;
cout<<"Data ke- : "<< n+1; cin>>x;
n++;
}
rata=(float)jumlah/(n-1);
cout << "Rata-rata = " << rata;
getch();
return 0;
}

C++ rata-rata bilangan

Kasus 4.3.
C++ rata-rata bilangan
#include
#include
main() {
int i, n, jumlah, x;
float rata;
cout << "Banyak data : "; cin >> n;
jumlah = 0;
for (i = 1; i<=n; i++) { cout << "Data ke- : " << i<<" "; cin >> x;
jumlah += x;
}
rata = (float) jumlah/n;
cout << "Rata-rata = " << rata;
getch();
return 0;
}