Soal Nlc 2019

by

Soal NLC 2018 – Tentunya dengan Soal NLC 2019 yang kami sampikan ini akan mampu menciptakan anda mampu mengerti dan memahami Soal NLC 2019 yang kami sampikan untuk anda semua. Soal yang kami berikan juga akan menawarkan pembahasaan dan juga kunci jawabannya sehingga anda tidak perlu kawatir wacana Soal NLC 2019 yang kami sampaikan tersebut.

Ini akan sangat memudahkan buat anda semua yang ingin berguru Soal NLC 2019 tersebut. Disini admin kunci tanggapan menunjukkan aneka macam soal-soal dan pembahasan untuk mampu anda pelajari juga sehingga anda memahami perihal soal yang dikala ini anda ingin pelajari.

Untuk selengkapnya wacana Soal NLC 2019 tersebut kamu mampu simak dibawah ini selengkapnya untuk anda semua, biar mampu menjadi manfaat untuk pelajaraan anda dikala ini.

Soal NLC 2019

Introduction

“Pak Dengklek sedang berlibur ke desa bebek. Dalam liburannya, secara tak sengaja beliau menemukan prasasti kuno ketika sedang menyusuri sawah desa bebek. Di dalam prasasti itu dia memperoleh sekumpulan N (1 ≤ N ≤ 1000, N bilangan ganjil) angka acak. Dikatakan bahwa tersembunyi angka hoki di dalam sekumpulan angka itu. Yang dimaksud angka hoki ialah jikalau sekumpulan angka itu berada dalam kondisi terurut, maka angka yang sempurna berada di tengah-tengah kumpulan angka itu adalah angka hoki. Pak Dengklek penasaran akan angka hoki itu, sehingga ia meminta pertolongan Anda. Bantulah beliau!”
Misalkan pola masukan dari sekumpulan angka acak di soal yaitu mirip di bawah ini:

2 1 3 6 5 8 4 7 10 21 12

Dengan sedikit anutan, kita tahu bahwa “angka hoki” yang dimaksud Pak Dengklek yaitu median dari kumpulan acak itu. Setelah mengenali bahwa yang dicari yakni nilai median, apa yang akan kita lakukan? Tentunya dalam mencari median akan lebih mudah juga sekumpulan angka di atas sudah dalam keadaan terurut seperti di bawah ini:

1 2 3 4 5 6 7 8 10 12 21

Setelah kumpulan angka tersebut telah dalam kondisi terurut menaik (ascending), maka nilai median mampu dengan segera didapatkan (rumus mencari median telah tau kan?). Kenapa dikatakan terurut menaik, karena bisa saja kita mengendalikan agar sekumpulan angka di atas berada dalam kondisi terurut menurun (descending), misalnya seperti pola berikut.

21 12 10 8 7 6 5 4 3 2 1

Bagaimana jika kita ingin mengurutkan sekumpulan kata? Misal ada kumpulan kata mirip di bawah ini:

halo
aku
sangat
senang
dan
bersemangat
mencar ilmu
pemrograman

kita mampu mengurutkannya secara leksikografis (sesuai urutan kamus, misalnya ‘A‘ muncul sebelum ‘B‘ dan ‘AKU‘ timbul sebelum ‘ANDA‘), mirip:

belajar
bersemangat
dan
halo
pemrograman
sangat
aku
senang

atau mampu juga diurutkan menurut panjang dari kata itu (kalau panjang kata sama, urutkan berdasarkan leksikografis), mirip:

dan
halo
saya
sungguh
bahagia
berguru
bersemangat
pemrograman

Dalam pemrograman, hal ini lazimdisebut sorting (atau mengurutkan). Dalam mengurutkan sekumpulan data, ada hukum yang digunakan untuk menentukan prioritas, misal bilangan yang lebih kecil muncul lebih dahulu, atau kata yang panjangnya lebih pendek muncul apalagi dulu. Banyak sekali algoritma yang tersedia untuk pengurutan sekumpulan data, ada yang gampang ditulis kodenya, ada juga yang kodenya panjang. Kali ini aku akan bahas beberapa algoritma sorting yang biasa dipakai, adalah:

  1. Bubble Sort (kompleksitas O(N2)).
  2. Quick Sort (kompleksitas expected O(N × log2N), worst case O(N2)).
  3. Merge Sort (kompleksitas O(N × log2N)).
  4. Count Sort (kompleksitas O(N)).
  5. Radix Sort (kompleksitas O(d × N), di mana d ialah panjang digit terpanjang dalam kumpulan data).
  6. Heap Sort (coming soon).

—————————————————————-

Bubble Sort

Bubble sort yakni salah satu algoritma pengurutan yang sederhana dan mudah di-coding. Ide dasarnya yakni dalam setiap looping, cari bilangan terkecil dan tempatkan di paling kiri (untuk ascending sort), penggalan kodenya yaitu selaku berikut:

  Soal Ipa Kelas 3 Sd Semester 1
1
2
3
4
5
6
7
8
for i := 1 to N do
    for j := 1 to N - 1 do
        if data[j] > data[j + 1] then
        begin
            temp := data[j];
            data[j] := data[j + 1];
            data[j + 1] := temp;
        end;

Perhatikan potongan instruksi di atas, terang untuk setiap looping ke-i akhir, kita akan menerima bilangan paling besar ke-i pada posisi data[N-i+1]. Kompleksitas Bubble sort ialah O(N2), artinya untuk kumpulan data sebanyak 1.000 buah data, algoritma ini membutuhkan 1.000.000 kali operasi untuk mengurutkan data tersebut. Untuk banyak data yang relatif kecil (sekitar di bawah 5.000) algoritma ini berjalan relatif cepat.

Mungkin kalian bertanya-tanya, kenapa algoritma ini dinamai Bubble Sort. Dari yang pernah saya baca atau dengar, jika kalian lihat di danau, gelembung gas dalam danau yang terbesar akan muncul ke permukaan pertama kali :).

Selain Bubble Sort, ada juga varian algoritma sorting lain yang sama-sama mempunyai kompleksitas O(N2) seperti Insertion Sort dan Selection Sort, tetapi tidak aku diskusikan alasannya menurut aku mereka bertiga agak mirip (bahkan saya sendiri bingung membedakan Bubble Sort dan Insertion Sort) dan kompleksitas pun sama-sama O(N2), jadi rasanya cukup mempelajari salah satu saja.

——————————————————-

Quick Sort

Seperti yang disebutkan sebelumnya, kompleksitas Bubble Sort yakni O(N2), artinya kalau jumlah data sebanyak 10.000 data (N = 10.000), maka Bubble Sort akan melaksanakan sekitar 100 juta operasi untuk mengurutkan sekumpulan data itu. Konversi yang umum digunakan yakni 1 detiknya komputer bisa melakukan 100 juta operasi sederhana, artinya untuk jumlah data yang relatif besar (misal, N = 1.000.000) maka Bubble Sort membutuhkan waktu yang cukup usang (N = 1 juta, mempunyai arti sekitar 1012 operasi, kalau 1 detiknya = 100 juta operasi, maka waktu yang dibutuhkan sekitar 10.000 detik atau nyaris 3 jam!).

Lalu apa yang mesti dilakukan untuk kalau kita ingin mengurutkan data yang banyaknya relatif besar? salah satu caranya ialah dengan menggunakan Quick Sort. Sesuai namanya, Quick Sort dengan kompleksitas O(N × log2N) ialah teknik sorting yang cukup cepat, dengan jumlah data sebanyak 1 juta, Quick Sort hanya melaksanakan sekitar 20 juta operasi, masih di bawah 1 detik :D.
Ide dasar dari Quick Sort adalah jika kita mempunyai sekumpulan angka lalu kita jejerkan dari kiri ke kanan, kita mampu mengambil angka yang berada di tengah-tengah/ pivot dan semua angka di sebelah kiri dari pivot yang lebih besar dari pivot dipindahkan ke sebelah kanan pivot, lalu semua angka di sebelah kanan dari pivot yang lebih kecil dari pivot dipindahkan ke sebelah kiri pivot. Jika proses ini diulang-ulang untuk sub-jangkauan data yang lebih kecil, pada jadinya kita akan mendapatkan barisan data yang terurut menaik (ascending).

Potongan arahan dari Quick Sort disertakan di bab bawah (Peringatan: Quick Sort menggunakan procedure dan konsep rekursif, jika kalian belum mengerti tentang kedua topik ini, diusulkan untuk memperkuat dasar procedure dan rekursif apalagi dulu).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
procedure quicksort(terkiri,terkanan: longint);
var kiri, kanan, temp, pivot: longint;
begin
   if terkiri < terkanan then
   begin
      kiri := terkiri;
      kanan := terkanan;
      pivot := data[(kiri + kanan) div 2];
      while kiri <= kanan do
      begin
         while data[kiri] < pivot do inc(kiri);
         while data[kanan] > pivot do dec(kanan);
         if kiri <= kanan then
         begin
            temp := data[kiri];
            data[kiri] := data[kanan];
            data[kanan] := temp;
            inc(kiri);
            dec(kanan);
         end;
      end;
      quicksort(terkiri,kanan);
      quicksort(kiri,terkanan);
   end;
end;

Procedure di atas dapat dipanggil di program utama dengan quicksort(1,N); dimana N yakni banyaknya data (asumsikan array kalian mulai dari indeks ke-1, jika mulai dari indeks ke-0 bisa disesuaikan sendiri, format bahwasanya yaitu quicksort(indeks_terawal,indeks_terakhir);).
Untuk Quick Sort, sebetulnya saya juga ada animasinya, tetapi dalam bahasa C++ dan visualisasi animasi tersebut memakai terkiri sebagai pivot, bukan (terkiri + terkanan) div 2 seperti cuilan instruksi di atas, jadi dibandingkan dengan menciptakan kalian galau tidak saya sertakan.

  Soal Zenius

---------------------------------------------------------

Merge Sort
Walaupun Quick Sort ialah algoritma sorting yang cukup cepat (bahkan yang tercepat di antara semua algoritma sorting O(N × log2N), berdasarkan panduan pengurutan dari PJJ TOKI – thx Veni!) tapi runtime Quick Sort sendiri boleh dikatakan tidak stabil. “Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sungguh cepat, tetapi pada perkara-kasus tertentu Quick Sort akan berlangsung agak lambat, dan bila sedang sial, untuk input tertentu (worst case) Quick Sort akan berlangsung dengan waktu O(N2). Namun pada umumnya (average case), Quick Sort berjalan dengan waktu O(N × log2N)“ – bimbingan pengurutan TOKI.

Selain Quick Sort, ada 1 lagi algoritma sorting dengan kompleksitas O(N × log2N) dan runtime-nya cukup stabil, ialah Merge Sort. Ide dasar dari Merge Sort yaitu membagi sekumpulan angka menjadi 2 bab yang lebih kecil, lalu per bagian diatasi masing-masing. Bagian yang sudah mengecil itu akan terus dibagi 2 sampai dirasa telah cukup kecil (1 unsur), tiap bagian yang kecil itu diurutkan masing-masing. Bagian besar sebelumnya akan mengundang 2 bagian kecil yang sudah terurut tadi untuk digabungkan menjadi 1 kumpulan besar yang terurut.

Source code dari Merge sort adalah sebagai berikut: (Peringatan: sama mirip Quick Sort, Merge Sort juga menggunakan konsep rekursif ditambah 1 procedure embel-embel)

1
2
3
4
5
6
7
8
9
10
procedure sort(terkiri, terkanan: longint);
begin
   if terkiri < terkanan then
   begin
      sort(terkiri, (terkiri + terkanan) div 2);
      sort(((terkiri + terkanan) div 2) + 1, terkanan);
      merge(terkiri,(terkiri + terkanan) div 2, ((terkiri + terkanan) div 2) + 1, terkanan);
   end;
end;

sedangkan serpihan isyarat dari procedure merge() adalah selaku berikut:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
procedure merge(a1, b1, a2, b2: longint);
var i, permulaan: longint;
    temp: array[1..1000000] of longint;
begin
   i := a1;
   permulaan := a1;
   while ((a1 <= b1) and (a2 <= b2)) do
   begin
      if data[a1] <= data[a2] then
      begin
         temp[i] := data[a1];
         inc(a1);
      end else
      begin
         temp[i] := data[a2];
         inc(a2);
      end;
      inc(i);
   end;
   while (a1 <= b1) do
   begin
      temp[i] := data[a1];
      inc(a1);
      inc(i);
   end;
   while (a2 <= b2) do
   begin
      temp[i] := data[a2];
      inc(a2);
      inc(i);
   end;
   for i := permulaan to b2 do data[i] := temp[i];
end;

Merge Sort dipanggil di acara utama dengan sort(1, N); di mana N yakni banyaknya data. Perhatikan dalam procedure merge() dipakai 1 array temporer kawasan kedua bagian kecil diurutkan, dan lalu di bab final data-data yang telah terurut itu akan dikembalikan kepada array.

Cukup panjang ya untuk suatu algoritma sorting jikalau daripada Quick Sort dan yang lain. Mungkin alasannya argumentasi ini juga Quick Sort yang lebih populer dipakai dalam programming contest walaupun runtime-nya kurang stabil.
 --------------------------------------------------------------------

Count Sort

