Guest User

2) Choose integers so that average is close to given real nu

a guest
Jan 9th, 2015
174
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. #include <cmath>
  5. #include <set>
  6.  
  7. set<long> bestAverage(double target, long first, long range)
  8. {
  9.     set<long> ret;
  10.    
  11.     double bestError = range;
  12.     long bestDivider = 0;
  13.     long bestIncrement;
  14.     long divider;
  15.    
  16.     if (target < first)
  17.     {
  18.         ret.insert(first);
  19.         return ret;
  20.     }
  21.     if (target > first + range - 1)
  22.     {
  23.         ret.insert(first + range - 1);
  24.         return ret;
  25.     }
  26.  
  27.     for(divider = 1; divider < range; divider++)
  28.     {
  29.         // find the franctions with given divider we can reach by averaging in the [first, first+range[ range
  30.         double lowerBound = (first + (first + divider - 1)) / 2.0;
  31.         double higherBound = ((first + range - 1) + (first + range - divider)) / 2.0;
  32.         // there exists a set with average in the range [lowerBound, higherBound] of the form n/divider
  33.        
  34.         double c1 = floor(target * divider) / divider;
  35.         double c2 = ceil(target * divider) / divider;
  36.         double error = min(target - c1, c2 - target);
  37.        
  38.         if ((lowerBound <= target) && (target <= higherBound) && (error < bestError))
  39.         {
  40.             bestError = error;
  41.             bestDivider = divider;
  42.             if (target - c1 < c2 - target)
  43.             {
  44.                 bestIncrement = (long)floor((target - lowerBound) * divider);
  45.             }
  46.             else
  47.             {
  48.                 bestIncrement = (long)ceil((target - lowerBound) * divider);
  49.             }
  50.         }
  51.     }
  52.    
  53.     if (bestDivider == 0)
  54.     {
  55.         return ret;
  56.     }
  57.  
  58.     long incrementLarge = range - bestDivider; // how many increment (from the least possible average) of 1/divider we make my moving an integer all the way from one side of the range to the other
  59.     long numberLarge = bestIncrement / incrementLarge; // how many integers we move all the way (integer division: rounds down)
  60.     long numberSmall = bestDivider - numberLarge;
  61.     long remainder = bestIncrement - numberLarge * incrementLarge;
  62.  
  63.     if (remainder > 0)
  64.     {
  65.         numberSmall--;
  66.     }
  67.  
  68.     for(long index = 0; index < numberSmall; index++)
  69.     {
  70.         ret.insert(first + index);
  71.     }
  72.  
  73.     if (remainder)
  74.     {
  75.         ret.insert(first + numberSmall + remainder);
  76.     }
  77.  
  78.     for(long index = 0; index < numberLarge; index++)
  79.     {
  80.         ret.insert(first + range - numberLarge + index);
  81.     }
  82.  
  83.     return ret;
  84. }
  85.  
  86. int main()
  87. {
  88.     set<long> answer;
  89.     set<long>::iterator it;
  90.    
  91.     double target = 3.1415926536;
  92.     double sum = 0;
  93.    
  94.     cout << "target is " << target << endl;
  95.  
  96.     answer = bestAverage(target, -100, 200);
  97.  
  98.     cout << "Average of " << endl;
  99.     for(it = answer.begin(); it != answer.end(); it++)
  100.     {
  101.         cout << *it << ", ";
  102.         sum += *it;
  103.     }
  104.     cout << endl << " is " << sum / answer.size() << endl;
  105.    
  106.     return 0;
  107. }
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.

×