makshev1

Untitled

Apr 20th, 2021
467
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*  1296. КУЧА КАМНЕЙ
  2.  
  3.     АЛГОРИТМ: задача решается методом перебора. В основной функции сначала происходит проверка индекса - если он равен N,
  4. то разбор одного из случаев закончен, и необходимо сравнить текущую разность между кучами с предыдущей и запомнить
  5. минимальное из этих чисел. Если индекс меньше N, то происходит рассмотрение возможных случаев разложения - рекурсивно
  6. вызывается эта же функция для случая, когда следующий элемент будет положен в кучу 1, и для случая, когда следующий
  7. элемент будет положен в кучу 2. Засчет этих рекурсивных вызовов происходит перебор всевозможных разложений.
  8.  
  9.     ОЦЕНКА ВРЕМЕНИ РАБОТЫ: для оценки сложности рекурсивного алгоритма построим дерево вызовов. Глубиной дерева будет являться (N+1),
  10. т.к. каждый новый вызов происходит сувеличением индекса (i) с нуля до N. На k-ом уровне происходит (2^k * c) операций =>
  11. всего операций (2^0 * c) + (2^1 * c) + ... + (2^N * c). Если вынести c за скобки, получится сумма геометрической прогрессии, равная
  12. S = 2^(N+1) - 1. Согласно О-асимптотике можно сказать, что T(N) = O(2^N) */
  13.  
  14. #include <iostream>
  15.  
  16.  
  17. using namespace std;
  18.  
  19. void heapDivide (int i, int s1, int s2);
  20. int N;
  21. int s;
  22. int* A;
  23. int m = INT_MAX;
  24.  
  25. int main()
  26. {
  27.     cin >> N;
  28.  
  29.     A = new int[N];
  30.     for (int i = 0; i < N; i++) {
  31.         cin >> A[i];
  32.         s += A[i];
  33.     }
  34.  
  35.     heapDivide(0, 0, 0);
  36.     cout << m;
  37.  
  38.     getchar();
  39.     getchar();
  40.  
  41.     return 0;
  42. }
  43.  
  44. void heapDivide (int i, int s1, int s2) {
  45.  
  46.     if(i == N) {
  47.         m = min(m, abs(s1 - s2));
  48.     }  else {
  49.         heapDivide(i + 1, s1 + A[i], s2);
  50.         heapDivide(i + 1, s1, s2 + A[i]);
  51.     }
  52.  
  53. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×