Harvard#5654
"Harvard arxitekturası" termini, təlimatlar və məlumatlar üçün fiziki olaraq ayrılmış yaddaşa malik kompüterlərə aiddir. Bu termin, 1944-cü ildə yaradılmış Harvard Mark I kompüterinin adından götürülmüşdür. Həmin kompüterdə təlimatlar kağız lentdə, məlumatlar isə relyelərdə saxlanılırdı.
Bəzi müasir mikrokontrollerlər "Harvard arxitekturası"ndan istifadə edirlər, lakin kağız lentlər və relyelərdən yox! Məlumatlar, hər biri eyni sayda hüceyrə ehtiva edən banklarda saxlanılır. Məlumatlara müraciət edən hər bir təlimat, bank daxilində bayt-ofset f və bank nömrəsini təyin etmək üçün istifadə olunan bit a malikdir. Əgər a 0-a bərabərdirsə, müraciət 0 nömrəli banka edilir. Əgər a 1-ə bərabərdirsə, bank nömrəsi xüsusi bank seçmə registrində (BSR) saxlanılır.
Məsələn, 8 hüceyrədən ibarət 4 bankımız olduğunu fərz edək. 5 nömrəli hüceyrəyə iki üsulla müraciət etmək olar: a = 0 və f = 5 olan bir təlimatla və ya BSR dəyərini 0 olaraq təyin edərək, sonra a = 1 və f = 5 olan təlimatla. Aydındır ki, birinci üsul daha sürətlidir, çünki BSR dəyərini təyin etməyə ehtiyac yoxdur. İndi fərz edək ki, eyni yaddaşda 20 nömrəli hüceyrəyə müraciət etmək lazımdır. İndi yalnız bir üsul tətbiq edilə bilər: BSR dəyərini 2 olaraq təyin edən təlimatı icra etmək (əgər artıq lazımi dəyər saxlanılmırsa), sonra a = 1 və f = 4 olan təlimatı icra etmək. Proqram əməliyyatlar ardıcıllığından ibarətdir. Hər bir əməliyyat:
dəyişənə müraciət, V_i kimi yazılır, burada i müsbət tam ədəddir;
təkrarlama, R_n < program > E kimi yazılır, burada n müsbət tam ədəddir və < program > istənilən proqramdır, bu əməliyyat proqramın n dəfə icra olunmasına bərabərdir.
Məsələ proqramın icra olunması üçün minimal vaxtı müəyyən etməkdir. Yəni, bankların sayı və ölçüsünü bilmək və proqramı əldə etməklə, proqramın icrası üçün lazım olan minimal təlimat sayını 1 (hüceyrələrə müraciət və bəlkə də BSR dəyərinin təyin edilməsi) müəyyən etmək lazımdır. Bunun üçün dəyişənləri yaddaş hüceyrələri ilə əlaqələndirmək və bütün təsvirlər arasında təlimat sayını minimallaşdıran təsviri müəyyən etmək lazımdır. Bu say çıxarılmalıdır. Diqqət yetirin ki, BSR dəyəri ilk təyinata qədər müəyyən edilməmişdir.
Giriş məlumatları iki sətirdən ibarət bir test ehtiva edir. Birinci sətirdə b və s — bankların sayı və bankda saxlanıla bilən dəyişənlərin sayı. İkinci sətir, 1000 elementdən çox olmayan boş olmayan bir proqramı ehtiva edir (hər biri R_n, V_i və E bir element hesab olunur).
Aşağıdakıları fərz etmək olar:
R_n təkrarlamasında, n 1 ≤ n ≤ 10^6 şərtini ödəyir;
R_n < program > E < program > təkrarlamasının gövdəsi boş deyil;
V_i dəyişəninə müraciətdə, i 1 ≤ i ≤ min(b*s, 13) şərtini ödəyir;
proqramda dəyişənlərə ümumi müraciət sayı 10^12-dən çox deyil.
Bir ədəd çıxarın — proqramın icrası üçün lazım olan minimal təlimat sayı.
Nümunə 1