fork(1) download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <functional>
  4. #include <vector>
  5. #include <cmath>
  6. #include <queue>
  7. #include <string>
  8. using namespace std;
  9.  
  10. using ld = double;
  11. using vld = vector<ld>;
  12.  
  13. vld generate(int n)
  14. {
  15. vld result;
  16. for (; n > 0; n--)
  17. result.push_back(ld(1) / n / n);
  18. reverse(result.begin(), result.end());
  19. return result;
  20. }
  21.  
  22. ld sum_series()
  23. {
  24. ld pi = acos(ld(0)) * 2;
  25. return pi * pi / 6;
  26. }
  27.  
  28. ld sum_naive(vld v)
  29. {
  30. ld result = 0;
  31. for (auto d : v)
  32. result += d;
  33. return result;
  34. }
  35.  
  36. ld sum_recursive_range(const vld &v, int l, int r)
  37. {
  38. if (l == r)
  39. return v[r];
  40.  
  41. int mid = (l + r) / 2;
  42. return sum_recursive_range(v, l, mid) + sum_recursive_range(v, mid + 1, r);
  43. }
  44.  
  45. ld sum_recursive(vld v)
  46. {
  47. random_shuffle(v.begin(), v.end());
  48. return sum_recursive_range(v, 0, (int)v.size() - 1);
  49. }
  50.  
  51. ld sum_huffman(vld v)
  52. {
  53. priority_queue<ld, vector<ld>, greater<ld>> q(v.begin(), v.end());
  54. while (q.size() != 1)
  55. {
  56. auto d1 = q.top();
  57. q.pop();
  58. auto d2 = q.top();
  59. q.pop();
  60. q.push(d1 + d2);
  61. }
  62. return q.top();
  63. }
  64.  
  65. void dump(string prefix, ld x)
  66. {
  67. cout << prefix << ": " << x << " (error " << fabs(x - sum_series()) << ")" << endl;
  68. }
  69.  
  70. void dump(int n)
  71. {
  72. auto v = generate(n);
  73.  
  74. cout << "Case #" << n << endl;
  75. dump("Naive direct", sum_naive(v));
  76. reverse(v.begin(), v.end());
  77. dump("Naive reversed", sum_naive(v));
  78.  
  79. dump("Recursive 1", sum_recursive(v));
  80. dump("Recursive 2", sum_recursive(v));
  81. dump("Recursive 3", sum_recursive(v));
  82. dump("Recursive 4", sum_recursive(v));
  83.  
  84. dump("Huffman", sum_huffman(v));
  85. }
  86.  
  87. int main()
  88. {
  89. srand(322);
  90.  
  91. cout.setf(ios::fixed);
  92. cout.precision(20);
  93.  
  94. cout << "Series sum: " << sum_series() << endl;
  95. dump(10000000);
  96.  
  97. return 0;
  98. }
  99.  
  100.  
Success #stdin #stdout 4.64s 15248KB
stdin
Standard input is empty
stdout
Series sum: 1.64493406684822640607
Case #10000000
Naive direct: 1.64493396684725956547 (error 0.00000010000096684060)
Naive reversed: 1.64493396684823145470 (error 0.00000009999999495136)
Recursive 1: 1.64493396684823123266 (error 0.00000009999999517341)
Recursive 2: 1.64493396684823167675 (error 0.00000009999999472932)
Recursive 3: 1.64493396684823145470 (error 0.00000009999999495136)
Recursive 4: 1.64493396684823167675 (error 0.00000009999999472932)
Huffman: 1.64493396684823145470 (error 0.00000009999999495136)