Guest User

Untitled

a guest
Feb 14th, 2016
141
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <conio.h>
  3. #include <fstream>
  4. #include <string>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. void wczytaj(int zbior[], int wielkosc);
  9. void preload(int &wielkosc);
  10. bool spr(int liczbaciec, int wielkosc);
  11. int ZnajdzMaxWartosc(int wielkosc, int zbior[]);
  12. void mapuj(int rozwiazanie[], int zbior[], int ilosc, int wielkosc, int start, int suma,bool &jest);
  13. int ZnajdzSubMaxWartosc(int max, int wielkosc, int zbior[]);
  14.  
  15. int max;
  16.  
  17. int main()
  18. {
  19. int *zbior, *rozwiazanie;
  20. int LiczbaCiec = 0, WielkosZbioru = 0;
  21. bool jest = false;
  22.  
  23. cout << "podaj ilosc ciec: " << endl;
  24. cin >> LiczbaCiec;
  25. cout << endl;
  26. preload(WielkosZbioru);
  27. zbior = new int[WielkosZbioru];
  28. wczytaj(zbior, WielkosZbioru );
  29.  
  30. if (spr(LiczbaCiec, WielkosZbioru))
  31. {
  32. cout << " dane wejsiowe poprawne" << endl;
  33.  
  34. rozwiazanie = new int[LiczbaCiec + 1];
  35. for (int i = 0; i < LiczbaCiec; i++)
  36. rozwiazanie[i] = 0;
  37.  
  38. max = ZnajdzMaxWartosc(WielkosZbioru, zbior);
  39. int submax = ZnajdzSubMaxWartosc(max, WielkosZbioru, zbior);
  40. rozwiazanie[0] = max - submax;
  41.  
  42. for (int i = 0; i <= WielkosZbioru; i++)
  43. if (rozwiazanie[0] == zbior[i])
  44. {
  45. zbior[i] = 0;
  46. break;
  47. }
  48.  
  49. cout << "\n\n";
  50. for (int x = 0; x < LiczbaCiec; x++)
  51. cout << rozwiazanie[x] << " ";
  52. cout << "\n";
  53. for (int x = 0; x < WielkosZbioru; x++)
  54. cout << zbior[x] << " ";
  55. //mapowanie
  56. mapuj(rozwiazanie, zbior, LiczbaCiec, WielkosZbioru, 1, 3, jest);
  57. if(!jest)
  58. cout << "\n brak rozwiazania\n";
  59. }
  60. else
  61. cout << "\n bledne dane wejsciowe\n";
  62.  
  63. _getch();
  64. return 0;
  65. }
  66. void preload(int &wielkosc)
  67. {
  68. fstream plik;
  69. string dane;
  70. int j = 0;
  71. //============ preload
  72. plik.open("test.txt", ios::in);
  73. while (!plik.eof())
  74. {
  75. getline(plik, dane, ' ');
  76. wielkosc++;
  77. }
  78. plik.close();
  79. }
  80. void wczytaj(int zbior[], int wielkosc)
  81. {
  82. fstream plik;
  83. string dane;
  84. int j = 0;
  85. plik.open("test.txt", ios::in);
  86. plik.clear();
  87. plik.seekg(0, ios::beg);
  88.  
  89. for (int i = 0; i < wielkosc; i++)
  90. {
  91. getline(plik, dane, ' ');
  92. zbior[i] = atoi(dane.c_str());
  93. }
  94.  
  95.  
  96. plik.close();
  97. //wielkosc -= 1;
  98. }
  99. bool spr(int c, int wielksoc)
  100. {
  101. double s1 = 1, s2 = 1;
  102.  
  103. for (int i = 1; i <= c; i++)
  104. s1 *= i;
  105. for (int i = 1; i <= c + 2; i++)
  106. s2 *= i;
  107. cout << s1 << " " << s2 << " " << wielksoc<< " " << s2 / (2 * s1) << endl;
  108. if (wielksoc == s2 / (2 * s1))
  109. return true;
  110. else return false;
  111. }
  112. int ZnajdzMaxWartosc(int c, int zbior[])
  113. {
  114. int maxi = 0;
  115. for (int i = 0; i <= c; i++)
  116. {
  117. if (maxi<zbior[i])
  118. maxi = zbior[i];
  119.  
  120. }
  121. return maxi;
  122. }
  123. int ZnajdzSubMaxWartosc(int maxi, int c, int zbior[])
  124. {
  125. int semimaxi = 0;
  126. for (int j = 0; j < c; j++)
  127. {
  128. if (zbior[j]>semimaxi && zbior[j] < max)
  129. semimaxi = zbior[j];
  130. }
  131. return semimaxi;
  132. }
  133. void mapuj(int rozwiazanie[], int zbior[], int ilosc, int wielkosc, int start, int suma, bool &jest)
  134. {
  135. if (start > ilosc && suma == max)
  136. {
  137. cout << "\n\nROZWIAZANIE\n";
  138. for (int x = 0; x < ilosc; x++)
  139. cout << rozwiazanie[x] << " ";
  140. cout << "\n";
  141. for (int x = 0; x < wielkosc; x++)
  142. cout << zbior[x] << " ";
  143. jest = true;
  144. return;
  145. }
  146. else if (start == ilosc && suma != max)
  147. return;
  148. if (jest)
  149. return;
  150. else for (int i = start; i <= ilosc; i++)
  151. {
  152. for (int j = 0; j < wielkosc; j++)
  153. {
  154. while (zbior[j] == 0)
  155. j++;
  156. if (suma + zbior[j] > max)// jak bedzie za duzo to skracamy poszukiwanie i przechodzimy dalej
  157. continue;
  158. rozwiazanie[i] = zbior[j];//dodajemy potencialne rozwiazanie
  159. zbior[j] = 0;
  160. int sumapar = rozwiazanie[i] + rozwiazanie[i - 1];
  161. for (int s = 0; s < wielkosc;s++)
  162. {
  163. if (sumapar == zbior[s])
  164. {
  165. //if (i - 1 != 0)
  166. zbior[s] = 0; // znalezlismy to usuwamy z potencialnych rozwiazan
  167. suma += rozwiazanie[i];
  168. for (int ss = 0; ss < wielkosc; ss++)
  169. {
  170. if (suma == zbior[ss])
  171. {
  172.  
  173. zbior[ss] = 0;//usuwamy z potencialnych rozwiazan
  174. //=========================================
  175. cout << "\n";
  176. for (int x = 0; x < ilosc; x++)
  177. cout << rozwiazanie[x] << " ";
  178. cout << "\n";
  179. for (int x = 0; x < wielkosc; x++)
  180. cout << zbior[x] << " ";
  181. //=========================================
  182. mapuj(rozwiazanie, zbior, ilosc, wielkosc, ++i, suma, jest);
  183. zbior[ss] = suma;// to nie to wiec zwracamy
  184. break;
  185. }
  186. }
  187. suma -= rozwiazanie[i];
  188. zbior[s] = sumapar;// to nie to wiec zwracamy
  189. break;
  190. }
  191. }
  192. zbior[j] = rozwiazanie[i];//to nie to wiec zwracamy
  193. rozwiazanie[i] = 0;
  194. }
  195. }
  196. }
RAW Paste Data