[MD-sorular] Ynt: Re: Ynt: Re: Project Euler 222.Soru
Kerem Altun
kerem.altun at gmail.com
16 Oca 2013 Çar 13:42:01 EET
randompermute() fonksiyonunda ilgili satırda k>0 yerine k>=0 olacak
yanılmıyorsam. Sonucu onemli derecede degistirebilir. Belki o yuzden
1592'nin altina inemediniz.
Kerem
2013/1/16 Burak Kaya <burakvonkaya at gmail.com>
> 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 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/2c2948f3/attachment-0001.htm>
MD-sorular mesaj listesiyle ilgili
daha fazla bilgi