�ݺ�ߣ

Gazete dağ ıtım similasyonu

Bir gazetenin 2 tane basımevi var. Gazeteler n (2<N< p>

Problemin şartlarına göre programın girdisi GIRDI2.TXT

adındaki metin dosyasından okunacaktır. Bu metin dosyanın

yapısı şöyledir:

1’ci satır : şehir sayısı(n).

2’ci satır : yolların sayısı(t).

3’cü satırdan itibaren t adet satır : 3 adet tam sayıdan oluşan i

şehri (yada basımevi) ile j şehri arasında k km’lik yolla

doğrudanbağlantı olduğunu gösteren i j k bilgileri. Bu giriş

dosyanın ilk iki satırı n ve t (int tipinde değişkenler) olarak

okuyarak üçüncü satırdan itibaren veri[i][j] (1<=i<=60; 1<=j<=3)

boyutundaki int tipli bir dizi olarak okunuyor. Sonra her bir

basımevinden her bir şehire en kısa yolu içerecek olan int

tipindeki dizi[i][j] (1<=i<=2; 1<=j<=60) dizisinin tüm

elemanlarına 1000 (yani çok büyük bir değer ki, sonradan daha

da kısa yol bulunup yerine yazılsın) atanır. Sonra veri[i][j] dizisi

kisayol() prosedürünün içerisinde işlenir: direk basımeviyle

bağlantıları olan şehirlere kadar yol uzunlukları dizi[i][j]

(1<=i<=2, 1<=j<=60 olması şartıyla dizi[i][j] – i’inci

basımevinden j’inci şehire kadar olan uzaklık) içerisine

kaydedilir, bu işlemleri yaparken de direk basımeviyle

bağlantısı olan bir şehrin(A) başka bir şehir(B) ile bağlantısı

mevcutsa, A’nın basımeviyle arasındaki uzaklığa A ve B

şehirlerin arasındaki uzaklık ilave edilerek dizi[i][B] dizi

elemanına, yani dizi[i][j]’nin B şehir ile ilgili kısıma atanır

(kaydetmeden önce karşılaştırma yapılır- eğer dizi[i][B]’deki

sayi daha küçükse, bu halde atama gerçekleştirilmez öylece

dizi[i][j] içerisindeki bilgiler en aza (en kısa yol) indirilmiş olur).

Örnek olarak aşağıdaki şemayi göz önüne alalım: buradaki –1

ve –2 ile gösterilen birimler- basımevler, 1’den 4’e kadar olanlar

- birer şehir ve bağlantılar üzerindeki yazılan sayılar - yol

uzunluklarıdır:

Yukarıda anlattığım algoritma bu şemaya göre öyle çalışır: (-1)

basımevinden (1) şehire olan (3) uzaklık dizi[1][1]’ e kaydedilir,

sonra (1)’in (2)’iyle bağlantı olduğundan dolayı 3+3 ilave

edilerek dizi[1][2]’ye kaydedilir ve ondan sonra da (-1)’den

(2)’ye (7) uzaklığın olduğu ortaya çıktığında artık bu değer

dizi[1][2]’ye kaydedilmez çünkü oraya daha önce attığımız (6)

değeri 7’den daha küçüktür... Gördüğümüz gibi algoritma (-1)

basımevinden (2) şehire kadar en kısa uzaklığı 6 olarak bilmiş

ve gerçekten insan gözüyle analiz yaparsak (-1) basımevinden

(2) şehire kadar en kısa uzaklığı 6 olduğunu görüyoruz...

Yukarıdaki anlattığım kisayol() prosedürü

yolun sadece bir şehirden geçme

ihtimalini inceliyor, ama bu şartlarda yol

bulunamayabilir ya da yandaki verilen

şekilde görüldüğü gibi birkaç şehir

üzerinden daha kısa bir yol bulunabilir(

-1’den 4’e yol uzunluğu 1 ve 2

şehirlerinden geçtiğimizde daha kısadır).

Bu hatayi düzeltmek amacıyla hem yeni verileri olan dizi[i][j]

dizisi hem de problemin verilerini içeren veri[i][j] dizisi incele()

prosedüründe incelenir.

Bu prosedürde dizi[i][j] dizisndeki verilen (i) basımevinden (j)

şehrine olan uzaklıkları direk olduğunu kabul eder ve kisayol()

prosedüründeki algoritmaya benzer bir şekilde çalışır : dizi[i][j]

dizisindeki herbir A şehrinin veri[i][j] dizisine göre bir B şehri ile

bağlantısı mevcutsa, A’nın basımeviyle arasındaki uzaklığa A

ve B şehirlerin arasındaki uzaklık ilave edilerek dizi[i][B] dizi

elemanına, yani dizi[i][j]’nin B şehri ile ilgili kısmına atanır.

Ama bazı problem şartlarında incele() prosedürün bir defa

kullanılması yeterli olmuyor. Dolaysıyla incele() prosedürün kaç

defa çalıştırılması gerektiğini tespit eden ve çalıştıran

algoritmaya ihtiyaç duyuyoruz.

do incele(); while(devam());

Yukarıda görüldüğü gibi algoritma devam() procedürün 0’a eşit

olmasına kadar incele() prosedürünü çalıştırır. Burada devam()

prosedürü eğer dizi[i][j] dizisinin herhangi bir elemanı 1000’e

eşit olursa yani yolun bulunamadını tespit ederse ‘1’ , aksi

halde ‘0’ değerini veriyor. Öylece tüm mevcut yolların

bulunması sağlanır.

Buraya kadar anlattığım işlemler dizi[i][j] dizisini herbir

basımevinden herhangi bir şehire kadar olan en kısa yollarını

içeren bir dizi haline getirir. Daha önce gösterdiğim örneğe göre

dizi[i][j] aşağıdaki hale gelir:

Dizi[i][j] j=1 j=2 j=3 j=4

i=1 3 6 11 13

i=2 14 11 6 18

Şimdi ise amacımız kamyonların hangi basımevinden hangi

şehirlere gittiğini tespit ederek toplam katettikleri mesafeyi

bulmaktır.Bunun için son() prosedürünü çalıştırmaktayız. İlk

önce herhangi bir şehir için hangi basımevi daha yakın

olduğunu tespit edip işaretlememiz gerek:

Şekilde gösterildiği gibi –1 basımevi için 1, 2 ve 4 şehirleri –

2’ye göre daha yakındır, ama problemin şartlarına göre –1

basımevinde sadece n/2=4/2=2 tane kamyon bulunmaktadır.

Dolaysıyla toplam kattedilen mesafeyi en az etkileyecek şekilde

–1 basımevinden gidilecek sadece iki tane şehir seçmemiz

gerekiyor. Bunu yapmak amacıyla 1, 2 ve 4 şehirleri için –1 ve

–2 basımevine kadar uzaklıkların farklarını alalım:

Bu farklardan en küçüğü olan sonucu en az etkileyendir,

dolaysıyla ya 2 ya da 4 şehrine gazete –2 basımevi tarafından

dağıtılacaktır. Mesela 2 şehrini seçelim, o zaman dizi aşağıdaki

gibi olur:

Yukarıdaki gördüğümüz ifade son() prosedürün sonucudur. Ve

bundan sonraki işlemler aşağıdaki gibidir:

i-) İşaretli kısımlarının toplamı bulunur:

3+11+6+13=33

ii-) İşaretlere dayanarak hangi basımevinden hangi şehirlere

gidileceği tespit edilir:

–1: 1 4

–2: 2 3

iii-) i-) ve ii-)’deki sonuçlar CIKTI2.TXT dosyasına kaydedilir.

Sonuç :

Yukarıda gösterdiğim örnek aslında çok kolaydır, yani

bilgisayara gerek duyulmadan çözülebilir, ama şehir sayısı

50’lere, yol sayısı ise 100’lere çıkınca bu çok karmaşık bir

problem olabilir ve çözülmesi zorlaşır, işte Gazete Dağıtım

programı bu amaçla �ⲹ��ı��ış��ı��

�ݺ�ߣ

Gazete dağıtım similasyonu

More Related Content

Gazete dağıtım similasyonu