[MD-sorular] Ynt: Re: Ynt: Re: Ynt: Re: Project Euler 222.Soru

dede dede_47 at mynet.com
18 Oca 2013 Cum 12:24:42 EET


Sayın Yüksel Yıldırım;
VerdiÄŸiniz sonuçta 30 mm lik topu unutmuÅŸsunuz;Bu topu verdiÄŸiniz sıralama
kuralına göre 50,48,46,44,42,40,38,36,34,32,30,31,33,35,37,39,41,43,45,47,49
siyahladığım yere koymalısınız bu durumda en az yükseklik:H=1641.923311286
olur.
Ä°yi çalışma dileklerimle..
A.kadir DeÄŸirmencioÄŸlu
 ----- Özgün Ä°leti -----Kimden : xleopar at yahoo.comKime : Burak Kaya <burakvonkaya at gmail.com>, dede <dede_47 at mynet.com>Cc : "md-sorular at matematikdunyasi.org" <md-sorular at matematikdunyasi.org>Gönderme tarihi : 18 Ocak 2013 Cuma 02:28Konu : Re: [MD-sorular] Ynt: Re: Ynt: Re: Project Euler 222.Soru


merhabalar,ben de pascal/delphi ile denedim.. (programlar ve kaynak kodlari) ektedir. 
 
dizilim 50 48 46 .. 32 31 .. 47 49 da olabiliyor, veya, asagida belirtildigi uzere, tersi seklinde de olabiliyor, dogal olarak..
sorunun cevabi da 1546,02935883299187 olmaktadir, --eger bir yerlerde hata yoksa :)iyi calismalar
 
 


From: Burak Kaya <burakvonkaya at gmail.com> To: dede <dede_47 at mynet.com> Cc: md-sorular at matematikdunyasi.org  Sent: Wednesday, January 16, 2013 1:30 PM Subject: Re: [MD-sorular] Ynt: Re: Ynt: Re: Project Euler 222.Soru 



Sayın Dede,  EÄŸer C dili için bir derleyiciniz varsa az sonra ekleyeceÄŸim kod tam olarak bahsettiÄŸim "naif" algoritmayı gerçekleÅŸtiriyor. Dün 1592'yi görebildim, ama permütasyon seçimleri rastgele olduÄŸu için siz nereye kadar inebilirsiniz bilemem. Program sonsuza kadar çalışıyor bu arada, her bulduÄŸu yeni en iyi çözümde ekrana toplam yüksekliÄŸi ve dizilimi yazıyor.  Ama bu sorunun çözümü böyle olmamalı. Matematiksel bir kısayol, ya da çözümün nasıl olması gerektiÄŸini gösteren sezgisel bir argüman olmalı gibi ama göremiyorum ne yazık ki.  #include <stdio.h> #include <stdlib.h> #include <math.h>  int a[21],t[21],b[21]={25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5}; double sum=3000,temp;   void printarray() {     int k = 0;     for (k = 0; k < 21; k++) printf("%d ", b[k]+25);     printf("\n---------------------\nSUM:%f\n\n",sum); } void randompermute() {     int k;     for (k = 0; k < 21; k++)     a[k] = k;     for (k = 20; k > 0; k--) {     int
  j =
rand() % (k+1);     int temp = a[j];     a[j] = a[k];     a[k] = temp;     } } void compute() {      int i;      for(i=0,temp=0;i<20;i++){temp=temp+sqrt(b[a[i]]+b[a[i+1]]);}      temp=temp*10*sqrt(2);      temp=temp+50+b[a[0]]+b[a[20]];      if(temp<sum)      {                  for(i=0;i<21;i++) t[i]=b[a[i]];                  for(i=0;i<21;i++) b[i]=t[i];                  sum=temp;                  printarray();      } } int main(void) {     int k;     srand(time(NULL));     for(k=0;k<21;k++) a[k]=k;     for (;;)     {     randompermute();     compute();     }     return 0; }  On 1/16/2013 5:05 AM, dede wrote:

 Sayın Burak Kaya, 
"En küçük yükseklik için,topların diziliÅŸ sırası önemlidir." uyarınızda haklısınız;
zira diziliÅŸ sırasını aÅŸağıda ki N dizisindeki gibi (rakamlar,topların yarıçaplarını gösteriyor)
rastgele deÄŸiÅŸtirdim,topların merkezleri arasındaki düÅŸey yukseklikleri içeren H dizisini elde ettim.
(ilk top 31 mm,son top 50 mm olduÄŸundan 50+31=81 eklendi) H=1596,69784 olup ilk bulduÄŸum 1597,69878 deÄŸerinden küçüktür. 
N=(31,30,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50)     
H=81+(46.9042,48.9898,54.7723,58.30951,61.64414,64.80740,67.82329,
70.71067,73.48469,76.15773,78.7400,81.24038,83.66600,86.02325,
88.31760,90.55385,92.73618,94.86832,96.95359,98.99494)=1596.69784
Bu itibarla borunun yüksekliÄŸi,topların diziliÅŸ sırasına baÄŸlı olmaktadır. 
Bahsettiğiniz programlamayı anladım;ancak bu programlama benim 
"programlama" bilgimi aÅŸar,bu itibarla bu soru için "benden bu kadar"! 
Ä°lgi/uyarı ve yardımlarınız için tekrar teÅŸekkür eder, 
Esenik ve iyi çalışmalar dilerim. 
A.Kadir DeÄŸirmencioÄŸlu 
 
  ----- Özgün Ä°leti ----- Kimden : burakvonkaya at gmail.com Kime : md-sorular at matematikdunyasi.org Gönderme tarihi : 16 Ocak 2013 ÇarÅŸamba 03:29 Konu : Re: [MD-sorular] Ynt: Re: Project Euler 222.Soru 

