2013 Yılı Soruları - KTÜ Bilgisayar Mühendisliği

KARADENİZ TEKNİK ÜNİVERSİTESİ
BİLGİSAYAR MÜHENDİSLİĞİ
4. BİLGİSAYAR OLİMPİYATLARI
FİNAL SORULARI
08 Mayıs 2013 Çarşamba, Saat 13:00
SORU : 1 DEĞERİ : 100 PUAN
HAZIRLAYAN : Öğr.Gör. Ömer ÇAKIR
Robot İzleme (Robot Tracing)
Önüne çıkan engelleri aşağıda anlatılan algoritmaya göre aşıp çıkış noktasına ulaşan bir robotun
başlangıç noktasından çıkış noktasına kadar hangi güzergahı izlediğini belirlemeniz istenmektedir.
Robot, doğu (X-ekseni) ve kuzey (Y-ekseni) olmak üzere iki yönde hareket kabiliyetine sahiptir.
Robotun bulunduğu ortam ve engeller şekildeki gibi bir matris ile temsil edilmiştir. mxn boyutlu bir
matris için robotun başlangıç noktası BN=(0,0), çıkış noktası ÇN=(m-1,n-1)‘dir. m ve n değeri en fazla
20000 olabilir. Robot hareket ederken, o anki konumundan çıkış noktasına doğru olan vektörün (X,Y)
bileşenlerinden büyük olanı doğrultusunda ilerleyecektir. İkisi eşit olursa X-ekseni (doğu) boyunca
ilerleyecektir. Eğer hesaplanan yönde bir engel varsa diğer yönde gidilmeye çalışılacaktır. Sonra yine
çıkış noktasına doğru olan vektörün (X,Y) bileşenlerine göre yön belirlenecektir.
Aşağıda örnek giriş/çıkış dosyaları verilmiştir. Giriş dosyasında ilk iki değer sırasıyla m ve n’dir.
Yani matrisin sütun ve satır büyüklükleridir. Üçüncü değer ortamdaki engellerin sayısıdır. Sonraki
satırlar da bu engellerin başlangıç ve bitiş koordinatlarıdır. Çıkış dosyasına robotun izlediği güzergaha
ait koordinatlar ve adım sayısı yazılmıştır. Eğer robot hiçbir yönde ilerleyemezse çıkış dosyasına sadece
hareketsiz kaldığı koordinat yazılacaktır.
giris.txt
8 8 2
3 2 5 2
5 4 5 6
1 satır boşluk
8 8 2
3 2 5 2
5 4 5 7
cikis.txt
STEPS = 14
( 1, 0 )
( 1, 1 )
( 2, 1 )
( 2, 2 )
( 2, 3 )
( 3, 3 )
( 4, 3 )
( 4, 4 )
( 4, 5 )
( 4, 6 )
( 4, 7 )
( 5, 7 )
( 6, 7 )
( 7, 7 )
1 satır boşluk
7
ÇN
6
5
4
3
2
1
Y=0
BN
( 4, 7 )
X=0
1
2
3
4
5
6
7
Değerlendirme Kriterleri
Program çıkış dosyasının doğruluğuna göre 70 puan; programın koşma süresine göre de 30 puan üzerinden
değerlendirilecektir. Koşma süresi açısından değerlendirilebilmek için çıkış dosyanın doğru olması şarttır.
KARADENİZ TEKNİK ÜNİVERSİTESİ
BİLGİSAYAR MÜHENDİSLİĞİ
4. BİLGİSAYAR OLİMPİYATLARI
FİNAL SORULARI
08 Mayıs 2013 Çarşamba, Saat 13:00
SORU : 2 DEĞERİ : 100 PUAN
HAZIRLAYAN : Araş. Gör. Çağatay M. YILMAZ
Sudoku Kontrolcüsü
Sudoku, Japoncada "sayılar tek olmalı" anlamında gelen popüler bir boşluk doldurma oyunudur. Oyunda
9x9'luk bir matris R={1,2,3,4,5,6,7,8,9} kümesindeki rakamlar ile aşağıdaki kurallar göz önüne alınarak
doldurulur.



Her bir satırda R kümesindeki rakamlar sadece bir defa bulunmalıdır.
Her bir sütunda R kümesindeki rakamlar sadece bir defa bulunmalıdır.
Her bir alt matris bloğunda R kümesindeki rakamlar sadece bir defa bulunmalıdır.
Alt matris bloğu, 3x3 boyutunda alt matrislerdir, bir sudoku matrisinde 9 tane bulunurlar ve hiçbiri bir diğeri ile
çakışmaz.
Şekil 1'de örnek bir sudoku matrisi ve çözümü verilmiştir. Yukarıda da anlatıldığı gibi sudoku çözümünde aynı
satır, sütun ve alt matrislerde R kümesindeki tüm rakamlar sadece birer kez kullanılmıştır.
Şekil 1. Boş bir Sudoku Matrisi ve Çözümü
Giris1.txt içeriğindeki bir girdi dosyayı okuyan ve yukarıda belirtilen kurallara göre bir sudoku matrisinin doğru
çözülüp çözülmediğini kontrol eden uygulamayı geliştiriniz. Uygulama öncelikle dosyadan okuduğu değerleri
matris şeklinde ekrana basmalı ve daha sonra aşağıdaki durumlarda gerekli başarı veya hata çıktılarını vermelidir.



