İlkel üçgenlerin sayısı nasıl bulunabilir?

0 beğenilme 0 beğenilmeme
128 kez görüntülendi

Üçgenlerin  kenar uzunlukları  tamsayı a,b,c olsun.

Kenar uzunlukları için  a<=b<=c koşulu sağlansın.

a,b,c  'nin en büyük ortak böleni 1 (bir) ise o üçgene

ilkel üçgen denir.

N , doğal bir sayı olsun.

a<=b<=c<N  için üçgenlerin ve ilkel üçgenlerin

sayıları ile ilgilenilmektedir.

Örnekler:

a<=b<=c<10 için  95 üçgenden  74 tanesi ilkel üçgendir.

a<=b<=c<20 için 715 üçgenden 582 tanesi ilkel üçgendir.

a<=b<=c<30 için 2360 üçgenden 1935 tanesi ilkel üçgendir.

a<=b<=c<40 için 5530 üçgenden  4521 tanesi ilkel üçgendir.

a<=b<=c<50 için 10725 üçgenden 8831 tanesi ilkel üçgendir.

a<=b<=c<N  için T  üçgenden P tanesi ilkel üçgendir.

N doğal sayısı verildiğinde T ve P doğal sayılarını bulmak için

neler yapılabilir? (Hızlı algoritma, formül, bağıntı, kısa yol vb.)


10, Ocak, 10 Bilgisayar Bilimi kategorisinde suitable2015 (3,893 puan) tarafından  soruldu

 Çözüm için herhangi bir yöntem  bulamadım..

Üçgen olma koşullarını göz ardı etmeyen ve verilen bir $N$ doğal sayısından küçük kenar uzunluklarına sahip üçgen sayısını bulduran bir bilgisayar programı yazılabilir sanırım. Ama nasıl yazılırı sakın bana sormayın :))

ebob (a,b,c)=1 olacak üçlüleri bulacak bir yöntem var galiba yanlış hatırlamıyorsam.Küçük bir araştırma yapılabilir.Fakat bunları küçüklük şartına bağlı kalarak üçgen oluşturacak şekilde seçmek bilgisayar programına bakar.Mehmet Toktaş'ın dediği gibi uzak dursun programcılık.anlamadım gitti yahu :-)

 üçgensel soruları görünce kaçıyorum :)

@Anil. Bulus yapmak icin kactiginiz belli  oluyor. En kisa zamanda yaklasik da olsa bir dogrusal  regresyon dogrusu denklemi sizden buraya gelebilir:) 

:):):):)                        

Üçgenin  iç yarıçapı (r>=2) biliniyorsa  ilkel pisagor üçgenlerinin

 sayısını veren formülü Neville Robbins  iç yarıçap  

uzunluğunun farklı asal çarpanlarına bakarak bulmuş.

r=105 (teksayı) =3*5*7 ise ilkel pisagor üçgenlerinin sayısı

 =$ 2^{farklı  asal  çarpanların  sayısı}=2^3=8$

r=32 (çift) =2*2*2*2*2 ise ilkel pisagor üçgenlerinin sayısı

=$2^{farklı  asal  çarpanların  sayısı - 1}=2^{1-1}=1$

bunu yeni duydum.Güzelmiş hocam not alalım.

Tüm kenarları ve alanı tamsayı olan üçgenlerin

 (Tamsayı Heron Üçgenleri) sayısını bulmak daha kolay.

(   ebob(a,b,c)=1  kontrolü yapılmadığı için  )

Örnekler:

.a<=b<=c<N

N<100 için 235 Heron üçgeni vardır.

N<200 için 848 Heron üçgeni vardır.

N<300 için 1746 Heron üçgeni vardır.

N<400 için 2832 Heron üçgeni vardır.

N<500 için 4148 Heron üçgeni vardır.

N<600 için 5609 Heron üçgeni vardır.

N<700 için 7193 Heron üçgeni vardır.

N<800 için 8886 Heron üçgeni vardır.

N<900 için 10755 Heron üçgeni vardır.

N<1000 için 12752 Heron üçgeni vardır.

Sayın @suitable2015 bu sayıları nasıl bulduk? Bilgisayar yardımıyla mı?

Kenarları ve alanı tamsayı olan üçgenlerin sayısını bulmak için 

c<=b<=a<n alındığında üç çevrim yardımıyla 

alanın tamsayı olup olmadığını kontrol ettim.

a  kenarı 1 den n e kadar değişsin

b kenarı (a+1)/ 2  'nin tavanından a ya kadar değişsin.

c kenarı a-b+1 den b ye kadar değişsin

alan tamsayı ise say ve üçgenlerin kenar uzunluklarını yaz

Bu da Project Euler 513 ile ilgili bir alt soru. Hazırlık sorusu, ilksel olmayan üçgenleri de bulurum, nasıl olsa onların da katları da o özellikleri sağlar, böylece hızlanmış olur programım düşüncesi var gibi... Bir sonuç bulur eninde sonunda.

Ancak, 3 adet döngü kurarak (Brute Force Approach), ki o kodda o haliyle bile bir sürü optimizasyon gerekiyor, bu soru çözülmez. O(N3) karmaşıklık... Çözülür birkaç ay programı çalıştırırsınız, onun da ne anlamı var değil mi?

Orijinal sorunun altına ne yapılması gerektiği yazılmıştır. O(N3)'ten kurtulmak için, "Hashing" kullanılabilir. Zaten Python'da çözülecek soru değil. 

İlk 5000 için, C++ 48 sn, Python 6 dakika benim makinede, dediğim yönteme göre...

Brute Force yöntemi, yukarıdaki yöntem, Python benim makinede 1 saat çalıştı, sonuca ulaşmadı, ben de kapattım. Belki o yöntemi kullanan kişi, ne kadar sürede 5000 için sonuç bulduğunu söyler. 

Hashing, hızlı kayıt arama yapmak için kullanılan, modüler aritmetik esasına dayanan bir yöntem. Python'da hashing tabloları oluşturmak zahmetsiz, C++'da ise, linkli liste array oluşturmak gerekiyor. 

struct node {

unsigned int a;

unsigned int b;

unsigned long long t;

};


struct left {

unsigned int mc;

unsigned int c;

unsigned long long t;

};


Bu üstte görülen, sol ve sağ tablolar arasında sıradan karşılaştırma yapılıyor. Bunun için de dediğim gibi kenarortay bağıntısını sol ve sağ eşitlikler şeklinde yazmak gerekiyor. Özel bir bağıntıya ihtiyaç yok. Bu alttaki de yazdığım hashing kodu. 
unsigned long hashing_(std::list<left>lefttable[64001],std::list<node>hashtable[64001]){
int count=0;
std::list<left>::iterator it;
std::list<node>::iterator it1;
for (int i=0;i<64001;i++){
//std::cout<<"i="<<i<<"\n";
it=lefttable[i].begin();
while (it!=lefttable[i].end()){
//std::cout<<it->c<<"\n";
it1=hashtable[i].begin();
while (it1!=hashtable[i].end()){
if ((it->t)==(it1->t)){
if ((it1->b)<=(it->c)){
if ((it->c)<(it1->a)+(it1->b)){
if ((it->c)>abs(it1->a-it1->b)){
//std::cout<<it1->a<<" "<<it1->b<<" "<<it->c<<" "<<"\n";
count+=1;
//std::cout<<count<<"\n";
}
}
}
}
it1++;
}
it++;
}
}
return count;
}


naim2.jpe (0,1 MB) Tabii bu kodun bir kısmı. Problem çok zor değil. Bence contestcen.com'daki 3 Pandigital sorusu daha zor. Orada yanlış hatırlamıyorsam, 30 basamaklı sayılar söz konusuydu. 

Neyse konumuza dönersem, C++'da memory miktarı nasıl arttırılır hiç uğraşmadım, 64000'lük hashing tabloları işimi gördü. Hashing Function'da, 64001. Hashing Function daha düzgün seçilebilir, bunun için de çeşitli yöntemler var, o ayrı bir konu. 

Program, her iki tabloyu modüler aritmetik esasına göre dolduruyor. Hashing Collision olduğu durumda ise, linkli liste array ile bu çakışmalar çözülüyor. Zaten Collision olmaması imkânsız. 

Daha sonra ise, iki tablo arasında göz göz karşılaştırma yapılıyor, çok basit bir teknik. Ancak, karmaşıklık O(N2). 

Daha çok zamanım olursa... 

a<=b<=c<=5000 için C++'da çalışma zamanı 38.6 saniye, ekran çıktısında da görünüyor, onu da koydum. Aynı yöntem, Python'da 5-6 dakika... Üstelik, Python'da 100000'lik bir tablo var. Ne kadar büyük olursa, iç kısımdaki arama sayısı azalıyor. Buna rağmen...

