Programming Forums - help with assignment code returns no answer

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - help with assignment code returns no answer (http://www.programmingforums.org/showthread.php?t=12189)

help with assignment code returns no answer

i have been on this particular challenge for quite a while now and i want to finish it but i do not know what is wrong with my source.

i would appreciate help and thanks in advance.

this program is trying to do the following

Number Triangles

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

The above figure shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. In the sample shown above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

my triangle is in the zip file.

#include <iostream>

#include <fstream>

using namespace std;



int main()

{

   int num, rows;

   int maxsum[200][200] = {0};

   int best = 0;

    //cout << "it works here: definitions ";

   ifstream infile("INPUT.TXT");

   ofstream outfile("OUTPUT.TXT");

    //cout << "it works here: filestreams ";

   infile >> rows;

   //cout << "it works here: infilestream rows ";

   for(int b = 0; b < 200; b++)

   {

                maxsum[0][b] = 0;

                //cout << "it works here: first for loop: iter:" << b<<" \n";

                for(int r = 1; r < rows; r++)

                {

                        //cout << "it works here: second for loop: iter:"<<r<<" ";

                        //maxsum[r][0] = 0;

                        for(int c = 1; c < r; c++)

                        {

                                //cout << "it works here: third for loop: iter:"<<c<<" ";

                                infile >> num;

                                // cout << num << " ";

                                maxsum[r][c] = (maxsum[r-1][c-1] > maxsum[r-1][c]) ?

                        (maxsum[r-1][c-1] + num) :

                        (maxsum[r-1][c]   + num);

                                // cout << maxsum[r][c] << " " << maxsum[r-1][c-1] << " " << maxsum[r-1][c] << " ";

                        }

                        maxsum[r][r+1] = 0;

                }



                for(int k = 1; k < rows; k++)

                {

                        if(best < maxsum[rows][k]) 

                                best = maxsum[rows][k];

                        //cout << "it works here: fourth for loop: iter:"<<b<<" ";

                }

        }

        outfile << best;

    cout << best<<endl;

        cout << "it works here: last thing\n";

        return 0;

}

the input file is included

>i would appreciate help
I'm sure you would, but until you ask an actual question, you won't get actual help.

>and thanks in advance.
"Thanks in advance" is used by bill collectors as a way to create a feeling of dominance with the expectation of compliance. Some people are very offended by it, so I would recommend saving your thanks until after you've been helped (but never forget it).

I also find your name to be humorously ironic after watching your thread on Daniweb.

i would have thought the name of the thread was enough.

and as to my name i did not stab daniweb in the back by moving into programmingforums because they are friends or allies or something
this thread is to help me complete the assignment the daniweb one was to get rid of the "unknown error".

>i would have thought the name of the thread was enough.
It's not. 'No answer' and 'incorrect answer' are two very different things. From what I've seen of your other thread(s), the problem is that the result is a very large negative number, which suggests that you're overflowing the data type.

I think this will work :



int sum = 0;

int table[5][5] = {.....};



void solve(int i, int j, int &sum_temp)

{

     if (i =< j and i <= 5)

     {

            sum_temp += table[i][j];

            solve(i++ ,j , sum_temp);

            solve(i++, j++, sum_temp);

     }

     else if(i == 6)

     {

              if (sum < sum_temp) sum = sum_temp;

     }

}

But be careful that this program if it works correctly :) (i will try at home) for very large matrixes will need a lot of time solving.

>I think this will work
If by "work" you mean stack overflow then yes, it works perfectly. ;) Tell me, what are the values of i and j after these recursive calls?

solve(i++ ,j , sum_temp);

solve(i++, j++, sum_temp);

sorry to every body here is the revised code :

#include <iostream>

#include <conio.h>



using namespace std;



int table[5][5] = 

/*{{1, 0, 0, 0, 0}, 

{2, 3, 0, 0, 0}, 

{4, 5, 6, 0, 0},

{7, 8, 9, 10, 0},

{11, 12, 13, 14, 15}};*/



{{7, 0, 0, 0, 0}, 

{3, 8, 0, 0, 0}, 

{8, 1, 0, 0, 0},

{2, 7, 4, 4, 0},

{4, 5, 2, 6, 5}};//*/