Hatta bir satır daha ilerletelim  =(r_0-25)+25+10*sqrt2*(sqrt((r_0-25)+(r_1-25))+...+sqrt((r_19-25)+(r_20-25)))+(r_20-25)+25=   r_i-25=a_i dersek   =50+a_0+10*sqrt2*[sqrt(a_0+a_1)+sqrt(a_1+a_2)+...+sqrt(a_19+a_20)]+a_20   öyle ki (a0,a1,...,a20), {5,6,7,...,25}'in bir permütasyonu. Åžimdi bunu nasıl minimize ederiz? Sorunun Project Euler sorusu olduÄŸunu göz önüne alırsak, direk analitik bir yol olmasa gerek (belki de vardır bilemiyorum). Peki nasıl bir program yazabiliriz?   21! olasılığı tek tek denemeyecekseniz tabii ki. Åžöyle çok basit bir "evrimsel" yaklaşım deneyebiliriz.   -a=(a0,a1,...,a20)=(25,24,23,...,5) çözümü ile baÅŸla ve toplamı hesapla.  -S_20'nin (yani 20 eleman üzerindeki simetrik grubun) rastgele bir f permütasyonunu al (buradaki rastgelelik fonksiyonu sizin seçiminize kalmış).  -f(a)'yı bul ve toplamı hesapla. EÄŸer eldeki en iyi toplamdan küçük ise a'yı f(a) ile deÄŸiÅŸtir, deÄŸilse bir ÅŸey yapma. Adım 2'ye geri dön.   Böyle "rastgele"
yaklaşımlar fazla iÅŸe yaramaz gözükse de emin olun belirli bir süreden sonra optimal çözümün kendisini kesinlikle vermese de optimal çözüme yeterince yaklaşıyorlar. Bunu programlayıp bilgisayarınızı bir kaç saat açık bırakın, bakalım elde ettiÄŸiniz çözümden daha iyisi var mıymış :)     On 1/15/2013 7:19 PM, Burak Kaya wrote:

Sayın Dede,   Topları aÅŸağıdan yukarı belirli bir dizilimle yerleÅŸtirelim ve yarıçapları da r_0,r_1,...,r_20 olsun. YüksekliÄŸi hesaplarsak   r_0+ sqrt((r_0+r1)^2-(100-(r_0+r1))^2)+sqrt((r_1+r2)^2-(100-(r_1+r2))^2)+...+sqrt((r_19+r20)^2-(100-(r_19+r20))^2)+r_20=  r_0+sqrt(100*(2*(r_0+r_1)-100))+...+sqrt(100*(2*(r_19+r_20)-100))+r_20=  r_0+10*sqrt2*(sqrt(r_0+r_1-50)+...+sqrt(r_19+r_20-50))+r_20=   olacak (r0,r1,...,r20), {30,31,...,50}'nin bir permütasyonu olmak üzere. Bunun, topların sırasına baÄŸlı olduÄŸu aÅŸikar olsa gerek.   Sorunun zor yanı ne? 21! dizilimi kaba kuvvetle denemek yerine bir kısa yol bulmak!   Bu tabii iki boyutta. Üç boyutta düÅŸünürseniz iÅŸ iyice zorlaÅŸacak çünkü -mesela yukarıdan baktığınızda- topların merkezlerini aynı düzlem üzerinde koymadığınız zaman belki de merkezleri yüksekliÄŸi kısaltacak ÅŸekilde ayarlamanın yolu vardır!   On 1/15/2013 1:05 PM, dede wrote:

   Sayın Burak Kaya,
Haklısınız;verdiÄŸim çözümde hep topların(kürelerin)borunun altından yukarıya doÄŸru 
sıralandığını/dizildiÄŸini düÅŸündüm.Ancak 100 mm çaplı boruya konan topların yarıçapları 
30 mm,31 mm,32 mm,....,50 mm olarak verilmiş (21 adet top).Yani topları hangi sırayla dizerseniz 
dizin (büyükten küçüÄŸe,küçükten büyüÄŸe,karışık) iki topun yan yan gelmesi olanaksız.
(30 mm yarıçaplı topu nereye koyarsanız koyun,2*30=60 mm yer kaplar, geriye 100-60=40mm 
yani 40/2=20 mm yarıçaplı yer kalır ki,buraya koyacağınız bu yarıçapta top yok!)Åžunu anlatmak istiyorum:Topları nasıl dizerseniz dizin,ilk iletide verdiÄŸim eÅŸitlikte köklü ifadelerin bazılarının 
yeri deÄŸiÅŸir,bu da sonuca etki etmez.(köklü ifade de her terim, 50 mm yarıçaplı ilk topun merkezinden baÅŸlamak üzere,topların merkezleri arasında ki sıralı uzaklıklardır.) Bu soruyu 
3 boyutlu düÅŸünmekte sonucu etkilemiyor;zira yine 3 boyutlu olarak topları nasıl dizerseniz dizin,yanına baÅŸka bir top koyma olanağı yok;bu durumda ise topların diziliÅŸ sırası önemli olmuyor. 
Project Euler yarişmasını tertipleyenlerin doğru yanıtları bildiğim kadar yayınlanmıyor,internette ki 
yanıtlar soruyu çözenlerin verdiÄŸi yanıtlar.(Yani doÄŸru oldukları garanti deÄŸil!) 
Bu yazdıklarım belki yanlıştır;sizin ikazınız doÄŸrultusunda soruyu çözen bir üyemiz(umarım) vardır! 
HerÅŸeye raÄŸmen ilgi ve yanıtınız için teÅŸekkür eder; 
Sağlık/esenlikler dilerim. 
A.Kadir DeÄŸiremencioÄŸlu 
Not:Ä°lk bakışta topların diziliÅŸ sırası sonucu etkilemiyor gibi görünse de, topları karışık dizerek,yanıtı bulmaya çalışacağım.Sanki bu soruda bir "cinlik" yapılmış gibi; bu cinlik topların diziliÅŸ sırası olabilir. 
  ----- Özgün Ä°leti ----- Kimden : burakvonkaya at gmail.com Kime : md-sorular at matematikdunyasi.org Gönderme tarihi : 15 Ocak 2013 Salı 16:12 Konu : Re: [MD-sorular] Project Euler 222.Soru

Topların büyükten küçüÄŸe sıralanması gerektiÄŸini nereden biliyorsunuz ki (verdiÄŸiniz ifadeden anladığım kadarıyla bu ÅŸekilde yapmışsınız)? Zaten problemin amacı anladığım kadarıyla -bir ÅŸekilde- permütasyonları hızlı bir ÅŸekilde deneyerek optimale yaklaÅŸtırmak.   Bir de gene verdiÄŸiniz ifadeden gördüÄŸüm kadarıyla problemi iki boyutta hayal etmiÅŸsiniz. Ä°lk okuduÄŸumda üç boyutlu bir ÅŸeyler hayal etmek gerekiyor gibi geldi ama emin olamadım ÅŸimdi.   On 1/15/2013 7:59 AM, dede wrote:

 
DeÄŸerli Üyeler,
BoÅŸ zamanlarımda,"diÅŸime göre olan" Project Euler sorularını çözmeye çalışırım; 
ÅŸimdiye kadar belki 200 den fazla soruyu çözdüm (yani programladım) hepsinde 
bulduÄŸum sonuç,internette verilen sonuçla aynı çıkmıştır.Ancak bu projenin 222.sorusu 
nu çözünce, bulduÄŸum sonuç internette verilenden farklıydı.O kadar inatlaÅŸtım ki,soruyu
1/1  ölçeÄŸinde çizdim,oradan hesapladım;bulduÄŸum sonuç internetteki sonuçla 
uyuÅŸmuyordu.Benim çözümüm;  
 
H=50+30+kök(99^2-1^2)+kök(97^2 -3^2)+kök(95^2 -5^2)+kök(
 93^2-7^2)+kök(91^2-9^2)+kök(89^2-11^2)+kök(
 87^2-13^2)+kök(85^2-15^2)+kök(83^2-17^2)+kök(
 81^2-19^2)+kök(79^2 -21^2)+kök(77^2-23^2+kök(
 75^2-25^2)+kök(73^2-27^2)+kök(71^2-29^2)+kök(
 69^2-31^2)+kök(67^2-33^2)+kök(65^2-35^2)+kök(
 63^2-37^2)+kök(61^2-39^2)=1597,698
Bu soru için internette verilen sonuç,H=1590.933 dür.Zamanı/merakı fazla 
olan üyelerden birisi bu soruya yoÄŸunlaşıp benim yanıtın mı,internetteki 
yanıtın mı yanlış olduğu konusunda bana yardımcı olabilir mi? 
Saygılarımla.... 
A.Kadir DeÄŸirmencioÄŸlu 
Not:Yukarıda ki yanıt;
H=80+Toplam(n=1'den 20'ye kadar:kök((100-(2n-1))^2-(2n-1)^2)) nin açık yazımıdır. 
 

_______________________________________________ MD-sorular e-posta listesi sorular at matematikdunyasi.org http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular



 
_______________________________________________ MD-sorular e-posta listesi sorular at matematikdunyasi.org http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular





_______________________________________________MD-sorular e-posta listesisorular at matematikdunyasi.orghttp://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular

-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20130118/ac0b6e3c/attachment.htm>


MD-sorular mesaj listesiyle ilgili daha fazla bilgi