PDA

View Full Version : Need help recurssion



Recursive
06-05-2012, 08:16 PM
I am trying to make a cpp program that asks you for an array size, it will then get the array size and the values you want in the array, then it will calculate the value the 2 smallest numbers in the array. So far this is what I have


#include <iostream>
using namespace std;

int addstuff(int array[], int size)
{
int small;
int Nexsmall;
int sum;
if (size == 1)
return array[0];
else


small = array[0];

for (int A = 0; A < size; A++)
{
if (array[A] < small)
small = array[A];
}

Nexsmall = array[1];

for (int X = 0; X < size; X++)
{
if ((array[X] < Nexsmall)&&(array[X] >= small))
{
Nexsmall = array[X];
}

}

//if (Nexsmall == small)


sum = (Nexsmall + small);

return sum;
}

int main()
{
int size;


cout << "Enter the size of the array you want then enter the values in the array: ";
cin>> size;
int Addit[size];
cout<<"Enter the values in the array: ";
for (int I = 0; I < size; I++)
{
cin>> Addit[I];
}

cout<<"The numbers in the array were: "<<endl;
for(int J = 0; J < size; J++)
{
cout<<Addit[J]<<", ";
}
cout<<endl;
cout<<"The sum of the 2 smallest values is: "<<addstuff(Addit, size);
return 0;
}

This works to an extent in that it does not calculate the values of the 2 smallest numbers if they are both the same. Example of the result I get after running it is:


Enter the size of the array you want then enter the values in the array: 6
Enter the values in the array: 1
2
3
4
5
1
The numbers in the array were:
1, 2, 3, 4, 5, 1,
The sum of the 2 smallest values is: 3

Help?

Brandon
06-05-2012, 08:53 PM
I would use pointers in the below code but I'm lazy right now so I used pass by value.. Anyway it still works either way just more memory intensive. This is just an example of how it can be done. I know you might want to do it with arrays but I'll leave that to you unless you need further help.


#include <windows.h>
#include <iostream>
#include <vector>

using namespace std;

int Smallest(vector<int> Array)
{
if (Array.size() == 1)
return Array[0];

int A = Array[0];
for (int I = 0; I < Array.size(); I++)
A = Array[I] < A ? Array[I] : A;

return A;
}

vector<int> DeleteValue(vector<int> ListOfValues, int ValueToDelete)
{
for (int I = 0; I < ListOfValues.size(); I++)
if (ListOfValues[I] == ValueToDelete)
{
ListOfValues.erase(ListOfValues.begin() + I);
return ListOfValues;
}
}

int SumSmallestAmount(int Array[], int size, int HowMany)
{
int result = 0;
vector<int> ListOfValues;

for (int I = 0; I < size; I++)
ListOfValues.push_back(Array[I]);

for (int I = 0; I < HowMany; I++)
{
int J = Smallest(ListOfValues);
result += J;
ListOfValues = DeleteValue(ListOfValues, J);
}

return result;
}

int main()
{
int Array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
cout<<SumSmallestAmount(Array, 10, 4); //Sum of the 4 lowest values.. 0 + 1 + 2 + 3.
}

boobooo42
06-06-2012, 01:07 AM
The proper, and really only, way to create dynamic arrays is with pointers.

I got my C++ book out just for this. WHeee



int size;
cin >> size;
int *list = new int[size];

after you have created the array named 'list' you don't need the * to access the variables in the list. But if you were to use it in a function protoype, then you need the *

Recursive
06-06-2012, 05:29 AM
OMG Brandon, what's with you and trying to make c++ more complicated than it already is?

What in the world of c++ is this? Especially that first function

vector<int> DeleteValue(vector<int> ListOfValues, int ValueToDelete)
{
for (int I = 0; I < ListOfValues.size(); I++)
if (ListOfValues[I] == ValueToDelete)
{
ListOfValues.erase(ListOfValues.begin() + I);
return ListOfValues;
}
}

int SumSmallestAmount(int Array[], int size, int HowMany)
{
int result = 0;
vector<int> ListOfValues;

for (int I = 0; I < size; I++)
ListOfValues.push_back(Array[I]);

for (int I = 0; I < HowMany; I++)
{
int J = Smallest(ListOfValues);
result += J;
ListOfValues = DeleteValue(ListOfValues, J);
}

return result;
}

Brandon
06-06-2012, 05:35 AM
What do you mean make it more complicated :S

The first function returns a vector of integers.. A vector is basically a dynamic array. So essentially I'm using that as an array of integers. What that function is doing is deleted a value from the vector.

Next function will sum the smallest values in the array you provide it. it uses a vector to copy the array for use with the delete function.

Everytime it finds a small value, it stores it adds it to the previous value and then deletes it from the vector. This allows us to add as many minimum values from the array as we like.

I got lazy and did not want to use
int* ListOfValues = new int[size];
delete[] ListOfValues..

Thus I used a vector.

You can use that above function like this.. lets say you want the sum of the 5 smallest values in the following array:

int Array[12] = {0, 4, 1, 2, 3,7, 6, 8, 99, 10, 13, 12}

You'd do:
SumSmallestAmount(Array, 12, 5); Where 12 is the size, 5 is the amount of small values you wish to sum.

Simple as that :S I do not wish to make anyone's life harder than it already is. I hope I did not discourage you. I just wrote what I thought would be easiest for you to understand rather than me placing pointers everywhere. I used to teach C++ to myself and I know how it gets which is why I posted that instead of manually resizing the arrays which is tedious. I know a lot of ppl say C++ is hard :c Trust me I know enough students I tutored saying it's hard. I wouldn't try to make it harder for you :c



If you prefer arrays then this is just a simple solution:


#include <windows.h>
#include <iostream>
#include <vector>

using namespace std;

/** Finds the Smallest Value(s) in an array **/
int Smallest(int Array[], int size)
{
if (size == 1) //So we check if the size of the array is 1. If it is, return the only element.
return Array[0];

int A = Array[0]; //Initialize a global variable to hold our result as the first element.
for (int I = 0; I < size; I++) //Loop through our array while checking if the previous value is less or greater than the current one.
A = Array[I] < A ? Array[I] : A; //If Array[I] < A then A = Array[I] else A = itself. This compares if the previous value (A) is less than the current on (Array[I]).

return A; //return the smallest value.
}

/** Simulates Delete a Value from an array **/
void DeleteElement(int Array[], int& size, int Value)
{
for (int I = 0; I < size; I++) //First we loop through our array.
if (Array[I] == Value) //We check if the value we want to delete is in our array.
{
for (I; I < size - 1; I++) //if it is, loop through our array and shift that value to the very end.
Array[I] = Array[I + 1];
--size; //this is our tracker variable and we minus one from the size to simulate deleting.
break; //after deleting once, we break out of our loop unless you want to delete all of the found values.
}
}

/** Finds Sum of the smallest values in an array **/
int SumSmallestAmount(int Array[], int size, int HowMany)
{
int result = 0; //initialize a global variable that holds the sum of our values.
for (int I = 0; I < HowMany; I++) //we want to sum a certain amount of values so just loop until we reach that amount.
{
int J = Smallest(Array, size); //lets store the smallest amount in a variable.
result += J; //we add our new smallest amount to our previous one which can be 0 or more.
DeleteElement(Array, size, J); //after adding our value, we delete it from the array and start all over until we are done summing the amount.
}

return result; //finally return our sum of "HowMany" values.
}

int main()
{
int Array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; //Our list of numbers.
cout<<SumSmallestAmount(Array, 10, 4); //Prints the sum of the 4 smallest values in the array of size 10.
}


The reason we delete after summing the result is because when we find the smallest value 2 or more times, we don't want that value to always be the same unless it's a duplicate. So after summing it, we just remove it and call smallest again which should give us a new one unless of course it occurred one or more times.

The code looks WAY CLEANER without comments :c Now it looks horrible and looks hard at first sight.

Recursive
06-06-2012, 06:14 AM
Ohh ok. Seems as if the profs at uni did not teach us enough of c++ to make it easier to work with. So how does that delete[] ListOfValues thing work anyways. I seem to recall the profs giving us an assignment in c++ which is to go through an array of values and resizing the array while doing something else with it. So if you don't mind can you post the entire code for that delete[] ListOfValues and what library is it in?

My goal really is to learn as much of c++ and pascal during this summer as I can cause I got a 75% in the course at school and I want to improve seeing as c++ is very widely used.

Brandon
06-06-2012, 06:33 AM
Ohh ok. Seems as if the profs at uni did not teach us enough of c++ to make it easier to work with. So how does that delete[] ListOfValues thing work anyways. I seem to recall the profs giving us an assignment in c++ which is to go through an array of values and resizing the array while doing something else with it. So if you don't mind can you post the entire code for that delete[] ListOfValues and what library is it in?

My goal really is to learn as much of c++ and pascal during this summer as I can cause I got a 75% in the course at school and I want to improve seeing as c++ is very widely used.


My goal is to help you reach yours (ADDED COMMENTS to the Code). Anyway, well now you have two methods as shown above (I just posted the arrays version).

1. Using a vector, you can delete a value any time you wish using vector::erase(Index to remove).
Vectors are found in the <vector> library. Just use #include <vector>

2. The second solution I posted uses strictly arrays since you have not used vectors yet.
To answer your question, You cannot "Delete" from a static array. If an array is allocated with the "new" operator (int* Meh = new int[size]) then it is possible by copying all values to a new array of a different(lesser) size. Otherwise it's impossible and you will understand why when you learn of stack allocation.

3. The New[] and Delete[] Operator is just there and does not need a library. When you use new type[size] to allocate something, you must delete it when you are done using it by doing delete[] NameOfVariable

4. Since we cannot delete from static arrays which you are creating by doing int Array[size], then we simulate deleting by shifting the value we want to delete to the very end of the array. Then we minus one from the size and keep track of it. In all reality, the value was never deleted and it's still there all we did was just memorize that we "simulated removing" 1 value.


Example of simulation:

lets say we have int Array[5] = {1, 2, 3, 4, 5}.
We want to delete the second element (#2) from the array.
We cannot do that since the array is stack allocated aka static and not dynamic (realizable).
So we shall move #2 to the where #5 is.
After doing this the array looks like: {1, 3, 4, 5, 2}.
We know the size of the array is 5 right, so we create a variable and assign it a value of 4. This variable will keep track of how many elements we "deleted/shifted" and in this case we shifted/deleted 1.

We know our array is actually 5 but meh we have a variable keeping track that says it's 4. Get it? Static arrays use a fake deletion and the value is never actually deleted.