SHARE
TWEET

find_rings_2.cc

slatenails Oct 16th, 2013 42 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <deque>
  4. #include <cmath>
  5.  
  6. struct Component
  7. {       int num;
  8.         double scale;
  9. };
  10.  
  11. std::deque<Component> solution;
  12.  
  13. template<class T> inline T abs (T a)
  14. {       return (a > 0) ? a : -a;
  15. }
  16.  
  17. inline bool isZero (double a)
  18. {       return abs<double> (a) < 0.0001;
  19. }
  20.  
  21. inline bool isInteger (double a)
  22. {       return isZero (a - (int) a);
  23. }
  24.  
  25. // =============================================================================
  26. // ringFinder
  27. //
  28. // This is the main algorithm of the ring finder. It tries to use math to find
  29. // the one ring between r0 and r1. If it fails (the ring number is non-integral),
  30. // it finds an intermediate radius (ceil of the ring number times scale) and
  31. // splits the radius at this point, calling this function again to try find the
  32. // rings between r0 - r and r - r1.
  33. //
  34. // This does not always yield into usable results. If at some point r == r0 or
  35. // r == r1, there is no hope of finding the rings, at least with this algorithm,
  36. // as it would fall into an infinite recursion.
  37. // -----------------------------------------------------------------------------
  38. bool ringFinder (double r0, double r1)
  39. {       // Find the scale and number of a ring between r1 and r0.
  40.         double scale = r1 - r0;
  41.         double num = r0 / scale;
  42.  
  43.         // If the ring number is integral, we have found a fitting ring to r0 -> r1!
  44.         if (isInteger (num))
  45.         {       Component cmp;
  46.                 cmp.scale = scale;
  47.                 cmp.num = (int) ceil (num);
  48.                 solution.push_back (cmp);
  49.         }
  50.         else
  51.         {       // If not, find an intermediate <r> between the radii
  52.                 double r = ceil (num) * scale;
  53.  
  54.                 // If r is the same as r0 or r1, we simply cannot find any rings between
  55.                 // r0 and r1. Stop and return failure.
  56.                 if (isZero (r0 - r) || isZero (r1 - r))
  57.                         return false;
  58.  
  59.                 // Split this ring into r0 -> r and r -> r1. Recurse to possibly find
  60.                 // the rings for these. If either recurse fails, the entire algorithm
  61.                 // fails as well.
  62.                 if (!ringFinder (r0, r) || !ringFinder (r, r1))
  63.                         return false;
  64.         }
  65.  
  66.         // The algorithm did not fail, thus we succeeded!
  67.         return true;
  68. }
  69.  
  70. int main (int argc, char* argv[])
  71. {       char* endptr0, *endptr1;
  72.         double r0, r1;
  73.  
  74.         if (argc != 3)
  75.         {       fprintf (stderr, "usage: %s <r0> <r1>\n", argv[0]);
  76.                 return 1;
  77.         }
  78.  
  79.         r0 = strtod (argv[1], &endptr0);
  80.         r1 = strtod (argv[2], &endptr1);
  81.  
  82.         if (*endptr0 != '\0' || *endptr1 != '\0')
  83.         {       fprintf (stderr, "error: arguments are not numbers\n");
  84.                 return 1;
  85.         }
  86.  
  87.         if (r0 > r1)
  88.                 std::swap (r0, r1);
  89.  
  90.         if (!ringFinder (r0, r1))
  91.         {       printf ("Failed to find rings for %g - %g\n", r0, r1);
  92.                 exit (EXIT_FAILURE);
  93.         }
  94.  
  95.         for (std::deque<Component>::iterator it = solution.begin(); it != solution.end(); ++it)
  96.                 printf ("Ring %d, scale by %g (%g -> %g)\n", it->num, it->scale,
  97.                         it->num * it->scale, (it->num + 1) * it->scale);
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top