int sum = 0;



void solve(int i, int j, int sum_temp)

{

     if (i >= j && i < 5 && j < 5)

     {

            sum_temp += table[i][j];

            solve(++i ,j , sum_temp);

            solve(i, ++j, sum_temp);

     }

     else if(i == 5)

     {

              if (sum < sum_temp) sum = sum_temp;

     }

}





int main()

{

        int temp = 0, i = 0, j = 0;



        solve(i, j, temp);

        cout << "Sum is : " << sum << endl;

        getchar();

}

I will work today to solve it iteratively.

Quote:

Originally Posted by Narue (Post 121446)

>I think this will work
If by "work" you mean stack overflow then yes, it works perfectly. ;)

If you read carefully to what i said :
"I THINK THIS WILL WORK", it doesn`t mean that i was 100% sure of it working correctly but as you can see now i think that the new post will work. I only tested it with those two tables, if you see a bug please tell me. ;)

>If you read carefully to what i said
I did read carefully what you said. That's how I knew it was wrong, and a cursory glance at the code was solid proof. ;) You don't guess when it comes to correctness, you test and verify. And of course, you only post untested code in places like this (where people like me reside) if you're supremely confident that it's perfect. ;)

Quote:

Originally Posted by Narue (Post 121511)

I post untested code because i don`t have an internet connection at home. And here where i live the internet connection costs. So when i see a post i reply first with what i think and then as i said to you, that you haven`t read carefully to what i said : "I WILL TEST IT AT HOME". This means that i wasn`t at home in the moment i made a post. What do you think of my previous post and about this one :

#include <iostream>

#include <conio.h>

#include <fstream>

#include <string>



using namespace std;

/*

7 

3 8 

8 1 0 

2 7 4 4 

4 5 2 6 5

*/

const int NMAX = 200;

/*int table[5][5] = 

{{1, 0, 0, 0, 0}, 

{2, 3, 0, 0, 0}, 

{4, 5, 6, 0, 0},

{7, 8, 9, 10, 0},

{11, 12, 13, 14, 15}};



{{7, 0, 0, 0, 0}, 

{3, 8, 0, 0, 0}, 

{8, 1, 0, 0, 0},

{2, 7, 4, 4, 0},

{4, 5, 2, 6, 5}};//*/

int table[NMAX][NMAX] = {0};

int sum = 0;



int find_max();



bool open_file(string fileName)

{

        ifstream inStream(fileName.c_str(), ios::in);

        int size = 0, read = 0, count = 0;



        while (inStream)

        {

                inStream >> read;

                table[size][count] = read;



                if (count == size)

                {

                        size++;

                        count = 0;

                }

                else

                        count++;

        }

        inStream.close();

        return true;

}



void solve_recursive(int i, int j, int sum_temp)

{

     if (i >= j && i < NMAX && j < NMAX)

     {

            sum_temp += table[i][j];

                        

            solve_recursive(++i ,j , sum_temp);

            solve_recursive(i, ++j, sum_temp);

     }

     else if(i == NMAX)

     {

                 if (sum < sum_temp) sum = sum_temp;

     }

}



void solve_iterative()

{

        for (int i = 1; i < NMAX; i++)

                for (int j = 0; j <= i; j++)

                {

                        if (j == i)

                                table[i][j] += table[i-1][j-1];

                        else if (j == 0)

                                table[i][j] += table[i-1][j];

                        else

                                table[i][j] += (table[i-1][j-1] > table[i-1][j]) ? table[i-1][j-1] : table[i-1][j];

                }



        sum = find_max();

}



int find_max()

{

        const int I = NMAX - 1;

        int temp = table[i][0];



        for (int j = 1; j < NMAX; j++)

                if (table[i][j] > temp) temp = table[i][j];



        return temp;

}



int main()

{

        int temp = 0, i = 0, j = 0;

        string file("INPUT.TXT");



        open_file(file);

        solve_recursive(i, j, temp);

        cout << "Recursive sum : " << sum << endl;

        solve_iterative();

        cout << "Iterative sum : " << sum << endl;

        getchar();

}

Again i tell that if ANYONE sees a bug please report it here.