locked
finding a value is pascal\'s triangle by index in c++ RRS feed

  • Question

  • Hello, i am trying to find a recursive way to find a value in pascal's triangle by index. for example, for the index (4,3)
    i will get the value in the 4th row in the 3rd column, which is 10 (if the first row and column are 0).

    i found a few examples on how to do this, and these examples got tons of upvotes but when i tried running them on my pc they weren't even close to the right answer. any ideas? here is the code i tried btw:
    #include <iostream>
    #include <stdio.h>
    
    using namespace std;
    
    int pascal(int row, int col);
    
    int main()
    {
    	int val = pascal(4, 3);
    	cout << val << endl;    // this example prints 16
    	getchar();              // the right answer is 10
    	return 0;
    }
    
    int pascal(int row, int col) {
    	if (row == 0)
    		return 1;
    	else
    	{
    		row--;
    		return(pascal(row, col) + pascal(row, ++col));
    	}
    }



    • Edited by shongr2k1 Tuesday, February 12, 2019 10:40 AM
    Tuesday, February 12, 2019 10:39 AM

Answers

  • Off topic for this forum.

    Danny


    When you see answers and helpful posts, please click Vote As Helpful, Propose As Answer, and/or Mark As Answer MCSE:Server Infrastructure, MCSE:Desktop Infrastructure, MCSA Server 2012, Citrix CCIA & CCEE, Cisco CCNA, VMware VCP 3/4/5 Twitter: @dnyvandam http://www.dannyvandam.net

    Wednesday, February 27, 2019 7:05 PM
    Answerer

All replies

  • If you have a C or C++ question, you will get much better answers in the "C++ Standards, Extensions, and Interop" forum.

    Regarding the results your program produces, since it has undefined behavior there are no correct results.  Had it produced the results you were expecting, the behavior would still be undefined.

    Look at the last statement in function pascal.  There is no restriction on the order in which of the two recursive calls to pascal is executed.  Thus you do not know if the first call to pascal will use the original value of col or the incremented value. 

    Did you copy the code correctly?  Or did the original use col+1 and you changed it to ++col thinking it was equivalent?  Tell us where you found the code.

    Note that since the updated value of col appears to never be used in your code, storing the updated value back in the variable would have been a waste.


    Tuesday, February 12, 2019 4:42 PM
  • ok first of all, how do i move it to the other forum?
    secondly, i found the code here: https://stackoverflow.com/questions/1763954/c-pascals-triangle
    but it did not work so i tried changing some things.

    about the undefined behavior, are you sure? because it always brings up the same result (if you dont change the index).

    thanks for the help! :D

    -shon


    EDIT:

    this code for pascal works:
    int pascal(int row, int col) {
      if (col == 0 || col == row) {
        return 1;
      } else {
        return pascal(row - 1, col - 1) + pascal(row - 1, col);
      }
    }

    but in a weird way. the rows start from 1 and the columns start from 0. is there a way to fix it to start from 0 in both indexes? 


    • Edited by shongr2k1 Tuesday, February 12, 2019 4:58 PM
    Tuesday, February 12, 2019 4:52 PM
  • ok first of all, how do i move it to the other forum?

    I think only a moderator can move it from one forum to another and the ones in this forum are not very active. The easiest thing to do is to repost the question in the appropriate forum.

    secondly, i found the code here: https://stackoverflow.com/questions/1763954/c-pascals-triangle
    but it did not work so i tried changing some things.

    In what way did it not work? Given the upvotes, it seems like it worked for some people.


    about the undefined behavior, are you sure? because it always brings up the same result (if you dont change the index).

    There are no constraints on undefined behavior. The consistency you observe is an artifact that the generated code always executes the two calls in the same order and does not access any indeterminate data.  This could change if you alter any of the compiler options (such as optimization), update the compiler, compile the code on a different system, etc.

    EDIT:

    this code for pascal works:

    int pascal(int row, int col) {
      if (col == 0 || col == row) {
        return 1;
      } else {
        return pascal(row - 1, col - 1) + pascal(row - 1, col);
      }
    }

    but in a weird way. the rows start from 1 and the columns start from 0. is there a way to fix it to start from 0 in both indexes? 


    Yes there is.  You will have to rework both the if statement and the return statement.  What I suggest you do is take a four row table and number the rows and columns consistent with this code.  Then step through the code with the debugger until you thoroughly understand how it uses those indexes.  Then using a different color pen renumber the rows and columns the way you want.  Since you want the new code to perform the same using these numbers, determine the appropriate changes to the statements.
    Tuesday, February 12, 2019 9:02 PM
  • Off topic for this forum.

    Danny


    When you see answers and helpful posts, please click Vote As Helpful, Propose As Answer, and/or Mark As Answer MCSE:Server Infrastructure, MCSE:Desktop Infrastructure, MCSA Server 2012, Citrix CCIA & CCEE, Cisco CCNA, VMware VCP 3/4/5 Twitter: @dnyvandam http://www.dannyvandam.net

    Wednesday, February 27, 2019 7:05 PM
    Answerer