Guest User

Untitled

a guest
Feb 14th, 2016
63
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. bool ZnajdzSumePar(int rozwiazanie[], int zbior[], int it, int *sumapar, int wielkosc, int *gdzie);
  15. bool ZnajdzSumeCalkowita(int rozwiazanie[], int zbior[], int it, int *suma, int wielkosc, int *gdzie);
  16. void wypisz(int rozwiazanie[], int zbior[], int wielkosc, int ilosc,int start);
  17.  
  18. int max;
  19.  
  20. int main()
  21. {
  22. int *zbior, *rozwiazanie;
  23. int LiczbaCiec = 0, WielkosZbioru = 0;
  24. bool jest = false;
  25.  
  26. cout << "podaj ilosc ciec: " << endl;
  27. cin >> LiczbaCiec;
  28. cout << endl;
  29. preload(WielkosZbioru);
  30. zbior = new int[WielkosZbioru];
  31. wczytaj(zbior, WielkosZbioru );
  32.  
  33. if (spr(LiczbaCiec, WielkosZbioru))
  34. {
  35. cout << " dane wejsiowe poprawne" << endl;
  36.  
  37. rozwiazanie = new int[LiczbaCiec + 1];
  38. for (int i = 0; i <= LiczbaCiec; i++)
  39. rozwiazanie[i] = 0;
  40.  
  41. max = ZnajdzMaxWartosc(WielkosZbioru, zbior);
  42. int submax = ZnajdzSubMaxWartosc(max, WielkosZbioru, zbior);
  43. rozwiazanie[0] = max - submax;
  44.  
  45. for (int i = 0; i <= WielkosZbioru; i++)
  46. if (rozwiazanie[0] == zbior[i])
  47. {
  48. zbior[i] = 0;
  49. break;
  50. }
  51.  
  52. cout << "\n\n";
  53. for (int x = 0; x <= LiczbaCiec; x++)
  54. cout << rozwiazanie[x] << " ";
  55. cout << "\n";
  56. for (int x = 0; x < WielkosZbioru; x++)
  57. cout << zbior[x] << " ";
  58. //mapowanie
  59. mapuj(rozwiazanie, zbior, LiczbaCiec, WielkosZbioru, 1, 3, jest);
  60. if(!jest)
  61. cout << "\n brak rozwiazania\n";
  62. }
  63. else
  64. cout << "\n bledne dane wejsciowe\n";
  65.  
  66. _getch();
  67. return 0;
  68. }
  69. void preload(int &wielkosc)
  70. {
  71. fstream plik;
  72. string dane;
  73. int j = 0;
  74. //============ preload
  75. plik.open("test.txt", ios::in);
  76. while (!plik.eof())
  77. {
  78. getline(plik, dane, ' ');
  79. wielkosc++;
  80. }
  81. plik.close();
  82. }
  83. void wczytaj(int zbior[], int wielkosc)
  84. {
  85. fstream plik;
  86. string dane;
  87. int j = 0;
  88. plik.open("test.txt", ios::in);
  89. plik.clear();
  90. plik.seekg(0, ios::beg);
  91.  
  92. for (int i = 0; i < wielkosc; i++)
  93. {
  94. getline(plik, dane, ' ');
  95. zbior[i] = atoi(dane.c_str());
  96. }
  97.  
  98.  
  99. plik.close();
  100. //wielkosc -= 1;
  101. }
  102. bool spr(int c, int wielksoc)
  103. {
  104. double s1 = 1, s2 = 1;
  105.  
  106. for (int i = 1; i <= c; i++)
  107. s1 *= i;
  108. for (int i = 1; i <= c + 2; i++)
  109. s2 *= i;
  110. cout << s1 << " " << s2 << " " << wielksoc<< " " << s2 / (2 * s1) << endl;
  111. if (wielksoc == s2 / (2 * s1))
  112. return true;
  113. else return false;
  114. }
  115. int ZnajdzMaxWartosc(int c, int zbior[])
  116. {
  117. int maxi = 0;
  118. for (int i = 0; i <= c; i++)
  119. {
  120. if (maxi<zbior[i])
  121. maxi = zbior[i];
  122.  
  123. }
  124. return maxi;
  125. }
  126. int ZnajdzSubMaxWartosc(int maxi, int c, int zbior[])
  127. {
  128. int semimaxi = 0;
  129. for (int j = 0; j < c; j++)
  130. {
  131. if (zbior[j]>semimaxi && zbior[j] < max)
  132. semimaxi = zbior[j];
  133. }
  134. return semimaxi;
  135. }
  136. bool ZnajdzSumePar(int rozwiazanie[], int zbior[], int it, int *sumapar, int wielkosc, int *gdzie)
  137. {
  138. *sumapar = rozwiazanie[it] + rozwiazanie[it - 1];
  139. for (int s = 0; s < wielkosc; s++)
  140. {
  141. if (*sumapar == zbior[s])
  142. {
  143.  
  144. *gdzie = s;
  145. return true;
  146. }
  147. }
  148. return false;
  149. }
  150.  
  151. bool ZnajdzSumeCalkowita(int rozwiazanie[], int zbior[], int it, int *suma, int wielkosc, int *gdzie)
  152. {
  153. *suma += rozwiazanie[it];
  154. for (int s = 0; s < wielkosc; s++)
  155. {
  156. if (*suma == zbior[s])
  157. {
  158.  
  159. *gdzie = s;
  160. return true;
  161. }
  162. }
  163. suma -= rozwiazanie[it];
  164. return false;
  165. }
  166. void wypisz(int rozwiazanie[], int zbior[], int wielkosc, int ilosc,int start)
  167. {
  168. //=====================================================
  169. cout << "\n\n rozwiazanie" << start << "\n";
  170. for (int x = 0; x <= ilosc; x++)
  171. cout << rozwiazanie[x] << " ";
  172. cout << "\n";
  173. for (int x = 0; x < wielkosc; x++)
  174. cout << zbior[x] << " ";
  175. //====================================================
  176. }
  177. void mapuj(int rozwiazanie[], int zbior[], int ilosc, int wielkosc, int start, int suma, bool &jest)
  178. {
  179. int gdziePara=0, gdzieSuma=0;
  180. if (start > ilosc && suma == max)
  181. {
  182. cout << "\n\nROZWIAZANIE\n";
  183. for (int x = 0; x <= ilosc; x++)
  184. cout << rozwiazanie[x] << " ";
  185. cout << "\n";
  186. for (int x = 0; x < wielkosc; x++)
  187. cout << zbior[x] << " ";
  188. jest = true;
  189. return;
  190. }
  191. else if (start == ilosc && suma != max)
  192. return;
  193. if (jest)
  194. return;
  195. else
  196. for (int j = 0; j < wielkosc; j++)
  197. {
  198. while (zbior[j] == 0)
  199. j++;
  200. if (suma + zbior[j] > max)// jak bedzie za duzo to skracamy poszukiwanie i przechodzimy dalej
  201. continue;
  202. rozwiazanie[start] = zbior[j];//dodajemy potencialne rozwiazanie
  203. zbior[j] = 0;
  204. wypisz(rozwiazanie, zbior, wielkosc, ilosc, start);//wypisanie
  205. int sumapar = 0;
  206. if (ZnajdzSumePar(rozwiazanie, zbior, start, &sumapar, wielkosc, &gdziePara))
  207. {
  208. zbior[gdziePara] = 0;
  209. wypisz(rozwiazanie, zbior, wielkosc, ilosc, start);//wypisanie
  210. if (ZnajdzSumeCalkowita(rozwiazanie, zbior, start, &suma, wielkosc, &gdzieSuma))
  211. {
  212. zbior[gdzieSuma] = 0;
  213. wypisz(rozwiazanie, zbior, wielkosc, ilosc, start);//wypisanie
  214. mapuj(rozwiazanie, zbior, ilosc, wielkosc, ++start, suma, jest);
  215. zbior[gdzieSuma] = suma;
  216. suma -= rozwiazanie[start];
  217. }
  218. zbior[gdziePara] = sumapar;
  219. sumapar = 0;
  220. }
  221. zbior[j] = rozwiazanie[start];//to nie to wiec zwracamy
  222. rozwiazanie[start] = 0;
  223. }
  224.  
  225. }
RAW Paste Data