Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <vector>
  4. #include <ctime>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int countCaptures(vector<int> queens)
  10. {
  11.     int counter = 0;
  12.     for(int i=0; i<queens.size()-1; ++i)
  13.     {
  14.         for(int j=i+1; j<queens.size(); ++j)
  15.         {
  16.             if(i-queens[i] == j-queens[j] || i+queens[i] == j+queens[j]) counter++;
  17.         }
  18.     }
  19.     return counter;
  20. }
  21.  
  22. void showVector(vector<int> queens)
  23. {
  24.     for(int i=0; i<queens.size(); i++) cout << queens[i] << "\t";
  25.     cout << endl;
  26. }
  27.  
  28. void showBoard(vector<int> queens)
  29. {
  30.     for(int i=0; i<queens.size(); i++)
  31.     {
  32.         for(int j=0; j<queens.size(); j++)
  33.         {
  34.             if(queens[i]==j) cout << "1 ";
  35.             else cout << "0 ";
  36.         }
  37.         cout << endl;
  38.     }
  39. }
  40.  
  41.  
  42. int main()
  43. {
  44.     srand(time(nullptr));
  45.     int n, k, g, m;
  46.     cout << "Podaj rozmiar planszy: ";
  47.     cin >> n;
  48.     cout << "Podaj licznosc populacji: ";
  49.     cin >> k;
  50.     g = 1;
  51.     cout << "Podaj liczbe generacji: ";
  52.     cin >> g;
  53.     cout << "Podaj prawdopodobienstwo mutacji: ";
  54.     cin >> m;
  55.     vector<vector <int>> population(k, vector<int>(n));
  56.     vector<vector <int>> newPopulation(k, vector<int>(n));
  57.     vector <int> best(n);
  58.     vector <int> captures(k,0);
  59.     vector <int> ranking(k,0);
  60.     bool isFound = false;
  61.     for(int i=0; i<k; ++i)
  62.     {
  63.         for(int j=0; j<n; ++j)
  64.         {
  65.             population[i][j] = j;
  66.         }
  67.         random_shuffle(begin(population[i]), end(population[i]));
  68.     }
  69.     int capturesMax, rankSum;
  70.  
  71.  
  72.     for(int i=0; i<g; i++)
  73.     {
  74.         best = population[0];
  75.         capturesMax = 0;
  76.         rankSum = 0;
  77.         for(int j=0; j<k; j++)
  78.         {
  79.             captures[j] = countCaptures(population[j]);
  80.             if(captures[j]==0)
  81.             {
  82.                 best = population[j];
  83.                 isFound = true;
  84.                 break;
  85.             }
  86.             if(captures[j] > capturesMax) capturesMax = captures[j];
  87.             if(captures[j] < countCaptures(best)) best = population[j];
  88.         }
  89.  
  90.         if(isFound == true) break;
  91.  
  92.         for(int j=0; j<k; j++)
  93.         {
  94.             ranking[j] = capturesMax - captures[j] + 1;
  95.             rankSum += ranking[j];
  96.         }
  97.  
  98.         int roulette;
  99.         for(int j=0; j<k; j++)
  100.         {
  101.             roulette = rand()%rankSum+1;
  102.             int temp = 0;
  103.             for(int l=0; l<k; l++)
  104.             {
  105.                 temp += ranking[l];
  106.                 if(temp >= roulette) newPopulation[j] = population[l];
  107.             }
  108.         }
  109.  
  110.         for(int j=0; j<k; j++)
  111.         {
  112.             if(rand()%101 < m*100)
  113.             {
  114.                 swap(newPopulation[rand()%n], newPopulation[rand()%n]);
  115.             }
  116.         }
  117.  
  118.         population = newPopulation;
  119.     }
  120.  
  121.     cout << endl << endl;
  122.     showVector(best);
  123.     showBoard(best);
  124.     cout << endl << "Liczba bic: " << countCaptures(best);
  125.  
  126.  
  127.  
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement