Daftar

Coding Coding Coding


Programming & Web Coding, web, aplikasi, dan karier developer.

Balas
 
Alat Thread
Darkc0der Darkc0der sedang offline
20th November 2011 #1
Ceriwiser Tanggal Bergabung: Nov 2011 Post: 598 Rep Power: 16 Darkc0der mempunyai hidup yang Normal
Default Coding Coding Coding
Halo semuanya dalam thread yg saya buka ini saya akan posting soal2 tentang programming mulai dari level mudah sampai sulit. Soal2 yang saya posting akan seputar matematika dan algoritma. Thread ini saya buka bukan sebagai ajang pamer kemampuan melainkan sebagai hiburan utk mengisi waktu luang dengan berpikir dan coding.



Soal 1 [4/10]: ( Sudah terjawab oleh bobomelulu)

f(1) = 1

f(2) = 2

f(3) = 3

f(x) = f(x-1) + f(x-2) + f(x-3) untuk x>3

Berapakah nilai 4 digit terakhir dari f(1,000,000,000,000,007) ?

(tantangan dari soal ini adalah bagaimana kita menghitung nilai secara cepat).


Spoiler for pembahasan:






Soal ini membutuhkan teknik perkalian matriks, teori modular aritmatika dan cara cepat memangkatkan bilangan.



Coba perhatikan matriks berikut:



A = [1 2 3] (isinya dari f(1), f(2) dan f(3))



B = 0 0 1

1 0 1

0 1 1



Coba kalikan A dengan B maka kita akan dapatkan



[2 3 6]



kalikan lagi dengan B maka kita akan dapatkan



[3 6 11]



kalau diperhatikan setiap elemen dalam matriks tersebut akan bergeser dan elemen terakhir akan digantikan dengan nilai penjumlahan 3 elemen sebelumnya.



Nah dari situ kita bisa mengambil kesimpulan bahwa jika ingin mendapatkan nilai f(X) kita harus melakukan perkalian matriks sebanyak X-3 kali untuk mendapatkan hasil di element terakhir.

Contoh:

Mau tau nilai f(4) berarti matriks A dikalikan 1x dengan B

Mau tau nilai f(5) berarti matriks A dikalikan 2x dengan B

Mau tau nilai f(6) berarti matriks A dikalikan 3x dengan B



((A x B) x B) x B sama dengan A x (B^3)



Berarti untuk menghitung f(1,000,000,000,000,007) sama dengan A x (B^1,000,000,000,000,004)



Nah timbul lagi kesulitan bagaimana kita menghitung nilai B^1,000,000,000,000,004 dengan cepat?



Kita gunakan metode divide and conquer berikut:



ilustrasi ketika menghitung B^35:

B^35 = B^17 * B^17 * B

B^17 = B^8 * B^8 * B

B^8 = B^4 * B^4

B^4 = B^2 * B^2

B^2 = B * B



Dari situ kita lihat bahwa utk menghitung B^35 hanya membutuhkan log2(35) = 5 operasi.

Berarti untuk menghitung B^1,000,000,000,000,004 hanya membutuhkan log2(1,000,000,000,000,004) = 50 operasi.



Nah lalu karena yang diminta hanya 4 digit terakhir tiap perhitungan kita modulus 10000. Teori modular aritmetika:

(a x b) % x = ((a%x) * (b%x)) % x

(a + b) % x = ((a%x) + (b%x)) % x








Spoiler for solusi c++ saya:







PHP Code:



<span style="color: #000000">
#include

#include

#include

using namespace std;



<span style="color: #FF8000">#define REP(i,n) for(int i=0,_n=(n);i
ans = nextInteger()

freq = 1

while hasNextInteger()

temp = nextInteger()

if
ans == temp then

freq
++

else

freq--

end if



if
freq == 0 then

ans
= temp

end
if

end while



print
ans







Cara ini akan menghasilkan output dengan betul karena kondisi frekuensi > 50%, saya sudah buktikan cara ini benar dengan melakukan uji coba permutasi 10 elemen (1 1 1 1 1 1 2 3 4 5) .












Spoiler for cara bobomelulu beda dengan saya:






Karena rangenya cukup di 32-bit integer, gue perlu counter sebanyak 32 element.



Untuk tiap integer, kita cari binary representationnya. Misalkan angka 5, ... ....00000101 ada index bit 0 dan 2 yg nyala ... maka gue akan increment counter[0] dan counter[2].



Begitu seterusnya sampe setiap input habis dibaca.



Mestinya nilai frequensi terbesar bisa didapet dengan melihat counter[i] untuk tiap i dari 0 s/d 31 ... Kalo nilai counter[i] > 50jt, maka bit ini pasti juga nyala di nilai yg paling sering muncul.



Gue belum test bener, tapi ini coba coba dengan input:

{ 5, 5, 6, 7, 5, 5, 5, 9 }



0 1 0 1

0 1 0 1

0 1 1 0

0 1 1 1

0 1 0 1

0 1 0 1

0 1 0 1

1 0 0 1

-------

1 7 2 7 yg lebih dari 4 adalah bit 0 dan bit 2

0 1 0 1 => 5











Soal 3 [1/10]: ( Sudah terjawab oleh mnemonix)

Hitung digit ke-50 dibelakang koma dari 123412 / 4234



Contoh kalo yang ditanyakan digit ke-5 maka jawabannya adalah 5.

123412 / 4234 = 29.147850


Spoiler for pembahasan dari saya:






Ini soal sangat mudah, bisa di solve dengan kertas dan pulpen (kalo emang niat ). Tapi bisa juga dicodingin berdasarkan pembagian cara SD, berikut potongan code saya:


PHP Code:



<span style="color: #000000">
int a = 123412;

int b = 4234;

System.out.print((a/b)+".");

a %= b;

for(
int i=0;i<span style="color: #007700"><span style="color: #000000">
int calc(int n,int k) {

vectorp(n);

for(
int i=0;i<span style="color: #007700">


















Cara O(n lg n), cara ini efisien dilakukan jika nilai n lumayan besar (n














</div>
</div>



Cara O(n), cara ini efisien dilakukan jika nilai n besar (n

<span style="color: #000000">
int calc(int n,int k) {

int ret = 0;

for(
int i=2;i<span style="color: #007700">
REGIONALBALI REGIONALBALI sedang offline
20th November 2011 #2
Member Aktif Tanggal Bergabung: Feb 2011 Post: 239 Rep Power: 0 REGIONALBALI mempunyai banyak pengalamanREGIONALBALI mempunyai banyak pengalamanREGIONALBALI mempunyai banyak pengalamanREGIONALBALI mempunyai banyak pengalamanREGIONALBALI mempunyai banyak pengalamanREGIONALBALI mempunyai banyak pengalamanREGIONALBALI mempunyai banyak pengalaman
Default
lengkap banget penyelesainya.

klo ane sendiri selesan matrik paling menggunakn matlab(biar cepet)
kecuali ujian ndan...
Balas


Aturan Posting
Kamu tidak boleh membuat thread baru
Kamu tidak boleh membalas
Kamu tidak boleh mengirim lampiran
Kamu tidak boleh mengedit post kamu

BB code Hidup
Smilie saat ini Hidup
Kode [IMG] adalah Hidup
Kode HTML adalah Mati


Terkait
Thread Pembuat Thread Forum Balasan Postingan Terakhir
Android coding Badguy13 Programming & Web 0 20th November 2011 09:22 AM
[Ask coding] Badguy13 Programming & Web 0 20th November 2011 09:10 AM
Ask Coding JSP Badguy13 Programming & Web 0 20th November 2011 08:53 AM
[ASK] Coding VB 6 Badguy13 Programming & Web 0 20th November 2011 12:52 AM
ask coding VB6 JagoVB Programming & Web 0 20th November 2011 12:36 AM

Semua waktu adalah GMT +7. Waktu sekarang adalah 06:12 AM.