Catatan si Jay

September 16, 2010

Algoritma Pembagian

Filed under: Matematika, Teori Bilangan — Hendra Jaya @ 10:05 am

Teorema 1 : Untuk sembarang bilangan bulat a dan d, dimana d\neq 0. Pasti ada bilangan bulat q dan r yang memenuhi a=qd+r dimana 0\leq r<|d|
Secara matematis : Untuk a,d\in\mathbb{Z}, dimana d\neq 0. Pasti ada q,r\in\mathbb{Z} yang memenuhi a=qd+r dimana 0\leq r<\mid d\mid

Selanjutnya :

  • a disebut dividend (bilangan yang dibagi)
  • d disebut divisor (bilangan pembagi/faktor)
  • q disebut quotient (hasil bagi)
  • r disebut remainder (sisa bagi)

Teorema 2 : d dinyatakan habis membagi a jika dan hanya jika r=0. Sebaliknya, d dinyatakan tidak habis membagi a jika dan hanya jika r\neq 0
Secara matematis : d\mid a\Leftrightarrow r=0. Sebaliknya, d\nmid a\Leftrightarrow r\neq 0

Contoh 1 :

\begin{array}{rlrl}2&\mid&6&\text{Baca : 2 habis membagi 6}\\\\-9&\mid&36&\text{Baca : -9 habis membagi 36}\\\\25&\mid&-100&\text{Baca : 25 habis membagi -100}\\\\3&\mid&21&\text{Baca : 3 habis membagi 21}\\\\197&\mid&0&\text{Baca : 197 habis membagi 0}\\\\-11&\mid&-33&\text{Baca : -11 habis membagi -33}\end{array}

Contoh 2 :

\begin{array}{rlrl}3&\nmid&14&\text{Baca : 3 tidak habis membagi 14}\\\\8&\nmid&-53&\text{Baca : 8 tidak habis membagi -53}\\\\-9&\nmid&37&\text{Baca : -9 tidak habis membagi 37}\\\\-9&\nmid&-30&\text{Baca : -9 tidak habis membagi -30}\\\\5&\nmid&17&\text{Baca : 5 tidak habis membagi 17}\\\\13&\nmid&25&\text{Baca : 13 tidak habis membagi 25}\\\\22&\nmid&20&\text{Baca : 22 tidak habis membagi 20}\end{array}

Teorema 3 :  Untuk bilangan bulat a, b, dan c. Jika a habis membagi b dan b habis membagi c, maka a habis membagi c
Secara matematis : Untuk a,b,c\in\mathbb{Z}. Jika a\mid b dan b\mid c maka a\mid c

Teorema 4 : Untuk bilangan bulat a, b, m dan n. Jika c habis membagi a dan c habis membagi b, maka c habis membagi (ma+nb)
Secara matematis : Untuk a,b,m,n\in\mathbb{Z}. Jika c\mid a dan c\mid b maka c\mid (ma+nb)

Dalam algoritma pembagian a=qd+r, perhatikan bahwa sisa bagi/remainder (r) BUKAN hal yang sama dengan fungsi mod(a,d) pada ilmu komputasi. Memang ada hubungannya, tetapi kedua hal ini adalah hal yang berbeda. Serupa dengan algoritma pembagian, d dikatakan habis membagi a jika dan hanya jika mod(a,d)=0.

Contoh 1 (lagi) :

\begin{array}{rlrlrll}6&=&3&.&2&+&0\\\\36&=&-4&.&-9&+&0\\\\-100&=&-4&.&25&+&0\\\\21&=&7&.&3&+&0\\\\ 0 &=&0&.&197&+&0\\\\-33&=&3&.&-11&+&0\end{array}

Contoh 2 (lagi) :

\begin{array}{rlrlrll}14&=&4&.&3&+&2\\\\-53&=&-7&.&8&+&3\\\\37&=&-4&.&-9&+&1\\\\-30&=&-4&.&-9&+&6\\\\17&=&3&.&5&+&2\\\\25&=&1&.&13&+&12\\\\20&=&0&.&22&+&20\end{array}

Untuk selanjutnya, kita definisikan istilah faktor (divisor) dari bilangan bulat a adalah bilangan bulat d yang habis membagi a.
Secara matematis : Faktor/divisor dari a adalah d yang memenuhi d\mid a, dimana a,d\in\mathbb{Z}.

Contoh 3 :

  • Faktor-faktor (divisors) dari 24 : \pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 8,\pm 12,\pm 24
  • Faktor-faktor (divisors) dari 84 : \pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 7,\pm 12,\pm 14,\pm 21,\pm 28,\pm 42,\pm 84

Cobol Programmer

Obat Ngantuk

  1. Bintang Dengan hanya mempertimbangkan faktor-faktor (divisors) positif, maka faktor dari 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24. Totalnya ada 8 faktor positif untuk 24. Dengan aturan yang sama, faktor-faktor positif dari 84 adalah 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84 dan banyaknya ada 12 buah. Ternyata, sebagian besar bilangan memiliki faktor positif dalam jumlah genap. Hanya ada segelintir bilangan yang memiliki faktor positif dalam jumlah ganjil. Cari tahu bilangan jenis apa yang memiliki faktor positif dalam jumlah ganjil dan jelaskan mengapa bisa begitu. Pembahasan ada di sini.
  2. BintangBintang Rancanglah suatu fungsi – sebut saja FakPos(n) – yang mengembalikan banyaknya faktor positif dari suatu bilangan bulat positif n. Sebagai contoh, FakPos(24) = 8 dan FakPos(84) = 12. Untuk mempermudah proses pemfaktoran, akan disediakan test case dalam format :
    <number> <pi>^<ei> <pj>^<ej> <pk>^<ek>…<pn>^<en>

    Contoh input :

    24 2^3 3^1
    84 2^2 3^1 7^1
    337500 2^2 3^3 5^5
    384813 3^2 11^1 13^2 23^1  

    Contoh output :
    8
    12
    72
    36

    Karakteristik input :
    1< \text{number}<10^{13}\text{, number}\in\mathbb{Z}
    p_i<p_j<p_k<...<p_n\text{ dimana }p\in\text{Bilangan Prima}
    \text{number}=p_i^{e_i}p_j^{e_j}p_k^{e_k}...p_n^{e_n}
    Setiap baris berisi satu test case.
    Jumlah test case = 100

    Time Limit
    2 detik

    Test Case(s)
    Ambil di sini.

    Pembahasan
    Problem dibahas di sini.

6 Komentar »

  1. hoaaammmm….

    Komentar oleh Loreng — September 17, 2010 @ 7:36 am

  2. hooaaammm

    Komentar oleh Loreng — September 17, 2010 @ 7:39 am

  3. Hoammm,sehr langweilig seiner Artikel ist

    Komentar oleh Corokeren — September 18, 2010 @ 9:21 am

  4. coba kujawab ya obat ngantuknya

    obat ngantuk nomer satu:
    bilangan yang merupakan kuadrat dari suatu bilangan prima, faktor positifnya ganjil.
    Misal :
    4 = 1,2,4
    9 = 1,3,9
    25 = 1,5,25

    kemudian, gimana dgn bilangan yg jumlah faktor positif = 5,7,9, dst ?
    misal faktor positif n = 1, 2, 3, 5, n
    maka n = 30. tapi 2 * 3 = 6, 3 * 5 = 15, dan 2 * 5 = 10 juga faktor positif yg menjadikan jumlah = 8.
    Dengan demikian jika melibatkan lebih dari satu faktor prima, pasti jumlah faktor positif = genap karena harus melibatkan kombinasi dari faktor2 antara 1 dan n. Jika jumlah faktor positif antara 1 dan n ganjil, kombinasi yg ditambahkan ganjil, jika genap kombinasi yg ditambahkan genap sehingga hasilnya pasti genap.

    faktor prima bisa berulang, misalnya 12 yang mempunyai faktor 2,2,3. Dimana setelah ditambah dengan kombinasi2nya yaitu 2*2 = 4, 2 * 3 =6, faktor2 positifnya adalah 1,2,3,4,6,12 yg jumlahnya genap.

    tapi jika 2^4 = 16, faktor positifnya = 1,2,4,8,16 = 5 = ganjil
    sedangkan 2^3 menghasilkan jumlah faktor positif genap

    jadi n^m dengan m genap menghasilkan jumlah faktor positif ganjil karena faktor positifnya selain 1 dan n juga ditambah sebanyak (m-1).
    n1^m1 . n2^m2 juga menghasilkan jumlah faktor positif ganjil karena jumlah kombinasi perkalian dari faktor2 primanya juga pasti ganjil.

    maka kesimpulannya bilangan yang memiliki jumlah faktor positif ganjil adalah bilangan n1^m1 . n2^m2 …. dengan n adalah bilangan prima dan m adalah genap.

    ada tipe bilangan lain gak?

    nomer dua :

    faktor positif kan sama dengan kombinasi dari faktor2 prima.
    Misal, 24 faktor2 positifnya : 1,2,3,4,6,8,12,24
    2 = 2
    4 = 2 * 2
    8 = 2 * 2 * 2
    6 = 2 * 3
    12 = 2 * 2 * 3
    24 = 2 * 2 * 2 * 3
    3 = 3

    aku bikin suatu array untuk menampung faktor2 prima-nya, kemudian tinggal generate kombinasinya
    Misal untuk contoh nomer 3 (337500):

    public class iseng {
    static int[] data = {2,2,3,3,3,5,5,5,5,5};//2^2 * 3^3 * 5^5 = 337500
    static int jumlah = 0;

    public static void rec(int index, long kali){
    jumlah++;
    System.out.println(kali);
    for (int i = index; i < data.length; i++) {
    if (i == index || data[i] != data[i-1])
    rec(i+1,kali * data[i]);
    }
    }
    public static void main(String[] arggs) {
    rec(0,1);
    System.out.println("hasilnya = "+jumlah);
    }
    }

    kurang efisien sih, bisa dioptimize lagi kl mau. tp 100 test case pasti hanya butuh beberapa mili second.

    Komentar oleh Peter Aloysius — September 19, 2010 @ 4:23 am

    • Makasih buat jawabannya Pet.
      Untuk obat ngantuk yang pertama : Benar. Secara singkat, bilangan yang memiliki faktor positif dalam jumlah ganjil adalah bilangan kuadrat.
      Untuk obat ngantuk yang kedua : Benar. Di dalam post berikutnya akan dibahas pendekatan lain yang cukup “ajaib”🙂

      Komentar oleh Hendra Jaya — September 20, 2010 @ 5:37 am


RSS feed for comments on this post. TrackBack URI

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

Buat situs web atau blog gratis di WordPress.com.

%d blogger menyukai ini: