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

Untitled

By: a guest on Sep 15th, 2012  |  syntax: C  |  size: 1.03 KB  |  views: 57  |  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. #include <stdlib.h>
  3. #include <gmp.h>
  4.  
  5. int main(int argc, char *argv[])
  6. {
  7.         const int denominations[] = { 1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
  8.         const int lenDenominations = sizeof(denominations)/sizeof(denominations[0]);
  9.         const int target = 9000000;
  10.  
  11.         MP_INT (*table)[lenDenominations] = malloc(sizeof(MP_INT)*(target+1)*lenDenominations);
  12.         for (int i = 0; i < lenDenominations; i++)
  13.                 mpz_init_set_si(&table[target][i], 1);
  14.  
  15.         for (int sumSoFar = target-1; sumSoFar >= 0; sumSoFar--)
  16.         {
  17.                 for (int minDenomination = lenDenominations-1; minDenomination >= 0; minDenomination--)
  18.                 {
  19.                         mpz_init_set_si(&table[sumSoFar][minDenomination], 0);
  20.                         for (int i = minDenomination; i < lenDenominations; i++)
  21.                         {
  22.                                 int newSumSoFar = sumSoFar + denominations[i];
  23.                                 if (newSumSoFar <= target)
  24.                                         mpz_add(&table[sumSoFar][minDenomination], &table[sumSoFar][minDenomination], &table[newSumSoFar][i]);
  25.                         }
  26.                 }
  27.         }
  28.  
  29.         mpz_out_str(stdout, 10, &table[0][0]);
  30.         fputc('\n', stdout);
  31.  
  32.         return 0;
  33. }
clone this paste RAW Paste Data