Advertisement
silviubogan

Problemă rezolvată matrice clasa a XI-a mate-info neintensiv

Nov 5th, 2018
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. using namespace std;
  5.  
  6. void back(int K, int N, int P, vector<vector<int>> &Sols, int Sol[])
  7. {
  8.     if (K > P)
  9.     {
  10.         vector<int> v(0);
  11.         for (int i = 1; i <= P; ++i)
  12.         {
  13.             v.push_back(Sol[i]);
  14.         }
  15.         Sols.push_back(v);
  16.         return;
  17.     }
  18.  
  19.     for (int i = Sol[K - 1] + 1; i <= N; ++i)
  20.     {
  21.         Sol[K] = i;
  22.         back(K + 1, N, P, Sols, Sol);
  23.     }
  24. }
  25.  
  26. void back2(int K, int N, int P, vector<vector<int>> &Sols,
  27.     vector<int> &SolFin, vector<bool> &Fol, int &suma, ofstream &out)
  28. {
  29.     if (K > P)
  30.     {
  31.         for (int i = 1; i <= P; ++i)
  32.         {
  33.             out << "( ";
  34.             for (int j = 0; j < P; ++j)
  35.             {
  36.                 out << Sols[SolFin[i]][j] << ' ';
  37.             }
  38.             out << ")" << endl;
  39.         }
  40.         out << " = " << suma << endl << endl;
  41.         return;
  42.     }
  43.  
  44.     for (int i = SolFin[K - 1] + 1; i < N; ++i)
  45.     {
  46.         bool continue2 = false;
  47.         int sumaLocal = 0;
  48.         for (int j = 0; j < P; ++j)
  49.         {
  50.             if (Fol[Sols[i][j]])
  51.             {
  52.                 for (int k = j - 1; k >= 0; --k)
  53.                 {
  54.                     Fol[Sols[i][k]] = false;
  55.                 }
  56.                 continue2 = true;
  57.                 break;
  58.             }
  59.             Fol[Sols[i][j]] = true;
  60.             sumaLocal += Sols[i][j];
  61.         }
  62.  
  63.         if (continue2)
  64.         {
  65.             continue;
  66.         }
  67.  
  68.         if (K == 1)
  69.         {
  70.             suma = sumaLocal;
  71.         }
  72.         else // if (K > 1)
  73.         {
  74.             if (suma != sumaLocal)
  75.             {
  76.                 for (int j = 0; j < P; ++j)
  77.                 {
  78.                     Fol[Sols[i][j]] = false;
  79.                 }
  80.                 continue;
  81.             }
  82.         }
  83.  
  84.         SolFin.push_back(i);
  85.         back2(K + 1, N, P, Sols, SolFin, Fol, suma, out);
  86.         SolFin.pop_back();
  87.  
  88.         for (int j = 0; j < P; ++j)
  89.         {
  90.             Fol[Sols[i][j]] = false;
  91.         }
  92.     }
  93. }
  94.  
  95.  
  96. int main()
  97. {
  98.     int n;
  99.     cout << "n = "; cin >> n;
  100.  
  101.     ofstream out("iesire.out");
  102.  
  103.     vector<vector<int>> Sols(0);
  104.     int Sol[100];
  105.     Sol[0] = 0;
  106.     back(1, n * n, n, Sols, Sol);
  107.     vector<int> SolFin(1, -1); // incepand de la indicele propriu 1, contine indici din Sols
  108.     vector<bool> SolFol(Sols.size() + 1, false);
  109.     vector<bool> Fol(n * n + 1, false);
  110.     int suma = 0;
  111.     back2(1, Sols.size(), n, Sols, SolFin, Fol, suma, out);
  112.  
  113.     out.close();
  114.  
  115.     return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement