 # find_rings_2.cc

Oct 16th, 2013
51
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);
76.         return 1;
77.     }
78.
79.     r0 = strtod (argv, &endptr0);
80.     r1 = strtod (argv, &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