I'd say, whole numbers.
Memoization seems to have solved it, with a nice pair of mutually recursive functions.
Code:
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int min(int x,int y,int z)
{
x=(y<x)?y:x;
x=(z<x)?z:x;
return x;
}
int check(int n,int x,int y,int z);
int check_rec(int n,int x,int y,int z) /*-1 for no, 1 for yes*/
{
if(n<min(x,y,z))
return -1;
else if(n==x||n==y||n==z)
return 1;
else
return (check(n-x,x,y,z)==1||check(n-y,x,y,z)==1||check(n-z,x,y,z)==1)?1:-1;
}
int check(int n,int x,int y,int z)
{
static int* table=NULL;
if(!table)
table=calloc(1000,sizeof(int));
if(n<0)
return -1;
if(table[n]==0)
table[n]=check_rec(n,x,y,z);
return table[n];
}
int main(void)
{
int n,x,y,z;
clock_t tms,tme;
srand(time(NULL));
while(1)
{
int m;
n= rand() % 999 +1;
x= rand() % 100+1;
y= rand() % 100+1;
z= rand() % 100+1;
printf("%d %d %d %d\n",n,x,y,z);
tms = clock();
m = check(n,x,y,z);
tme = clock();
printf("MM:%d\t%lf\n",m,((double)(tme-tms))/CLOCKS_PER_SEC);
}
return 0;
}
Now, I'd look for a while trying to find a better solution.
I'm not yet totally sure how Euclid's Algorithm can help, but the similarity is worth investigating more.