fork download
copy 
  1.     #include <cmath>
  2.  
  3.     #include <algorithm>
  4.     #include <iostream>
  5.     #include <vector>
  6.  
  7.     // The resulting vector contains at index i the sum of 2^-j for j in [i+1, N]
  8.     // and is padded with one 0 to get the same length as `v`
  9.     static std::vector<double> partialSums(std::vector<double> const& v) {
  10.         std::vector<double> result;
  11.  
  12.         // When summing doubles, we need to start with the smaller ones
  13.         // because of the precision of representations...
  14.  
  15.         double sum = 0;
  16.         for (std::vector<double>::const_reverse_iterator it = v.rbegin(), end = v.rend(); it != end; ++it)
  17.         {
  18.             sum += *it;
  19.             result.push_back(sum);
  20.         }
  21.  
  22.         result.pop_back(); // there is a +1 offset in the indexes of the result
  23.  
  24.         std::reverse(result.begin(), result.end());
  25.  
  26.         result.push_back(0); // pad the vector to have the same length as `v`
  27.  
  28.         return result;   
  29.     }
  30.  
  31.     // The resulting vector contains the indexes elected
  32.     static std::vector<size_t> getIndexesImpl(std::vector<double> const& v,
  33.                                               std::vector<double> const& ps,
  34.                                               double r)
  35.     {
  36.       std::vector<size_t> indexes;
  37.  
  38.       for (size_t i = 0, max = v.size(); i != max; ++i) {
  39.           if (r >= v[i]) {
  40.               std::cout << ".." << r << ">=" << v[i] << "\n";
  41.               r -= v[i];
  42.               indexes.push_back(i);
  43.               continue;
  44.           }
  45.  
  46.           // We favor the closest to 0 in case of equality
  47.           if (std::fabs(r - v[i]) < std::fabs(r - ps[i])) {
  48.               std::cout << ".." << v[i] - r << " < " << r - ps[i] << "\n";
  49.               indexes.push_back(i);
  50.               return indexes;
  51.           }
  52.       }
  53.  
  54.       return indexes;
  55.     }
  56.  
  57.     std::vector<size_t> getIndexes(std::vector<double>& v, double r) {
  58.         std::vector<double> const ps = partialSums(v);
  59.         return getIndexesImpl(v, ps, r);
  60.     }
  61.  
  62.     void printIndexes(std::vector<double>& v, double r) {
  63.         std::vector<size_t> indexes = getIndexes(v, r);
  64.         std::cout << r << ":\n";
  65.         for (size_t i = 0, max = indexes.size(); i != max; ++i) {
  66.             std::cout << "   " << indexes[i] << ": " << v[indexes[i]] << "\n";
  67.         }
  68.  
  69.         std::reverse(indexes.begin(), indexes.end());
  70.         double sum = 0;
  71.         for (size_t i = 0, max = indexes.size(); i != max; ++i) {
  72.             sum += v[indexes[i]];
  73.         }
  74.         std::cout << "=> " << sum << "\n";
  75.     }
  76.  
  77.     int main() {
  78.         std::vector<double> v;
  79.         v.push_back(1.0/2);
  80.         v.push_back(1.0/4);
  81.         v.push_back(1.0/8);
  82.         v.push_back(1.0/16);
  83.         v.push_back(1.0/32);
  84.  
  85.         printIndexes(v, 0.3);
  86.         printIndexes(v, 0.25665238);
  87.     }
Success #stdin #stdout 0.02s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
..0.3>=0.25
..0.0125 < 0.01875
0.3:
   1: 0.25
   3: 0.0625
=> 0.3125
..0.256652>=0.25
0.256652:
   1: 0.25
=> 0.25
https://ideone.com/y7RWz
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

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!