[MD-sorular] Deve ile muz taşımak

[dede_47]

Bir arkadaşımız, iki tüccarın deve ile muz taşıması şeklinde bir soru
sormuştu ve Fatih Kürşad Cansu arkadaşımız buna doğru bir algoritma ile 55
adet muzun taşınabileceğini bulmuştu.Çözümünde çok ufak bir hesap hatası
yapmıştı (zira doğru yanıt 53 idi).Bu küçük işlem hatasını kendisine
ilettiğimde, hesap hatası olabileceğini belirttiğini,benim kendisinin
çözüm algoritması dışında bir algoritmamım olup/olmadığını sormuştu.Bu da
benim kafama takılmış,bir gece uykusuz kalmam sonucu, aşağıdaki
algoritmanın doğru çözümü verebileceğini buldum.Bu algoritmada ve yaptığım
çözümde hata olabilir, göstereceklere teşekkürlerimle işte algoritmam ve
çözümüm.Önce kullanacağımız harfleri tanımlayalım:
M=Taşınacak toplam muz sayısı, P=Devenin taşıyabileceği azamı muz
sayısı,L=Muzun taşınacağı iki şehir arasında ki
mesafe,q=Devenin ileri/geri hareketinde her birim mesafe için yediği
muz adedi olsun.(muz adedi/km)
Öncelikle iki önemli noktayı belirtelim:a-Muz kaybı devenin
ileri/geri yol yürümesiyle orantılı olarak artmaktadır.Dolayısıyla azamı
muzu taşıyabilmek için devenin ileri/geri yapacağı yol en
az olmalı, b-Devenin muzu taşıdığı her menzilde (bu menzile etap
diyelim) ,yediği muz sayısını en az yapabilmek için, taşınacak muz;
her  etapta tam P kadar azaltılmalıdır.(Yani P=100 ve M=400 ise
1.etapta 300 muz,2.etapta 200 muz,3.etapta 100 muz kalacak şekilde etap
uzunlukları seçilmelidir.) Bu iki hususun ışığında artık çözüm
algoritmamızı yazabiliriz:
1-Etap sayısını (k) yi hesapla.( k=(M-P)/P dır.n=k+1)
2-Etap uzunluklarını hesapla(Etap uzunlukları,
E(k)=P^2/(2M-(2k-1)P)=P/(2(n-k)+1) dır.k=1,2,3..(n-1)
3-Hesaplanan etap uzunluklarını topla.(Bu toplama S diyelim)
Eğer S<L ise taşınabilecek en fazla muz
sayısı,           
Q=P-qL+P(Toplam(k=1 den (n-1)) kadar;1/(2(n-k)+1) olur.
4)Eğer S>L ise, hesaplanan etapların paydası en küçük olanından
başlayarak S<L sağlanana kadar etap sayısını azalt(ihmal et)
S<L olunca kalan etap sayıları için adım 3 e göre taşınacak muz
sayısını hesapla.
1-Bu algoritmayı sitede sorulan soruya uygulayalım:Bu soruda q=1 muz
adedi/km, P=100 muz, M=300 muz ve L=100 km olduğundan etap sayısı
k=(300-100)/100=2 olduğundan etap sayısı k=2  ve n=k+1=3
dür.
2-İki adet etabımız olup bu etapların uzunlukları
E(1)=100/(2(3-1)+1)=100/5=20 km ve
E(2)=100/(2(3-2)+1)=100/3=33.33333  km.
3-Etap mesafeleri toplamı S=20+100/3=160/3=53.3333<100 olduğundan
taşınabilecek muz sayısı,Q=100-100+100(20+100/*3)=160/3=53.33333 adet
olur.Bu sonuç teorik olup kesirli muzun taşınması anlamsız
olacağından,taşınan muz sayısı 53 olacaktır!(Devenın yerine otomobil,
muzun yerine de litre olarak benzin koyarsanız 100 km mesafeye,azami 100
litre benzin taşıyabilen bir otomobil toplam 300 litrelik benzinin
53.33333 litresini taşır diyebilirdik.Bu örnekde tabii q=1 litre/km olarak
otonun yakıt tüketimi alınmalıdır.)
Şimdi S>L olacak şekilde bir örnek yapalım;Bu halde P=200
muz,M=1000 muz ve L=100 km q=1 olsun. n=1000/200=5 ve k=n-1=5-1=4 etap
olur.Etaplarımız E(1)=200/(2(5-1)+1)=200/9; 
E(2)=200/(2(5-2)+1)=200/7,  E(3)=200/(2(5-3)+1)=200/5, 
E(4)=200/(2(5-4)+1)=200/3 olup bunların toplamı
E(1)+E(2)+E(3)+E(4)=9920/63=157.46>100 olduğundan paydası en küçük olan
E(4) etabını atalım,kalanların toplamı E(1)+E(2)+E(3)=5720/63=90.79<100
olduğundan algoritmanın 3. adımını uygulayarak taşınabilecek muz sayısı
Q=200-100+90.79=190.79 muz olarak bulunur.
Bu algoritmayı çok sayıda örnek üzerinde denedim, sonuçlar doğru
çıktı, ama matematik ispat ister.Bu nedenle bu algoritmanın kesin doğru
olduğunu ileri sürmüyorum, bir gece uykusuzluğunun sonucu bu algoritmaya
buldum.Ayrıca bu algoritmanın (n)  sayısının kesirli olması halinde
çalışıp çalışmadığını incelemedim, bilmiyorum belki orada da çalışır. Bir
yanlışım varsa bildirilmesi dileklerimle;dikkatli zekaların bilgisine
sunarım.
                                                                                                      
A.Kadir Değirmencioğlu
 
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20080504/f85399a2/attachment.htm