[MD-sorular] Ynt: Re: Ynt: Re: Project Euler 222.Soru
Burak Kaya
burakvonkaya at gmail.com
16 Oca 2013 Çar 13:30:34 EET
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
> <mailto:burakvonkaya at gmail.com>
> *Kime :* md-sorular at matematikdunyasi.org
> <mailto: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 listesisorular 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/bce847ac/attachment.htm>
MD-sorular mesaj listesiyle ilgili
daha fazla bilgi