Ben bunu şöyle düşündüm: Her hane, toplam beş tane çarpıma katkıda bulunuyor. Bazen kendisinden önce başlamış olan bir beşlinin sonlarındaki bir çarpan oluyor, bazen de kendisinden sonraya doğru da uzayan beşlilerin çarpanı oluyor.
Değeri 5 olan bir haneye bakalım. Ardışık sayılardan oluşan pencereyi sağa doğru kaydırdıkça bu hanenin katkıda bulunduğu 5 çarpım aşağıdakilerdir.
'
... 1 2 3 4 5 6 7 8 9 ... <-- haneler
--> [1 2 3 4 5]
[2 3 4 5 6]
[3 4 5 6 7]
[4 5 6 7 8]
[5 6 7 8 9] -->
'
Baştaki ve sondaki sayılar 5'ten daha az çarpıma katkıda bulunabilirler. Onlara özel muamele yapmak yerine, başta ve sonda 4'er tane daha çarpım varmış gibi işlem yaptım ve sonradan o uçlardaki fazlalıkları gözardı ettim.
Bu mantığı yürüterek yazdığım program şu:
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
struct EnBüyükÇarpım
{
int değer;
int yer;
string toString()
{
return format("değer: %s, yer: %s", değer, yer);
}
}
/**
* En büyük değeri ve en büyük değerin yerini döndürür.
*/
EnBüyükÇarpım hesap(const char[] sayı, int pencereGenişliği)
{
/*
* Başta ve sonda pencere genişliğinin bir eksiği kadar fazlalık
* kullanıyoruz. Örneğin pencere genişliği 5 olduğunda 4'er tane fazlalık
* olacak.
*/
int fazlalık = pencereGenişliği - 1;
int[] çarpımlar = new int[sayı.length + (2 * fazlalık)];
/* Bütün çarpımlar 1'le başlayacak. */
çarpımlar[] = 1;
/* ASCII tablosu sağolsun. ;) */
sayı[] -= '0';
foreach (i, hane; sayı) {
/* Her hane, pencereGenişliği kadar çarpıma katkıda bulunur. */
çarpımlar[i .. i + pencereGenişliği] *= hane;
}
int enBüyükÇarpım = int.min;
int enBüyükÇarpımYer = int.min;
/* Baştaki ve sondaki fazlalıklar dışındakilerin en büyüğünü arıyoruz. */
foreach (int i, çarpım; çarpımlar[fazlalık .. $ - fazlalık]) {
if (çarpım > enBüyükÇarpım) {
enBüyükÇarpım = çarpım;
enBüyükÇarpımYer = i;
}
}
return EnBüyükÇarpım(enBüyükÇarpım, enBüyükÇarpımYer);
}
void main()
{
File dosya = File("sayi.txt","r");
char[] sayı;
foreach (string satır; lines(dosya)) {
sayı ~= chomp(satır);
}
foreach (i; 0 .. 100_000) {
hesap(sayı, 5);
}
/* Bir kere de yazdıralım: */
writeln(hesap(sayı, 5));
}
Dizilerin "Bütün elemanlar üzerindeki işlemler" başlığında anlatılan olanaklarından yararlandım (http://ddili.org/ders/d/dilimler.html):
-
Bütün çarpımları 1'e eşitlemek: 'çarpımlar[] = 1'
-
Bütün hanelerin tamsayı karşılıklarını bulmak: 'sayı[] -= '0'' (Sayıların ASCII tablosundaki değerlerle geldikleri varsayımıyla)
-
Hanenin değerini 5 çarpıma da çarpmak: 'çarpımlar[i .. i + pencereGenişliği] *= hane'
Bir de, soruda istenmese de en büyük çarpımın hangi hanede başladığını da döndürdüm.
Ali
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]