fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <tuple>
  4.  
  5. int WeightImpl(int i, int q, int d); // forward declaration
  6.  
  7. // Use memoization and use `WeightImpl` for the real computation
  8. int Weight(int i, int q, int d){
  9.     static std::map<std::tuple<int, int, int>, int> memo;
  10.  
  11.     auto it = memo.find(std::make_tuple(i, q, d));
  12.     if (it != memo.end()) {
  13.         return it->second;
  14.     }
  15.     const int res = WeightImpl(i, q, d);
  16.     memo[std::make_tuple(i, q, d)] = res;
  17.     return res;
  18. }
  19.  
  20. // Do the real computation
  21. int WeightImpl(int i, int q, int d){
  22.     int j, sum = 0;
  23.     if (i <= 0)
  24.         return 0;
  25.     else if (i == 1)
  26.         return 1;
  27.     for (j = 1; j <= d; j++){
  28.         sum += Weight((i - j), q, d); // Call the memoize version to save intermediate result
  29.     }
  30.     sum = 1 + ((q - 1) * sum);
  31.     return sum;
  32. }
  33.  
  34. int main() {
  35. 	std::cout << Weight(6, 5, 3) << std::endl;
  36. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3085
https://ideone.com/663sZE
language:
C++14 (gcc 8.3)
created:
10 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!