Çö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:  Bu sorun harika bir web sitesi tarafından sağlanmaktadır.  abone olabileceğiniz  ! Çö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!   ProjectEuler.net   Burada  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   olan ilk   ne olduğunu anlamamız isteniyor. Öncelikle üçgen sayının ve bölenin ne olduğuna daha iyi bakalım. böleni üçgen sayının  Üç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ü   . İşte bazı örnekler:  onları her zaman üçgen şeklinde düzenleyebilirsiniz  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   tarafından da sunulmuştur: Gauss  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   sayısının   (veya   ) tanımını vermek gerçekten çok basit: bu   Örneğin 3, 18'in bölenidir, çünkü 3 ile 6'yı çarparak tekrar 18 elde edebiliriz. n böleninin çarpanının , başka bir   tamsayısıyla çarpılarak tekrar   değerini veren bir   sayısıdır. k n j  Ancak 5, 18'in böleni değildir, çünkü 5 ile çarpıldığında 18 sonucunu veren bir   sayısı yoktur. k  Tanım gereği, aynı zamanda önemli bir özellik de elde ederiz: Eğer     elde etmek için   ile çarpılabileceği için   bir böleni ise   o zaman n'yi elde etmek için   ile çarpılabileceği için   de n'nin bir böleni olur  j, n'yi k n'nin , j k .    (aslında   her zaman 1 olabilir ve   ,   olabilir). Bu şekilde, bir   sayısının her zaman en az iki   ve   böleni olduğundan emin olabiliriz n j k j k n  Ayrıca, başka bir deyişle,   . Yani örneğin 18/3 = 6 ve kalan 0'dır.  geri kalanı 0'a eşitse   sayısı,   sayısının böleni olur n/j'nin j n  Bu kavramı   ise     bir böleni olduğunu söyleyerek   daha iyi formüle edebiliriz. Başka bir deyişle, şu ikinci özelliği elde ederiz:  , n %j = 0 j'nin n'nin modüler aritmetikle  İlgilendiğimiz üçüncü ve son özellik   Bunu anlamak oldukça basittir. İlk özellikten, faktörlerin 1,…,n aralığında bir şekilde birbirine “bağlı” olduğunu biliyoruz. ,   sayısının kendisinden ziyade     büyük bir böleni olamayacağıdır. n n /2'den  Bunun nedeni, eğer     Bu nedenle ayrıca   Yine 18'i örnek alalım, bölenlerini bulalım ve bu özelliği yansıtacak şekilde renklendirelim.  j \ n ise j * k = n olmasıdır. k \ n.  Yani, örneğin, eğer   ve tam tersi eğer   bu, 1 dışında kullanabileceğimiz en küçük   2 olduğu anlamına gelir, bu da bize en büyük   verir. mümkün,   (bizim durumumuzda 9)   Bu çalışıyor: j = 3, k = 6 j = 6, k = 3 ise, j'nin k'yı n/2 .  ç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:   2'ye bölemiyorsak (çünkü tek olmak bize rasyonel bir sayı verecektir); bu sadece   bu da bize her zaman  n'yi j > 2'yi kullanabileceğimiz anlamına gelir, k < n/2 sonuçlarını verecektir.  Son olarak,   Örneğin,   olası bir   çarpanı başka bir   çarpanını üretecektir. Bu durum hakkında daha sonra kod kısmında daha fazla tartışacağız.  ve   eşit olabileceği tek bir durum vardır:   bir kare sayı olması. j k'nin n'nin n = 36 olduğunda, j = 6 k = 6  Bu kavramlar elbette oldukça önemsiz ama çözümümüzde çok önemli olacaklar!   Kod  Kod   yazılacaktır, çünkü gerçekten hızlı bir dildir ve okunabilirliği hala yüksektir. Çözümü ikiye böleceğiz: Önce   . Go'da bir sayının bölenlerini bulan bir fonksiyon oluşturacağız, sonra bunu üçgen sayılara uygulayacağız  Önce fonksiyonu görelim:   https://Gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true  Bir   tamsayısını kabul eden ve bölenlerimizi içeren bir tamsayı   döndüren fonksiyonumuzu yaratıyoruz. Bundan sonra önemsiz çarpanları yani 1 ve   kendisini   . n out n out  Daha sonra   2'den   döndürmeye başlarız (ikinci özellikten; ayrıca   kendisiyle ilgilenmediğimizi unutmayın çünkü   çift olması durumunda   bölenlere   tarafından eklenecektir)   yineleme: bu nedenle j≤ n/     duruyoruz. j n/2 n/2 n k = n/2 j = 2 j = 2 j<n/2 j≤ n/2  Bu şekilde, bölenleri yalnızca   ilk yarısında kontrol edebiliriz, bu da süreci biraz hızlandırır. n  Her döngüde 3 şeyi kontrol ederiz:  Üçüncü if ifadesi aslında   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   ekledik. Ayrıca   hesaplayıp sonraki   geçerek   karşılığını da listeye ekleyebiliriz; n%j==0 j n/j j k'nin  İkinci if ifadesi,   bir kare olup olmadığını ve dolayısıyla     kökü olup olmadığını kontrol eder. Eğer öyleyse, kopyaları önlemek için   öğesine yalnızca bir   böleni eklenecektir ve ardından algoritma devam eder. n j n out j  Diyelim ki   : eğer bu küçük blok eksik olsaydı, üçüncü if ifadesi tetiklenirdi,   ve   alınmasına   olurdu, böylece bir kopya oluşturulurdu. n = 36 j = 6 k = n/j = 36/6 = 6 out  İlk if ifadesi en karmaşık olanıdır: amacı tekrar eden   ç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   mevcut olacaktır. jk out  Özellikle bu üçüncü noktayla ilgili olarak kontrol edilmesi gereken iki durum vardır:   mi yoksa   ? out[len(out)-1] == j out[len(out)-2] == j  İlk durum klasiktir: örneğin T₇ = 28 sayısını alın:    olduğunda girilen son değere eşit olacaktır. Bu nedenle döngüyü kırabiliriz. j = 7  İkinci durum yalnızca bir   karesi bulduğumuzda ortaya çıkar. Tekrar 36'yı ele alalım, örneğin: n    olduğunda, yalnızca bir kez görünen   karekökünün önüne eklenen son değere eşit olacaktır. Dolayısıyla bu noktada döngüyü kırabiliriz. j = 9 n  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   sayacı yaratacağız. İlişkili   üçgen sayısını Gauss denklemiyle hesaplıyoruz ve kaç böleni olduğunu kontrol ediyoruz. c tn  Eğer 500'den fazlaysa sonuç olarak bu   döndürürüz. tn   https://Gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go  Ama...bir sorun var!    matematik bilmeceleri ve problemleri sunmanın yanı sıra,   . ProjectEuler.net gerçekten harika bir proje: 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,   . 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! 😅 kopyala-yapıştır çözümünü verip başarıyı elde etmenin adil olacağını düşünmüyorum   Zaman Karmaşıklığı  Çok daha iyi çözümlerin bulunduğundan eminim çünkü bunun oldukça berbat bir atış olduğunu düşünüyorum!    işlevi doğrusal zamanda çalışır: çünkü   örneğinin boyutuna bağlıdır ve aynı zamanda en fazla   döngü çalıştırır; bunu bir O(n) olarak düşünebiliriz. FindDivisor n n/2  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.    argüman veya fonksiyonumuz haline geldiğinden ve onun içinde en fazla   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   ! tn n/2 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

Read My Stories

Bu ses hikayenin orijinal dilinde üretilmiştir!

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

Sulara Yelken Açmak: Data Lakes ile Üretim Sınıfında RAG Uygulamaları Geliştirme

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

Başarılı Buluta Geçiş İçin Tam Kılavuz: Stratejiler ve En İyi Uygulamalar

Yapay Zekanın Gücünü Ortaya Çıkarıyoruz. En Son Tekniklerin Sistematik Bir İncelemesi: Özet ve Giriş

Sulara Yelken Açmak: Data Lakes ile Üretim Sınıfında RAG Uygulamaları Geliştirme

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

Başarılı Buluta Geçiş İçin Tam Kılavuz: Stratejiler ve En İyi Uygulamalar

Yapay Zekanın Gücünü Ortaya Çıkarıyoruz. En Son Tekniklerin Sistematik Bir İncelemesi: Özet ve Giriş

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps