Buradaki asıl soru, palindromik sayılarla ilgili değil. Şu özellikleri taşıyan bir sayı istiyoruz:
1. Üç basamaklı iki sayının çarpımı olsun
2. Bir P özelliğini sağlasın (mesela palindromik olsun, gözü yeşil olsun vs)
Ve bu iki özelliği taşıyan en büyük sayı olsun.
Bu aslında, bir graftaki iki noktanın arasındaki en kısa yollardan birisini bulma sorusuyla neredeyse özdeş. Diğer yanıtlarda verilen algoritmalar bu açıdan bakıldığında exhaustive denilen yöntemi kullanıyor, yani olası büyün yolları oluşturuyor, daha sonra da bu yollar arasında en kısa olanı seçiyor. Bu yöntem doğru sonucu bulacaktır ama kesinlikle verimsiz olacaktır. Bunun yerine, depth first breadth first arama diye tabir edilen yöntem ile iterasyonun yapılması gerekli. Yani, $A$'dan $B$'ye giden yıllar arasındaki en kısa olan bir tanesini arıyorsak, önce $A$'da başlayan bir adımlık yollara bakmalı, bunlar arasında bir tanesi $B$'ye varıyorsa o yolu seçip çıkarıp aramamızı bitirmeliyiz. Eğer bir adımlık yollarda bulamazsak, iki adımlık yollara bakmalıyız vs. Bu sayede bulacağımız ilk sonucun en kısa yollardan birisi olacağı kesin. Burada da benzer bir yöntem uygulamalıyız.
Peki analojiyi nasıl kuracağız?
$999*999$ bulabileceğimiz en büyük sayı (sonsuz hehehe). Bu sayı $P$ özelliğini sağlıyorsa işimiz bitti, hiç işlem yapmaya bile gerek yok. Diyelim ki aradığımız sayı bu değil. Ne yapacağız? Büyün aday sayıları çarpım yapıp bulmadan öyle bir sayı üretmek istiyorum ki, eğer bu bulduğum sayı $P$ özelliğini sağlıyorsa, evet bu sayı $P$ özelliğini sağlaan en büyük sayı diyebileyim. Tabii ki sıradaki deneyeceğim sayı $999*998$ olacak. Peki bir sonraki denemeyi neyle yapacağım? Bir çıkartacağım ama hangisinden? Toplamları eşit olan iki çift sayıdan, birbirlerine yakın olanların çarğımı daha büyük olacağı için, önce $998*998$ sayısı $P$ özelliğini sağlıyor mu diye bakacağım, sonra $999*997$ sayısı $P$ özelliğini sağlıyor mu diye bakacağım. Bu şekilde bulacağım ilk sayı, üç basamaklı iki sayının çarpımı olarak elde edilen en büyük $P$ özelliğini sağlayan olacaktır.
İşin en az işlem yaparak aranılan sayıyı bulma kısmını hallettik, şimdi de bunu bilgisayara nasıl yaptıracağımız sorusunu çözmeliyiz. Dikkatli olmalıyız, öyle bir dizi oluşturmalıyız ki, dizimiz azalan olsun, böylece $P$ özelliğini sağladığını gördüğümüz ilk dizi elemanı aynı zamanda en büyük olsun. O halde, bu paragrafın başında söylediğim işin matematik kısmını hallettik lafı rafa kalktı, yine biraz işlem yapacağız.
Ağacımızın tepesin de $(999,999)$ ikilimiz var. Bundan sonraki seviyede $(999,998)$ ve $(998,999)$ var ama bunlardan bir tanesi için kontrol mekanizmamızı çalıştırmamız yeterli. Sonraki katta $(998,998)$ ve $(999,997)$ bulacağız. Peki hangisini önce deneyelim, tabii ki birincisini, iki paragraf yukarıda bunun nedenini açıklamıştır. Üç kat aşağıda neleri bulacağız? İki sayının toplamı üç azalmış olacak. O halde $(998,997)$ ve $(999,996)$ bulacağız, yine ilk önce birbirine yakın sayılardan oluşan ikiliyi çarpıp $P$ özelliği sağlanıyor mu diye bakmalıyız. Hadi birazcık daha görsel olalım:
1. adım (iterasyondaki) $Toplam = 1998$, bunu verenler:
$(999,999)$
2. adım (iterasyondaki) $Toplam = 1997$, bunu verenler:
$(999,998)$
3. adım (iterasyondaki) $Toplam = 1996$, bunu verenler:
$(998,998), (999,997)$
$\vdots$
2n-1.. adım (iterasyondaki) $Toplam = 1999-(2n-1)$, bunu verenler:
$(999-(n-1),999-n), (999-(n-2),999-(n+1)), \cdots, (999,999-(2n-1))$
def sayiBul(P, ustSinir, altSinir):
'''P, tamsayı alıp Boolean cikti veren bir fonksiyon
ustSinir/altSinir, tamsayı ikililerindeki elemanlarin üst/alt sınırı
çarpımları P özelliğini saglayan ikililerin carpımı en büyük olanını verir'''
for seviye in range(2*(ustSinir-altSinir)):
if seviye%2 == 1:
ikilim = [ustSinir-int((seviye//2)),ustSinir-int((seviye//2))-1]
else:
ikilim = [ustSinir-int(seviye/2),ustSinir-int(seviye/2)]
for adim in range(min(seviye//2,ustSinir-(seviye//2)-altSinir)+1):
if P(ikilim[0]*ikilim[1]) == True:
print('Aranan özellikteki en büyük sayı ' + str(ikilim[0]*ikilim[1]))
return ikilim
ikilim[0] += 1
ikilim[1] -= 1
print('Verilen aralıkta istenilen tipte ikili yoktur.')
Bu iterasyon biçimine üst sınır olarak $999$ altsınır olarak da $100$ girdiğimizde oluşturulan ikililerin bir kısmı şöyle gözüküyor.
Ağacımızda 0 kat indiğimizde bulduğumuz ikililer:
[999, 999]
Ağacımızda 1 kat indiğimizde bulduğumuz ikililer:
[999, 998]
Ağacımızda 2 kat indiğimizde bulduğumuz ikililer:
[998, 998]
[999, 997]
Ağacımızda 3 kat indiğimizde bulduğumuz ikililer:
[998, 997]
[999, 996]
Ağacımızda 4 kat indiğimizde bulduğumuz ikililer:
[997, 997]
[998, 996]
[999, 995]
Ağacımızda 5 kat indiğimizde bulduğumuz ikililer:
[997, 996]
[998, 995]
[999, 994]
Ağacımızda 6 kat indiğimizde bulduğumuz ikililer:
[996, 996]
[997, 995]
[998, 994]
[999, 993]
.
.
.
Ağacımızda 25 kat indiğimizde bulduğumuz ikililer:
[987, 986]
[988, 985]
[989, 984]
[990, 983]
[991, 982]
[992, 981]
[993, 980]
[994, 979]
[995, 978]
[996, 977]
[997, 976]
[998, 975]
[999, 974]
Şimdi $P$ yerine aşağıdaki palindromik mi değil mi testini yapan fonksiyonu koyup sayıBul(P,999,100) fonksiyonunu çağırırsak sonuç bulunur.
def palindromMu(n):
'''n palindrom ise True değilse False veren fonksiyon
pozitif ve negatif tamsayılar için çalışır'''
if str(abs(n)) == str(abs(n))[::-1]:
return True
else:
return False