Olimpiade Sains Kota (OSK) 2012 - Komputer, Nomor 37–39

swap(a,b,c) 
swap ini sama seperti algorithma swap , hanya saja kali ini kita akan menggunakannya dalam bentuk lebih dari 1 object.
fungsi dari procedure swap adalah mengganti object tanpa merubah pola barisannya.
(1,2,3,4,5,6) Swap(a,b,c)

contoh swap(2,4,6)
langkah pertama 
simpan dummy 1 ( b+1 sampai c ) yaitu (1,2,3,4,[5,6])
simpan dummy 2 ( a sampai b ) yaitu (1,[2,3,4],5,6)
kemudian swap kedua pola dalam kurung tersebut
jadinya (1,[5,6],[2,3,4])
1,5,6,2,3,4

==============================================================================

Nomer 37

(1,2,3,4,5,6) swap(2,4,6)
(1,[2,3,4],[5,6])
(1,[5,6],[2,3,4])
1,5,6,2,3,4

Jawaban = D. 1,5,6,2,3,4

===============================================================================

Nomer 38

array berukuran kecil, masih bisa dikerjakan secara manual.
(6,4,3,5,1,2) swap(1,2,4)
([6,4],[3,5],1,2)
([3,5],[6,4],1,2)
(3,5,6,4,1,2) -> swap(3,4,5)
(3,5,[6,4],[1],2)
(3,5,[1],[6,4],2)
(3,5,1,6,4,2)

Jawaban = E. 3,5,1,6,4,2

 

================================================================================

Nomer 39

Untuk soal ini sedikit dibuat lebih sulit. karena Solusi harus menggunakan algoritma sort , terlebih lagi kita harus meminimal lisir jawaban
saya gunakan teknik seperti merge sort.
dengan cara membagi 2 tiap pemanggilan swap menggunakan rekursif dibelah dibelai --"

jadi banyaknya data N = 18 ( pada soal )
(5, 8, 10, 11, 25, 30, 33, 42, 49, 54, 63, 64, 66, 75, 78, 84, 93, 96)
frequensi data sekarang = 18
bagi 2 ambil tengah nya yaitu swap(1,n/2,n) atau swap(1,9,18)
([5, 8, 10, 11, 25, 30, 33, 42, 49], [54, 63, 64, 66, 75, 78, 84, 93, 96])
([54, 63, 64, 66, 75, 78, 84, 93, 96], [5, 8, 10, 11, 25, 30, 33, 42, 49])
nah setelah membagi 2 dan melakukan swap .
pisahkan rekursif mereka dengan membagi dua lagi seterusnya sampai dengan tersisa 1 angka

[54, 63, 64, 66, 75, 78, 84, 93, 96] ==== [5, 8, 10, 11, 25, 30, 33, 42, 49]
([54, 63, 64, 66, 75],[78, 84, 93, 96])
([78, 84, 93, 96],[54, 63, 64, 66,75])

bagi 2 lagi 
([78, 84, 93, 96] ===== [54, 63, 64, 66,75])
([78,84],[93,96])
([93,96],[78,84])

bagi 2 lagi 
([93,96] ===== [78,84])
([93],[96])

bagi 2 lagi
([93],[96])
([96],[93])
(96 ====  93)
============= End Of Line

atau bisa juga tanpa memperdulikan angka-angka hanya dengan frequensi setiap bagi 2.

F(18) = F(9) + F(9) + 1
F(9) = F(4) + F(5) + 1
F(5) = F(2) + F(3) + 1
F(4) = F(2) + F(2) + 1
F(3) = F(1) + F(2) + 1
F(2) = F(1) + F(1) + 1
F(1) = 0;

F(1) = 0;
F(2) = F(1) + F(1) + 1 = 0 + 0 + 1 = 1
F(3) = F(1) + F(2) + 1 = 0 + 1 + 1 = 2
F(4) = F(2) + F(2) + 1 = 1 + 1 + 1 = 3
F(5) = F(2) + F(3) + 1 = 1 + 2 + 1 = 4
F(9) = F(4) + F(5) + 1 = 3 + 4 + 1 = 8
F(18) = F(9)+ F(9) + 1 = 8 + 8 + 1 = 17

Jawaban = B. 17