It is actually a bit untidy since since i never finished before time. But i still want to clean it up.
What im trying to solve is the coin problem. The implementation is slightly different for this assignment.
The idea is one finds the best way to make change using a given set of coins. Let say u make change for 1,2,3,...,99,100 and u cannot make change for 101 using the given coins then 100 is the answer..
Showing you piece of the code will not help. So here the whole thing..Bare in mind its still under contruction so there are things that are not that efficient...
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 500
#define true 1
#define false 0;
long getMinimum(long t1, long t2)
{
if (t1 > t2)
return t2;
return t1;
}
long fillPosition(long *atracker, long **a,long temp_array[], int i , int j)
{
static int count = 0;
if (i == 1) return j;
printf("count: %d\n",++count);
if( atracker[i - 1] >= j) //there exist a value at [i-1][j] in the matrix; we process as normal
{
printf("atracker at i : %d %ld count: %d\n",i,atracker[i - 1],count) ;
atracker[i] = atracker[i] + 1;
if(j - temp_array[i] < 0) return a[i-1][j];
return getMinimum( a[i-1][j], (a[i][j - temp_array[i]] + 1) );
}
long temp = a[i][j - temp_array[i]] + 1;
if (a[i] == NULL) printf("null pointer");
a[i] = realloc(a[i], (atracker[i] + 1) * sizeof(long )); //make space for the new number
atracker[i] = atracker[i] + 1; //update the tracker
return 1;
}
void initializeArray(long *atracker,long **a,long n, long k)
{ //N = the amount of different numbers. each in its own row
//K = the number limit. Used for now. we will dynamically allocate the rest
//printf("xsize: %ld, ysize: %ld\n",n,k);
long i,j;
long count = 0;
for(i = 0; i < n; i++){
for(j = 0; j <= k; j++)
{
if (i == 1 && j != 0)
{
a[i][j] = j;
}
else
if (i == 0 || j == 0)
{
a[i][j] = 0;
count++;
}
else a[i][j] = -1;
}
//printf("j stopped at: %ld count: %ld",j,count);
}
//printf("\n");
atracker[1] = k ;
}
void mergeSort(long A[],long lo,long hi){
void merge(long [],long ,long, long);
if (lo < hi){
long mid = (lo + hi) / 2; //get the midpoint subscript
mergeSort(A,lo,mid); //sort first half
mergeSort(A,mid+1,hi); //sort second half
merge(A,lo,mid,hi); //merge sorted halves
}
}
void merge(long A[],long lo,long mid,long hi)
{
//A[lo..mid] and A[mid+1..hi] are sorted;
//merge the pieces so that A[lo..hi] are sorted;
static long T[MaxSize];
long i = lo;
long j = mid + 1;
long k = lo;
while (i <=mid || j <= hi)
{
if (i > mid) T[k++] = A[j++]; //A[lo..mid] completely processed
else if (j > hi) T[k++] = A[i++]; //A[mid+1..hi] completely processed
else if (A[i] < A[j]) T[k++] = A[i++]; //neither part completed
else T[k++] = A[j++];
}
for(j = lo; j <=hi; j++) A[j] = T[j]; //copy merge elements back to A
}
void initializeArray_1d(long A[], long lo, long hi, long value)
{
int i;
for ( i = 0; i < hi; i++)
A[i] = value;
}
int main()
{
FILE * pFile;
long **a; /* this is the array name */
long *atracker; //used to keep track of the amount on a given row
long K;
long N;
long y_size;
long x_size;
long temp_array[MaxSize]; //used to load stamp values
long i;
long j;
pFile = fopen("INPUTC.txt","r");
if(pFile == NULL)
perror ("The following error occurred: ");
fscanf(pFile,"%ld",&K);
fscanf(pFile,"%ld",&N);
x_size = N + 1;
y_size = K + 1;
//printf("xsize: %ld, ysize: %ld\n",x_size,y_size);
/* allocate storage for an array of pointers */
a = malloc(x_size * sizeof(long *));
atracker = malloc(x_size * sizeof(long)); //initial amount is set to the amount of coins
/* for each pointer, allocate storage for an array of ints */
for (i = 0; i < x_size; i++)
{
a[i] = malloc(y_size * sizeof(long));
}
initializeArray_1d(temp_array,0,MaxSize,10001);
initializeArray_1d(atracker,0,y_size,0);
initializeArray(atracker,a,x_size,y_size);
//printf("%ld \n",atracker[1]);
temp_array[0] = 0;
for(i = 1; i <= x_size; i++)
{
fscanf(pFile,"%ld",&temp_array[i]);
}
mergeSort(temp_array,0,MaxSize -1 );
/* Copy temp array into ist column of 2d array starting at pos 1
for(i = 1; i < x_size; i++)
{
a[i][0] = temp_array[i-1];
}*/
//for(i = 0; i < x_size; i++)
//printf("%ld %ld \n",i,temp_array[i]);
long hold = 0;
/*//i = 11;*/
for(i = 2; i <= x_size -1;i++)
//for(i = 2; i < 9; i++)
{
j = 1;
hold = 0;
while(hold <= K)
{
hold = fillPosition(atracker,a,temp_array,i,j);
a[i][j] = hold;
j++;
}
}
/*
long t = 0;
for(i = 0; i < x_size; i++)
{
printf("array[%ld][%ld] = %ld \n",i,t,temp_array[i]);
} */
/**/
for(i = 0; i < x_size; i++)
{
for (j = 0; j < atracker[i]; j++)
printf("%ld ",a[i][j]);
printf("\n\n");
}
free(a);
fclose (pFile);
return 0;
}and the input file would look something like
40 3
1 2 5
where 1 2 5 are the coins that can be used...at any given point in time u may never used more than 40 coins and 3 the amount of coins given.
Perfection of means and confusion of ends seem to characterize our age. Albert Einstein :confused:
Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
Back to top
