|
Mavzu-16: Graflarda erkin uchlarini tanlash, bo'yash. To’plamlarning to’plam ostilari aniqlash, birlashtirish
|
| bet | 4/4 | | Sana | 22.01.2024 | | Hajmi | 240,97 Kb. | | #142848 |
Bog'liq Algoritm-16-9 (1) pascal-work, Mavzu Buxgalteriya hisobida raqamlashtirish texnologiyalari Rej, 4-MATEMATIKA 333333333, Matematika 4-sinf, Холиков Зиёвиддин (2), ADVANTAGES AND DISADVANTAGES OF TEACHING GRAMMAR INDUCTIVELY, THE TYPES OF MORPHEMES AND THE GRAMMATICAL CATEGORIES, таможня маълумотномалари бланкаси 2021 йил, salimov feruz ped, Xavfsizlik qoidalari (uzb 7-semestr 76-soat), R Javohir kurs ishi (Rahimov) (2), nodir, O‘RQ 410 сон 22 09 2016 “Mehnatni muhofaza qilish to‘g‘risida”gi, umar raximov, metodichka AutoCAD tajriba EEC++ da dastur kodi:
#include "stdafx.h"
#include
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; ifor (k=0; kfor (i=0; ifor (j=0; jif (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]D[i][j]=D[i][k]+D[k][j];
for (i=0; i{
for (j=0; jcout<} }
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
cout<<"Количество вершин в графе > "; cin>>n;
cout<<"Введите матрицу весов ребер:\n";
for (i=0; ifor (j=0; j{
cout<<"GR["< ";
cin>>GR[i][j];
}
cout<<"Матрица кратчайших путей:"<FU(GR, n);
system("pause>>void");
}
Tasavvur qilaylik, har bir elementi vazn haqida ma’lumot saqlovchi qo’shma matritsa quyidagicha berilgan bo’lsin:
Quyidagi grafda tugunlar soni 3 ga teng va u quyidagi matrisa bilan berilgan.
Algoritm masalasi:
Matrisani shunday qayta yozish kerakki, undagi har bir element i va j tugun orasidagi qirra vaznini emas, balki I dan j gacha qisqa yo’l vaznini saqlasin. Misol uchun kichik bir graf olamiz. Shu sababli undagi qiymatlar deyarli o’zgarmasligi ham mumkin. Ammo dastur narijasida unda 2ta element qiymati almashganligini ko’rish mumkin. Quyidagi sxemada buni tahlil qilish mumkin.
Ushbu jadvalda algoritmning asosiy qismini ifodalovchi 27ta bosqichi keltirilgan. Usulning bajarilish vaqti O(|V|3) bo'lganligi sababli bosqichlar soni shunchalik ko'p. Graf 3 ta tugunga ega va 33=27 ga teng. Birinchi o'zgarish k = 1, i = 2 va j = 3 bo’lgandagi iteratsiyada sodir bo'ladi. Bunda D[2][1]=1, D[1][3]=2, D[2][3]=4. Shart to'g'ri, ya'ni D[1][3] + D[3][2] = 3 va 3 <4, shuning uchun D[2][3] matritsa elementi yangi qiymat oladi. Keyingi qadam, shart bajarilganda ikkinchi satr va uchinchi ustunda joylashgan elementga haqiqatan ham o'zgarishlar kiritiladi.
Foydalanilgan adabiyotlar:
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ» Вильямс, 2013 год, 1324 стр. Издание 3-е
http://www.math.nsc.ru/LBRT/k5/OR-MMF/Kleinberg_Tardoc_algoritmy_razrabotka_i_primenenie.pdf
https://e-maxx.ru/bookz/files/cormen.pdf
https://studfile.net/preview/5535319/page:24/
|
| |
