2013 Yılı Soruları - KTÜ Bilgisayar Mühendisliği
Transkript
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) …