Euler Projesi 150. Soru

Bir Üçgen Dizinin Minimum Toplamlı Alt-üçgeni

Pozitif ve negatif tam sayıların bir üçgen dizisinde, en küçük toplamlı bir alt-üçgeni bulmaya çalışıyoruz.

Aşağıdaki örnekte işaretlenen şartları sağlayan üçgen içindeki sayıların toplamı -42’dir.

Böyle 100 sırası bulunan bir üçgen dizi oluşturmak istiyoruz, böylece (Doğrusal Eşleşik Üreteç adı verilen) aşağıdaki gibi bir rastgele sayı üreteci kullanarak 500500 adet ±219 aralığında sözde-rastgele sk sayısı üretiyoruz:

t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 220
sk := t−219

Böylece: s1 = 273519, s2 = −153582, s3 = 450905 vb.

Sözde-rastgele sayıları kullanarak üçgen dizimiz şöylece oluşturulur:

s1
s2  s3
s4  s5  s6
s7  s8  s9  s10

Alt-üçgenler dizinin herhengi elemanından başlayıp istediğimiz kadar aşağı doğru genişletilebilir (altındaki sıradan iki eleman, onun altından üç eleman vb).

Bu alt-üçgen içinde kalan sayıların toplamına “alt-üçgenin toplamı” diyoruz.

Olası en küçük alt-üçgen toplamını bulunuz.

Okumaya devam et