Masalah 3n + 1
Deskripsi
Dalam masalah 3n+1, Anda diminta menganalisis sifat-sifat statu algoritma untuk suatu input yang diberikan.
Perhatikan algoritma berikut ini:
- input n
- print n
- if n = 1 then STOP
- if n ganjil then n = 3n+1
- else n = n/2
- GOTO 2
Diberikan input 22, barisan bilangan-bilangan berikut akan dicetak:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Menurut dugaan algoritma di atas akan berhenti ketika angka 1 dicetak untuk sebarang bilangan bulat (integer) yang diinputkan. Meskipun algoritma di atas cukup sederhana, tidak diketahui apakah dugaan ini benar. Telah diverifikasi bahwa untuk semua bilangan bulat n sehingga 0<n<1,000,000 dugaan tersebut benar adanya. Jika diberikan input n, adalah mungkin untuk menentukan jumlah angka tercetak (termasuk 1). Jumlah angka tercetak ini disebut panjang siklus dari n. Dalam contoh di atas, panjang siklus dari 22 adalah 16 . Dalam tugas ini, untuk setiap dua bilangan i dan j, Anda diminta untuk menentukan panjang siklus maksimum dari semua bilangan di antara i dan j.
Masukan
Input akan terdiri dari pasangan bilangan bulat (integer) i dan j. Semua bilangan bulat akan kurang dari 1.000.000 dan lebih besar dari 0. Anda harus memproses semua pasangan bilangan bulat dan untuk menentukan panjang siklus maksimum dari semua bilangan bulat antara dan termasuk i dan j.
Keluaran
Untuk setiap pasangan integer masukan i dan j, Anda harus mencetak keluaran i, j, dan panjang siklus maksimum untuk integer di antara dan termasuk i dan j. Ketiga angka harus dipisahkan oleh satu spasi dengan kesemua tiga angka tersebut dalam satu baris. Bilangan bulat i dan j harus muncul dalam keluaran dalam urutan yang sama di mana mereka muncul dalam masukan dan harus diikuti dengan panjang siklus maksimum (pada baris yang sama).
Contoh Masukan Contoh Keluaran
1 10 1 10 20
100 200 100 200 125
201 210 201 210 89
900 1000 900 1000 174
Berikut Code nya dengan menggunakan Java.
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
Q100 q100 = new Q100();
final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = reader.readLine()) != null) {
String REGEX_WHITESPACE = "\s+";
String cleanLine = line.trim().replaceAll(REGEX_WHITESPACE, " ");
String[] tokens = cleanLine.split(REGEX_WHITESPACE);
if (tokens.length == 2) {
long a = new Long(tokens[0]).longValue();
long b = new Long(tokens[1]).longValue();
System.out.println(cleanLine + " " + q100.countMaxIterationBetweenTwoNumbers(a, b));
}
}
}
public static class Q100 {
private final long MAX_CACHE_SIZE = 65536;
private final long[] cache = new long[(int) MAX_CACHE_SIZE];
public long countIteration(long originalNumber) {
long n = originalNumber;
long count = 1;
while (n > 1) {
if (((n - 1) >> 1) == (n >> 1)) {
long newNumber = (3 * n) + 1;
if (newNumber < n) {
throw new RuntimeException("overflow :" + originalNumber);
} else {
n = newNumber;
}
} else {
n = n >> 1;
}
if (n < MAX_CACHE_SIZE && cache[(int) n] != 0) {
return count + cache[(int) n];
}
count++;
}
return count;
}
public long countMaxIterationBetweenTwoNumbers(long a, long b) {
final long big;
final long small;
if (a > b) {
big = a;
small = b;
} else {
small = a;
big = b;
}
long winner = -1;
for (long i = small; i <= big; i++) {
long count = countIteration(i);
if (i < MAX_CACHE_SIZE) {
cache[(int) i] = count;
}
if (count > winner) {
winner = count;
}
}
return winner;
}
}
}Berikut ini Hasilnya :
