[MD-sorular] Ynt: Re: Ynt: Re: Ynt: Re: Project Euler 222.Soru
dede
dede_47 at mynet.com
16 Oca 2013 Çar 14:22:25 EET
Sayın Burak Kaya;
C programlama bilmiyorum,ayrıca verdiÄŸiniz programı çalıştıracak
derleyicim de yok! Sadece VisualBasic ve Mathematica programlama
biliyorum;onlarda da bu sorunun programını iyi yapamadım.(Mathematica 6
da yaptım, bilgisayarımı 6 saat çalıştırdım;sonuç yok!Sıkıldım ve bilgisayarı
durdurdum.)
DediÄŸiniz gibi bu sorunun çözümü böyle olmamalı;matematiksel kısa bir yol olmalı;
ama o yolu ben de göremedim/bulamadım.
Sonuçta ben bir "amatörüm".Bir soruya ancak bu kadar "nüfuz" edebiliyorum;
gerisi ileri düzeylerin/profesyonellerin iÅŸi!
Zaman verdiÄŸiniz/ilgilendiÄŸiniz için tekrar teÅŸekkürlerimle,
Selamlar...
A.Kadir DeÄŸirmencioÄŸlu
----- Özgün Ä°leti -----Kimden : burakvonkaya at gmail.comKime : dede <dede_47 at mynet.com>Cc : md-sorular at matematikdunyasi.orgGönderme tarihi : 16 Ocak 2013 ÇarÅŸamba 13:29Konu : Re: Ynt: Re: [MD-sorular] 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
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20130116/53b93e93/attachment.htm>
MD-sorular mesaj listesiyle ilgili
daha fazla bilgi