Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

fractions.cpp

By: a guest on Feb 1st, 2013  |  syntax: C++  |  size: 1.57 KB  |  views: 31  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }