Consider all integer combinations of a
b for 2 <= a <= 5 and 2 <= b <= 5:
2
2=4, 2
3=8, 2
4=16, 2
5=32
3
2=9, 3
3=27, 3
4=81, 3
5=243
4
2=16, 4
3=64, 4
4=256, 4
5=1024
5
2=25, 5
3=125, 5
4=625, 5
5=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by a
b for 2 <= a <= 100 and 2 <= b <= 100?
Sumber:
http://projecteuler.net/index.php?section=problems&id=29Secara kasar, kita tahu bahawa kita akan menggunakan proses loop untuk menyelesaikan masalah ini. Jarak antara nombor asas dan nombor kuasa di beri antara 2 - 5 (termasuk). Ini bermaksud, nombor kuasa tersebut akan meningkat sebanyak 3 kali dari nombor 2 hingga ke nombor 5. Aplikasi mudah dalam pengaturcaraan bagi soalan sebegini; kita akan menyimpan kesemua nombor tersebut ke dalam sebuah array dan periksa mana-mana nombor yang sama yang terdapat dalam array tersebut. Salah satu daripada algorithm yang mudah, kita boleh menggunakan nested for-loop untuk memeriksa kesemua nombor tersebut.
Sebagai contoh, ini merupakan array yang korang ada:
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]Korang hanya perlu periksa a[0] dengan setiap satu elemen yang terdapat dalam array tersebut sehingga a[9]. Kemudian, lakukan perkara yang sama pada a[1] dan seterusnya. Namun begitu, cara ini baik untuk array yang bersaiz kecil. Jika korang mempunyai array yang mengandungi 10,000 elemen, algorithm ini bukan lagi efisien!
Bagi masalah 29, aku menggunakan 2 pakej untuk menyelesaikan masalah. Pertama, aku mengimport pakej
java.util kerana aku ingin menggunakan class Array di samping aku juga mengimport pakej
java.math kerana aku ingin menguruskan nombor besar dengan menggunakan class BigInteger. Kaji kod sumber yang sudah aku tulis dan cuba fahamkan.
Apa-apa pun, aku akan membuat sedikit penerangan. Secara asasnya, aku masih menggunakan for-loop dalam algorithm aku. Namun begitu, aku cuba mengelakkan daripada menggunakan 2 for-loop apabila tiba pada tahap untuk memeriksa mana-mana elemen yang sama. Bagi menggantikan fungsi tersebut, aku menggunakan
Arrays.binarySearch() untuk mendapatkan posisi elemen terkini.
Arrays.binarySearch() akan memulangkan nilai posisi bagi elemen yang korang minta daripada sebuah array. Idea yang aku gunakan, jika posisi yang di berikan tidak sama dengan posisi sebenar, pasti terdapat duplikasi bagi elemen tersebut. Dengan menggunakan idea ini, mudah bagi aku untuk mengira; jumlah elemen yang mengandungi nilai yang sama. Akhir sekali, tolak nilai tersebut dengan jumlah keseluruhan saiz array.
Kod Sumber:import java.util.Arrays;
import java.math.BigInteger;
public class Masalah029 {
public static void main(String[] args)
throws Exception{
BigInteger base = new BigInteger("2");
BigInteger one = new BigInteger("1");
BigInteger value = new BigInteger("1");
String[] x = new String[9801];
int totalSame = 0;
int xArray = 0;
for(int i = 0; i < 99; i++){
for(int exp = 2; exp <= 100; exp++){
value = base.pow(exp);
x[xArray] = value.toString();
xArray++;
}
base = base.add(one);
}
Arrays.sort(x);
for(int i = 0; i < x.length; i++){
int check = Arrays.binarySearch(x, x[i]);
if(check != i)
totalSame++;
}
System.out.println("No of same: " + totalSame);
}
}