Giris1.txt dosyasındaki gibi uygulama doğru çözülmüş bir sudoku matrisi girildiğinde "Sudoku doğru
çözülmüş." çıktısını vermelidir.
Giris2.txt dosyasındaki gibi içerisinde 'c' gibi R kümesinde olmayan bir karakter olduğunda "i. satır j.
sütunda geçersiz c karakteri var." hata çıktısını vermeli ve devamında sudoku kontrolünü yapmamalıdır.
Giris3.txt dosyasında olduğu gibi i. satır ve j. sütunda tekrarlayan bir değer varsa aşağıdaki hata çıktılarını
vermelidir. (Sudoku matrisinde tekrarlayan 1 eleman varsa aşağıdaki 3 hatada oluşmuştur.)
 i. satırda aynı değer tekrarlamış.
 j. sütunda aynı değer tekrarlamış.
 k. alt matriste aynı değerler tekrarlanmış. (Alt matris numaraları Şekil 1'deki gibidir.)
Değerlendirme Kriterleri:
Uygulamanın değerlendirilebilmesi için .txt formatındaki dosyaları hata vermeden okuyabilmeli ve
okunan matris içeriğini ekrana matris şeklinde basabilmelidir. Uygulama her çalıştırıldığında Giris1.txt,
Giris2.txt ve Giris3.txt dosyalarından birisi verilecek ve yukarıdaki kriterlere göre başarısı ayrı ayrı
değerlendirilecektir.
Puanlama:
 Dosyadan matris değerlerini okuma ve ekrana basma: 15 puan.
 Giris2.txt dosyasındaki gibi R kümesinde olmayan hatalı değer tespiti: 15 Puan
 Giris3.txt dosyasındaki gibi tekrarlayan değer tespiti ve hatanın olduğu satır sütun bilgisini
yazdırma: 30 Puan
 Giris3.txt dosyasında ki gibi 3x3'lük herhangi bir alt matristeki hatayı bulma ve hatalı alt matrisin
numarasını yazdırma: 40 Puan
KARADENİZ TEKNİK ÜNİVERSİTESİ
BİLGİSAYAR MÜHENDİSLİĞİ
4. BİLGİSAYAR OLİMPİYATLARI
FİNAL SORULARI
08 Mayıs 2013 Çarşamba, Saat 13:00
SORU : 3 DEĞERİ : 100 PUAN
HAZIRLAYAN : Uzman Zafer YAVUZ
Yüzey doldurma işlemini hazır fonksiyon kullanmadan doldurmanız istenmektedir. Giriş
dosyasında verilen koordinatları köşe noktaları alıp, bu noktalardan konveks bir poligon oluşturunuz.
Oluşan bu poligonun içini doldurarak çıkış dosyasına yazınız. Çıkış dosyasında siyah bölgeler için 0 ve
beyaz bölgeler için 1 değeri yazınız.
Giriş dosyasında poligonun köşe koordinatları verilmektedir. -1 değerini okuyana kadar giriş
dosyasında koordinatlar yazılıdır. -1 değeri okununca en son okunan nokta ile ilk nokta birleştirilerek
kapalı bir poligon oluşturulur.
Aşağıda örnek bir giriş dosyası ve çıkış dosyasının resmi görülmektedir. Poligonun çizileceği
yüzeyin boyutlarını 100x160 olarak alınız. Değerlendirme yapılırken önce doğruluk daha sonra da hız
kontrol edilecektir. (%70 doğruluk, %30 hız)
Giriş Dosyası
40,34
83,14
101,51
33,77
40,34
-1
Çıkış Dosyasının Görüntüsü (Font küçültülerek resmedilmiştir.)
KARADENİZ TEKNİK ÜNİVERSİTESİ
BİLGİSAYAR MÜHENDİSLİĞİ
4. BİLGİSAYAR OLİMPİYATLARI
FİNAL SORULARI
08 Mayıs 2013 Çarşamba, Saat 13:00
SORU : 4 DEĞERİ : 100 PUAN
HAZIRLAYAN : Uzman Zafer YAVUZ
N = 10.000 olmak üzere sayısal değerleri N’den küçük olan ve bir dik üçgenin kenarları olabilecek
tüm tam sayı üçlülerini cikis.txt dosyasına yazınız. Benzer üçgenler için ayrı bir hesap yapmayınız.
Örneğin (3,4,5) üçlüsü bir dik üçgenin kenarları olabileceği gibi (6,8,10) üçlüsü de bir dik üçgenin
kenarları olabilir. Ancak (6,8,10) üçlüsü (3,4,5) üçlüsünün tam katları olduğundan ayrı bir çözüm olarak
kabul edilmez. Bu nedenle (6,8,10)’u cikis.txt dosyasına yazmayınız. (Sorunun çözümünde şablon
main.cpp dosyasını kullanınız)
Değerlendirme
Tam çözüm : 100p
Benzer üçgenleri dikkate almayarak tam çözüm : 30p
Tam çözüm yapanlar arasında;
En hızlı çözen : +50p
2. en hızlı çözen : +30p
3. en hızlı çözen : +15p
Örnek giriş ve çıkış dosyaları
Giriş.txt (N)
Cikis.txt
10000
(3,4,5)
(5,12,13)
…