Bence, bu problemi çözmek yerine, daha basit bir problem olan şu problem çözülmeli ki yol alınabilsin. Bakın, belki burada 3 adet döngüyü alt alta koymak işe yarayabilir. Ben olsam, eğer Project Euler sorularıyla uğraşıyor veya uğraşacak olsam, önce C öğrenirdim. Şu problemi C'de çözmeye çalışırdım, ondan sonra da Project Euler'e dalardım. Sağlam bir C ile. Tabii, C'yi öğrenirken, Data Structures'da çalışırdım. İşte mesela, Hashing. Tam da o konulardan biri...

** Triangle Within a Triangle 
       A triangle DEF is located interior to triangle ABC with all 15 distances distinct integers. What is the smallest case (smallest area of ABC)?  



Ekteki dosya incelenebilir.image

Peki, Siz o zaman Python kullanın veya ne isterseniz onu. Ancak, ben Size C++'nın Python karşısındaki çalışma hızı bağlamında gücünü gösterdim. Aynı algoritma, birinde saniyeler bazında çözüm üretirken, diğeri dakikalar mertebesinde sonuç veriyor...

Ayrıca, o tablo tam olarak bir şey göstermiyor. Bir kullanıcı bazı sorularda Python kullanabilir, bazı sorularda C++ kullanabilir. Tıpkı benim yaptığım gibi. Bu tip soruda neden Python kullanayım ki, C++ dururken. Project Euler'in bazı sorularında, nispeten daha kolay olanlarında, pekâla Python kullanılabilir. 

Esas nokta o değil sadece tabii. Algoritmanız veya Algoritma bilginiz. Oluşturduğunuz, 3 adet döngü. Daha önce de söyledim, oluşturduğunuz programın karmaşıklık fonksiyonu O(N3). Ben, bunu O(N2)'ye indirdim. Nasıl indirdiğimi de gösterdim. Bence, onu anlamaya çalışın. Siz de aynı kenarortay teoremini kullanıyorsunuz, ben de aynısını. Ortada başka bir mucize formül yok.

Sizin algoritmanız ile benim algoritmamın Python'daki çalışma hızlarını da gösterdim. Siz hâlâ, 5000 sınır değeri için, programınızın kaç saat çalıştığını itiraf etmediniz. Aradan 1 saat geçince, Sizinkini kapattım. O(N2) karmaşıklıktaki olan, 6 dakika seviyesinde çalıştı, aynı platformdan bahsediyorum. Sadece karmaşıklık bu kadar fark ettiriyor. Siz, O(N2) karmaşıklığı, logaritmik karmaşıklığa indirirsiniz, o zaman daha iyi bir iş yapmış olursunuz.

Ben, Sizin yerinizde olsam, nedir bu "Hashing", öğrenmeye çalışırdım, hattâ Python'da bir örnek kodlardım. En azından yapmaya çalışırdım.

Defaatle, buralarda paylaştınız bu tip soruları, görüyorum. Hangi sorduğunuz soruya cevap alabildiniz? Demek ki burası, bunun yeri değil. Kategorinin "Bigisayar Bilimleri" olması bu sonucu değiştirmiyor.

Contestcen.com'un sorularıyla başladınız işe meselâ. Yapan var mı? İlgilenen var mı? Bir iki iddiâ uğruna ben ilgilenmiştim bir zamanlar, o zaman bu siteyi de bilmiyordum üstelik. 

Neden o sorduğunuz soruları yapmıyorsunuz, bu kadar ilgiliyseniz bu işlerle. Kendiniz soruyorsunuz, ama yapmıyorsunuz, biri bitmeden başka bir soruya geçiyorsunuz, biri bitmeden bir başkasına... 

Diyelim ki kaza sonucu şu sorduğunuz kenarortay sorusunun yanıtını buldunuz, ne elde edeceksiniz? O(N3) karmaşıklıkta program yazıyorsunuz. Hashing nedir? Linkli Liste nedir? Linkli Liste Array nedir? Bir bakın, öğrenmeye çalışın, ya da boşverin bu işleri. 

Python bile olsa, bir dizi tanımlayın, diziyi kullanın. Hashing tabloları oluşturun.... İş, 3 adet döngüyü alt alta yerleştirmek değil...

Soruyu gördüğüm zaman, kaynağı da belliyse, yapmak zorunda hissediyorum kendimi... Hashing...  Nickname'i yeni aldım, kartal20. 20 Denizli'nin plaka işareti. :)

Soru pek zor değil. İlk a<=b=c<=5000 değeri için 25 sn'de çözüm üretiyor C++'daki hashing algoritmam. İlişikteki resim de doğruluyor, bakılabilir. Cevaba gelince, milyar mertebesindedir. 

image

...