Soru
n-> n/2 (Eğer n, çift ise)
n-> 3n+1 (Eğer n, tek ise)
13 sayısını bu kurala uyguladığımızda
13->40->20->10->5->16->8->4->2->1
Dizilimini elde ediliyor.
1 ile sonuçlanan bu dizilime Collatz Dizilimi diyoruz.
Bir milyonun altındaki hangi sayı, en uzun dizilimi vermektedir?
Çözüm
Bu soru için direkt kodlamayı vermeyeceğim. Esasında basit bir soru, kodlamadan ziyade çözüm yöntemini bulmanın önemli olduğunu düşünüyorum.
Bunu deneme yanılma ile bulmaya çalıştığınızda epey bir işlem gücü isteyecektir.
Burada yakalamamız gereken yaklaşım, bazı sayılar için daha önceden yapılan dizilimi tekrar yaptığımız.
Yani 1'den 10'a kadar olan dizilimi bulduk diyelim. 13 sayısının dizilimine baktığımızda görüyoruz ki:13->40->20->10->5->16->8->4->2->1
Zaten 10 için yaptığımız dizilimi barındırıyor. Öyleyse daha fazla ileri gitmeye gerek yok. Bunların her birini kaydedip, denetimini yaptığımızda işlem gücünden hayli kazanç elde etmiş oluyoruz.
Cevap : 837799 sayısı 525 uzunluğunda dizilim oluşturur.
Hiç yorum yok:
Yorum Gönder