Lig Problemi

Lig probleminde bir takım diğer takımlarla sadece bir kez karşılaşır. Karşılaşmalar sonucu takımların toplam galibiyet, mağlubiyet, beraberlik, attığı gol ve yediği gol sayısı elde edilir. Elde edilen bu değerler ile aşağıdaki gibi bir tablo oluşturulur.


Problemin başlangıcında yukarıdaki tablo verilir. Bu tabloya bakarak mümkün tüm durum ve skor sayılarının makul bir sürede bulunması istenmektedir.

İki takım karşılaştığında (ilk takıma göre) sonuç Galibiyet (1), Mağlubiyet (2) veya Beraberlikle (0) sonuçlanabilir. Örneğin; A, B ve C gibi 3 takım karşılaştığında A-B = 1, A-C = 0, B-C = 2 gibi sonuçlar elde edilebilir. A-B = 1 sonucu, A takımının B takımını yendiğini göstermektedir. Bu sonuçlar (1 0 2)  bir durumu oluşturmaktadır. Problem bizden buna benzer tüm durumları bulmamızı istemektedir.

Yukarıdaki (1 0 2) durumuna uygun olarak bu 3 takımın karşılaşma sonuçları A-B = 2-1, A-C = 0-0 ve B-C = 2-4 olabilir. Bu sonuçlar (2-1 0-0 2-4) bir skoru oluşturmaktadır. Problem bizden buna benzer tüm skorların bulunmasını istemektedir.

Lig problemi kombinasyonlar ve sayı parçalama algoritmalarından oluşmaktadır. Problemin çözümü öz yinelemeli bir yapıya sahiptir ve çözümde hız çok önemli bir unsurdur. Bu açıdan bakıldığında progblemin bilgisayarda çözümünün gerçekleştirilmesi için en uygun dillerden biri  C++ programlama dilidir.

Tasarım ve Algoritmalar
Program tasarımı 6 adımdan oluşmaktadır.

Adım 1- Tablo Girişi:

Veriler tablo halinde bir txt dosyasından alınır. Takım isimleri takım matrisinde (Şekil 1.a) tutulur. Diğer sayısal değeler ise matriste (Şekil 1.b) tutulur.

        

           Şekil 1.b

              Şekil 1.a

Adım 2- Rastgele Tablo Oluşturmak:

Rastgele tablo oluşturulurken rastgele skorlar oluşturup bu skorların toplamından bir tablo oluşturulması istenmemektedir. Bu açıdan farklı bir algoritma gereklidir. Rastgele tablo oluşturulurken kullanıcıdan takım sayısı ( örnek: n = 5 takım sayısı) alınır. Ardından karşılaşma sayısı n*(n – 1)/2 formülünden (örnek: 10 karşılaşma) hesaplanır. Karşılaşma sayısı kadar (0-2) arasında rastgele değerler bulunarak bir durum (örnek: 1 0 2 2 2 1 0 0 0 2) oluşturulur. Rastgele oluşturulan duruma bakılarak matrisin G, B ve M sütunları doldurulur. M sütunu Y sütununa kopyalanır. Takımların attığı gol sayıları rastgele olarak aşağıdaki formülde belirtilen aralıktan seçilir.

Galibiyet Sayısı <= x <= ( (Galibiyet Sayısı + Beraberlik Sayısı) * 4 )

Maksimum bir sayı aşağıdaki formül ile belirlenir.

Maksimum Sayı = ((Takım Sayısı – 1)*4) – Takım Sayısı – 1

Bu sayıya bağlı olarak rastgele bir değer seçilip tüm takımların yediği gol sayısı değerlerine eklenir.

Adım 3- Veri Kontrolü:

Veri kontrolünde txt dosyasından girilen yada rastgele oluşturulan tablo kontrol edilir.

Programın bir sonraki adıma geçebilmesi için tablonun aşağıdaki kontrollerden geçmesi gerekir.

-Atılan gol sayısı kadar yenilen gol sayısı olmalıdır.

– Galibiyet sayısı kadar mağlubiyet sayısı olmalıdır.

-Bir takımın maç sayısı, galibiyet ve mağlubiyet sayısının toplamına eşit olmalıdır.

-Beraberlik sayısının kontrolü için graf algoritmasından faydalanılır. Bu algoritmaya göre beraberlik sayıları büyükten küçüğe doğru sıralanır. İlk değer sayı diğer sayılara dağıtılır. Ve tekrardan baştaki işleme dönülür. Ardından tüm değerler sıfırlanmışsa girilen beraberlik durumları geçerlidir denir. Yukarıdaki tabloya göre ;

Örnek:

1- 3 2 1 1 1
2- 0 1 0 0 1
3- 1 1 0 0 0
4- 0 0 0 0 0

Bu örneğe göre beraberlik sayısı doğru girilmiştir.

Adım 4- Eşleşme Grafı, Eşleşme Matrisi ve Değerlendirme Matrisi Oluşturulması:

Takımların birbirleri ile eşleşmeleri bulunur. Bu eşleşmelerin grafı (şekil 4.a) oluşturulur. Ardından bu karşılaşmalar sırası ile eşleşme matrisine (şekil 4.b) yazılır. Skorların bulunmasında kullanılmak üzere değerlendirme matrisi oluşturulur. Değerlendirme matrisi bir takımın kaç maç sonra matris içerisinde ki tüm değerlerinin sıfırlanmış olması gerektiğini gösterir. 5 takım için (şekil 4.c) bakınız. A takımının 4 maç, B takımının 7 maç sonra değerleri kontrol edilmelidir.

        Şekil 4.a

                  Şekil 4.b

          

Şekil 4.c

    Adım 5- Durumların Bulunması:
Durumların bulunması tamamen öz-yinemeli bir yapıdadır. Fonksiyon derinlik (0) “sıfır” dan başlar ve son derinliğe(örnek için: 10. seviye) kadar ilerler. Her derinlik eşleşme matrisindeki bir karşılaşmaya (Örnek 0. derinlik A-B  karşılaşmasıdır) denk düşer. A-B karşılaşmasına bakılır. İlk olarak galibiyet durumu değerlendirilir. Galibiyet şartı sağlanırsa durum için tuttuğumuz geçici bir yığına (şekil 5.b) galibiyet değeri olarak (1) “bir” yazılır. Ardından A takımının galibiyet sayısından ve B takımının mağlubiyet sayısından bir eksiltilerek , fonksiyon derinlik (2) “iki” için tekrar çağrılır. Son derinliğe gelindiğinde geçiçi yığın tüm durumların saklandığı durum yığınına tersden kopyalanır(şekil 5.c).  Şekil 5.a fonksiyonun çalışmasını temsil etmektedir. Aynı hizadaki düğümler aynı derinliğe karşılık düşmektedir. Düğümlerde aşağıya doğru inilirken matris giderek sıfırlanmaktadır. Eğer Galibiyet, Mağlubiyet ve Beraberlik durumu yoksa bir önceki düğüme geri dönülür ve bir önceki düğümde matrisden silinen değerler geriye alınır. Bu sayede fonksiyon tamamen sonlandığında matris bozulmadan kalmış olur. Şekilde  “X” işareti ile gösterilen düğümler daha önce kontrol edilmiş ve kapanmış olan fonksiyonları göstermektedir. “Null” değeri ile gösterilen düğümler ise henüz kontrol edilmemiştir. Bu düğümlere sonraki adımlarda bakılacaktır.

 Şekil 5.b

   Şekil 5.a

Şekil 5.c

    Adım 6- Skorların Bulunması:
Skorların bulunmasındaki mantık, durumların bulunmasındaki mantık ile aynıdır. Ağaç yapısı gibi çalışan öz-yinelemeli bir fonksiyon kullanılır. Bulunan durumlardan sırası ile bir durum seçilir. Ardından seçilen bu duruma bakarak skorlar üretilir. Seçilen durum örnek: 1 0 2 2 2 1 0 0 0 2 olsun.
İlk karşılaşmadan (0. karşılaşmadan) başlanır. A-B = 1 için A ve B takımın alabileceği maksimum skor belirlenir.  Bunun için A ve B takımının tablonun o anki durumuna bağlı olarak atabileceği maksimum gol sayısı ve yiyebileceği maksimum gol sayısı aşağıdaki formülden belirlenir.
A takımının Atacağı Maksimum Gol Sayısı = Attığı Toplam Gol Sayısı – Galibiyet Sayısı + 1
Örnek: Atacağı Max Gol = 7 – 2 + 1 = 6
A takımın Yiyeceği Maksimum Gol Sayısı = Min( Attığı Toplam Gol Sayısı – Galibiyet Sayısı, Yediği Toplam Gol Sayısı – Mağlubiyet Sayısı)
Örnek: Yiyeceği Max Gol = Min(7-2, 3-0) = 3
B takımının Atacağı Maksimum Gol Sayısı = Min( Attığı Toplam Gol Sayısı – Galibiyet Sayısı, Yediği Toplam Gol Sayısı – Mağlubiyet Sayısı)
Örnek: Atacağı Max Gol = Min(7-1, 5-0) = 5
B takımının Yiyeceği Maksimum Gol Sayısı = Yediği Toplam Gol Sayısı – Mağlubiyet Sayısı + 1
Örnek: Yiyeceği Max Gol = 5 – 0 + 1 = 6
Bulunan bu değerlerden A – B maçının maksimum değeri aşağıdaki formül ile bulunur.
A için Min(A takımının atacağı max gol, B takımının yiyeceği max gol)
Örnek: A = Min(6,6) = 6
B için Min(B takımın atacağı max gol, A takımın yiyeceği max gol)
Örnek: B = Min(5,3) = 3
Sonuç olarak A-B karşılaşması maksimum (6,3) skoru ile bitebilir. Fakat problemde maksimum atılabilecek gol sayısı 4 olarak belirlendiği için bulunan değerler kontrol edilir. Buna göre A-B maçı maksimum (4-3)  ile bitebilir(A takımı B takımını yendiği için). Bu durumda
A > 4 ise A = 4 değeri verilir. B > 3 ise B = 3 değeri verilir. Eğer A-B karşılaşması 4-3 ile bitebiliyorsa 4-3 skorunun alt parçalanmalarıyla da bitebilir. (4-2, 4-1, 4-0, 3-2 …) Bir skor parçalanması seçilir (örneğin 4-3) . A takımın galibiyetinden 1, attığından 4 çıkartılır. B takımının mağlubiyetinden 1, yediğinden 3 çıkartılır. Bulunan bu skor, geçici skor yığınına atılır. Ardından fonksiyon bir sonraki derinlik değeri için tekrar çağrılır.
Fonksiyon her çağrıldığında o anki karşılaşma sayısının değerlendirme matrisindeki bir değer ile eşleşip eşleşmediğine bakılır. Eğer eşleşme varsa değerlendirme matrisinin o indisi hangi takımın matristeki değerlerinin tamamen sıfırlanmış olması gerektiğini belirtir. Aksi takdirde kontrol yapılmaz bu sayede gereksiz kontrol işlemlerinden kaçınılarak programın hızlı bir şekilde icrası gerçekleştirilir.
Örneğin: Karşılaşma No : 4 olduğunda Değerlendirme Matrisinde [4,7,9], 4 (0. indis)  ile eşleşir. Matriste 0. İndis A takımını göstermektedir. Öyleyse A takımının tüm değerleri sıfırlanmış olmalıdır. Eğer değerler sıfırlanmamışsa bir önceki adıma geri dönülür ve matristen çıkarılan değerler geriye alınır. Geçici skor yığınından bir en üstteki değer çıkartılır.
Bu şekilde devam edilerek son derinliğe gelinir. Bir skor bulunduğunda tüm skorların tutulduğu skor yığınına atılır. Şekil 6.a bu fonksiyonun nasıl çalıştığını temsil etmektedir. Tablolar o anki derinlikte matrisin son durumunu göstermektedir. “X” simgesi ile gösterilen düğümler daha önceden bakılan skorları belirtmektedir. “NULL” ile gösterilen düğümler ise henüz bakılmamış skorlardır. Bu skorları sonraki adımlarda bakılacaktır.

Şekil 6.a

Lig problemini Linux işletim sisteminde Netbeans idesini kullanarak geliştirdim. Kaynak kodları kopyalayıp yapıştırarak kendi geliştirme ortamınızda kullabilirsiniz. Projenin kaynak kodunu indirmek için bu adrese tıklayın. Umarım ufkunuzu açmak adına ve öz yinelemeli kod mantığını daha iyi anlamanız açısından faydalı olmuştur.

3 thoughts on “Lig Problemi

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s