2-amaliy mashg’ulot topshiriqlari.
{a,b,c,d,e} shaharlar berilgan bo’lsa, kommivoyajer masalasini yechish uchun yo’nalishlarning barcha ko’rinishlarini aniqlash dasturini tuzing
#include
#include
#include
using namespace std;
int main()
{
vector cities {'a', 'b', 'c', 'd', 'e'};
vector paths;
// Permütatsiyalarni hisoblash
do {
string path;
for(char city: cities){
path += city;
}
paths.push_back(path);
} while (next_permutation(cities.begin(), cities.end()));
// Natijalarni chiqarish
for(string path: paths){
cout << path << endl;
}
return 0;
}
3-amaliy mashg’ulot topshiriqlari
Pitsa tarqatuvchi ishchiga shaharning 6 ta nuqtasidan buyurtma tushdi. Pitsa tarqatuvchi hodimga shu buyurtma berilgan nuqtalar orasidagi masofalar ma’lum. U iqtisodiy tomondan va vaqt bo’yicha yutishga harakat qilmoqchi. Unga eng kam masofa bosib o’tgan holda pitsalarni tarqatib chiqishiga yordam bering.
Grafning minimal narxli daraxt skletini Prim algoritmi yordamida quring.
1. Minimal kenglik daraxtini (MST) boshlash uchun ixtiyoriy nuqtani tanlang, masalan, birinchi tartibli joy.
2. Boshlanish nuqtasini istalgan boshqa buyurtma joyiga bog'laydigan eng arzon chekkani toping. O'sha chekkani maqsad nuqtasi bilan birga MST ga qo'shing.
3. 2-bosqichni takrorlang, lekin bu safar MSTdagi nuqtalardan birini qolgan buyurtma joylariga bog'laydigan eng arzon chekkani qidiring.
4. Barcha buyurtma joylari ulanmaguncha MSTga chekka qo‘shishda davom eting va MSTdan tashqaridagi buyurtma joylarini bog‘laydigan boshqa chekkalar qolmaydi.
5. Natijada barcha buyurtma joylarini qamrab oladigan va bosib o'tgan masofani minimallashtirgan MST paydo bo'ldi.
Do'stlaringiz bilan baham: |