Advertisement
MeehoweCK

Untitled

Dec 18th, 2018
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <conio.h>
  4.  
  5. using namespace std;
  6.  
  7. bool zbior_rosnacy(vector<short> zbior)
  8. {
  9.     short poprzednia = zbior[0];
  10.     for(short i = 1; i < zbior.size(); ++i)
  11.     {
  12.         if(zbior[i] <= poprzednia)
  13.             return false;
  14.         poprzednia = zbior[i];
  15.     }
  16.     return true;
  17. }
  18.  
  19. int suma(vector<short> zbior)
  20. {
  21.     int wynik = 0;
  22.     for(short i = 0; i < (zbior.size() - 1); ++i)
  23.         wynik += zbior[i];
  24.     return wynik;
  25. }
  26.  
  27. void wypisz_zbior(vector<short> zbior)
  28. {
  29.     for(short i = 0; i < zbior.size(); ++i)
  30.         cout << zbior[i] << "\t";
  31. }
  32.  
  33. bool utworz_nowy_zbior(vector<short> stary_zbior, vector<short>& nowy_zbior)
  34. {
  35.     short n = stary_zbior.size();       // obecna wielkosc zbioru
  36.     short wielkosc = suma(stary_zbior) + stary_zbior[n-1];
  37.     vector<short> nowy;
  38.     nowy.resize(n);
  39.  
  40.     for(short k = n-2; k >= 0; --k)     // k - poczatek modyfikowanego zbioru
  41.     {
  42.         for(short i = 0; i < n; ++i)
  43.             nowy[i] = stary_zbior[i];       // kopiowanie dotychczasowego zbioru
  44.         ++nowy[k];
  45.         for(short p = k+1; p < (n-1); ++p)      // pozycja obecnie modyfikowanej liczby
  46.             nowy[p] = nowy[p-1] + 1;
  47.         nowy[n - 1] = wielkosc - suma(nowy);
  48.         if(zbior_rosnacy(nowy))
  49.         {
  50.             // wczytanie nowego zbioru:
  51.             for(short i = 0; i < n; ++i)
  52.                 nowy_zbior[i] = nowy[i];
  53.             return true;
  54.         }
  55.     }
  56.  
  57.     // jezeli jestesmy tutaj, to znaczy, ze nalezy zwiekszyc zbior o 1
  58.     ++n;
  59.     nowy.resize(n);
  60.     for(short i = 0; i < (n-1); ++i)
  61.         nowy[i] = i + 1;
  62.     nowy[n-1] = wielkosc - suma(nowy);
  63.     if(zbior_rosnacy(nowy))
  64.     {
  65.         // wczytanie nowego zbioru:
  66.         nowy_zbior.resize(n);
  67.         for(short i = 0; i < n; ++i)
  68.             nowy_zbior[i] = nowy[i];
  69.         return true;
  70.     }
  71.     else
  72.         return false;       // brak kolejnego zbioru
  73. }
  74.  
  75. void spr(vector<short> tablica)
  76. {
  77.     for(short i = 0; i < tablica.size(); ++i)
  78.         cout << tablica[i] << "\t";
  79.     cout << endl;
  80.     getch();
  81. }
  82.  
  83. int main()
  84. {
  85.     short n, liczba;
  86.     int wynik = 32767;
  87.     vector<short> tablica;
  88.     cin >> n;
  89.  
  90.     tablica.resize(n+1);
  91.     for(short i = 0; i < n; ++i)
  92.         tablica[i] = 0;
  93.  
  94.     for(short i = 0; i < n; ++i)
  95.     {
  96.         cin >> liczba;
  97.         ++tablica[liczba];
  98.     }
  99.  
  100.     for(short i = 1; i < tablica.size(); ++i)
  101.     {
  102.         tablica[i] = i - tablica[i];
  103.         if(tablica[i] < 0)
  104.             tablica[i] = 0;
  105.     }
  106.  
  107.     wypisz_zbior(tablica);
  108.     cout << endl;
  109.     // algorytm szukania zbiorΓ³w - najwazniejsza czesc!!!
  110.     vector<short> zbior;
  111.     zbior.resize(1);
  112.     zbior = {n};
  113.  
  114.     do
  115.     {
  116.         wypisz_zbior(zbior);
  117.         liczba = 0;
  118.         for(short i = 0; i < zbior.size(); ++i)
  119.         {
  120.             liczba += tablica[zbior[i]];
  121.             if(liczba >= wynik)
  122.                 break;
  123.         }
  124.         cout << "liczba: " << liczba << ", wynik: " << wynik << endl;
  125.         if(liczba < wynik)
  126.             wynik = liczba;
  127.         if(wynik == 1)
  128.             break;
  129.     } while(utworz_nowy_zbior(zbior, zbior));
  130.  
  131.     cout << wynik;
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement