Jolly Jumper Problem, iseng saja

 Jolly Jumper

Kemarin aku lihat-lihat si Ucup yang bikin program buat menyelesaikan masalah jolly jumper. Jolly jumper itu apa sih?

Definisi masalahnya adalah sebagai berikut:

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,

1 4 2 3

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.
Input

Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.
Output
For each line of input, generate a line of output saying “Jolly” or “Not jolly”.
Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

Diambil dari sini.

Nah gimana cara penyelesaiannya?

Ada beberapa cara yang diajukan untuk menyelesaikan masalah ini:

  1. Dengan mencari secara iteratif setiap nilai dari 1…n-1. -> cenderung brute force
  2. Dengan menyimpan selisih tiap angka yang berdekatan dalam deret, lalu secara iteratif memeriksa apakah setiap 1…n-1 ada dalam selisih deret tersebut.

Opsi pertama kira-kira seperti ini:

Array deret;
bool flag=false;

for i from 1 to n-1{
for j from 1 to n-1{
if ( absolute_value(deret[j+1]-deret[j]) == i){
flag = true;
break;
}
else flag=false;
}
}
if flag==true then “jolly”
else “not jolly”

Opsi kedua kira-kira seperti ini:

Array deret;
set diff_container;
bool flag = true;
for i from 1 to n-1{
temp = absolute_value(deret[j+1]-deret[j]);
diff_container.add(temp)
}

for i from 1 to n-1{
if (!diff_container.contains(i)) flag=false;
}

if flag==true then “jolly”
else “not jolly”

Mana yang lebih efisien? Yang pertama membutuhkan big-O kuadratik, sedang yang kedua big-O linear? So? Yang kedua donk. Tapi tunggu dulu, bagaimana cara tahunya?Kita kan juga harus tahu bagaimana tipe data set dan array melakukan pencarian?

So?

Diuji lewat running timenya aja, tapi itu tugas peserta kuliah, bukan saya. Saya kan cuman iseng2 saja nulis ini, Btw ini bukan cuman hasil pemikiran saya lho…😀

Ada cara lain?  Atau pseudocode yang saya ajukan salah?

About dnial

You don't see anything You don't hear anything You don't know anything Move along and pretend nothing happen

Posted on 20 September, 2007, in IT, programming. Bookmark the permalink. 5 Komentar.

  1. Soal kayak begini cuma punya kemungkinan yang big-O nya adalah 1 jika kita disuruh mencari siapa yang ngasih tugas😛

  2. @galih
    Bukan…
    btw pseudocodenya ada yg salah lho….

    @mansup
    Hehehe….

  3. calonorangtenarsedunia

    *pusing*

  4. Memang bukan konsumsi orang non-IT😀

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: