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

Şək.1.1. Eratosfen alqoritminin blok-sxemi
Addım-addım detallaşdırma dedikdə qurulan hər bir alqoritmin, hətta alt alqoritmin kompüterin imkanlarının nəzərə alınması ilə yenidən işlənməsi, xırdalanması nəzərdə tutulur. Məsələn, şəkil 1.1-in 7-ci blokunda a massivinin 0-dan fərqli elementlərini, yəni sadə ədədləri çapa göndərmək nəzərdə tutulmuşdur. Bu blokun özünü də şəkil 1.2-dəki kimi detallaşdırmaq olar.



6





8

i=  , h=1
71
0





a(i)
1
72
0





a(i)
73


Şək.1.2. Eratosfen alqoritminin 7-ci blokunun detallaşdırılması
Eyni qayda ilə ƏBOB hesablamaq üçün Evklid alqoritmini makroalqoritm şəklində qurub, sonra detallaşdırmaq olar[5]. ƏBOB(x,y) hesablamaq üçün Evklid tərəfindən irəli sürülmüş alqoritm aşağıdakı kimidir:
1) əgər x>y, keç 4-cü addıma;
2) əgər y > x, keç 5-ci addıma;
3) əgər x = y, onda çap et: “ƏBOB(x,y) = x = y”, son;
4) x:= x-y, keç 1-ə;
5) y:= y-x, keç 1-ə.
Bu alqoritmdə bölmə əməlindən istifadə olunmamışdır. Bölmədən istifadə ilə alqoritmi aşağıdakı kimi qurmaq olar:
1) əgər x>y, keç 4-cü addıma;
2) əgər y > x, keç 6-cı addıma;
3) çap et: “ƏBOB(x,y) = x = y”, son;
4) x:=q(x/y) (x-in y-ə bölünməsindən alınan qalıq x-ə mənisədilir);
5) əgər x=0, onda çap et: “ƏBOB(x,y) = y”, son, əks halda keç növbəti addıma;
6) y:=q(y/x), əgər y=0, onda çap et: “ƏBOB(x,y) = x”, son, əks halda keç 4-ə.
Bu alqoritmdə addımların sayı çox olsa da, Evklidin özü tərəfindən qurulan alqoritmə nisbətən daha effektivdir. Buna hər iki alqoritmin işi zamanı addımların sayına görə əmin olmaq mümkündür.
Birinci üsulla(alqoritmlə) hesablamalara aid misallar:
(24,9) → (15,9) → (6,3) → (3,3), beləliklə, ƏBOB(24,9)=3;
(75,16) → (59,16) → (43,16) → (27,16) → (11,16) → (11,5) → (6,5) → (1,5) → (1,4) → (1,3) → (1,2) → (1,1), deməli, ƏBOB(75,16)=1, yəni 75 və 16 ədədləri qarşılıqlı sadə ədədlərdir.
İkinci üsulla(alqoritmlə) hesablamalara aid misallar:
(24,9) → (6,9) → (6,3) → (0,3), beləliklə, ƏBOB(24,9)=3;
(75,16) → (11,16) → (11,5) → (1,5) → (1,0), deməli, ƏBOB(75,16)=1.
Evklid alqoritminin başqa modifikasiyalarını da (üçüncü alqoritmi) qurmaq olar, məsələn, elə etmək olar ki, (x,y) cütündən hansı böyükdürsə, o həmişə qarşıda olsun.
(48,18)→(18,12) → (12,6) → (6,0), beləliklə, ƏBOB(48,18)=6;
(74,16)→(16,10)→(10,6)→(6,4)→(4,2)→(2,0).
Deməli, ƏBOB(74,16)=2.
Buna nail olmaq üçün alqoritm şəkil 1.3.-dəki kimi qurula bilər. Əslində, 2-ci və 3-cü alqoritmlər bir-birinə bərabərdir, ancaq 3-cü alqoritmlə informasiya emalını izləmək daha rahatdır. Birinci alqoritm isə bunlara ekvivalentdir.

başlanğıccc





x,y



z=y,
y=x,
x=z



x>y

x=y


0 0
1

z=mod(x,y)



ƏBOB=x

y=0


x=y, y=z

1


son


Şək.1.3. Evklid alqoritmi
İndi isə kommivoyajer haqqında məsələnin həlli alqoritminin detallaşdırılmasına baxaq. Kommivoyajer hər hansı şirkətin elə bir əməkdaşına deyilir ki, o, şirkətdən ezamiyyətə gedərək, müəyyən sayda (məsələn, n sayda) obyektləri gəzib, yenidən şirkətə qayıtmalıdır. Bu zaman onun qarşısında duran ən mühüm vəzifələrdən biri yol xərcini minimallaşdırmaqdır. Məlumdur ki, kommivoyajer məsələsində şəhərlərin sayı n-ə bərabər olanda ezamiyyət marşrutlarının sayı (n-1)! ədədinə bərabər olur. Fərz edək, baxılan sistemdə şirkət də daxil olmaqla obyektlərin sayı 4-ə bərabərdir. Bunları 1, 2, 3, 4 ilə nömrələyək. Bütün obyektlər arasında birbaşa yolun olduğunu və hər cüt obyektlər arasında yol xərcinin məlum olmasını fərz edək. Aşağıdakı cədvəldə i-ci və j-ci obyektlər arasında yol xərci cədvəlin i-ci sətri ilə j-ci sütununun kəsişməsindəki ədəd ilə qeyd edilib.

