100 - The 3n + 1 problem

Kali ini saya akan membahas soal UVA yang berjudul "The 3n + 1", untuk soal selengkapnya bisa dilihat di sini. Ada sebuah istilah "loop cycle" yang didefinisikan sebagai berikut :

input n
print n
selama n != 1
    jika n ganjil maka n = 3 * n + 1
    jika n ganjil maka n = n / 2
    print n

Jika program tersebut dieksekusi, untuk n = 5, maka akan tercetak angka 5, 16, 8, 4, 2, 1. Artinya untuk n = 5 terdapat 6 iterasi, ya kan? Nah, dalam soal diatas, kita diminta untuk mendapatkan nilai iterasi maksimal dari rentang suatu bilangan, yah let's say bilangannya adalah i dan j. Nah bagaimana cara agan untuk mendapatkannya? Sebenarnya ada banyak pendekatan sih. Mungkin bisa kita mulai dengan algo primitif seperti di bawah ini untuk mendapatkan jumlah "loop cycle" dari masing-masing bilangan :

while (temp > 1)
{
    if (temp % 2 != 0)
        temp = 3 * temp + 1;
    else
        temp = temp >> 1;
    c++;
}

Namun, ada sesuatu yang bisa kita mainkan di sini. Apa yah? Ya, lihat di bagian kondisional ketika temp ganjil. Ganjil x ganjil + 1 jadi bilangan apa hayo? Yup, betul, jadi genap. Terus ngapain bos? Kita bisa rangkap 2 statemen sekaligus dalam sekali loop ketika nilai temp ganjil, masuk? Jadi syntaksnya akan jadi seperti ini,

while (temp > 1)
{
    if (temp & 1)
    {
        temp = 3 * temp + 1;
        temp = temp >> 1;
        c+=2;
    }
    else
    {
        temp = temp >> 1;
        c++;
    }
}

perintah di atas sudah dimodifikasi dengan mengganti operator aritmatika (+,-,x,/) dengan operator bitwise, karena operator bitwise ini memiliki waktu eksekusi yang lebih cepat dari operator aritmatik biasa, temp = temp >> 1, artinya temp dibagi 2, karena bit paling kiri dibuang sebanyak satu bit, sedangkan untuk memeriksa bilangannya ganjil atau genap cukup dengan operator and (&), maksudnya jika bilangan ganjil (bit paling kiri bernilai 1 dalam representasi biner) di "and" kan dengan 1 pasti hasilnya satu kan? Makanya ini bisa digunakan untuk mendeteksi sebuah bilangan ganjil atau genap.

Yup, untuk masalah cycle loop beres lah. Dalam soal tersebut, kita diminta untuk menerima inputan selama file input masih ada, apa maksudnya gan? Kita diminta untuk menerima inputan selama kondisi EOF (end of file -> kondisi dimana scanf bernilai false) belum ditemui. Jangan lupa, bahwa program ini juga menerima input terbalik, artinya 1 10000 dengan 10000 1 dianggap sama. Oleh karena itu harus ada pengecekan setelah input. Eits, ada yang lupa, kita kan diminta untuk mendapatkan nilai terbesar dari loop cycle, ya kan? maka dari itu, setelah kita dapatkan nilai loop cycle dari setiap bilangan dalam rentang, selalu periksa loop cycle yang didapat sekarang dengan loop cycle yang didapat sebelumnya, lebih besar atau lebih kecil. So, panjang lebar ngomong dari atas ke bawah ternyata cuma untuk kodingan sependek ini, ladies and gentleman, i give you, 3n + 1 solution, here it is

#include "stdio.h"
int main()
{
    long long int a, b, x, y, i, maks, c, temp;
    while (scanf("%lld %lld", &a, &b) != EOF)
    {
        maks = 0;
        if (a < b)
        {
            x = a;
            y = b;
        }
        else
        {
            x = b;
            y = a;
        }
        for (i = x; i <= y; i++)
        {
            temp = i;
            c = 1;
            while (temp > 1)
            {
                if (temp & 1)
                {
                    temp = 3 * temp + 1;
                    temp = temp >> 1;
                    c+=2;
                }
                else
                {
                    temp = temp >> 1;
                    c++;
                }
            }
            if (c > maks)
                maks = c;
        }
        printf("%lld %lld %lld\n", a, b, maks);
    }
}

Nah, sampai kita pada akhir post, semoga bermanfaat, terus belajar, dan mohon maaf jika ane berbuat salah. Salam Coding...:)