Kalau dari tadi kita membicarakan algoritma sorting yang konvensional, sekarang kita akan membahas yang agak “unik”. Namanya Count Sort (atau Counting Sort), kompleksitasnya hanya O(N + M) di mana N ialah banyaknya data dan M adalah selisih antara bilangan terbesar dan terkecil dalam kumpulan data. Oleh alasannya itu Count Sort dalam beberapa masalah bisa lebih singkat dibanding algoritma O(N × log2N) lain.
Ide dasar dari Count Sort sendiri yaitu mengkalkulasikan berapa banyak angka “1” di kumpulan data, berapa banyak angka “2”, angka “3”, angka “4”, dan seterusnya. Setelah itu kita looping sekali lagi untuk mengeluarkan angka “1” sesuai jumlahnya di kumpulan data, angka “2” sesuai jumlahnya, angka “3”, angka “4”, dan seterusnya. Kedengarannya gampang ya?
Potongan aba-aba dari Count Sort yaitu sebagai di bawah ini (sebelumnya, set nilai di array cnt dengan 0, mampu dengan fillchar atau looping sekali).

  Soal Qada Dan Qadar

1

2
3
4
5
6
7
8
for x := 1 to N do inc(cnt[data[x]]);
now := 1;
for x := data_terkecil to data_terbesar do if(cnt[x] > 0) then
    for y := 1 to cnt[x] do
    begin
       data[now] := x;
       inc(now);
    end;

Dari pecahan instruksi di atas kita tahu bahwa ukuran array dari cnt haruslah meraih dari bilangan terkecil hingga bilangan paling besar dalam data, maksudnya jikalau masukan data yaitu sebagai berikut:

7 1 10 3 100 -1 -5 -100 1532

Maka ukuran dari cnt haruslah menjangkau dari -100 sampai 1532. Seperti yang bisa ditebak, Count Sort tidak mampu digunakan jika jarak antara data terbesar dan data terkecil dalam kumpulan data terlalu besar, contohnya mirip di bawah ini:

-12345678912 1 2 1234567890

Banyak data pada input di atas memang kecil, cuma 4 elemen, namun bilangan terbesarnya 1234567890 dan bilangan terkecilnya -12345678912, mustahil kita mampu menawarkan array dengan ukuran sebesar itu.
Kelemahan lain Count Sort yaitu cuma bisa dipakai untuk mengurutkan bilangan bundar, tidak mampu bilangan desimal atau kalimat.
-------------------------------------------------------------

Radix Sort

Selain Count Sort, ada 1 lagi algoritma sorting dengan kompleksitas waktu O(N) (bahu-membahu O(d × N), di mana d yakni panjang digit terpanjang dalam kumpulan data), yaitu Radix Sort. Sepengetahuan saya, jarang sekali hingga ada yang menggunakan Radix Sort dalam programming contest sebab algoritma O(N × log2N) mirip Quick Sort sendiri telah lebih dari cukup. Saya sertakan di sini hanya untuk memperbesar pengetahuan kalian saja. Kalau tidak berhasrat, halaman ini mampu di-skip.
Ide dasar dari Radix Sort yaitu mengurutkan kumpulan data berdasarkan angka satuan, puluhan, ratusan, ribuan, dan seterusnya. Source code dari Radix Sort yakni selaku berikut:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure radixsort(N: longint);
var temp: array[1..10000] of longint;
    bucket: array[0..9] of longint;
    i, largest, exp: longint;
begin
   largest := 0;
   exp := 1;
   for i := 1 to N do if data[i] > largest then largest := data[i];
   while largest div exp > 0 do
   begin
      for i := 0 to 9 do bucket[i] := 0;
      for i := 1 to N do inc(bucket[(data[i] div exp) mod 10]);
      for i := 1 to 9 do bucket[i] := bucket[i] + bucket[i - 1];
      for i := N downto 1 do
      begin
         temp[bucket[(data[i] div exp) mod 10]] := data[i];
         dec(bucket[(data[i] div exp) mod 10]);
      end;
      for i := 1 to N do data[i] := temp[i];
      exp := exp * 10;
   end;
end;

Kalau pecahan arahan di atas cermati, mungkin kalian akan mengajukan pertanyaan-tanya, “bagaimana kalau kumpulan data mempunyai nilai negatif atau 0 (nol)?” Memang, instruksi di atas hanya bekerja untuk kumpulan data yang tidak mengandung bilangan negatif dan bilangan terbesarnya tidak nol. Untuk mensiasati kumpulan data dengan bilangan negatif, dapat dibentuk menjadi 2 bab; kumpulan bilangan negatif dan non-negatif. Setelah masing-masing diurutkan baru digabungkan.

sumber: felikjunvianto.wordpress.com