TÜBİTAK – 2023 Bilim Olimpiyatları – Bilgisayar – A Kitapçığı – Soru 40

Soru : B dizisi [ 1, -4, 3, 4, -2, 6, -5, 2] değerlerini içeren 8 elemanlı bir dizi
olsun. Aşağıdaki mystery fonksiyonu, mystery(B,0,7) şeklinde çağrılırsa hangi
değeri döner?

#include<stdio.h>

int f(int A[], int l, int m, int h) 
{
	int SL = -10000, SR = -10000;
	int t = 0, i, j;
	for (i = m; i >= l; i--) 
	{
		t = t + A[i];
		if (t > SL) 
		{
			SL = t;
		}
	}
	t = 0;
	for (j = m+1; j <= h; j++) 
	{
		t = t + A[j];
		if (t > SR) 
		{
			SR = t;
		}
	}
	return SL + SR;
}
int mystery(int A[],int l, int h)
{
	if (h == l)
		return A[l];
	else 
	{
	int m = (l + h)/2;
	int left = mystery(A, l, m);
	int right = mystery(A, m+1, h);
	int X = f(A, l, m, h);
	if ( left >= right && left >= X )
		return left;
	else if ( right >= left && right >= X)
		return right;
	else
		return X;
	}
}

main()
{
	int B[] = {1,-4,3,4,-2,6,-5,2};
	printf("Sonuc = %d",mystery(B,0,7));
}

Cevap : Verilen mystery fonksiyonu verilen dizideki en büyük ardışık sayılar toplamını hesaplayan özyinelemeli bir fonksiyondur. İlk olarak mystery fonksiyonu dizinin ortasındaki indis olan m’yi hesaplar. Özyinelemeli olarak dizinin ilk yarısındaki (l ve m indeksleri arası elemanları içeren) en büyük ardışık sayı toplamını hesaplar ve bu değeri left değişkenine atar. Sonra yine özyinemeli olarak dizinin ikinci yarısındaki (m+1 ve h indeksleri arası) en büyük ardışık sayı toplamını hesaplar ve bu değeri right değişkenine atar. Dizinin bütünündeki maksimum ardışık sayı toplamını veren alt dizi tamamen ilk yarı veya tamamen ikinci yarıda olabileceği gibi, bir kısmı ilk yarı bir kısmı ikinci yarıda da olabilir. f fonksiyonu bir kısmı ilk yarıda, bir kısmı ikinci yarıda olan en büyük ardışık sayı toplamını hesaplamak için şu basamakları izler: ilk olarak m indeksinden sola doğru giderek ilk yarıda bulunan ve m indisindeki elemanı içeren maksimum ardışık toplamı bulur, bunu SL değişkeninde tutar;
daha sonra aynı şekilde m indeksinden sağa doğru giderek ikinci yarıda bulunan ve m+1 indisindeki elemanı içeren maksimum ardışık toplamı bulur, bunu SR değişkeninde tutar. SL ve SR’nın toplamı m ve m+1 indislerindeki elemanların her ikisini de içeren en büyük ardışık sayı toplamını verir, f fonksiyonu bu değeri döner. mystery fonksiyonu f fonksiyonunun döndüğü değeri X değişkenine atar. Sonra X, left ve right değişkenlerinin değerleri arasındaki maksimumu bulur, bu dizideki en büyük ardışık sayılar toplamıdır. B dizisinde toplamı maksimum olan ardışık sayılar dizisi 3, 4,-2 ve 6 olup, toplamları 11’dir.