Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
2 beğenilme 0 beğenilmeme
2.9k kez görüntülendi
Bir palindrom sayı, normal yazılışı ve tersten yazılışı aynı olan sayıdır. $2$ basamaklı iki sayının çarpımıyla elde edilebilecek en büyük palindrom sayı $9009=91\times 99$ dur.

$\underline{Soru:}$  $3$ basamaklı iki sayının çarpımıyla elde edilebilecek en büyük palindrom sayı nedir?
Veri Bilimi kategorisinde (470 puan) tarafından  | 2.9k kez görüntülendi
Sadece program ile mi cozum istiyorsun, matematiksel de olur mu?
matematiksel de olur hocam. isterseniz program ile de olur.

3 Cevaplar

1 beğenilme 0 beğenilmeme

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

 

(3.7k puan) tarafından 
tarafından düzenlendi
Toplam 2203 kez döngü  çalıştı. Bu algoritmanın en kötü seneryosu bu özelliğe sahip olan bir sayının olmadığı durum. Bu durumda algoritma olası bütün ikilileri taramış oluyor. Ancak diğerleri sabit zamanlı ve bu zaman, yukardaki algoritmanın en kötü senaryosuyla eş.
sayiBul(palindromMu, 9999, 1000)
>>> Aranan özellikteki en büyük sayı 99000099
>>> 2500 deneme yapıldı.
>>> [9999,9901]

 

Yukarıdaki programın sonuna, aranılan aralıkta istenen tipte ikili bulunamadığında bunu belirten bir çıkış da konulmalı.

ekledim.
Hocam başka açıdan bakmaya çalışıyorum da. Kabaca matematiksel olarak elde edilecek sayının 6 basamaklı olması gerektiğini gözlemyelebiliyoruz ya hani. Elde edeceğimiz sayı ABCCBA şeklinde olacak diyebiliyoruz bu yorumla. Çözümlesek diye düşündüm 100001*A + 10010*B + 1100*C şeklinde oluyor ve bu sayı 11 ile tam bölünebiliyor. 11 asal olduğu için çarpılan iki sayıdan birinin kesinlikle 11'e bölünmesi gerektiğini söyleyebiliyoruz. Sayılardan birini 990'dan geriye doğru 11'er azalacak şekilde ilerletebiliriz sanırım. Diğer sayıyı da 999'dan geriye doğru değer aldırabiliriz. Sizin çözümünüzle de birleştirilebilir mi diye düşündüm bir an.
örneğin benım cevabımda i değerini 99 dan başlatıp,i değerini 11 arttırırsak sizin kastettiğiniz olay olur,program daha kısa sürede çalışır,ama çift taraflı yaparsak sonuç bulamayız.
0 beğenilme 0 beğenilmeme

Mathematica ile cozum

 

list = Times @@@ Tuples[Range[900, 999], 2];
Max[Pick[list, PalindromeQ /@ list, True]]

906609

 

Eger carpanlari da bulmak istiyorsak, o zaman su isi gorur.

 

list = Tuples[Range[900, 999], 2];
list2 = Transpose[{list, Times @@@ list}];
MaximalBy[Pick[list2, PalindromeQ /@ list2[[All, 2]], True], Last]

{{{913, 993}, 906609}, {{993, 913}, 906609}}

 

PalindromeQ kullanmadan yapmak icin.

list = Times @@@ Tuples[Range[900, 999], 2];
sel = (#1 - Reverse@#2) & @@@ (Partition[#, 3] & /@ IntegerDigits /@ list);
Pick[list, sel, {0, 0, 0}]//Max
906609

 

(2.9k puan) tarafından 
tarafından düzenlendi
Burada anladığım kadarıyla algoritma, üç basamaklı sayıların çarpımıyla elde edilen sayıların içindeki en büyük palindromik sayıyı bul.

 

Ama bu işin nasıl yapıldığına dair bir şey söylemiyor bu algoritma, palindromik sayıları tanıyan kütüphaneye soruyor yalnızca. Aranılan şey bu mu emin değilim.
Soru acik degil malesef. Ama algoritma soruluyorsa cok zor degil. En buyugu istendigi icin 900 ile 999  arasindaki sayilari carpimina bakmak mantikli. Bu carpimlar 6 basamakli oldugundan, ilk 3 ve son 3 digitlerin tersinin farkina bakilir, egr fark sifir ise carpim palindromdur deriz.
veya çarpım sonucunun elemanları diziye aktarılarak dizi elemanları kontrol edilir.bu bi tık daha uzun olur.

ee şey,soru sahibinin denemeleri ? :P

Sorun sahibinin denemesi bu şekilde :)

