fork download
copy 
  1. #include <vector>
  2. #include <random>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <numeric>
  6.  
  7. std::ranlux48 rng;
  8.  
  9. // whatever, used sparingly
  10. int pow2(int c)
  11. {
  12.     if (c == 1) return 2;
  13.     return 2 * pow2(c - 1);
  14. }
  15.  
  16. int simulate(int c)
  17. {
  18.     static std::uniform_real_distribution<double> distr(0.0, 1.0);
  19.  
  20.     std::vector<int> levels(c+1, 0);
  21.     levels[0] = 1; // root
  22.  
  23.     int lastNodeLevel = 0;
  24.     for (int i = 0; i < c; ++i)
  25.     {
  26.         for (int currentNodeLevel = lastNodeLevel; currentNodeLevel >= 0; --currentNodeLevel) //from the back so it can be done in place
  27.         {
  28.             const double thresholdProb = std::pow(0.5, currentNodeLevel + 1);
  29.             const int nodesAtCurrentLevel = levels[currentNodeLevel];
  30.             for (int j = 0; j < nodesAtCurrentLevel; ++j)
  31.             {
  32.                 if (distr(rng) < thresholdProb)
  33.                 {
  34.                     ++levels[currentNodeLevel + 1];
  35.                     lastNodeLevel = std::max(lastNodeLevel, currentNodeLevel + 1);
  36.                 }
  37.             }
  38.         }
  39.     }
  40.  
  41.     return std::accumulate(levels.begin(), levels.end(), 0);
  42. }
  43.  
  44. int main()
  45. {
  46.     constexpr int cMin = 1;
  47.     constexpr int cMax = 10;
  48.     constexpr int iterations = 1000;
  49.  
  50.     for (int c = cMin; c <= cMax; ++c)
  51.     {
  52.         int maxNodes = pow2(c);
  53.  
  54.         std::vector<int> counts;
  55.         counts.resize(maxNodes + 1, 0);
  56.         std::cout << "c = " << c << ", iterations = " << iterations << '\n';
  57.         for (int i = 0; i < iterations; ++i)
  58.             ++counts[simulate(c)];
  59.  
  60.         for (int i = 1; i <= maxNodes; ++i)
  61.         {
  62.             if (counts[i] == 0) continue;
  63.             std::cout << "n = " << i << ": " << counts[i] / static_cast<double>(iterations) << '\n';
  64.         }
  65.  
  66.         std::cout << "---------------------------------\n";
  67.     }
  68.     return 0;
  69. }
  70.  
  71.  
Success #stdin #stdout 0.08s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
c = 1, iterations = 1000
n = 1: 0.502
n = 2: 0.498
---------------------------------
c = 2, iterations = 1000
n = 1: 0.236
n = 2: 0.433
n = 3: 0.266
n = 4: 0.065
---------------------------------
c = 3, iterations = 1000
n = 1: 0.112
n = 2: 0.294
n = 3: 0.29
n = 4: 0.197
n = 5: 0.083
n = 6: 0.019
n = 7: 0.005
---------------------------------
c = 4, iterations = 1000
n = 1: 0.068
n = 2: 0.176
n = 3: 0.217
n = 4: 0.227
n = 5: 0.163
n = 6: 0.092
n = 7: 0.032
n = 8: 0.018
n = 9: 0.006
n = 10: 0.001
---------------------------------
c = 5, iterations = 1000
n = 1: 0.041
n = 2: 0.087
n = 3: 0.167
n = 4: 0.168
n = 5: 0.183
n = 6: 0.138
n = 7: 0.1
n = 8: 0.055
n = 9: 0.034
n = 10: 0.015
n = 11: 0.007
n = 12: 0.001
n = 13: 0.004
---------------------------------
c = 6, iterations = 1000
n = 1: 0.017
n = 2: 0.053
n = 3: 0.099
n = 4: 0.133
n = 5: 0.148
n = 6: 0.152
n = 7: 0.122
n = 8: 0.081
n = 9: 0.062
n = 10: 0.059
n = 11: 0.033
n = 12: 0.021
n = 13: 0.011
n = 14: 0.003
n = 15: 0.003
n = 16: 0.002
n = 17: 0.001
---------------------------------
c = 7, iterations = 1000
n = 1: 0.009
n = 2: 0.025
n = 3: 0.056
n = 4: 0.078
n = 5: 0.096
n = 6: 0.105
n = 7: 0.12
n = 8: 0.135
n = 9: 0.1
n = 10: 0.075
n = 11: 0.078
n = 12: 0.047
n = 13: 0.027
n = 14: 0.023
n = 15: 0.012
n = 16: 0.007
n = 17: 0.001
n = 18: 0.002
n = 19: 0.003
n = 20: 0.001
---------------------------------
c = 8, iterations = 1000
n = 1: 0.007
n = 2: 0.01
n = 3: 0.027
n = 4: 0.055
n = 5: 0.056
n = 6: 0.09
n = 7: 0.092
n = 8: 0.098
n = 9: 0.098
n = 10: 0.089
n = 11: 0.098
n = 12: 0.064
n = 13: 0.068
n = 14: 0.037
n = 15: 0.041
n = 16: 0.024
n = 17: 0.015
n = 18: 0.012
n = 19: 0.007
n = 20: 0.005
n = 21: 0.002
n = 22: 0.003
n = 25: 0.002
---------------------------------
c = 9, iterations = 1000
n = 1: 0.001
n = 2: 0.01
n = 3: 0.012
n = 4: 0.03
n = 5: 0.043
n = 6: 0.052
n = 7: 0.054
n = 8: 0.087
n = 9: 0.084
n = 10: 0.094
n = 11: 0.071
n = 12: 0.086
n = 13: 0.066
n = 14: 0.062
n = 15: 0.049
n = 16: 0.048
n = 17: 0.038
n = 18: 0.031
n = 19: 0.017
n = 20: 0.018
n = 21: 0.019
n = 22: 0.007
n = 23: 0.003
n = 24: 0.007
n = 25: 0.004
n = 26: 0.001
n = 27: 0.003
n = 29: 0.002
n = 30: 0.001
---------------------------------
c = 10, iterations = 1000
n = 2: 0.001
n = 3: 0.017
n = 4: 0.018
n = 5: 0.022
n = 6: 0.026
n = 7: 0.06
n = 8: 0.053
n = 9: 0.065
n = 10: 0.071
n = 11: 0.071
n = 12: 0.067
n = 13: 0.069
n = 14: 0.064
n = 15: 0.058
n = 16: 0.064
n = 17: 0.057
n = 18: 0.042
n = 19: 0.044
n = 20: 0.03
n = 21: 0.023
n = 22: 0.015
n = 23: 0.008
n = 24: 0.009
n = 25: 0.01
n = 26: 0.011
n = 27: 0.007
n = 28: 0.003
n = 29: 0.006
n = 30: 0.002
n = 31: 0.003
n = 32: 0.002
n = 36: 0.002
---------------------------------
https://ideone.com/T82lPL
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!