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

Burak Kaya burakvonkaya at gmail.com
16 Oca 2013 Çar 03:29:09 EET


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 listesisorular 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/20130115/c73ae7fb/attachment.htm>


MD-sorular mesaj listesiyle ilgili daha fazla bilgi