Dastlabki qadam - Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

Dastlabki qadam.
Manbaga (1 belgili uchga)
0
1
qiymatni mos
qo‗yamiz va
}
1
{
R
to‗plamga ega bo‗lamiz. Shuning uchun,
}
6
,
5
,
4
,
3
,
2
{
\
R
V
R
bo‗ladi.
Umumiy qadam. 1- iteratsiya.
}
1
{
R
va
}
6
,
5
,
4
,
3
,
2
{
R
bo‗lgani
uchun boshlangʻich uchi
R
to‗plamga tegishli, oxirgi uchi esa
R
to‗plam
elementi bo‗lgan barcha yoylar to‗plami
)}
4
,
1
(
),
3
,
1
(
),
2
,
1
{(
)
,
(
R
R
ga ega
bo‗lamiz.
)
,
(
R
R
to‗plamga tegishli bo‗lgan har bir yoy uchun
ij
h
ning
qiymatlarini topamiz:
)
2
,
1
(
yoy uchun
2
2
0
12
1
12
c
h
;
)
3
,
1
(
yoy uchun
10
10
0
13
1
13
c
h
;
)
4
,
1
(
yoy uchun
13
13
0
14
1
14
c
h
.
2
9
6
10
7
–6
13
12
8
1
5
1
2
3
5
6
4
184
Bu
12
h
,
13
h
va
14
h
miqdorlar orasida eng kichigi
12
h
bo‗lgani uchun
)
2
,
1
(
yoyni ajratamiz (3- shaklda bu yoy qalin chiziq bilan belgilangan) va
2
belgili uchga
2
2
qiymatni mos qo‗yamiz. Algoritmga ko‗ra
2
uchni
R
to‗plamdan chiqarib,
R
to‗plamga kiritamiz. Natijada
7
}
2
,
1
{
R
va
}
6
,
5
,
4
,
3
{
R
to‗plamlarga ega bo‗lamiz.
Ikkala uchi ham
R
to‗plamga tegishli bo‗lgan bitta
)
2
,
1
(
yoy
bo‗lgani uchun faqat bitta
2
12
1
c
tengsizlikning bajarilishini
tekshirish kifoya. Bu tengsizlik
2
2
0
ko‗rinishdagi to‗gʻri
munosabatdan iborat bo‗lgani uchun 2- iteratsiyaga o‗tamiz.
2- iteratsiya.
)}
5
2
(
)
3
2
(
)
4
1
(
)
3
1
{(
)
(
,
,
,
,
,
,
,
R
R,
bo‗lgani sababli
10
13
h
,
13
14
h
,
7
23
h
va
11
25
h
qiymatlarni va
7
}
,
,
,
min{
23
25
23
14
13
h
h
h
h
h
ekanligini
aniqlaymiz. Bu yerda eng kichik qiymat
)
3
,
2
(
yoyga mos keladi.
Shuning uchun,
)
3
,
2
(
yoyni ajratamiz va
7
3
qiymatni
3
belgili uchga
mos qo‗yamiz.
3
belgili uchni
R
to‗plamdan chiqarib,
R
to‗plamga
kiritgandan so‗ng
}
3
,
2
,
1
{
R
va
}
6
,
5
,
4
{
R
to‗plamlar hosil bo‗ladi.
Ikkala uchi ham
R
to‗plamga tegishli bo‗lgan uchta
)
2
,
1
(
,
)
3
,
1
(
va
)
3
,
2
(
yoylardan birinchisi uchun
2
12
1
c
tengsizlikning bajarilishi 1-
iteratsiyada tekshirilganligi va
1
,
2
qiymatlarning o‗zgarmaganligi
sababli faqat ikkinchi va uchinchi yoylarga mos
3
13
1
c
va
3
23
2
c
munosabatlarni tekshirish kifoya. Bu munosabatlar
7
10
0
va
7
5
2
ko‗rinishda bajariladi. Shuning uchun 3- iteratsiyaga o‗tamiz.
3- iteratsiya.
Boshlangʻich uchi
}
3
,
2
,
1
{
R
to‗plamga tegishli, oxiri
esa
}
6
,
5
,
4
{
R
to‗plamga tegishli bo‗lgan yoylar to‗rtta:
)
4
,
1
(
,
)
5
,
2
(
,
)
4
,
3
(
va
)
5
,
3
(
. Shu yoylarga mos
ij
h
ning qiymatlari
13
14
h
,
11
25
h
,
15
34
h
,
13
35
h
va, shuning uchun,
11
}
,
,
,
min{
25
35
34
25
14
h
h
h
h
h
bo‗ladi. Demak, bu
iteratsiyada
)
5
,
2
(
yoyni ajratamiz va
11
5
deb olamiz. Endi, algoritmga
ko‗ra,
}
5
,
3
,
2
,
1
{
R
va
}
6
,
4
{
R
to‗plamlarni hosil qilamiz.
Ikkala uchi ham
R
to‗plamga tegishli bo‗lgan yoylar oltita:
)
2
,
1
(
,
)
3
,
2
(
,
)
3
,
1
(
,
)
5
,
2
(
,
)
5
,
3
(
va
)
3
,
5
(
. Bu yoylarning har biri uchun
j
ij
i
c
tengsizlikning bajarilishini tekshirishimiz kerak. Lekin, 1- va 2-
7
Yozuvning ixchamligi nuqtai nazardan bu yerda va bundan keyin hosil bo‗lgan to‗plamlar uchun
R
va
R
belgilar qoldiriladi.
185
iteratsiyalarda
)
2
,
1
(
,
)
3
,
2
(
va
)
3
,
1
(
yoylar uchun bu ish bajarilganligi
sababli tekshirishni tarkibida
5
belgili uch qatnashgan
)
5
,
2
(
,
)
5
,
3
(
va
)
3
,
5
(
yoylar uchun amalga oshirib, quyidagilarga ega bo‗lamiz:
)
5
,
2
(
yoy
uchun
5
25
2
c
munosabat to‗gʻri (
11
9
2
),
)
5
,
3
(
yoy uchun
5
35
3
c
munosabat to‗gʻri (
11
6
7
), lekin
)
3
,
5
(
yoy uchun
3
53
5
c
munosabat
noto‗gʻri (
7
5
)
6
(
11
). Oxirgi munosabatni hisobga olib, algoritmga
ko‗ra
7
3
o‗rniga
5
3
deb olamiz va
)
3
,
5
(
yoyni ajratilgan deb, ilgari
ajratilgan
)
3
,
2
(
yoyni esa ajratilmagan deb hisoblaymiz (3- shaklda
7
3
yozuvning va
)
3
,
2
(
yoyning qalin chiziq‘i ustiga ajratilganlikni inkor
qiluvchi
belgisi qo‗yilgan).
4-
iteratsiya.
}
5
,
3
,
2
1
{
,
R
,
}
6
,
4
{
R
bo‗lgani
uchun
)}
6
,
5
(
),
6
,
3
(
),
4
,
3
(
),
4
,
1
{(
)
,
(
R
R
va
13
14
h
,
13
34
h
,
17
36
h
,
18
56
h
hamda
13
}
,
,
,
min{
34
14
56
36
34
14
h
h
h
h
h
h
bo‗ladi. Demak,
)
4
,
1
(
va
)
4
,
3
(
yoylarni
ajratamiz hamda 4 belgili uchga
13
4
qiymatni mos qo‗yamiz. Natijada
}
4
,
5
,
3
,
2
1
{
,
R
,
}
6
{
R
to‗plamlarga ega bo‗lamiz.
j
ij
i
c
munosabatning to‗gʻriligi
)
3
,
1
(
,
)
4
,
1
(
,
)
3
,
2
(
,
)
5
,
3
(
,
)
3
,
5
(
va
)
4
,
3
(
yoylar uchun tekshirilib ko‗rilganda, uning barcha yoylar uchun
bajarilishi ma‘lum bo‗ladi.
5- iteratsiya.
Endi
)}
6
,
5
(
),
6
,
4
(
),
6
,
3
{(
)
,
(
R
R
bo‗lgani uchun
17
36
h
,
14
46
h
,
18
56
h
va
14
}
,
,
min{
46
56
46
36
h
h
h
h
bo‗ladi. Bu yerda minimum
)
6
,
4
(
yoyda erishilgani uchun uni ajratib, orgrafning oxirgi
6
belgili uchiga
14
6
qiymatni mos qo‗yamiz.
Oxirgi qadam.
Berilgan orgrafda 1 belgili uchdan 6 belgili
uchgacha eng qisqa uzunlikka ega yo‗l(lar)ni topish maqsadida,
2
9
6
10
7
–6
13
12
8
1
5
1
2
3
5
6
4
186
algoritmga asosan, grafning oxirgi
6
belgili uchidan boshlab ajratilgan
yoylar yo‗nalishiga qarama-qarshi yo‗nalishda harakatlanib, uning 1
belgili uchiga kelishimiz kerak.
6
belgili uchga kiruvchi uchta yoydan
faqat bittasi (
)
6
,
4
(
yoy) ajratilgan bo‗lgani uchun
)
6
,
4
(
yoy yo‗nalishiga
qarama-qarshi yo‗nalishda harakat qilib,
6
belgili uchdan
4
belgili
uchga kelamiz.
4
belgili uchga kiruvchi ikkala (
)
4
,
1
(
va
)
4
,
3
(
) yoylar
ham ajratilgan bo‗lgani uchun biz tuzmoqchi bo‗lgan eng qisqa
uzunlikka ega yo‗l yagona emas.
Agar harakatni
)
4
,
1
(
yoy yo‗nalishiga teskari yo‗nalishda davom
ettirsak, u holda
4
belgili uchdan
1
belgili uchga kelib, eng qisqa
uzunlikka ega yo‗llardan biri bo‗lgan
)
6
,
4
,
1
(
1
marshrutni topamiz.
Agarda harakatni
)
4
,
3
(
yoy yo‗nalishiga teskari yo‗nalishda davom
ettirsak, u holda
4
belgili uchdan
3
belgili uchga kelamiz.
3
belgili
uchga kiruvchi ikkita yoydan faqat bittasi (
)
3
,
5
(
yoy) ajratilgan bo‗lgani
uchun
3
belgili uchdan
5
belgili uchga kelamiz. Shu usulda davom
etsak, oldin
2
belgili, keyin esa
1
belgili uchga o‗tib mumkin bo‗lgan
eng qisqa uzunlikka ega bo‗lgan yo‗llardan ikkinchisini, ya‘ni
)
6
,
4
,
3
,
5
,
2
,
1
(
2
marshrutni aniqlaymiz.
Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka
ega
1
va
2
yo‗llar borligini aniqladik. Bu yo‗llarning har biri minimal
14
6
uzunlikka ega.
|