Soru 1
Örnek cevap / çözüm yolu
Verilen algoritmanın işleyişini gösteren sözde kod (pseudocode):
BAŞLA
en_buyuk = A[0]
HER i = 0'dan n-1'e KADAR:
toplam = 0
HER j = i'den n-1'e KADAR:
toplam = toplam + A[j]
EĞER toplam > en_buyuk İSE:
en_buyuk = toplam
SON EĞER
SON DÖNGÜ
SON DÖNGÜ
YAZDIR en_buyuk
BİTİR
Çözüm açıklaması: Tüketme yaklaşımı (brute force) ile dizideki tüm ardışık alt kümelerin toplamı iki iç içe döngü yardımıyla hesaplanır ve elde edilen en büyük toplam güncellenerek bulunur.
Soru 2
Kısa cevap
En büyük toplam: 11
Çözüm yolu ve kontrol
A = \{5, -3, 2, 7, -4, 1\} kümesindeki ardışık elemanların toplamları:
- 5 ile başlayanlar: 5, 5 + (-3) = 2, 5 + (-3) + 2 = 4, 5 + (-3) + 2 + 7 = 11, 5 + (-3) + 2 + 7 + (-4) = 7, 5 + (-3) + 2 + 7 + (-4) + 1 = 8
- -3 ile başlayanlar: -3, (-3) + 2 = -1, (-3) + 2 + 7 = 6, (-3) + 2 + 7 + (-4) = 2, (-3) + 2 + 7 + (-4) + 1 = 3
- 2 ile başlayanlar: 2, 2 + 7 = 9, 2 + 7 + (-4) = 5, 2 + 7 + (-4) + 1 = 6
- 7 ile başlayanlar: 7, 7 + (-4) = 3, 7 + (-4) + 1 = 4
- -4 ile başlayanlar: -4, (-4) + 1 = -3
- 1 ile başlayanlar: 1
Tüm ardışık toplamlar incelendiğinde en büyük değer 5 + (-3) + 2 + 7 = 11 olarak elde edilir.
Soru 3
Kısa cevap
Tablo 1’in doldurulmuş değerleri:
-
1. Sütun (5 ile başlayanlar):
- 5 = 5
- 5 + (-3) = 2
- 5 + (-3) + 2 = 4
- 5 + (-3) + 2 + 7 = 11
- 5 + (-3) + 2 + 7 + (-4) = 7
- 5 + (-3) + 2 + 7 + (-4) + 1 = 8
-
2. Sütun (-3 ile başlayanlar):
- -3 = -3
- (-3) + 2 = -1
- (-3) + 2 + 7 = 6
- (-3) + 2 + 7 + (-4) = 2
- (-3) + 2 + 7 + (-4) + 1 = 3
-
3. Sütun (2 ile başlayanlar):
- 2 = 2
- 2 + 7 = 9
- 2 + 7 + (-4) = 5
- 2 + 7 + (-4) + 1 = 6
-
4. Sütun (7 ile başlayanlar):
- 7 = 7
- 7 + (-4) = 3
- 7 + (-4) + 1 = 4
-
5. Sütun (-4 ile başlayanlar):
- -4 = -4
- (-4) + 1 = -3
-
6. Sütun (1 ile başlayanlar):
- 1 = 1
Çözüm açıklaması: Tabloda verilen her hücre, ilgili başlangıç elemanından itibaren sağa doğru birer eleman eklenerek hesaplanan ardışık toplam sonuçlarını içerir.
Soru 4
Örnek cevap / çözüm yolu
- soruda yapılan hesaplamalar ile Tablo 1’deki değerler birebir aynıdır ve ulaşılan en büyük toplam 11’dir.
Eleman sayısının artmasının etkileri:
- Tüketme yaklaşımında eleman sayısı n olduğunda hesaplanması gereken toplam alt dizi sayısı \frac{n(n+1)}{2} tanedir.
- Kümenin eleman sayısı arttıkça işlem sayısı karesel olarak (O(n^2) zaman karmaşıklığı ile) büyür.
- Bu durum, eleman sayısı fazla olan dizilerde doğru sonuca ulaşma süresini (hesaplama zamanını) ciddi ölçüde artırır. Kadane algoritması gibi gelişmiş yöntemler ise problemi O(n) sürede tek geçişle çözerek hesaplama zamanını minimize eder.
Kitapta kolayca gezin
← Önceki sayfa: 131 · 
Matematik Ders Kitabı 2. Kitap cevapları · Sonraki sayfa: 133 →