pelatihan osk algoritmika (1)
TRANSCRIPT
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 1/42
algoritmika
Pelatihan OSK 2015
Rakha Kanz Kautsar
February 9, 2015
0
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 2/42
review pascal
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 3/42
basic structure
program x;
var
{Deklarasi variabel}
i,j,k : integer;
const
{Deklarasi konstanta}
PI = 3.1415;
procedure p(str:ansistring);
begin
{Isi prosedur}
end;
function f(x:integer):integer;
begin
{Isi fungsi}
end;
begin
{Isi program utama}
end.
2
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 4/42
conditional
if {conditional} then begin{do something}
end;
3
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 5/42
conditional
if {conditional} then begin
{do something}end else begin
{do something else}
end;
4
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 6/42
conditional
if {conditional} then begin
{do something}
end else if {another conditional} then begin{do something else}
end else begin
{if all fails, do something}
end;
5
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 7/42
loop
while {conditional} do begin{do something while true}
end;
6
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 8/42
loop
repeat{do something until true}
until {conditional};
7
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 9/42
loop
for {variable}:={begin value}
to {end value} do begin
{do something with the variable}
end;
8
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 10/42
loop
for i:=1 to 10 do begin
writeln(i);
end;
for i:=10 downto 1 do begin
writeln(i);
end;
9
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 11/42
contoh soal
Apa keluaran dari program berikut?
p:=true;
q:=false;
if (p=false or 3 mod 2 = 1) and (q=true and 1=1) then
writeln(’A’)else
writeln(’B’);
end;
10
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 12/42
contoh soal
Apa keluaran dari program berikut?
n:=3;
for i:=1 to n do begin
for j:=1 to j do begin
if(i<j) then write(’.’)else write(’#’);
end;
writeln;
end;
10
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 13/42
tipe data
Tipe Range
byte ..
shortint -..
smallint -....word ...
integer smallint or longint
cardinal longword
longint -..int -..
qword ..
11
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 14/42
beberapa algoritma penting
s g
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 15/42
swapping
procedure swap(var x,y:integer);
var tmp;
begintmp:=x;
x:=y;
y:=x;
end;
13
swapping
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 16/42
swapping
procedure swap(var x,y:integer);
begin
x:=x+y;
y:=x-y;
x:=x-y;
end;
13
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 17/42
euclidean algorithm
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 18/42
euclidean algorithm
gcd(a,b) =
a, if b = 0.
gcd(b,a mod b), otherwise.
14
euclidean algorithm
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 19/42
euclidean algorithm
function gcd(a,b:integer):integer;
beginif b=0 then gcd:=a
else gcd:=gcd(b,a mod b);
end;
14
sieve of eratosthenes
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 20/42
sieve of eratosthenes
// p adalah array [1..MAX] of boolean
// berisi default true.
for i:=2 to MAX do beginif p[i] then
for j:=i*i to MAX do p[j]:=false;
end;
// i bilangan prima iff p[i]=true.
15
fast exponentiation
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 21/42
fast exponentiation
be =
1,
if e
= 0b
e
2 · be
2 , if even.
b · be−1, if odd.
16
fast exponentiation
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 22/42
fast exponentiation
function pangkat(b,e:integer):longint;var
tmp:longint;
begin
if e=0 then pangkat:=1else if (e mod 2 = 1) then
pangkat:=b*pangkat(e-1)
else begin
tmp:=pangkat(e div 2);pangkat:=tmp*tmp;
end;
end;
16
fast exponentiation
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 23/42
fast exponentiation
function pangkat(b,e:longint):longint;var
res:longint;
begin
while e>0 do beginif (e mod 2 = 1) then
res *= b;
e := e div 2;
b := b * b;end;
pangkat := res;
end; 16
flood fill (dfs)
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 24/42
flood fill (dfs)
procedure dfs(x,y:integer);
begin
if safe(x,y) then begin
visited[x,y]:=true;
// Process..
dfs(x,y+1);
dfs(x,y-1);
dfs(x+1,y);
dfs(x-1,y);
end;
end;
17
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 25/42
rekursi
factorial
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 26/42
function factorial(x:integer):longint;
beginif x<2 then factorial:=x
else factorial:= x * factorial(x-1);
end;
19
fibonacci
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 27/42
function fib(n:integer):longint;
beginif n<2 then fib:=1
else fib:=fib(n-1)-fib(n-2);
end;
20
struktur umum
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 28/42
function f(parameter):return_value;
beginif ... then f:=base_case
else f:= f() //recurse ;
end;
21
approach
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 29/42
function sikat(x,y:longint):longint;
begin
if (x>=y) then sikat:=x
else sikat:=3*sikat(x+1,y)+2*sikat(x,y-1);end;
22
approach
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 30/42
function sikat(x,y:longint):longint;
begin
if (x>=y) then sikat:=x
else sikat:=3*sikat(x+1,y)+2*sikat(x,y-1);end;
1. Pohon Faktor
22
approach
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 31/42
function sikat(x,y:longint):longint;
begin
if (x>=y) then sikat:=x
else sikat:=3*sikat(x+1,y)+2*sikat(x,y-1);end;
1. Pohon Faktor
2. Tabel DP
22
approach
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 32/42
function sikat(x,y:longint):longint;
begin
if (x>=y) then sikat:=x
else sikat:=3*sikat(x+1,y)+2*sikat(x,y-1);end;
1. Pohon Faktor
2. Tabel DP
3. Khusus
22
approach
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 33/42
vardata :
array[1..10] of integer =
(3,9,2,6,1,4,7,8,5,10);
procedure kambing(m : integer);
begin
if (m<=10) then
begin
kambing(m*2);
write(data[m],’ ’);
kambing(m*2+1);
end;
end;
Hasil pemanggilan kambing(1) adalah...23
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 34/42
sorting
bubble sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 35/42
swapped:=true;
repeat
swapped:=false;
for i:=2 to n do begin
if A[i]>A[i-1] then begin
swap(A[i],A[i-1]);
swapped:=true;
end;
end;n:=n-1;
until swapped=false;
25
selection sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 36/42
for i:=1 to n do begin
idx_min:=i;
for j:=i+1 to n do begin
if A[j]<A[idx_min] then
idx_min:=j;
end;
swap(A[i],A[idx_min]);
end;
26
insertion sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 37/42
for i:=2 to n do begin
for j:=i downto 2 do begin
if A[j]>A[j-1] then break
else swap(A[j],A[j-1]);
end;
end;
27
and other sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 38/42
∙ Merge Sort
28
and other sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 39/42
∙ Merge Sort
∙ Heap Sort
28
and other sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 40/42
∙ Merge Sort
∙ Heap Sort
∙ Quick Sort
28
and other sort
8/19/2019 Pelatihan OSK Algoritmika (1)
http://slidepdf.com/reader/full/pelatihan-osk-algoritmika-1 41/42
∙ Merge Sort
∙ Heap Sort
∙ Quick Sort
∙ Topological Sort
28