codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
//this program creats a array and fills it with random integers // then as the user inputs it searches the array for any two numbers that will sum to the input number // limits of the program the highest random integer this program will produce is 2^16-1 or 65535 because that is the maximum space for a int variable //wanted to extend this to double values but caused other errors i didn't want to deal with #include <iostream> #include <cstdlib> using namespace std; void prepareArray(int intArray[], int size); bool findPair(int intArray[], int size,int targetNum, int &firstNum, int& secondNum); //is considerably slow after array is larger than 10000 bool SortFindPair(int sortedArray[], int size, int targetNum, int& first, int& second); void findUnSummedSorted(int sortedArray[], int size); void findUnSummed(int intArray[],int size); int compare (const void * a, const void * b); int main() { // initialize const int SIZE = 10000; int intArray[SIZE]; int sortedArray[SIZE]; int targetNumber = 0, numberOne = 0, numberTwo = 0; char goAgain = 'y'; // fills the array prepareArray(intArray,SIZE); //copys and sorts the array for(int i = 0; i < SIZE; i++) sortedArray[i] = intArray[i]; qsort(sortedArray,SIZE,sizeof(int),compare); while(goAgain == 'y') { // asks user for a number to search cout << "What number would you like to find the sum to?" << endl; cin >> targetNumber; // searches for the pair and displays results cout << "sorted" << endl; if(SortFindPair(sortedArray,SIZE,targetNumber,numberOne,numberTwo)) cout << "Two numbers that sum to " << targetNumber << " are " << numberOne << " and " << numberTwo << "." << endl << endl; else cout << "Sorry but no numbers could be summed to equal " << targetNumber << endl << endl; cout << "unsorted" << endl; if(findPair(intArray,SIZE,targetNumber,numberOne,numberTwo)) cout << "Two numbers that sum to " << targetNumber << " are " << numberOne << " and " << numberTwo << "." << endl << endl; else cout << "Sorry but no numbers could be summed to equal " << targetNumber << endl << endl; cout << "Would you like to try again?" << endl; cin >> goAgain; //findUnSummedSorted(sortedArray,SIZE); //findUnSummed(intArray,SIZE); //warning this line extremely slow for SIZE values greater than 10,000 } return(0); } // fills the array with random numbers void prepareArray(int intArray[], int size) { for(int i = 0; i < size; i++) if((size - i)%(i+1)==0) intArray[i] = rand()*rand()*rand()%size; else intArray[i] = (rand()+rand())%size; for(int i = 0; i < size; i++) //prevents negetive values in the array if( intArray[i] < 0) intArray[i] = intArray[i]*-1; } // searches and array of numbers and returns true and a pair of numbers whose sum is equal to the target number, or false // if no pair of numbers exist // this will work for any array sorted or not but takes a while for large numbers bool findPair(int intArray[], int size,int targetNum, int& firstNum, int& secondNum) { // check that it's actually possible to sum to the target if(targetNum > size*2-2 || targetNum < 0) return(false); // loops through all the numbers between the first and size-1 for( int first = 0; first < size - 1; first++) { if(intArray[first] <= targetNum) // makes sure that we arent summing numbers greater than the target number { // loops through all the numbers between the first and size for(int second = first+1; second < size; second++) { if(intArray[second] <= targetNum) //makes sure that we aren't summing numbers greater than the target num { // checks to see if the sum of the first and second numbers equal the target number if(intArray[first]+intArray[second]==targetNum) { // if so sets the value of firstNum and secondNum respectively and returns true firstNum = intArray[first]; secondNum= intArray[second]; return(true); } } } // else goes to the next number } } // since no pair is found return false return(false); } void findUnSummed(int intArray[],int size) {// just for fun goes through the array and finds all the numbers that can be summed by the numbers in the array int one=0,two=0; // filling in space for the findPair function bool result = false; int totalUnSummable = 0; for(int i = 0; i < size*2 - 1; i++) { result =findPair(intArray,size,i,one,two); if(!result) { cout << i << "\t"; totalUnSummable++; } } cout << "Total number that cant be summed to is " << totalUnSummable << endl; } void findUnSummedSorted(int sortedArray[], int size) {// just for fun goes through the array and finds all the numbers that can be summed by the numbers in the array int one=0,two=0; // filling in space for the findPair function bool result = false; int totalUnSummable = 0; for(int i = 0; i < size*2 - 1; i++) { result =SortFindPair(sortedArray,size,i,one,two); if(!result) { cout << i << "\t"; totalUnSummable++; } } cout << "Total number that cant be summed to is " << totalUnSummable << endl; } int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } // only works for sorted arrays bool SortFindPair(int intArray[], int size, int targetNum, int& first, int& second) { int halfwayIndex = 0, upperBoundIndex = 0,index = 0; //find halfway index= targetNum/2; // starting at the index at half of target number if(intArray[index] > targetNum/2) while(intArray[index] > targetNum/2 && index >= 0) index--; if(intArray[index] == targetNum/2) while(intArray[index-1] == targetNum/2) index--;//finds first occurence of target/2 else if (intArray[index] < targetNum/2) while(intArray[index] < targetNum/2) index++; halfwayIndex = index; // if the key is equal to half the target value great // else if the key is less than half the target increment the index until a key is found that is greater than half // set halfway to that index -1 //find upperBound // if the target number is greater than or equal to the size of the array set the upperbound to the size of the array if(targetNum >= size) upperBoundIndex = size-1; else for(int i = targetNum; i < size; i ++) { // else if the key at index targetnum is less than the value of targetNum increment the index until one is found with // a value greater than the target number // set the value of upperbound to the value of the index - 1 if(intArray[i] > targetNum) { upperBoundIndex = i; break; } upperBoundIndex = i; } //starting at the last value of the first half of the searchable array check the sum of every value in the second half of // the searchable array for equivalance with the target number starting with the first value in the second half of the array for(int firstHalfIndex = halfwayIndex; firstHalfIndex >= 0; firstHalfIndex --) { for(int secondHalfIndex = halfwayIndex+1; secondHalfIndex <= upperBoundIndex; secondHalfIndex++) { if(intArray[firstHalfIndex] + intArray[secondHalfIndex] == targetNum) { first = intArray[firstHalfIndex]; second = intArray[secondHalfIndex]; return (true); } } } return(false); }
Private
[
?
]
Run code
Submit