sonsuz Kurucu sordu 6 gün önce
Bir bilgisayar tamircisi o gün içerisinde hangi bilgisayarları tamir edeceğine bir gün öncesinden kendisine verilen taleplerdeki bilgisayar geliş saatleri ve tamirin ne kadar süreceği bilgisini kullanarak karar vermektedir. Aynı anda sadece bir bilgisayar tamir edebildiğinden ve bir bilgisayar gelir gelmez tamire başlamak istediğinden, kendisine gelen talepler içinden bazılarını reddetmek zorunda kalmaktadır. Çünkü bilgisayar geliş saati ve tamir bitiş saatleri örtüşen iki bilgisayar varsa bunlardan sadece bir tanesini seçebilir.
Örnek vermek gerekirse, gelen talepler:
A: sabah 9’da gelecek ve tamir 2 saat sürecek
B: sabah 10’da gelecek ve tamir yarım saat sürecek
C: sabah 11’de gelecek ve tamir 3 saat sürecek
ise tamirci A ve B bilgisayarlarından birisini reddetmek zorundadır. Yani o günün tamir planında ya A ve C olacaktır ya da B ve C olacaktır.
Tamircinin hedefi o gün içerisinde en fazla sayıda bilgisayar tamir etmek olduğundan tamirci için aşağıdaki gibi bir algoritma tasarladık:
- Bilgisayarları tamir bitiş zamanlarına göre küçükten büyüğe sırala. Bu sıralamaya göre sıralanmış bilgisayarlara A1, A2, .. An diyelim.
- A1’i o günkü tamir planına ekle.
- 2. bilgisayardan n. bilgisayara kadar sıra ile aşağıdaki işlemi gerçekleştir: Eğer sıradaki bilgisayarın geliş saati plana en son eklenmiş bilgisayarın bitiş saatinden sonra ise sıradaki bilgisayarı tamir planına ekle, değil ise bilgisayarın sahibine bilgisayarının tamirinin o gün yapılamayacağını bildir.
Bu verilen algoritma, o gün için karşılanabilecek en fazla talep sayısında talebi plana koyar. Bu algoritmayı yukarıdaki örneğe uyguladığımızda bilgisayarlar tamir bitiş saatlerine göre B, A, C olarak sıralanacaklar ve algoritmamız B ve C bilgisayarlarını o gün tamir edilecek bilgisayarlar olarak belirleyecektir.
Soru 16: Aşağıda verilmiş tamir taleplerine göre algoritmamız hangi bilgisayarları o günün tamir planına ekler?
| A1 | A2 | A3 | A4 | A5 | |
|---|---|---|---|---|---|
| Geliş saati | 9:00 | 10:00 | 10:30 | 14:00 | 15:00 |
| Tamir süresi | 5 saat | 3.5 saat | 2 saat | 3 saat | 1.5 saat |
Soru 17: Aşağıda verilmiş tamir taleplerine göre aşağıdaki değişikliklerden hangisi yapılırsa o gün 3 tane bilgisayar tamir edilebilir?
| A1 | A2 | A3 | A4 | A5 | |
|---|---|---|---|---|---|
| Geliş saati | 9:00 | 10:00 | 10:30 | 14:00 | 15:00 |
| Tamir süresi | 5 saat | 3.5 saat | 2 saat | 3 saat | 1.5 saat |
Soru 18: Aşağıda verilmiş tamir taleplerine göre en fazla kaç bilgisayar o gün tamir edilebilir?
| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| Geliş saati | 9:00 | 11:00 | 8:00 | 13:00 | 11:00 | 14:00 | 16:00 | 16:00 | 10:00 | 20:00 |
| Tamir süresi (saat) | 3 | 2 | 6 | 2 | 5 | 4 | 3 | 4 | 1 | 12 |
Soru 19: Algoritmamızı aşağıda verilmiş tamir taleplerine uyguladığımızda hangi bilgisayarlar tamir planına eklenir?
| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| Geliş saati | 8:00 | 7:00 | 10:00 | 13:00 | 11:00 | 10:00 | 14:00 | 15:00 | 12:00 | 16:00 |
| Tamir süresi (saat) | 2 | 3.5 | 4 | 2 | 4.5 | 6 | 2.5 | 2 | 5.5 | 2 |
Soru 20: Aşağıda verilen tamir taleplerini göz önüne aldığımızda ve verilen algoritma uygulandığında, A4 ve A5 no’lu taleplerin tamir planında yer almaması için sondaki A8 talebinin başlangıç saati ve süresi şıklarındakinden hangisi olabilir?
| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | |
|---|---|---|---|---|---|---|---|---|
| Geliş saati | 8:00 | 7:00 | 10:00 | 12:00 | 15:00 | 14:00 | 13:00 | ? |
| Tamir süresi (saat) | 3 | 2 | 1.5 | 3 | 1 | 3 | 4.5 | ? |