----	100	150	120
60	---	20	160
80	190	---	200
30	180	110	---

Şirkətin nömrəsini 4-lə işarə edək. Kommivoyajerin mümkün marşrutları aşağıdakılar olacaq: 4 – 1 – 2 – 3 – 4 , 4 – 1 – 3 – 2 – 4, 4 – 2 – 1 – 3 – 4, 4 – 2 – 3 – 1 – 4, 4 – 3 – 1 – 2 – 4, 4 – 3 – 2 – 1 – 4. Göründüyü kimi, variantların sayı (4-1)!=6 ədədinə bərabərdir.

Bu məsələnin həllinin makroalqoritmi aşağıdakı kimi təsvir edilə bilər:
1. k:=0,
2. k:=k+1,
3. əgər k≤(n-1)! olarsa, keç 4-cü addıma, əks halda 5-ci addıma,
4. k nömrəli marşrutun qurulması və yadda saxlanılması, keç 2-ci addıma,
5. qurulmuş k-1 ədəd marşrutdan optimal (ən ucuz) olan variantın seçilməsi, son.
Göründüyü kimi, variantlar qurulanda hər zaman kənardakı ədədlər, yəni 4 sabit qalır və marşrutlar aralıq rəqəmlərin ardıcıllığı ilə bir-birindən fərqlənir. Ona görə də variantları kənar ədədlər istisna olmaqla aralıq ədədlərdən ibarət sözlərlə identifikasiya etmək olar. Bu yolla yaddaşa qənaət etmək olar. Aralıq ədədlər 1,2,3, yəni əlifbanın simvollarının sayı 3-ə bərabərdir, deməli marşrutları identifikasiya edən bir sözdən digər sözə keçid 3-lük say sistemində sözün üzərinə 1 gəlməklə reallaşa bilər. Giriş sözünü “123” qəbul edək. Qurulan sözdə bir simvol iki dəfə təkrarlanırsa, yaxud “0” simvolu iştirak edirsə, bu söz yeni variant kimi qəbul edilmir və “+1” əməliyyatı bir daha təkrarlanır. Bu yolla sözlər aşağıdakı kimi qurulur:
1) 123+1=130 2) 130+1=131 3) 131+1=132
4) 132 +1=133 5) 133 +1=200 6) 200+1=201
7) 201+1=202 8) 202+1=203 9) 203+1=210
10) 210+1=211 11) 211+1=212 12) 212+1=213
13) 213+1=220 14) 220+1=221 15) 221+1=222
16) 222+1=223 17) 223+1=230 18) 230+1=231
19) 231+1=232 20) 232+1=233 21) 233+1=300
22) 300+1=301 23) 301+1=302 24) 302+1=303
25) 303+1=310 26) 310+1=311 27) 311+1=312
28) 312+1=313 29) 313+1=320 30) 320+1=321
Alternatıv marşrutları identifikasiya edən sözlər tünd rənglə qeyd edilib. Yuxarıdakı hesablamalar alqoritmin 4-cü blokunun detallaşdırılmasını əks etdirir.
Yuxarıdan aşağıya yanaşma üsulunu məsələnin həll oblastının tədricən addım-addım daraldılması kimi də şərh etmək olar. Bir sıra məsələlərin həlli başlanğıcda dəqiq informasiyanın olmaması ucbatından geniş oblastda axtarılır. Həll prosesində hər addımda faydalı informasiyadan istifadə edərək həll oblastını tədricən daraltmaq mümkün olur. Bu yanaşmanın alqoritmini aşağıdakı kimi təsvir etmək olar:
1) məsələ ilə tanışlıq, 2) məsələnin mümkün həllər oblastının qurulması, 3) bu oblastda həllin axtarılması, 4) həll tapıldısa - son, əks halda növbəti addıma keç, 5) həll oblastının müəyyən üsullarla daraldılması, 3-cü addıma keç.
Misal olaraq, tənliyin kökünün təqribi hesablanması üsullarını qeyd etmək olar.
_{Toxunanlar üsulu}. =0 tənliyini həll etmək üçün kökün daxil olduğu parçanı müəyyən etmək zəruridir, bunu [a,b] ilə işarə edək.

Baş-c

1

2

a,b,


3







i=0
4



i=i+1
5




6





|x_i-x_i-1|<

7
0

son
8 9

x_i