Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

Şək.1.16. Üç diskdən ibarət hanoy qülləsi haqqında məsələnin matris modeli ilə qoyuluşu

1																										1
2				2									1				1									2
3				3		1		3	2	1		3	2				2	3		1	2	3				3

Şəkil 1.17-dən göründüyü kimi, n=3 olduqda məsələnin 7 addımdan ibarət həlli var. Şəkil 1.17-də hər ox bir addımı, yalnız sonuncu ox iki addımı ifadə edir.
Şək.1.17. Üç diskdən ibarət hanoy qülləsi haqqında məsələnin həll sxemi

Eyni qayda ilə göstərmək olar ki, 3-cü çubuq yardımçı olduğu halda, yəni məqsəd, diskləri 2-ci çubuğa köçürmək olarsa, bu halda da məsələnin həlli var. Ümumiyyətlə, disklərin sayı 3,5,7, və s. tək ədəd olduqda birinci əməliyyat kiçik diski məqsəd çubuğuna köçürməkdən ibarət olmalıdır. Göstərək ki, disklərin sayı 4 olduqda da hanoy qülləsi haqqında məsələnin həlli var. İsbat üçün aşağıdakı işarələri qəbul edək:

– bu, birinci çubuqdan 3-cü çubuğa 3 diskin köçürülməsi məsələsinin alqoritminin şərti işarəsidir;
( ) - bu, birinci çubuqdan 3-cü çubuğa üstdəki diskin köçürülməsi əməliyyatının şərti işarəsidir;
tipli makroəməliyyatdan istifadə edərək, 4 diskə aid məsələnin həll sxemini qura bilərik:

1														1
2					1				1					2
3					2				2					3
4				4	3				3	4				4

Şək. 1.18. Dörd diskdən ibarət hanoy qülləsi haqqında məsələnin həll sxemi

Bu sxemi riyazi şəkildə aşağıdakı kimi yazmaq olar:

Тeorem. İxtiyari n sayda disk üçün hanoy qülləsi haqqında məsələnin həlli var.
İsbatı:
n=3 və n=4 olduqda məsələnin həlli olduğunu isbat etdik. Tutaq ki, məsələnin həlli n-1 üçün mövcuddur. Göstərək ki, onda n disk üçün də məsələnin həlli var.
.
Beləliklə, teorem isbat olundu.
Deməli, disklərin sayı tək olanda birinci əməliyyat üstdəki diski məqsəd çubuğuna köçürmədən ibarət olduğu halda, bunların sayı cüt olduqda ilk əməliyyat üstdəki diski yardımçı çubuğa köçürmə olmalıdır. Bu məsələnin həlli alqoritmi şəkil 1.19-da təsvir edilib.
İndi də riyazi məsələlərin həllində riyazi induksiya üsulunun tətbiqlərinə baxaq.
Bir sıra cəmləmə düsturlarına baxaq və bunlarin doğruluğunu ryazi induksiya üsulu ilə isbat edək:

n=2 olduqda 1/2= 1-1/2,
n=3 olduqda

n=k üçün düsturun doğruluğunu qəbul edək:

n=k+1 üçün düsturun doğruluğunu isbat edək.

Eyni qayda ilə isbat etmək olar ki:

2) 1+2²+3² +...+n² = ,
3) 1+2³+. . . +n³ = ,
4) 1+3²+. . . +(2n-1)² = ,
5) 1+3³+. . . +(2n-1)³ = n²(2 n²-1).





Şək.1.19. n diskdən ibarət hanoy qülləsi haqqında məsələnin həlli alqoritmi
2.Alqoritmlərin realizasiyasında maşın yaddaşının istifadəsi

2.1. Alqoritmlərin qurulmasında informasiya strukturlarının tətbiqinin xüsusiyyətləri
Məlumdur ki, alqoritmlərin qurulmasında massivlərdən, identifikatorlardan və vektorlardan geniş istifadə olunur. Bundan başqa həll edilən məsələnin xüsusiyyətindən və informasiya emalına qoyulan tələblərdən asılı olaraq verilənlərin saxlanılması, emalı və ötürülməsi üçün istifadə olunan müxtəlif informasiya strukturlarından da istifadə olunur [8,19].


1

2 3

4 5



6
Şək. 2.1. Şəbəkə tipli qraf

Şəkil 2.1-də təsvir olunan şəbəkəyə nəzər salaq. 1 və 6 nömrəli düyünlər arasında ən qısa məsafəni və buna uyğun yolu tapmaq tələb olunur. Mümkün həll üsullarından biri budur ki, 1 və 6-cı düyünləri birləşdirən bütün yolları qurub, bunlardan minimal olanı seçək. Bu üsulu iki fərqli yanaşma ilə yerinə yetirmək olar.

I) Dərinliyə seçim. Bu yanaşmanın mahiyyəti şəkil 2.2 vasitəsi ilə şərh olunub.
Şək. 2.2. Şəbəkənin dərinliyə seçmə üsulu ilə qurulan obrazı

Şəkil 2.2-də təsvir edilən fiqur şəkil 2.1-də təsvir edilən şəbəkənin ağac tipli obrazıdır. Mötərizələrin qarşısında ağacın düyünlərinin nömrələri bunların qurulma ardıcıllığı ilə, mötərizələrdə bu düyünlərin proobrazları qeyd edilib. Ağacın düyünlərində onların obrazları qeyd edilməsə, qurulan ağacda müxtəlif düyünlər eyni adla yadda saxlanıla bilər, bu hal əlverişli deyil.

Qurulmuş ağac əsasında S[1:4] stek tipli informasiya strukturundan istifadə etməklə mümkün yolları aşağıdakı sxemlə qurmaq olar:

1

1

2

1

2

4

1

2

4

6

1

2

4

1

2

1

2

5

1

2

5

6

..........................................................................................

Şək.2.3. Stek vasitəsi ilə mümkün yolların qurulması sxemi

Qurulan alternativ yollar tünd rənglə qeyd edilib. Bunların sayı 3-ə bərabərdir, şəkil 2.3-də bunlardan ikisinin qurulması sxemi təsvir olunub. Steki emal edən zaman hər dəfə yolun davamı S(4)-ün məzmunu əsasında qurulur. Əgər yolun davamı varsa, stekin məzmunu bir xana qədər sola sürüşdürülür və S(4) xanasına cari yolun davamını göstərən nömrə yazılır. Yolun davamı yoxsa, əksinə, stekin məzmunu bir mərtəbə sağa sürüşdürülür. Dərinliyə seçmə zamanı stekdə qonşu xanalardan soldakı sağdakına nisbətən “sələf”, əksinə sağdakı soldakına nisbətən “varis”lik münasibətini göstərir. Deməli, bu halda stekdən istifadə etmək məqsədəuyğundur.

II) Eninə seçim. Bu halda da əvvəlki halda olduğu kimi yardımçı ağac qurulur, lakin bu ağacın qurulma prinsipi əvvəlkindən fərqlənir. Bu halda ağacın kökündən başlayaraq hər dəfə hər bir cari düyünün bütün varis düyünləri qurulur və yadda saxlanılır. Bu qayda ilə qurulan ağacı aşağıdakı kimi təsvir etmək olar.

Şək.2.4. Şəbəkənin eninə seçmə üsulu ilə qurulan obrazı
Mötərizələrin qarşısında ağacın düyünlərinin nömrələri, onların qurulma ardıcıllığını göstərir və artma sırasında qeyd edilib. Mötərizələrdə isə bu düyünlərin proobrazlarının nömrələri qeyd edilib. Şəkil 2.4-də təsvir edilən ağacı yeni üsulla emal etmək lazımdır. Eninə seçmə zamanı stek işə yaramır, fərqli informasiya strukturu qurmaq lazımdır.
Ümumiyyətlə, verilənlərin yazılması, yadda saxlanılması və oxunması üsullarına görə birölçülü massivlərin aşağıdakı növlərinə baxılır[8,10]:
1) Stek elə informasiya strukturudur ki, buraya sonuncu daxil olan informasiya vahidi buradan birinci çıxır, əksinə buraya birinci daxil olan informasiya vahidi buradan sonuncu çıxır.
İnformasiyanı emal istiqamətinə görə stekləri iki yerə bölürlər:
а) soltərəfli steklər,

Bu halda həmişə yeni informasiya vahidi soldan birinci xanaya yazılır və oxunan informasiya da elə buradan oxunur;

б) sağtərəfli steklər,

Bu halda isə həmişə yeni informasiya vahidi sonuncu xanaya yazılır və oxunan informasiya da elə buradan oxunur.

Soltərəfli stekə hər hansı a veriləninin yazılması qaydasına baxaq:
1)
2)
Soltərəfli stekdən hər hansı verilənin b-yə yazılması qaydası aşağıdakı kimi olacaq:
1)
2)
Stekdən istifadə zamanı onun bir sıra xanaları boş ola bilər, bu halda yaddaşa və vaxta qənaət etmək zərurəti yaranır. Bu məqsədlə stekdə saxlanılan faydalı informasiyanın sərhədlərini yadda saxlamaq məqsədəuyğundur.
Məsələn, şəkil 2.5-də təsvir olunduğu kimi, əgər stek nömrəli xanaya qədər faydalı informasiya ilə doludursa, bu steki hər dəfə tamamilə sağa, yaxud sola sürüşdürmək effektiv hesab oluna bilməz, ona görə ki, bu halda biz sayda faydasız, izafi əməliyyat yerinə yetirmiş olarıq. Deməli, effektiv alqoritm qurmaq üçün verilənlərin yazılıb-oxunması əməliyyatlarını nömrəli xanaya qədər yerinə yetirmək lazımdır. Bununla yanaşı hər addımda stekin faydalı informasiyasını özündə saxlayan zonasının sərhədlərini yenidən qiymətləndirmək lazımdır.

Şək.2.5. Soltərəfli steklə informasiyanın emalı

Aydındır ki, sağa sürüşdürmə zamanı k kəmiyyəti bir vahid artır, sola sürüşdürmədə isə bir vahid azalır. Əgər soltərəfli stekin faydalı zonasının k sərhəddi məlum olarsa, ona informasiya vahidinin yazılması alqoritmi aşağıdakı kimi reallaşa bilər:

1)
2)
3)
və ya:
1)
2)
3)
k parametrini qiymətləndirmək üçün hesablamanın əvvəlində bütün xanalara sıfır yazılır. Bu hal onu göstərir ki, qurulan stek hələ ki, tamamilə faydasız informasiyanı saxlayır. Aşağıdakı əmrlərdən sonra faydasız informasiyanın sol sərhəddi k=2 olaraq qiymətləndirilir.
1)
2)
3)
İndi də soltərəfli stekə r sayda informasiya vahidinin yazılmasına baxaq. Fərz edək ki, bu informasiya stekə daxil olana qədər b massivində qərarlaşıb.
1)
2)
3)
4)
5)əgər olarsa -son, əks halda 1-ci addıma keçməli.
Soltərəfli stekdən vahid informasiyanın oxunmasına baxaq. Bu halda şərti ödənilir.
1)
2)
3)
4)
5)
6) əgər olarsa, onda 2-ci addıma keç, əks halda - son.
2) Növbə – elə birölçülü informasiya vahididir ki, buraya informasiya bir tərəfdən yazılır, ancaq digər tərəfdən oxunur. Ona görə də stekdən fərqli olaraq “buraya birinci gələn burdan birinci çıxır”. Bu tipli massivin adının “növbə” adlandırılması da buradan götürülüb. Növbələr iki cür olur: 1) informasiya soldan yazılır, sağdan oxunur, 2) əksinə, informasiya sağdan yazılır, soldan oxunur.
3) Dek elə informasiya strukturudur ki, o stek və növbənin simbiozudur. Onun iş prinsipini şəkil 2.6-da təsvir edilib.

Şək.2.6. Dek