• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# fractions.cpp

a guest Feb 1st, 2013 37 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdio.h>
2.
3. #define SIZE 5
4.
5. int lcm(int, int);
6. int gcd(int, int);
7. void swap(int&, int&);
8. void search(int *vals, int index, int lcm);
9.
10. int main()
11. {
12.    int vals[SIZE];
13.
14.    for(int n=2; n<SIZE; n++)
15.    {
16.       vals[0]=n;
17.       search(vals, 1, n);
18.    }
19. }
20.
21. // currentLCM is the LCM of all values in the array before index
22. void search(int *vals, int index, int currentLCM)
23. {
24.    // Compute currentLCM/vals[0] + currentLCM/[1] + ...
25.    int sum = 0;
26.    for(int i=0; i<index; i++)
27.       sum += currentLCM/vals[i];
28.    if(currentLCM<=sum) return; // current sum is too big
29.
30.    if(index==SIZE-1)
31.    {
32.       int rem = currentLCM - sum;
33.       if(currentLCM%rem == 0)
34.       {
35.          vals[SIZE-1] = currentLCM/rem;
36.          if(vals[SIZE-1] > vals[SIZE-2]) // don't allow a duplicate on the last value
37.          {
38.             for(int i=0; i<SIZE; i++)
39.                printf("%d ", vals[i]);
40.             printf("\n");
41.          }
42.       }
43.    }
44.    else
45.    {
46.       int minNext = vals[index-1] + 1;
47.       int valsLeft = SIZE - index;
48.       int maxNext = currentLCM * valsLeft / (currentLCM - sum);
49.       for(int i=minNext; i<=maxNext; i++)
50.       {
51.          vals[index] = i;
52.          search(vals, index+1, lcm(i, currentLCM));
53.       }
54.    }
55. }
56.
57. // Finds lowest common multiple of two integers
58. int lcm(int x, int y)
59. {
60.    return x/gcd(x,y)*y;
61. }
62.
63. // Finds gcd of two integers
64. int gcd(int x, int y)
65. {
66.    if(x<y) swap(x,y);
67.    if(y==0) return x;
68.    return gcd(x%y, y);
69. }
70.
71. // Swap two integers sexily
72. void swap(int &x, int &y)
73. {
74.    x=x^y;
75.    y=x^y;
76.    x=x^y;
77. }
RAW Paste Data
Top