Facebook
From Speedy Crocodile, 6 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 290
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <random>
  5. #include <vector>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. struct alam {
  11.         int a;
  12.         int lambda;
  13. };
  14.  
  15. struct Para {
  16.         int a;
  17.         int b;
  18. };
  19.  
  20. void makslambda(const vector <alam> & tabmnoznikow, vector<int>& mnoznik) {
  21.         int maks = tabmnoznikow[0].lambda;
  22.         for (int i = 1; i < tabmnoznikow.size(); i++) {
  23.                 if (maks < tabmnoznikow[i].lambda) {
  24.                         maks = tabmnoznikow[i].lambda;
  25.                 }
  26.         }
  27.         for (int i = 0; i < tabmnoznikow.size(); ++i) {
  28.                 if (maks == tabmnoznikow[i].lambda) {
  29.                         mnoznik.push_back(tabmnoznikow[i].a);
  30.                 }
  31.         }
  32. }
  33.  
  34. vector<Para>tablica_par = {
  35.         { 0,1 },{ 0,2 },{ 0,3 },{ 1,4 },{ 0,5 },{ 0,6 },{ 2,6 },{ 3,8 },{ 2,9 },{ 1,10 },{ 0,14 },{ 2,16 },{ 6,17 },{ 2,19 },{ 1,20 },{ 0,21 },{ 4,22 },{ 2,24 },{ 2,27 },
  36.         { 1,28 },{ 2,30 },{ 12,32 },{ 1,34 },{ 10,35 },{ 3,38 },{ 2,40 },{ 4,46 },{ 8,49 },{ 2,51 },{ 24,54 },{ 6,56 },{ 18,57 },{ 0,59 },{ 0,62 },{ 17,64 },{ 8,67 },
  37.         { 5,70 },{ 24,72 },{ 8,78 },{ 3,80 },{ 12,83 },{ 12,86 },{ 37,88 },{ 1,92 },{ 20,93 },{ 10,94 },{ 5,96 },{ 10,98 }
  38. };
  39.  
  40. void czytajdane(int & max, int & liczlosowe, int & Seed) {
  41.         cin >> max >> liczlosowe >> Seed;
  42.         while (liczlosowe < 0 || max < 0 ||
  43.                 Seed < 0 || Seed >= max) {
  44.                 cout << "!" << endl;
  45.                 cin >> max >> liczlosowe >> Seed;
  46.         }
  47. }
  48.  
  49. int losowanie(int pierwszy, const int modulo) {
  50.         random_device rd;
  51.         uniform_int_distribution<int>dist(pierwszy, modulo - 1);
  52.         return dist(rd);
  53. }
  54.  
  55. bool NWD(int modulo, int wzrost) {
  56.         do {
  57.                 if (modulo > wzrost) {
  58.                         modulo = modulo - wzrost;
  59.                 }
  60.                 else {
  61.                         wzrost = wzrost - modulo;
  62.                 }
  63.         } while (modulo != wzrost);
  64.         if (modulo == 1) {
  65.                 return false;
  66.         }
  67.         else {
  68.                 return true;
  69.         }
  70. }
  71.  
  72. int przyrost(int& modulo) {
  73.         int wzrost = losowanie(1, modulo);
  74.         while (NWD(modulo, wzrost)) {
  75.                 wzrost = losowanie(1, modulo);
  76.         }
  77.         return wzrost;
  78. }
  79.  
  80. bool teoria(int & mnoznik, const vector<int>& pierwsze, int modulo) {
  81.         int b = mnoznik - 1;
  82.         for (int i = 0; i < pierwsze.size(); ++i) {
  83.                 if (b % pierwsze[i] != 0) {
  84.                         return false;
  85.                 }
  86.         }
  87.         if (modulo % 4 == 0) {
  88.                 if (b % 4 == 0) {
  89.                         return true;
  90.                 }
  91.                 else {
  92.                         return false;
  93.                 }
  94.         }
  95. }
  96.  
  97. void wypelnij_mnoznikami(vector<alam>& tabmnoznikow, int& modulo) {
  98.         int podstawa = 2;
  99.         int lambda = 1;
  100.         long long tmp = podstawa;
  101.         int i = 0;
  102.         alam tymczasowe_alam;
  103.         while (podstawa < modulo) {
  104.                 while (NWD(modulo, podstawa)) {
  105.                         ++podstawa;
  106.                         tmp = podstawa;
  107.                 }
  108.                 while (tmp % modulo != 1) {
  109.                         lambda++;
  110.                         tmp *= podstawa;
  111.                         if (lambda > 100)break;
  112.                 }
  113.                 tymczasowe_alam.a = podstawa;
  114.                 tymczasowe_alam.lambda = lambda;
  115.                 tabmnoznikow.push_back(tymczasowe_alam);
  116.                 ++podstawa;
  117.                 lambda = 1;
  118.                 tmp = podstawa;
  119.         }
  120. }
  121.  
  122.  
  123. int mnoz(int& modulo, const vector<int>& czemu_tak_trudno) {
  124.         int mnoznik;
  125.         vector<alam> tabmnoznikow;
  126.         wypelnij_mnoznikami(tabmnoznikow, modulo);
  127.         vector<int> vecmnoznik;
  128.         makslambda(tabmnoznikow, vecmnoznik);
  129.         for (int i = 0; i < vecmnoznik.size(); ++i) {
  130.                 if (teoria(vecmnoznik[i], czemu_tak_trudno, modulo)) {
  131.                         return vecmnoznik[i];
  132.                 }
  133.         }
  134.         int maxmnoznik = vecmnoznik[0];
  135.         for (int i = 1; i < vecmnoznik.size(); ++i) {
  136.                 if (maxmnoznik < vecmnoznik[i]) {
  137.                         maxmnoznik = vecmnoznik[i];
  138.                 }
  139.         }
  140.         return maxmnoznik;
  141. }
  142.  
  143. void napierwsze(int modulo, vector<int>& pierwsze) {
  144.         int x = sqrt(modulo);
  145.         for (int i = 2; i <= x; i++) {
  146.                 while (modulo % i == 0) {
  147.                         pierwsze.push_back(i);
  148.                         modulo /= i;
  149.                 }
  150.                 if (modulo != 1) {
  151.                         return;
  152.                 }
  153.         }
  154.         pierwsze.push_back(modulo);
  155. }
  156.  
  157. void zapis(const string nazwa, int wartosc) {
  158.         ofstream wyj;
  159.         wyj.open(nazwa, ios::app);
  160.         wyj << wartosc << endl;
  161.         wyj.close();
  162. }
  163.  
  164. void losoweLCG(const int & modulo, const int & mnoznik, const int & przyrost, const int & seed, const int & liczlosowe) {
  165.         int x = seed;
  166.         for (int i = 0; i < liczlosowe; ++i) {
  167.                 x = (mnoznik * x + przyrost) % modulo;
  168.                 zapis("Wyniki.txt", x);
  169.         }
  170. }
  171.  
  172. void LCG(const int & maksymalne, int & seed, const int & liczlosowe) {
  173.         int modulo = maksymalne + 1;
  174.         int rosnie = przyrost(modulo);
  175.         vector<int> pierwsze;
  176.         napierwsze(modulo, pierwsze);
  177.         int mnoznik = mnoz(modulo, pierwsze);
  178.         losoweLCG(modulo, mnoznik, rosnie, seed, liczlosowe);
  179. }
  180.  
  181. void czytajdane(int& rozmiar, int& wartosc) {
  182.         cin >> rozmiar >> wartosc;
  183.         while (rozmiar < 0 || wartosc < 0) {
  184.                 cout << "!";
  185.                 cin >> rozmiar >> wartosc;
  186.         }
  187. }
  188.  
  189. Para znajdzpary(int rozmiar) {
  190.         Para idealna = tablica_par[0];
  191.         int i = 0;
  192.         if (rozmiar > 97)return tablica_par[47];
  193.         while (tablica_par[i].b < rozmiar) {
  194.                 if (tablica_par[i].b < rozmiar) {
  195.                         idealna = tablica_par[i];
  196.                 }
  197.                 i++;
  198.         }
  199.         return idealna;
  200. }
  201.  
  202. void odczyt(string nazwa, int rozmiar, vector<int>& tab) {
  203.         ifstream plik;
  204.         plik.open(nazwa.c_str());
  205.         int tmp;
  206.         if (!plik) {
  207.                 cout << "!";
  208.                 exit(EXIT_FAILURE);
  209.         }
  210.         for (int i = 0; i < rozmiar; ++i) {
  211.                 plik >> tmp;
  212.                 tab.push_back(tmp);
  213.         }
  214.         plik.close();
  215. }
  216.  
  217. void Generuj(const Para& idealnapara, const int & modulo, const int& rozmiar, vector<int>& tab) {
  218.         int k = idealnapara.a;
  219.         int j = idealnapara.b;
  220.         for (int i = 0; i <= 200 * rozmiar; ++i) {
  221.                 tab[k] = (tab[j] + tab[k]) % modulo;
  222.                 if (k == 0) {
  223.                         k = rozmiar;
  224.                 }
  225.                 else if (j == 0) {
  226.                         j = rozmiar;
  227.                 }
  228.                 --j;
  229.                 --k;
  230.         }
  231.         for (int i = 0; i < rozmiar; ++i) {
  232.                 zapis("wyniki2.txt", tab[i]);
  233.         }
  234. }
  235.  
  236. void ijeszczeadytywnie(const int & modul, const int & rozmiar) {
  237.         vector<int> tab;
  238.         Para idealnapara = znajdzpary(rozmiar);
  239.         odczyt("Wyniki.txt", rozmiar, tab);
  240.         reverse(tab.begin(), tab.end());
  241.         Generuj(idealnapara, modul, rozmiar, tab);
  242. }
  243.  
  244. void czysc(const string& nazwa) {
  245.         ofstream wyj;
  246.         wyj.open(nazwa);
  247.         wyj.close();
  248. }
  249.  
  250. int main()
  251. {
  252.         int maksymalna, liczlosowe, seed, rozmiar, modulo, wybor;
  253.         czysc("Wyniki.txt");
  254.         czysc("wyniki2.txt");
  255.         cout << "Liniowo - 1 " << endl;
  256.         cout << "Adytywnie - 2" << endl;
  257.         cin >> wybor;
  258.         if (wybor == 1) {
  259.                 czytajdane(maksymalna, liczlosowe, seed);
  260.                 LCG(maksymalna, seed, liczlosowe);
  261.         }
  262.         else if (wybor == 2) {
  263.                 czytajdane(rozmiar, modulo);
  264.                 seed = losowanie(0, rozmiar);
  265.                 LCG(modulo, seed, rozmiar);
  266.                 ijeszczeadytywnie(modulo, rozmiar);
  267.         }
  268.         else {
  269.                 cout << "!";
  270.         }
  271.         return 0;
  272. }