Günlük Kodlama Problemi: Üçgen Sayılar ve Büyük Bölenler

Çözülmesi gereken başka bir sorunu olan herkese tekrar hoş geldiniz! Bugün üçgen sayılardan ve onların bölenlerinden, özellikle de büyük sayılardan bahsedeceğiz!

Doğadaki üçgen sayıların muhteşem sanatsal temsiline hayran kalabilsek de, her zamanki sorumluluk reddi beyanlarımızı da belirtelim:

1. Bu sorun harika bir web sitesi tarafından sağlanmaktadır. ProjectEuler.net abone olabileceğiniz Burada ! Çözülmesi gereken 800'den fazla matematik ve kodlama problemi ve bunlarla ilgili geniş bir tartışma arşivi var. Kelimenin tam anlamıyla kafanızı dağıtmak ve yeni bir şeyler öğrenmek için mükemmel bir araçtır! Gidip bir göz atın ve karşılaştığınız zorlukları çözmeye çalışın!

   
   

2. Ben uzman bir programcı değilim: sadece bu tür şeyler hakkında yazmaktan hoşlanan ve çekimlerini paylaşmayı seven bir adam. Bunun en uygun çözüm olmayacağından eminim, bu nedenle daha iyi bir çözümünüz varsa veya onu nasıl optimize edeceğinize dair herhangi bir fikriniz varsa paylaşmak isterseniz memnuniyetle karşılarız!

Yeterince konuşalım, bugünün sorununun neler sunabileceğine bakalım:

Üçgen sayı dizisi, doğal sayıların eklenmesiyle oluşturulur. Yani 7. üçgen sayısı 1+2+3+4+5+6+7=28 olacaktır. İlk on terim şöyle olacaktır: 1,3,6,10,15,21,28,36,45,55,…

İlk yedi üçgen sayısının çarpanlarını sıralayalım:

28'in beşten fazla böleni olan ilk üçgen sayısı olduğunu görebiliriz.

Beş yüzün üzerinde böleni olan ilk üçgen sayısının değeri nedir?

Sorun oldukça basit: 500'den fazla böleni olan ilk üçgen sayının ne olduğunu anlamamız isteniyor. Öncelikle üçgen sayının ve bölenin ne olduğuna daha iyi bakalım.

Üçgen Sayılar

Üçgen sayılar, belirli bir sayıya kadar olan tüm doğal sayıların toplamından oluşan sayıların belirli bir alt kümesidir. Bunlara üçgen denir çünkü onları her zaman üçgen şeklinde düzenleyebilirsiniz . İşte bazı örnekler:

Yukarıdaki resimde 3'üncü, 4'üncü ve 5'inci üçgen sayılar var. Yani örneğin 3. sayı 1+2+3 = 6, 4. sayı ise 1+2+3+4 = 10 şeklinde oluşuyor. O halde genel olarak konuşursak, nᵗʰ üçgen sayısı Tₙ şuna eşittir:

Bu elbette matematikteki en ünlü serilerden biridir ve ardışık tam sayıların toplamının şuna eşit olduğunu belirten Gauss tarafından da sunulmuştur:

Yani temel olarak, örneğin 3. üçgen sayısını hesaplamak istiyorsak, basitçe 3*4/2 = 6'yı hesaplarız. Çözümümüzü yazmaya başladığımızda bu çok yardımcı olacaktır!

Bölenler

Bir n sayısının böleninin (veya çarpanının ) tanımını vermek gerçekten çok basit: bu , başka bir k tamsayısıyla çarpılarak tekrar n değerini veren bir j sayısıdır. Örneğin 3, 18'in bölenidir, çünkü 3 ile 6'yı çarparak tekrar 18 elde edebiliriz.

Ancak 5, 18'in böleni değildir, çünkü 5 ile çarpıldığında 18 sonucunu veren bir k sayısı yoktur.

Tanım gereği, aynı zamanda önemli bir özellik de elde ederiz: Eğer j, n'yi elde etmek için k ile çarpılabileceği için n'nin bir böleni ise , o zaman n'yi elde etmek için j ile çarpılabileceği için k de n'nin bir böleni olur .

Bu şekilde, bir n sayısının her zaman en az iki j ve k böleni olduğundan emin olabiliriz (aslında j her zaman 1 olabilir ve k , n olabilir).

Ayrıca, başka bir deyişle, n/j'nin geri kalanı 0'a eşitse j sayısı, n sayısının böleni olur . Yani örneğin 18/3 = 6 ve kalan 0'dır.

Bu kavramı , n %j = 0 ise j'nin n'nin bir böleni olduğunu söyleyerek modüler aritmetikle daha iyi formüle edebiliriz. Başka bir deyişle, şu ikinci özelliği elde ederiz:

İlgilendiğimiz üçüncü ve son özellik , n sayısının kendisinden ziyade n /2'den büyük bir böleni olamayacağıdır. Bunu anlamak oldukça basittir. İlk özellikten, faktörlerin 1,…,n aralığında bir şekilde birbirine “bağlı” olduğunu biliyoruz.

Bunun nedeni, eğer j \ n ise j * k = n olmasıdır. Bu nedenle ayrıca k \ n. Yine 18'i örnek alalım, bölenlerini bulalım ve bu özelliği yansıtacak şekilde renklendirelim.

Yani, örneğin, eğer j = 3, k = 6 ve tam tersi eğer j = 6, k = 3 ise, bu, 1 dışında kullanabileceğimiz en küçük j'nin 2 olduğu anlamına gelir, bu da bize en büyük k'yı verir. mümkün, n/2 (bizim durumumuzda 9) . Bu çalışıyor:

• çift sayılar için, bu durumda en büyük faktör tam olarak n'nin yarısına eşit olacaktır;

• tek sayılar için: n'yi 2'ye bölemiyorsak (çünkü tek olmak bize rasyonel bir sayı verecektir); bu sadece j > 2'yi kullanabileceğimiz anlamına gelir, bu da bize her zaman k < n/2 sonuçlarını verecektir.

  
  

Son olarak, j ve k'nin eşit olabileceği tek bir durum vardır: n'nin bir kare sayı olması. Örneğin, n = 36 olduğunda, olası bir j = 6 çarpanı başka bir k = 6 çarpanını üretecektir. Bu durum hakkında daha sonra kod kısmında daha fazla tartışacağız.

Bu kavramlar elbette oldukça önemsiz ama çözümümüzde çok önemli olacaklar!

Kod

Kod Go'da yazılacaktır, çünkü gerçekten hızlı bir dildir ve okunabilirliği hala yüksektir. Çözümü ikiye böleceğiz: Önce bir sayının bölenlerini bulan bir fonksiyon oluşturacağız, sonra bunu üçgen sayılara uygulayacağız .

Önce fonksiyonu görelim:

Bir n tamsayısını kabul eden ve bölenlerimizi içeren bir tamsayı out döndüren fonksiyonumuzu yaratıyoruz. Bundan sonra önemsiz çarpanları yani 1 ve n kendisini out .

Daha sonra j 2'den n/2 döndürmeye başlarız (ikinci özellikten; ayrıca n/2 kendisiyle ilgilenmediğimizi unutmayın çünkü n çift olması durumunda k = n/2 bölenlere j = 2 tarafından eklenecektir) j = 2 yineleme: bu nedenle j≤ n/ j<n/2 j≤ n/2 duruyoruz.

Bu şekilde, bölenleri yalnızca n ilk yarısında kontrol edebiliriz, bu da süreci biraz hızlandırır.

Her döngüde 3 şeyi kontrol ederiz:

• Üçüncü if ifadesi aslında n%j==0 olup olmadığını, diğer bir deyişle 0 ≡ n (mod j) olup olmadığını kontrol eder. Eğer öyleyse, bir faktör bulduk ve listeye j ekledik. Ayrıca n/j hesaplayıp sonraki j geçerek k'nin karşılığını da listeye ekleyebiliriz;

• İkinci if ifadesi, n bir kare olup olmadığını ve dolayısıyla j n kökü olup olmadığını kontrol eder. Eğer öyleyse, kopyaları önlemek için out öğesine yalnızca bir j böleni eklenecektir ve ardından algoritma devam eder.

  
  

  Diyelim ki n = 36 : eğer bu küçük blok eksik olsaydı, üçüncü if ifadesi tetiklenirdi, j = 6 ve k = n/j = 36/6 = 6 alınmasına out olurdu, böylece bir kopya oluşturulurdu.

• İlk if ifadesi en karmaşık olanıdır: amacı tekrar eden jk çiftlerine sahip olup olmadığımızı kontrol etmektir. Eğer öyleyse, döngüyü anında kırabiliriz, çünkü faktörümüzün tümü zaten out mevcut olacaktır.

  
  

Özellikle bu üçüncü noktayla ilgili olarak kontrol edilmesi gereken iki durum vardır: out[len(out)-1] == j mi yoksa out[len(out)-2] == j ?

İlk durum klasiktir: örneğin T₇ = 28 sayısını alın:

j = 7 olduğunda girilen son değere eşit olacaktır. Bu nedenle döngüyü kırabiliriz.

İkinci durum yalnızca bir n karesi bulduğumuzda ortaya çıkar. Tekrar 36'yı ele alalım, örneğin:

j = 9 olduğunda, yalnızca bir kez görünen n karekökünün önüne eklenen son değere eşit olacaktır. Dolayısıyla bu noktada döngüyü kırabiliriz.

Son olarak, bölenlerimize sahip olmak için basitçe return out .

Sonuçların Uygulanması

Artık fonksiyonumuz olduğuna göre onu her üçgen sayıya uygulayabiliriz. Üçgen sayılarımız için jeneratör görevi görecek bir c sayacı yaratacağız. İlişkili tn üçgen sayısını Gauss denklemiyle hesaplıyoruz ve kaç böleni olduğunu kontrol ediyoruz.

Eğer 500'den fazlaysa sonuç olarak bu tn döndürürüz.

Ama...bir sorun var!

ProjectEuler.net gerçekten harika bir proje: matematik bilmeceleri ve problemleri sunmanın yanı sıra, ana odak noktaları matematik hakkında öğrenmeye, düşünmeye ve akıl yürütmeye başlamak için bir araç sağlamaktır .

Ve bunu seviyorum: O kadar kararlılar ki, sorunlarına yönelik sonuçların ve kılavuzların yayınlanması aslında yasak (bu ilk 100 sorundan biri, dolayısıyla izin verildiğini anlıyorum).

Bu göz önüne alındığında, kopyala-yapıştır çözümünü verip başarıyı elde etmenin adil olacağını düşünmüyorum . Bu nedenle size gerçek çözümü vermiyorum: kendiniz deneyin ve benimkinden daha iyi bir algoritma bulmaya çalışın (bunlardan çok var). Üzgünüm beyler! 😅

Zaman Karmaşıklığı

Çok daha iyi çözümlerin bulunduğundan eminim çünkü bunun oldukça berbat bir atış olduğunu düşünüyorum!

FindDivisor işlevi doğrusal zamanda çalışır: çünkü n örneğinin boyutuna bağlıdır ve aynı zamanda en fazla n/2 döngü çalıştırır; bunu bir O(n) olarak düşünebiliriz.

Ancak, önce her üçgen sayısını hesaplamamız gerekir, bu da O(tn) zaman alır; burada tn sonuçtur (aslında hesapladığımız son sayıdır). Bu göz önüne alındığında, tüm algoritmanın yaklaşık zaman karmaşıklığı O(tn*n) olmalıdır.

tn argüman veya fonksiyonumuz haline geldiğinden ve onun içinde en fazla n/2 döngü çalıştırdığımızdan, zaman karmaşıklığını O(tn*tn/2) = O(tn²/2) = O(tn²) olarak yeniden yazabiliriz. Yani ne yazık ki ikinci dereceden bir zaman çözümü !

Algoritmanın bu kadar karmaşık olmasına rağmen yine de oldukça hızlı çalışmasına şaşırdım. Makinemde (AMD Ryzen 5, ortalama ck. 2700 MHz) sonuç vermek 322,564227 ms sürdü.

1000 böleni aşan ilk üçgen sayısını bulmaya çalışmak 3,827144472 saniye sürdü, dolayısıyla zaman tüketiminin hızla arttığı açıkça görülüyor.

Çözüm

Sonunda başardık! Umarım makaleyi beğenmişsinizdir ve umarım bundan ilginç bir şeyler çıkarmışsınızdır: eğer öyleyse, lütfen bir veya iki alkış bırakın ve makaleyi bu konuyla ilgilenebilecek biriyle paylaşın!

Harika iş için ProjectEuler'a bir kez daha büyük bir teşekkür: Gerçekten gidip neler sunabileceklerini kontrol etmenizi öneririm; Eminim bunu çok ilginç bulacaksınız!

Ve her zamanki gibi okuduğunuz için teşekkürler.

Nicola