Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <conio.h>
- using namespace std;
- bool zbior_rosnacy(vector<short> zbior)
- {
- short poprzednia = zbior[0];
- for(short i = 1; i < zbior.size(); ++i)
- {
- if(zbior[i] <= poprzednia)
- return false;
- poprzednia = zbior[i];
- }
- return true;
- }
- int suma(vector<short> zbior)
- {
- int wynik = 0;
- for(short i = 0; i < (zbior.size() - 1); ++i)
- wynik += zbior[i];
- return wynik;
- }
- void wypisz_zbior(vector<short> zbior)
- {
- for(short i = 0; i < zbior.size(); ++i)
- cout << zbior[i] << "\t";
- }
- bool utworz_nowy_zbior(vector<short> stary_zbior, vector<short>& nowy_zbior)
- {
- short n = stary_zbior.size(); // obecna wielkosc zbioru
- short wielkosc = suma(stary_zbior) + stary_zbior[n-1];
- vector<short> nowy;
- nowy.resize(n);
- for(short k = n-2; k >= 0; --k) // k - poczatek modyfikowanego zbioru
- {
- for(short i = 0; i < n; ++i)
- nowy[i] = stary_zbior[i]; // kopiowanie dotychczasowego zbioru
- ++nowy[k];
- for(short p = k+1; p < (n-1); ++p) // pozycja obecnie modyfikowanej liczby
- nowy[p] = nowy[p-1] + 1;
- nowy[n - 1] = wielkosc - suma(nowy);
- if(zbior_rosnacy(nowy))
- {
- // wczytanie nowego zbioru:
- for(short i = 0; i < n; ++i)
- nowy_zbior[i] = nowy[i];
- return true;
- }
- }
- // jezeli jestesmy tutaj, to znaczy, ze nalezy zwiekszyc zbior o 1
- ++n;
- nowy.resize(n);
- for(short i = 0; i < (n-1); ++i)
- nowy[i] = i + 1;
- nowy[n-1] = wielkosc - suma(nowy);
- if(zbior_rosnacy(nowy))
- {
- // wczytanie nowego zbioru:
- nowy_zbior.resize(n);
- for(short i = 0; i < n; ++i)
- nowy_zbior[i] = nowy[i];
- return true;
- }
- else
- return false; // brak kolejnego zbioru
- }
- void spr(vector<short> tablica)
- {
- for(short i = 0; i < tablica.size(); ++i)
- cout << tablica[i] << "\t";
- cout << endl;
- getch();
- }
- int main()
- {
- short n, liczba;
- int wynik = 32767;
- vector<short> tablica;
- cin >> n;
- tablica.resize(n+1);
- for(short i = 0; i < n; ++i)
- tablica[i] = 0;
- for(short i = 0; i < n; ++i)
- {
- cin >> liczba;
- ++tablica[liczba];
- }
- for(short i = 1; i < tablica.size(); ++i)
- {
- tablica[i] = i - tablica[i];
- if(tablica[i] < 0)
- tablica[i] = 0;
- }
- wypisz_zbior(tablica);
- cout << endl;
- // algorytm szukania zbiorów - najwazniejsza czesc!!!
- vector<short> zbior;
- zbior.resize(1);
- zbior = {n};
- do
- {
- wypisz_zbior(zbior);
- liczba = 0;
- for(short i = 0; i < zbior.size(); ++i)
- {
- liczba += tablica[zbior[i]];
- if(liczba >= wynik)
- break;
- }
- cout << "liczba: " << liczba << ", wynik: " << wynik << endl;
- if(liczba < wynik)
- wynik = liczba;
- if(wynik == 1)
- break;
- } while(utworz_nowy_zbior(zbior, zbior));
- cout << wynik;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement