What am I doing wrong?

[Arslan7041]

Take a look at EXERCISE 12 in this link: https://en.wikibooks.org/wiki/C%2B%2B_Programming/Exercises/Iterations

Write a program that asks the user to type an integer N and compute u(N) defined with :
u(0)=3
u(1)=2
u(n)=n*u(n-1)+(n+1)*u(n-2)+n

I've done the math for the next two on paper and here is what it should be:
u(3) = 56
u(4) = 303

I've tried to write a program to do this but it doesn't work. Here is what I have:

#include <iostream>
#include <cmath>


using namespace std;

int main()
{
    int N, zeroth=3, first=2, second, third;

for(int i = 1; i<10; i++)
{
    cout << "Enter in an integer N: " << flush;
    cin >> N;

    second = N*first + (N+1)*zeroth + N;

    if(N==0)
        cout << "u(" << N << ") = " << zeroth << endl << endl;
    else if (N==1)
        cout << "u(" << N << ") = " << first << endl << endl;

    else if (N==2)
        cout << "u(" << N << ") = " << second << endl << endl;

    else if(N>2)
    {

        second = N*first + (N+1)*zeroth + N;
        zeroth = first;
        first = second;
        third = N*first + (N+1)*zeroth + N;

        cout << "u("<< N << ") = " << third << endl << endl;

    }
}

    cin.get();
}

But my output for u(3) and u(4) dont match what I have on paper. I get 74 and 501 respectively.

What am I doing wrong? I've traced the program and still can't figure out hows its getting 74 for u(3).

Additionally, how do I make it so that the value does NOT change once I go back to u(3) from a different number?

Any help with this would be appreciated.

No this is not for class. Im just practicing c++ on my own.

[keskiverto]

No this is not for class. Im just practicing c++ on my own.

Quite literally homework then.


How about writing a function that takes an integer and returns an integer? One could call it, for example, int u( int n );

Then again, that leads to recursion, which probably is not the theme of the chapter. Perhaps, a more appropriate function is int u( int n, int u1, int u2 );

The keyword in your link is iteration. I see no iteration in your code for cases that have 1<N.

Note, the u(2) is not a special case; only u(0) and u(1) are (assuming that the user types only positive numbers).

[giblit]

The wiki article literally has like 5 example programs you could look at. Though as mentioned earlier you are missing iteration which is the key element of these exercises. I personally would do recursion like mentioned before but that isn't the purpose of exercise since they explicitly said iteration so in that case you will need some sort of loop.

[Arslan7041]

Quite literally homework then.

Thank you for making that wild assumption. If I've clearly said, "Im practicing c++ on my own" and even posted my own attempt at the code, then you should just trust me instead of going with the oh-so popular reply on this forum of "its homework". Is it that hard to believe that someone is genuinely trying to learn c++ on his own and found a website with example exercises and is having trouble with one of them?

I know I could do this with recursion, but I'd rather try to do it without it. I did exercise 8 (a similar problem) without recursion and it worked just fine. Im trying to do something similar here.

Thank you gilbilt and keskiverto for your responses. I'll play around a bit more based on your suggestions and re-post my revised code if I still need help.

P.S. I know the article has solutions, but I'd rather not look at them yet. I like to look at the solutions at the end once I've written my own code correctly. It saves me from the "hindsight bias".

[Arslan7041]

Ok, so below is a slight improvement to the original code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int N, zeroth=3, first=2, second, third;

    for(int i = 1; i<10; i++)
    {
        cout << "Enter in an integer N: " << flush;
        cin >> N;

        if(N==0)
            cout << "u(" << N << ") = " << zeroth << endl << endl;
        else if (N==1)
            cout << "u(" << N << ") = " << first << endl << endl;

        while(N>=2)
        {
            second = N*first + (N+1)*zeroth + N;
            zeroth = first;
            first = second;

            cout << "u("<< N << ") = " << second << endl << endl;
            break;

        }
    }

    cin.get();
}

It works, but only if I enter in the numbers in order (i.e. 0, 1, 2...). If I skip around or go back to a different number it messes up and outputs the incorrect answer.

So If I enter in a 1 after entering in a 3, it outputs "u(1) = 56". What I dont understand is why it doesn't perform the else if statement that I have for the case where N==1?

It seems as though it skips over it if I go back to.

If I go straight into the loop with N>2 on the first entry, then also it outputs the incorrect answer. Not sure why again.

Any idea what am I missing here?

[keskiverto]

You don't seem to understand the meaning of "homework". Homework (according to me) is something that one does at home (or similar location) on their own with a goal to learn.

Unlike attendees of classes, you have an extra challenge. You are your own "professor", who is "reluctant to guide the student", but will immediately know if you cheat. Then again, your "class" does not give any credit or diploma, so the only thing that you can get out of the study is knowledge and skill. IMO, one should attend classes in order to genuinely learn, not to "just get credit points".


The exercise is in an "appendix to a book" in a "group" that has label "iteration". Books tend to be divided into parts, chapters, sections, paragraphs. Humans have innate need to categorize. I used the label "chapter" as it did seem "a scope of natural size" for the topic (of iteration).


Most of those posted solutions are recursive. There is one iterative solution, and it is actually the shortest of them all due to nearly obfuscatingly compact style.

The (typical) recursive solution for this problem operates "top down". The user simply calls answer = u( N );. That keeps the "main program" extremely simple. The called function, however, has to make recursive calls with smaller N and take care of the conditions that end the recursion.

The iteration works "bottom up". The "main program" essentially calculates the value of u(x) for every x in [0..N], and has to store enough intermediary results for the iteration to progress. The main program is more complex, but the u() is called much less than in recursion.

Lets count for N=5.

Iteration: v(0) and v(1) are trivial. v() is called 4 times.

Recursion:
u(5)#1 calls u(4)#2 and u(3)#3
u(4)#2 calls u(3)#4 and u(2)#5
u(3)#4 calls u(2)#6 and u(1)#7
u(2)#6 calls u(1)#8 and u(0)#9
u(2)#5 calls u(1)#10 and u(0)#11
u(3)#3 calls u(2)#12 and u(1)#13
u(2)#12 calls u(1)#14 and u(0)#15

15 calls of u(), if I'm not mistaken and 5 is still a small N. Furthermore, the u() is more complex than the v().


PS. Why did you have the "repeat 10 times" loop on line 11?

[mutexe]

Homework (according to me) is something that one does at home (or similar location) on their own with a goal to learn.

I reckon you're in a minority with this definition. I left school over 20 years ago but when someone says the word "homework" I still think its work done at home, intended for school.
But maybe that's just me :)

[giblit]

You're going to need a few variables.

There are going to be 2 constants (or you can do 3)
1 - u(0) = 3
2 - u(1) = 2
3 - u(2) = 15 - optional and makes it easier

Then you are going to need 4 other variables.
1 - n
2 u(n-0)
3 u(n-1)
4 u(n-2)


then pseudo code:

set initial value for u(0), u(1), u(2)

iterate for n = 3 -> n
u(n-2) = u(n-1)
u(n-1) = u(n)
u(n) = n*u(n-1)+(n+1)*u(n-2)+n

return u(n)

*Notes: It will overflow very easily with integers just a heads up*

Oh and reason yours doesn't work is because you never reset your variables.


It will look like the sample below































SPOILER:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

//Example program #include <iostream> int u(int const n); int main() { int const iterations = 10; for(int n = 0; n < iterations; ++n) { std::cout << "u(" << n << ") = " << u(n) << std::endl; } return 0; } int u(int const n) { //set constant variables for u(0), u(1), and u(2) int const zero = 3; int const one = 2; int const two = 15; //return if u(0), u(1) or u(2) otherwise calculate if(n == 0) return zero; else if(n == 1) return one; else if(n == 2) return two; else { //set values for u(n-2), u(n-1), and u(n) int nMinus1 = one; int nMinus2 = zero; int nMinus0 = two; //n(2) will be first == 15 for(int i = 3; i <= n; ++i) { //set u(n-2) equal to u(n-1), set u(n-1) equal to u(n) and then calculate u(n) nMinus2 = nMinus1; nMinus1 = nMinus0; nMinus0 = i * nMinus1 + (i + 1) * nMinus2 + i; } //return u(n) return nMinus0; } }

u(0) = 3 u(1) = 2 u(2) = 15 u(3) = 56 u(4) = 303 u(5) = 1856 u(6) = 13263 u(7) = 107696 u(8) = 980943 u(9) = 9905456

[Arslan7041]

I finally figured out what I was doing wrong.

I was using the value of N to figure out the value of "second". I understand now that I needed to use a different variable to calculate N, and also iterate that value up to N while also doing the other two iterations.

Here is my final code. The outside for-loop is just so i can test 10 values of N.

#include <iostream>
#include <cmath>

using namespace std;

int main()
{

    for(int i = 1; i<10; i++)
    {
        int N, zeroth=3, first=2, second;

        cout << "Enter in an integer N: " << flush;
        cin >> N;

        if(N==0)
            cout << "u(" << N << ") = " << zeroth << endl << endl;
        else if (N==1)
            cout << "u(" << N << ") = " << first << endl << endl;
        else if (N>1)
        {
            for(int x = 2; x<=N; x++)
            {
                second = x*first + (x+1)*zeroth + x;
                zeroth = first;
                first = second;
            }

            cout << "u(" << N << ") = " << second <<  endl << endl;
        }


    }
    
    cin.get();
}

The new variable introduced is x.

This code works perfectly. It gives the correct answer regardless of whether the input is in numerical order or not.

Thank you everyone for your input.

Kerskiverto, I apologize for my rant.

Now I will try this using recursion :)

[Arslan7041]

Whats up with line 14 in the solution below?

Where did he get that expression from?

#include<iostream>
using namespace std;
      int N;
      long double ans;
      long double u (int n){
           long double rec;
           if (n==0)
              rec=3;
           if (n==1)
              rec=2;
           if (n>1)
              rec=n*u(n-1)+(n+1)*u(n-2)+n;
           if (n<0)
              rec=(u(n+2)-(n+2)-(n+2)*u(n+1))/(n+3); 
           return rec;}
      int main () {
          cout<<"Enter an integer N\t";
          cin>>N;
          ans=u(N);
          cout<<"u(N) =\t"<<ans<<endl;
          system("PAUSE");
          return 0;}