Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Buckets.cpp, written by Josh Mermelstein
- This program prompts the user for the number of buckets they want, and the sizes of those buckets
- it then prompts for the desired quantity of water to be made from those buckets
- it does simple tests to ensure all these values are positive and consistent with each other
- finally, it outputs a linear combination of the bucket sizes equal to the goal quantity
- consider including: a function to check if any two buckets are the same size
- and ask the user if they wish to replace one of them
- move the calculation of the gcd of the set of buckets[] outside of get_goal
- as it is used quite frequently.
- Last edit 11/06/11
- */
- #include <iostream>
- #include <math.h>
- using namespace std;
- int get_int(string message, int index);
- void get_sizes(int bucket[], int array_size);
- int gcd(int a, int b);
- int get_goal(int bucket[], int array_size);
- void calc_coefficients(int buckets[], int array_size, int coefficient[]);
- void reduce_coefficients(int coefficient[], int array_size, int bucket[]);
- void print(int buckets[], int array_size, int coefficient[], int goal);
- int main()
- {
- //stage 0, various declarations and the input of user data
- //seeming working perfectly as of 10/28 at 1:01 AM.
- int array_size = get_int("how many buckets would you like to use? ", -1);
- int bucket[array_size];
- int coefficient[array_size];
- get_sizes(bucket, array_size);
- int goal = get_goal(bucket, array_size);
- int collective_gcd = 0;
- //stage 1, we fill coefficient[] with the appropriate values such that
- //the dot product of it and bucket[] is the gcd of the bucket sizes
- calc_coefficients(bucket, array_size, coefficient);
- //stage 2, we scale coefficient[] by goal/gcd of the elements of bucket
- collective_gcd = bucket[0];
- for(int i = 1 ; i < array_size ; i++) //finds gcd of all bucket sizes
- {
- collective_gcd = gcd(bucket[i], collective_gcd);
- }
- for(int i = 0; i < array_size; i++)
- {
- coefficient[i] *= (goal/collective_gcd);
- }
- //stage 3, we reduce the coefficients
- reduce_coefficients(coefficient, array_size, bucket);
- //stage 4, we print
- print(bucket, array_size, coefficient, goal);
- return 0;
- }
- /*
- name get_int
- passed a string to display
- returns a user supplyed int
- */
- int get_int(string message, int index)
- {
- int user_input;
- cout << message;
- if(index >= 0)
- cout << '#' << index << ": ";
- cin >> user_input;
- if(user_input <= 0)
- {
- cout << "please enter a value greater than 0 " << endl;
- user_input = get_int(message, index);
- }
- return user_input;
- }
- /*
- name get_sizes
- passed an array and an int of its sizes
- returns nothing
- */
- void get_sizes(int bucket[], int array_size)
- {
- for(int i = 0 ; i < array_size ; i++)
- {
- bucket[i] = get_int("how much water can be held in bucket ", i);
- }
- }
- /*
- name gcd
- passed two ints
- returns their greates common divisor
- note this is just the euclidean algorithem implemeted in a while loop
- */
- int gcd(int a, int b)
- {
- if(b > a)
- return gcd(b, a);
- int c;
- c = a % b;
- if(c == 0)
- return b;
- while(c != 0)
- {
- c = a % b;
- a = b;
- b = c;
- }
- return a;
- }
- /*
- name get_goal
- passed an array of bucket sizes and an int of the size of that array
- returns the goal quantity
- notes gets it own function to make checking if the goal is possible easier
- checks to see if the goal is a divisor of the gcd of the set of buckets
- and if the goal is between 0 and the sum of the sizes of the buckets
- */
- int get_goal(int bucket[], int array_size)
- {
- int max_volume = 0;
- int goal = get_int("how much water would you like? ", -1);
- int running_gcd = bucket[0];
- for(int i = 1 ; i < array_size ; i++) //finds gcd of all bucket sizes
- {
- running_gcd = gcd(bucket[i], running_gcd);
- }
- for(int j = 0 ; j < array_size ; j++) //finds sum of buckets volumes
- {
- max_volume += bucket[j];
- }
- if((goal % running_gcd != 0) || (goal > max_volume) || (goal < 0))
- {
- cout << "The desired value cannot be made from the bucket sizes specified." << endl;
- cout << "Please enter a value that is an integer multiple of " << running_gcd;
- cout << " and is between 0 and " << max_volume << endl;
- return get_goal(bucket, array_size);
- }
- return goal;
- }
- /*
- name calc_coefficients
- passed an array of bucket sizes
- an int of the size of that array
- and array of equal size to hold the coefficents produced
- returns nothing
- notes not actually the extended euclidean algorithem
- */
- void calc_coefficients(int buckets[], int array_size, int coefficient[])
- {
- int running_gcd = gcd(buckets[0], buckets[1]);
- int co_gcd = 0;
- int future_gcd = 0;
- for(int i = 0; i < array_size ; i++)
- {
- coefficient[i] = 0;
- }
- while((buckets[0] * coefficient[0]) + (buckets[1] * coefficient[1]) != running_gcd)
- {
- if((buckets[0] * coefficient[0]) + (buckets[1] * coefficient[1]) > running_gcd)
- {
- coefficient[1]--;
- }
- else if((buckets[0] * coefficient[0]) + (buckets[1] * coefficient[1]) < running_gcd)
- {
- coefficient[0]++;
- }
- }
- for(int j = 2 ; j < array_size ; j++)
- {
- coefficient[j] = 0;
- co_gcd = 0;
- future_gcd = gcd(running_gcd, buckets[j]);
- while((buckets[j] * coefficient[j]) + (running_gcd * co_gcd) != future_gcd)
- {
- if((buckets[j] * coefficient[j]) + (running_gcd * co_gcd) > future_gcd)
- {
- coefficient[j]--;
- }
- else if((buckets[j] * coefficient[j]) + (running_gcd * co_gcd) < future_gcd)
- {
- co_gcd++;
- }
- }
- //multiple all previous coefficients by co_gcd
- for(int k = 0 ; k < j ; k++)
- {
- coefficient[k] *= co_gcd;
- }
- co_gcd = 0;
- running_gcd = future_gcd;
- }
- }
- /*
- name reduce coefficients
- passed the matrix of coefficients
- returns nothing
- purpose reduce the coefficients
- */
- void reduce_coefficients(int coefficient[], int array_size, int bucket[])
- {
- for(int i = 0; i < array_size; i++)
- {
- for(int j = i; j < array_size ; j++)
- {
- if(coefficient[i] > 0 && coefficient[j] < 0)
- {
- //first number too big, second too small
- while(coefficient[i] > bucket[j])
- {
- //note, it is unnecessary to handle the case of first too small, second too big as a result of the way the previous functions do their output.
- coefficient[i] -= bucket[j];
- coefficient[j] += bucket[i];
- }
- }
- }
- }
- }
- /*
- name print
- passed the two arrays of bucket sizes and coefficients, the sizes of those arrays, and the goal value.
- returns nothing
- purpose print the found solution
- */
- void print(int buckets[], int array_size, int coefficient[], int goal)
- {
- for(int i = 0; i < array_size - 1; i++)
- {
- cout << '(' << coefficient[i] << ")*" << buckets[i] << " + ";
- }
- cout << '(' << coefficient[array_size - 1] << ")*" << buckets[array_size - 1] << " = " << goal << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement