Algoritma Pembagian

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

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.
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.

Like this:

Be the first to like this post.

Komentar (6)

6 Komentar »

hoaaammmm….

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

Balas
hooaaammm

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

Balas
Hoammm,sehr langweilig seiner Artikel ist

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

Balas
- das Problem zu lösen dann
  
  Komentar oleh Hendra Jaya — September 18, 2010 @ 10:52 am
  
  Balas
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

Balas
- 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
  
  Balas