Merhabalar Yakın Zaman İçerisinde Project Euler Problemlerini Çözmeye Başladım
Şu an 14. problemdeyim kodu yazdım ama yavaş olduğu için internetten optimize edilmiş haline baktım ve kafama takılan ama anlamlandıramadığım bir bölüm oldu
import time
past = dict()
def collatz(n, past):
adim = 1
sayi = n
while n != 1:
if n in past: # Eğer n daha önce hesaplandıysa, adım sayısını geri getir
adim += past[n] - 1
break
if n % 2 == 0:
n //= 2 # Tam sayı bölmesi yapıyoruz
else:
n = n * 3 + 1
adim += 1
past[sayi] = adim # Bu sayıyı geçmişe kaydediyoruz
return adim
toplength = 0
number = 0
b = time.time()
for i in range(1, 1000001):
sayi = collatz(i, past)
if sayi > toplength:
toplength = sayi
number = i
s = time.time()
print(s-b)
print(number)
print(toplength)
kod böyle anlayamadığım kısım ise burada eğer bu sayı önceden denenmiş ise yani n in past true dönerse işlemler yapılmadan bir tasarruf sağlanıyor ama kafama takılan şey şu bu fonksiyona 1’den 1 milyona kadar sayılar veriliyor yani hep farklı (1,2,3,4,5 vs.) yani kaydettik diyelim ama bu sayılar her zaman farklı geldiği için hiç bir zaman n in past çalışmayacak ama çalışıyor bunu anlayamadım galiba bir yeri kaçıyorum. Beni aydınlatırsanız çok sevinirim.
Yapılan işlemi biraz açtığımızda aslında dizi içindeki ardışık sayıların hepsinin tek tek 1’e düşürülmesinin zaman kaybına yol açtığı anlaşılıyor. Bazı sayıları, dict’e eklenmiş herhangi bir sayıya kadar düşürmek bu zaman kaybının önlenmesini sağlıyor.
Yani iterasyonda sırası gelen bir i sayısını, dict’e eklenmiş herhangi bir j sayısına düşürene kadar x adım izleriz, sonra da j sayısı için gereken adım sayısını x’e ekleyerek, sayının 1’e eşitlenmesi için gereken adım sayısını buluruz.
n = 2 için 1 adımda n, 1’e indirilir.
=> n / 2 = 2 / 2 = 1
n = 3 için 7 adımda n, 1’e indirilir.
=> 3n + 1 = 3 * 3 + 1 = 10
=> n / 2 = 10 / 2 = 5
=> 3n + 1 = 3 * 5 + 1 = 16
=> n / 2 = 16 / 2 = 8
=> n / 2 = 8 / 2 = 4
=> n / 2 = 4 / 2 = 2
=> n / 2 = 2 / 2 = 1
n = 4 için 2 adımda n, 1’e indirilir.
=> n / 2 = 4 / 2 = 2
=> n / 2 = 2 / 2 = 1
n = 5 için 5 adımda n, 1’e indirilir.
=> 3n + 1 = 3 * 5 + 1 = 16
=> n / 2 = 16 / 2 = 8
=> n / 2 = 8 / 2 = 4
=> n / 2 = 4 / 2 = 2
=> n / 2 = 2 / 2 = 1
n == 3’ün 7. adımı, n == 2’nin 1. adımıyla aynıdır. 3’ü 1 yapmak için toplamda 7 adım gerekir.
n == 4 için, 4’ü 1 yapmak için toplamda 2 adım gerekir.
n == 5’in 4. adımından itibaren olan işlemler ile n == 4’ün işlemleri aynıdır. O halde 5 için toplamda 4 işlem yapabiliriz. İlk 3 işlem n’in değerini 4’e kadar düşürür. 4 zaten bir önceki iterasyonda dict nesnesine eklenmişti. O halde 3. adımdan sonra hesaplama yapmaya gerek yok.
n = 6 için 8 adımda n, 1’e indirilir.
=> n / 2 = 6 / 2 = 3
=> 3n + 1 = 3 * 3 + 1 = 10
=> n / 2 = 10 / 2 = 5
=> 3n + 1 = 3 * 5 + 1 = 16
=> n / 2 = 16 / 2 = 8
=> n / 2 = 8 / 2 = 4
=> n / 2 = 4 / 2 = 2
=> n / 2 = 2 / 2 = 1
Ancak n == 6 için olan hesaplamalara bakalım. 1. satırdaki işlem ile 6’yı 3’e düşürdük. 3 zaten dict’e eklenmişti. O halde 6’yı 1’e düşürmek için 2 işlem yeterlidir.
n = 7 için 16 adımda n, 1’e indirilir.
=> 3n + 1 = 7 * 3 + 1 = 22
=> n / 2 = 22 / 2 = 11
=> 3n + 1 = 11 * 3 + 1 = 34
=> n / 2 = 34 / 2 = 17
=> 3n + 1 = 17 * 3 + 1 = 52
=> n / 2 = 52 / 2 = 26
=> n / 2 = 26 / 2 = 13
=> 3n + 1 = 13 * 3 + 1 = 40
=> n / 2 = 40 / 2 = 20
=> n / 2 = 20 / 2 = 10
=> n / 2 = 10 / 2 = 5
=> 3n + 1 = 3 * 5 + 1 = 16
=> n / 2 = 16 / 2 = 8
=> n / 2 = 8 / 2 = 4
=> n / 2 = 4 / 2 = 2
=> n / 2 = 2 / 2 = 1
Ancak burada da 11. adımda 7 sayısı 5’e düşüyor. 5 sayısını daha önce eklediğimiz için, toplamda 12 adımda 7’yi 1’e indirebiliriz…
Umarım bu anlattıklarım yeterince açıklayıcı olmuştur.
Özür Diliyorum İlk Önce Ben o if n in past ifadesinin döngü içinde olduğunu kaçırmışım bende sandım n gelince bir defa kontrol ediliyor mesela n 12 geldi 12 hesaplanmışmı hayır o zaman hepsini hesapla gibi bir şey olduğunu sandım nasıl olduysa dediğim gibi n in past ifadesinin döngü içinde olduğu gözümden kaçmış anladım çok sağolun