• API
• FAQ
• Tools
• Archive
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);
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
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.

Top