Ma’lumotlar tuzilmasi va algoritmlar fanining maqsad va vazifasini izohlab bering

Birinchi qadam

Minimal qiymat 1-tugun. Uning qo'shnilari 2, 3 va 6-sonli vertikalardir. Biz tugun qo'shnilarini navbatma-navbat aylanib chiqamiz.

1-tugunning birinchi qo'shnisi 2-tugundir, chunki unga boradigan yo'lning uzunligi minimaldir. 1-tugun orqali o'tadigan yo'lning uzunligi 1-verteksgacha bo'lgan eng qisqa masofaning yig'indisiga, uning qiymati qiymatiga va 1-dan 2-gacha bo'lgan chekkaning uzunligiga, ya'ni 0 + 7 = 7 ga teng, bu hozirgi tugun 2 (10000) qiymatidan kamroqdir. Shunday qilib, 2-chi tugunning yangi qiymati 7 ga teng.

Xuddi shunday, biz boshqa barcha qo'shnilar uchun yo'l uzunligini topamiz (3 va 6-vertikal chiziqlar).

1-tugunning barcha qo'shnilari tekshirilgan. Hozirgi eng yuqori cho'qqigacha bo'lgan masofa 1 yakuniy hisoblanadi va qayta ko'rib chiqilmaydi. Top 1 tashrif buyurilgan deb belgilanadi.

Ikkinchi qadam

Algoritmning 1-bosqichi takrorlanadi. Yana biz kutilmagan cho'qqilarning "eng yaqinini" topamiz. Bu 7-qiymat bilan 2-tugun.
Yana, biz tanlangan tugunning qo'shnilarining qiymatlarini kamaytirishga harakat qilamiz, ular orqali 2-chi tugun orqali o'tishga harakat qilamiz. 2 cho'qqilarining qo'shnilari 1, 3 va 4 cho'qqilari.
Top 1 allaqachon tashrif buyurilgan. 2-tugunning keyingi qo'shnisi 3-tugundir, chunki u uchiga minimal tashrif buyurilgan deb belgilangan. Agar siz unga 2 ga kirsangiz, u holda bu yo'lning uzunligi 17 ga teng bo'ladi (7 + 10 = 17). Ammo uchinchi uchlikning hozirgi qiymati 9 va 9 <17 dir, shuning uchun qiymat o'zgarmaydi.

2-tugunning yana bir qo'shnisi - 4-sonli tugun. Agar siz uni 2-chi tomondan o'tsangiz, bu yo'lning uzunligi 22 ga teng bo'ladi (7 + 15 = 22). 22 <10000 dan boshlab, to'rtburchakning tegini 22 ga teng qilib qo'ying,
2 tugunning barcha qo'shnilari ko'rib chiqilgan, tashrif buyurilgan deb belgilang.

Uchinchi qadam

Algoritm bosqichini 3-sonli tugunni tanlab takrorlaymiz. "Qayta ishlash" dan so'ng quyidagi natijalarga erishamiz.