Kaminçik avtomatı

Кaminçik avtomatı "Mardj-2016" kvadrat cədvəldə işləyir. Hər bir hüceyrədə müəyyən bir anda müəyyən (bəlkə də sıfır) sayda kaminçik var. Avtomat giriş olaraq iki natural ədəd A və B qəbul edir. Bunlar müvafiq olaraq cədvəlin sol üst və sağ üst hüceyrələrində başlanğıcda yerləşən kaminçiklərin sayıdır. Başlanğıcda digər hüceyrələrdə kaminçik yoxdur. Hər bir hüceyrəyə bir funksiya qoşulub: bu funksiya həmin anda hüceyrədə yerləşən kaminçiklərin sayını qəbul edir və növbəti iterasiyada bu hüceyrədən yuxarı, sağ, aşağı və sol qonşu hüceyrələrə köçürülməli olan kaminçiklərin sayını qaytarır. Beləliklə, hər iterasiyada kaminçik avtomatı sadəcə olaraq bütün hüceyrələrdən qonşu hüceyrələrə qoşulmuş funksiyaların qaytardığı təlimatlara uyğun olaraq müvafiq sayda kaminçikləri köçürür. Əgər növbəti iterasiyada heç bir hüceyrə heç bir kaminçiyi heç bir qonşu hüceyrəyə köçürməzsə, bu iterasiyadan sonra "proqram" icrası başa çatır. Çıxışda avtomat sol alt və sağ alt hüceyrələrdəki kaminçiklərin sayını qaytarır.

Proqramın bitdiyi anda digər hüceyrələrdə olan kaminçiklərin sayları istənilən ola bilər və nəzərə alınmır.

Tapşırıq

Bu tapşırıq 5 alt tapşırıqdan ibarətdir:

1. Birinci alt tapşırıqda çıxışda (0, A + B) alınmalıdır, yəni sol alt hüceyrədə kaminçik olmamalıdır, sağ alt hüceyrədə isə kaminçiklərin sayı girişdəki ədədlərin cəminə bərabər olmalıdır. Bu alt tapşırıq 10 bal dəyərindədir.

2. İkinci alt tapşırıqda çıxışda (0, |A – B|) alınmalıdır, yəni sağ alt hüceyrədə kaminçiklərin sayı girişdəki ədədlərin fərqinin moduluna bərabər olmalıdır (sol alt hüceyrədə kaminçik olmamalıdır). Bu alt tapşırıq 20 bal dəyərindədir.

3. Üçüncü alt tapşırıqda çıxışda (0, min{A, B}) alınmalıdır, burada min{A, B} A və B ədədlərindən kiçik olanını göstərir (əgər A = B olarsa, min{A, B} = A = B). Bu alt tapşırıq 15 bal dəyərindədir.

4. Dördüncü alt tapşırıqda çıxışda (0, max{A, B}) alınmalıdır, burada max{A, B} A və B ədədlərindən böyük olanını göstərir (əgər A = B olarsa, max{A, B} = A = B). Bu alt tapşırıq 15 bal dəyərindədir.

5. Beşinci alt tapşırıqda çıxışda (1, 0) alınmalıdır, əgər A > B olarsa; (0, 1) alınmalıdır, əgər A < B olarsa; (0, 0) alınmalıdır, əgər A = B olarsa. Yəni, girişdəki iki ədəddən hansının daha böyük olduğu yerdə çıxışda bir kaminçik olmalıdır. Bu alt tapşırıq 40 bal dəyərindədir.

automaton funksiyasını/prosedurunu yazın ki, hüceyrədəki kaminçiklərin sayına və onun koordinatlarına görə qonşu hüceyrələrə köçürülməli olan kaminçiklərin sayını alt tapşırığın tələblərinə uyğun olaraq müəyyən etsin. Yəni, hər beş alt tapşırıq üçün kaminçik avtomatının işini həyata keçirən alqoritmi reallaşdırmalısınız. Bütün alt tapşırıqlar ayrı test bloklarından ibarətdir; hər blok 5 bal dəyərindədir və bir və ya bir neçə testdən ibarət ola bilər. Bu 5 balı qazanmaq üçün alqoritminiz blokdakı bütün testləri keçməlidir.

Reallaşdırma detalları

Siz funksiyanın/prosedurun reallaşdırmasını və lazım olduqda bu funksiyanın düzgün işləməsi üçün lazım olan digər kodu ehtiva edən, lakin proqramın öz bədənini (yəni, C++-da main funksiyası və ya Pascal-da begin/end bloku) ehtiva etməyən bir fayl göndərməlisiniz. Test zamanı faylınız münsiflər tərəfindən yazılmış xüsusi proqram bədəni ilə tamamlanacaq. Bədən sizin yazdığınız funksiyanı müvafiq şəkildə çağıracaq və onun həyata keçirdiyi alqoritmin düzgünlüyünü yoxlayacaq. Sizin reallaşdırdığınız funksiya aşağıdakı kimi olmalıdır (proqramlaşdırma dilləri üçün funksiyanın imzalarını elektron versiyada baxın):

automaton(subproblem, size, row, column, pebbles, top, right, bottom, left)

Funksiyanın parametrləri

1. subproblem — alt tapşırığın nömrəsi (yuxarıya baxın). Alt tapşırığın nömrəsi eyni proqramda funksiyanın işə salınması zamanı dəyişmir.

2. size — kvadrat cədvəlin ölçüsü (bir üfüqi/şaquli xəttdəki hüceyrələrin sayı). Ölçü eyni proqramda funksiyanın işə salınması zamanı dəyişmir.

3. row — hüceyrənin yerləşdiyi sətir; yuxarıdan aşağıya doğru 1-dən size-ə qədər nömrələnir: 1 — üst sətir, size — alt sətir.

4. column — hüceyrənin yerləşdiyi sütun; soldan sağa doğru 1-dən size-ə qədər nömrələnir: 1 — sol sütun, size — sağ sütun.

5. pebbles — hüceyrədəki kaminçiklərin sayı, müsbət tam ədəd (əgər bu say sıfırdırsa, heç bir köçürmə həyata keçirilə bilməz və funksiyanın çağırışı baş vermir). Siz bu dəyişənin dəyərini funksiyanın içində dəyişə bilərsiniz, lakin belə bir dəyişiklik heç bir təsir göstərməyəcək: köçürmələrdən sonra hüceyrədəki kaminçiklərin sayı avtomatik olaraq hüceyrədəki başlanğıc kaminçiklərin sayı ilə qonşu hüceyrələrə köçürülən kaminçiklərin sayı arasındakı fərqə bərabər olacaq (aşağıya baxın).

6. top — bu parametrin başlanğıc dəyəri (proqram bədəni tərəfindən ötürülən arqument) 0-a bərabərdir. Əgər bu hüceyrənin yuxarıda qonşusu varsa və oraya kaminçiklər köçürülməlidirsə, bu dəyəri müvafiq kaminçiklərin sayına bərabər etmək üçün yenidən yazmaq lazımdır.

7. right — bu parametrin başlanğıc dəyəri 0-a bərabərdir. Əgər bu hüceyrənin sağda qonşusu varsa və oraya kaminçiklər köçürülməlidirsə, bu dəyəri müvafiq kaminçiklərin sayına bərabər etmək üçün yenidən yazmaq lazımdır.

8. bottom — bu parametrin başlanğıc dəyəri 0-a bərabərdir. Əgər bu hüceyrənin aşağıda qonşusu varsa və oraya kaminçiklər köçürülməlidirsə, bu dəyəri müvafiq kaminçiklərin sayına bərabər etmək üçün yenidən yazmaq lazımdır.

9. left — bu parametrin başlanğıc dəyəri 0-a bərabərdir. Əgər bu hüceyrənin solda qonşusu varsa və oraya kaminçiklər köçürülməlidirsə, bu dəyəri müvafiq kaminçiklərin sayına bərabər etmək üçün yenidən yazmaq lazımdır.

Parametrlərin son dəyərləri top, right, bottom, left mənfi olmamalıdır və cəmi pebbles dəyərini aşmamalıdır.

Hər addımda funksiya yalnız həmin addımda ona ötürülən məlumatlara əsaslanaraq köçürmələri müəyyən etməlidir. Funksiyanın işinə əvvəlki qarşılıqlı təsir heç bir təsir göstərməməlidir. Bundan əlavə, funksiya deterministik olmalıdır, yəni sabit giriş məlumatları üçün həmişə eyni dəyərləri qaytarmalıdır.

Məhdudiyyətlər

• Cədvəlin ölçüsü 5-dən 10-a qədər istənilən ədəd ola bilər.

• Girişdəki ədədlər 1-dən 100-ə qədər istənilən dəyərə malik ola bilər.

• Avtomatın dayanacağı iterasiyaların sayı 10 000-dən çox olmamalıdır.

Öz testləriniz

Elektron versiyada əsas proqram bədəni automaton_tester.* nümunəsi verilmişdir ki, bu da sizin yaratdığınız giriş faylında verilmiş giriş məlumatları üzərində automaton funksiyasını işə salır və cədvəlin son vəziyyətini (və ya avtomat hələ dayanmayıbsa, 10 000 iterasiyadan sonra cədvəlin vəziyyətini) çıxarır. Bu proqramdan istifadə etmək üçün onu automaton.* faylını ehtiva edən eyni kataloqa yerləşdirin, burada sizin funksiyanızın reallaşdırması var, və həmin kataloqda aşağıda təsvir olunan struktura malik automaton.dat faylı yaradın. Qeyd edin ki, funksiyanızın qiymətləndirilməsi üçün istifadə olunacaq əsas proqram bədəni sizə təqdim olunan automaton_tester.* nümunəsindən fərqli olacaq. Xüsusilə, yoxlama zamanı funksiya cədvəlin istənilən hüceyrəsi və 1-dən 200-ə qədər istənilən kaminçik sayı üçün çağırıla bilər.

automaton_tester: giriş məlumatları

Yeganə sətir dörd natural ədəd ehtiva edir: müvafiq olaraq alt tapşırığın nömrəsi, cədvəlin ölçüsü, A və B ədədləri.

automaton_tester: çıxış məlumatları

Çıxış faylının birinci sətiri avtomatın çıxışındakı cüt ədədi və ya əgər funksiyanın hansısa addımında texniki tələbləri və ya iterasiya sayının məhdudiyyətlərini pozarsa, səhv diaqnostikasını ehtiva edəcək. Texniki pozuntular olmadıqda, növbəti sətirlər cədvəlin tam son vəziyyətini ehtiva edəcək.