Soru
Aşağıda verilen 20x20'lik haritada(tabloda) aşağı-yukarı, sağdan-sola ve çapraz olarak ardışık 4'lülerin oluşturduğu en büyük çarpım nedir?
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
Örneğin 26 x 63 x 78 x 14 = 1788696
Çözüm
Probleme farklı yöntemlerle yaklaşmak mümkün. Fakat kullanılacak metotlar genel olarak aynı. Sadece hızlandırmak için tüm olasılıkları değil de yüksek olma ihtimali olanları değerlendirme gibi yöntemlere gidilebilir.
Örneğin 20x20 değil de 1000000x1000000 olduğunu ve işlem hızının fazla zorlandığını farz edelim. Bu gibi bir durumda 80 üzeri olan sayıların yerini belirleyip, sadece onlar için bu işlemi yapabiliriz. Nitekim istatistiksel olarak böyle bir karede 90 üzerine bile bakabilirsiniz, çünkü illa ki 90 üzeri olanlar peş peşe gelecektir. 0-10 arasında olanları atlamak bile büyük zaman kazandırır.
Lafı fazla dolandırmadan neler yaptığımıza gelelim.
Kodlama
Öncelikle tabloyu bir stringe(string harita) aktardım. Sonrasında her bir satır ve sütunu tutacak iki boyutlu bir diziye ekledim. i sütun, j ise satır değerlerini tutuyor.
string[] sayilar = harita.Split(' ');
int[,] dizi = new int[20, 20];
int maks = 0;
int s = 0;
for (int i = 0; i < 20; i++) // i sütunlar
{
for (int j = 0; j < 20; j++) // j satırlar
{
dizi[i, j] = Convert.ToInt32(sayilar[s]);
s++;
}
}
Sonrasında ayrı ayrı üç fonksiyon oluşturdum. Bunlar dikeyde maksimumu, yatayda maksimumu ve çaprazda maksimumu bulan fonksiyonlar. Çaprazda iki farklı durum olduğuna dikkat edin, ben aynı fonksiyonda iki durumu da ele aldım.
static int DikeyCarpim_Maksimum(int[,] dizi)
{
int maks = 0, carpim = 0;
for (int i = 0; i <= 16; i++)
{
for (int j = 0; j < 20; j++)
{
carpim = dizi[i, j] * dizi[i + 1, j] * dizi[i + 2, j] * dizi[i + 3, j];
if (carpim > maks)
maks = carpim;
}
}
return maks;
}
static int YatayCarpim_Maksimum(int[,] dizi)
{
int maks = 0, carpim = 0;
for (int i = 0; i < 20; i++)
{
for (int j = 0; j <= 16; j++)
{
carpim = dizi[i, j] * dizi[i, j + 1] * dizi[i, j + 2] * dizi[i, j + 3];
if (carpim > maks)
maks = carpim;
}
}
return maks;
}
static int CaprazCarpim_Maksimum(int[,] dizi)
{
int maks = 0, carpim = 0;
for (int i = 0; i <= 16; i++)
{
for (int j = 0; j <= 16; j++)
{
carpim = dizi[i, j] * dizi[i + 1, j + 1] * dizi[i + 2, j + 2] * dizi[i + 3, j + 3];
if (carpim > maks)
maks = carpim;
}
}
for (int i = 0; i < 17; i++)
{
for (int j = 3; j < 20; j++)
{
carpim = dizi[i, j] * dizi[i + 1, j - 1] * dizi[i + 2, j - 2] * dizi[i + 3, j - 3];
if (carpim > maks)
maks = carpim;
}
}
return maks;
}
Bu fonksiyonlardan dönen sonuçlar karşılaştırıldığında:
Sonuç : 70600674
Çözüm 1ms sürdü.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
Hiç yorum yok:
Yorum Gönder