#3 basamakli 900'den buyuk esit iki doğal sayinin carpimi 6 basamaklidir
x = []
for i in range(900,999) :
    for j in range(900,999) :
        sayi = str(i * j)
        if sayi[0] == sayi[-1] and sayi[1] == sayi[-2] and sayi[2] == sayi[-3] :
            x.append(sayi)

print(max(x))

 

Bu yanıtların hepsinde sayının 900'den büyük sayıların çarpımıyla bulunacağı varsayımı var. Ya 800'lerden bir sayı veriyor olsaydı, hata ayıklama yok bu kodlarda.

$400*400=160000$  hala 6 basamakli, yani Range[400,999] yapilabilir. Daha kucuk sayilar icin If kullanmak gerekli ki carpimlari 4 ve 5 basamakli olan 3 basamakli sayilari  bulabilelim. Cok zor degil ama.

çok haklısınız Safak Ozden hocam.
doğru,her ihtimale karşı program min-max 6 basamaklı sayılar için taratmalı.
Ben de breath first depth-first algoritması ile bir yanıt yazdım.
Aslinda iki duruma bakmak yeterli. Carpimin sonucu 6 basamakli olanlar veya, 4 veya 5 basamakli olanlar. Cunku  carpim sonucu 4 ve 5 basamakli  ise her halukarda ilk 2 ve son 2 basamaklari karsilastiriyoruz. 5 basamakli ayilarda ortadaki sayinin  onemi yok palindrom olmasi icin.

 

Aradigimiz aralik o kadar kucuk ki, [100,999] arasindaki sayilarin hepsine (810.000 sayi var) bakmak bile 4 saniye suruyor. Verimli bir kod yazmaya gerek yok bence bu problem icin..

Ama bu sorudaki palindrom olma özelliği ya da aralık değiştirildiğinde yazdığımız programın yine kullanılabilir olmasını istemek bence makul. En azından benim refleksim o yönde. Yoksa elbette

palindrom = []

for i in range(100,1000):
    for j in range(100,1000):
        if str(i*j)== str(i*j)[::-1]:
            palindrom.append(i*j)
print(max(palindrom))

        

 

En son yazdığım exhaustive sıralama mantıklı kodu dört basamaklı sayılar için çalışıtırınca 99000099 sayısını bulması 62 küsür saniye sürüyor. Depth first breath first tekniğiyle yazılan programda bu süre 0.004983186721801758 saniyeye düşüyor.
Gayet haklısınız hocam,bu yönde bir istek olmadığı için,sadece 3 basamaklı sayıların çarpımı ile bulunan ,sonucu gösteren basit anlaşılabilir bir algoritma yazdım.tabiki  4 5 veya  6 haneli sayıların çarpımlarını'nın koşulu sağlayıp sağlamadığını aynı anda gösteren bir algoritmada kurabiliriz.

 

gerek var mı  ? :D
0 beğenilme 0 beğenilmeme
#include <stdio.h>

main()
{
	
	int A;
	
	for(int i=100;i<1000;i++)
	{
		for(int j=100;j<1000;j++)
		
		{A = i*j;
		int x = A / 1000;//6 basamaklık sayının ilk üç hanesi
		int y = A % 1000;//6 basamaklık sayının son üç hanesi
		//c z k değişkenleri,6 basamaklı sayının son hanesinin basamak değerleridir
		int c = y/100;//yüzler
		int z = (y /10) % 10;//onlar
		int k = y % 100;//birler basamağı		
		int t = 100*k+10*z+c;//son hanenin tersi alınmış		
		if( x-t == 0)//ilk ve son hanenin tersinin farkı, 0 olduğu durumda kontrolümüz.		
		{
		printf("çarpanlar 1.sayi = %d 2.sayi = %d \n ",i,j);
		printf("palindrom sayısı %d \n",A);
		
	}
		}
	}		
}

 

buyrun C kodu,program çalıştığında çift taraflı değer okutulduğu için,aynı rakamlar 2 kez gözükmüş olabilir :),hangi çarpanların sağladığınıda ekledim.
(159 puan) tarafından 
tarafından düzenlendi
20,260 soru
21,785 cevap
73,460 yorum
2,347,427 kullanıcı