• Dag’al kuch usuliga asoslangan algoritmlar
  • Kommivoyajer masalasi
  • Yechish usullari
  • Shaharlar ro’yxati raqamlarini kombinatsiya qilish dasturi void permute(int a[], int l, int r) { if (l == r){ for(int i=0; i
  • Dastur kodi (Lagranj interpolyatsion ko’phadi)




    Download 390.27 Kb.
    bet10/12
    Sana22.06.2022
    Hajmi390.27 Kb.
    #24202
    1   ...   4   5   6   7   8   9   10   11   12
    Bog'liq
    netniki
    4-jadval, 1-AI OAT, Pedagogika psixologiya Al 3 Abdusaimiov D, 1-amaliy ish, 6 mavzu excelda formula va funksiyalar bilan ishlash, Документ Microsoft Word, Иж.таъ.1-мус - мав., Mavzu1, Shahboz 1-MI, 1, Hilola Husainova, Doc1, 4-T va S am LABARATORIYA 4, 8-mavzu
    Dastur kodi (Lagranj interpolyatsion ko’phadi)

  • #include

  • using namespace std;

  • int main(){

  • float n, xx;

  • float x[100], y[100];

  • cout<<"n ni kiriting ";

  • cin>>n;

  • cout<

  • for(int i=0; i<=n; i++)

  • {

  • cin>>x[i]>>y[i];

  • }

  • cout<<"x agrument qiymatini kiriting ";

  • cin>>xx;

  • double S=0;

  • for(int i=0; i<=n;i++)

  • {

  • double p=1;

  • for(int j=0; j<=n; j++)

  • if(i!=j)

  • p*=(xx-x[j])/(x[i]-x[j]);

  • p*=y[i];

  • S+=p;

  • }

  • cout<

  • cout<

  • return 0; }

    17.Eng qisqa yo’lni tanlsh haqidagi masala. (dinamik dasturlash, graflar)

    • #include

    • #include

    • using namespace std;

    • struct tovar

    • {

    • string nom;

    • int massa;

    • int narx;

    • };


    • int main()

    • { //ma’lumotlarni kiritish;

    • vector mahsulot;

    • tovar k;

    • for(int i=0; i<3; i++)

    • {

    • cout<

    • cin>>k.nom;

    • cin>>k.massa;

    • cin>>k.narx;

    • mahsulot.push_back(k);

    • }

    • //narx bo’yicha kamayish tartibida saralash

    • for(int i=0; i<2; i++)

    • for(int j=i+1; j<3; j++)

    • if(mahsulot[i].narx

    • {

    • tovar temp=mahsulot[i];

    • mahsulot[i]=mahsulot[j];

    • mahsulot[j]=temp;

    • }

    • //eng qimmat narx bo’yicha sumkaga solish;

    • vector sumka;


    • int mSumka = 0;

    • int nSumka = 0;

    • for (int i=0;i<3;i++)

    • {

    • if(mSumka + mahsulot[i].massa <= 35)

    • {

    • mSumka+=mahsulot[i].massa;

    • nSumka+=mahsulot[i].narx;

    • sumka.push_back(mahsulot[i]);

    • }

    • }

    • //natijani ko'rish

    • cout<<"sumkada joylashtirilgan: "<

    • <<" kg. umumiy narxi "<

    • cout<<"-----------------------------------------------------"<

    • cout<<"sumkada joylashritilgan mahsulotlar: "<

    • for (int i=0;i

    • {

    • cout<

    • }

    • }

    18.“Dag’al kuch ” usulini misollar yordamida tushuntirib bering (brute force, to’liq tekshirib chiqish)
    Dag’al kuch usuliga asoslangan algoritmlar:

    • Matritsalarni ko’paytirish;

    • Ketma-ket qidiruv (Ro’yhatdagi eng kichik va eng katta elementni topish);

    • Tanlab saralash;

    • Pufakcha usulida saralash;

    • Satrdan qism satrni qidirish;

    • Tekislikda eng yaqin joylashgan nuqtalar juftligini topish.

    Kommivoyajer masalasi
    Shaharlar to’plami va ular orasidagi sayohat narxi (masofasi) berilgan.
    Shunday tartibni aniqlash kerakki, sayohatchi hamma shaharlarga tashrif buyurib, dastlabki shaharga qaytib kelganda, sayohatning umumiy narxi (masofasi) minimal bo’lsin.

    Kommivoyajer masalasi

    • Masalaning bir nechta variantlari mavjud :

    • Simmetrik kommivoyajer masalasi  (TSP = traveling salesman problem) Dji = Dij.

    • Assimmetrik kommivoyajer masalasi  (ATSP) Dji ≠ Dij.

    • Qisman tartiblash masalasi  (SOP = sequential ordering problem)

    • Гамильтон siklini izlash (HCP = нamiltonian cycle problem) -

    Yechish usullari
    1. Aniq usullar - Aniq usullar nafaqat biron bir yechimni topibgina qolmay, balki natijaning eng yaxshi yechim ekanligini isbotlaydi.
    Shaharlar orasidagi masofalarni matritsa shaklida yozamiz (pastdagi jadval). Masalan, 2-shahardan 3-shahargacha (va 3 dan 2 gacha) masofa 7. Grafik yo'naltirilmaganligi sababli, bu matritsa simmetrikdir. Chiziqlar shahardan unga "taqiqlangan" o'tishlarni belgilaydi.

    har qanday shahar boshlang'ich (va tugaydigan) sifatida tanlanishi mumkin. bu nol shahar bo'lsin. keyin nollar bilan o'ralgan 1 dan 4 gacha bo'lgan raqamlarning har qanday almashinuvi har bir shaharni bir marta bosib o'tadigan yo'lni anglatadi. masalan, 0,1,3,2,4,0 demak, 0 shahridan boshlab 1-shaharga, keyin 3-shaharga va h.k.
    Shaharlar ro’yxati raqamlarini kombinatsiya qilish dasturi
    void permute(int a[], int l, int r)
    {
    if (l == r){
    for(int i=0; i<=r; i++){
    cout<<*(a+i)<<" ";
    }
    cout<
    }
    else
    {

    Download 390.27 Kb.
  • 1   ...   4   5   6   7   8   9   10   11   12




    Download 390.27 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Dastur kodi (Lagranj interpolyatsion ko’phadi)

    Download 390.27 Kb.