C++ Recurssive solution

This is a discussion on C++ Recurssive solution within the C++ Programming forums, part of the General Programming Boards category; Hi Was working on a problem: Write a program (GUI or command line) that accepts input, performs calculations and returns ...

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    35

    C++ Recurssive solution

    Hi
    Was working on a problem:
    Write a program (GUI or command line) that accepts input, performs calculations and returns output to the user. Provide source code (with project files if applicable) and if we are unable to compile the code for some reason we will request binaries (please put these in a RAR file or a password protected ZIP or our email system will bounce the email).

    Please provide basic error checking on input and adequate comments. Correctness is very important, efficiency is a bonus. Source code clarity is highly valued. Fancy formatting or a GUI is not required. This is a chance to showcase your skills, so write the program in a way that will best display your talent.

    Input: K, N (where 0 < N < ∞, 0 < K < ∞, and K <= N)
    Output: Number of possible equations of K numbers whose sum is N

    Example Input:
    N=10

    K=3

    Example Output:

    1 + 1 + 8 = 10

    1 + 2 + 7 = 10

    1 + 3 + 6 = 10

    1 + 4 + 5 = 10

    2 + 2 + 6 = 10

    2 + 3 + 5 = 10

    2 + 4 + 4 = 10

    3 + 3 + 4 = 10
    Total unique equations = 8


    For reference, N=100, K=3 should have a result of 833 unique sets and print out 833 equations.
    I got the partial solution:
    Code:
    #include <io.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    /* main takes 2 arguments K,N such that where 0 < N < inf, 0 < K < inf, and K <= N.*/
    /*K and N are integers.*/
    
    
    
    int main(int argc, char** argv)
    {       
           char number1[20], number2[20];//size check
    	int numk,n;
            int total=0;
            printf("usage: Input k:<number1>\n\t Input n:<number2>\n");
            printf("Input k:");
            scanf("%s",number1);
            
            numk= (int)strtol (number1, NULL, 10 );
         
            printf("\nInput n: ");
            scanf("%s",number2);
            n = (int)strtol ( number2, NULL, 10 );
       if(n>0 )
      {
       if(numk>0 && numk<=n)
        {
          for(int i=1;i<=(n-2);i++)
          {
            for (int j=i; j<=(n-1-i);j++)
             {
               int k= n-i-j;
                      if(k>=j){
                                 total++;
                 printf("%d + %d+ %d= %d\n",i,j,k,n);
    
                                }
                  }
               }
            
    	    printf("Number of equations are:%d\n",total);
    	}
    	else
     	 printf("Error: n>0,k>0 and k<= n.\n");//try agin loop
    
        }
    
      /*
      ** Ensure that argv[argc] is indeed NULL by printing
      ** a message if (argv[argc] == NULL) evaluates to true.
      */
    
          if ( argv[argc] == NULL )
            puts ( "This is the end" );
    
       return EXIT_SUCCESS;
    
    }
    This is for one k value only and want to generalise it.how do we get a recussive solution so the k is auto mated.Also the code I wrote is in c style but compiles with g++.I wanted it to be more c++ style.I am not used/experienced with c++ much.

    Any help is appreciated.
    Thanks
    shweta
    Last edited by svaidya; 09-25-2009 at 09:28 PM.

  2. #2
    Registered User
    Join Date
    May 2007
    Posts
    35
    err we dont really need the prototype for the factorial function... it is never used for this code!

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,021
    First of all never use scanf with "%s", without a size specifier. It can lead to buffer overflow.

    In C++, prefer "std::cin >> var" to scanf, prefer std::string objects to character array, and prefer "std::cout << var" to printf.

    In both C and C++, there is no need to read into a string, before converting to integer. You can read in an integer directly.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Fix your indentation. I cant even bear to look at that as-is. Did the cat throw it up?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    May 2007
    Posts
    35
    @iMalc: mind your manners and stop being abusive. this is a help site used for learning.If you cant bear to look at it dont look at it.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    It's called a short sharp shock! There was no personal attack there, I was simply expressing exaggerated disgust at the code itself. Some people need a wake-up call every now and then.

    That looks much better!
    Okay, you want to make a recursive solution. The first thing you need to do is make another function. Can you do that?
    You also want "C++ style" code. Well given it's so small that wont mean using classes, you just need to use things like cin and cout. Look up some examples of those.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User VC15's Avatar
    Join Date
    Sep 2009
    Location
    Russia, Orel
    Posts
    2
    To my mind the statement of the problem is incorrect. N is supposed to be infinte. So if N = 10^200 that's OK. And in this case there is an enormous amount of possible equations.
    Let's consider that N <= 100. Now we can write a beautiful C++ solution of the problem.
    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int n, k, total;
    
    void rec(int cur, int k, int last, vector < int >& items)
    {
    	if (k == 1)
    	{
    		++total;
    		items.push_back(cur);
    		for (size_t i = 0; i < items.size(); ++i)
    		{
    			cout << items[i] << " " << (i < items.size() - 1 ? "+ " : "= ");
    		}
    		cout << n << endl << endl;
    		items.pop_back();
    	}
    	else
    	{
    		for (int i = last; i <= cur / k; ++i)
    		{
    			items.push_back(i);
    			rec(cur - i, k - 1, i, items);
    			items.pop_back();
    		}
    	}
    }
    
    int main()
    {
    	cin >> k >> n;
    	total = 0;
    	vector < int > items;
    	items.reserve(k);
    
    	rec(n, k, 1, items);
    	cout << "Total unique equations = " << total << endl;
    
    	return 0;
    }
    Excuse me, but I haven't implemented input checking.
    Some tips about code posted:
    1. cin is used for input and cout for output. These classes are not as fast as scanf and printf. So we use them because we know that the input and output are not very large.
    2. We use vector<int> to keep numbers used in the current equation. vector is a standard C++ template, it is an array with variable length.
    3. The major idea of the recursive solution is as follows. We need to generate K numbers sum of which equals to N. Let's take a number 1 <= X <= N and generate (K - 1) numbers sum of which is (N - X).
    4. To make our program generate only unique euqations we use numbers not less than one used on the previous step.

    I hope that you will understand my explanation because I'm not sure in quality of my English

  8. #8
    Registered User
    Join Date
    May 2007
    Posts
    35
    @iMalc: You can use that language who has a lot of experience programming and not with someone who is just starting.If you want to comment on the way the code is written say nicely without offending /demotivating others.

    @VC15: Thanks a lot buddy that is useful.I will look more into the vector class and reserve function .Had never heard of it before

    Thanks guys I learnt a lot here...
    I really appreciate.

  9. #9
    Registered User
    Join Date
    May 2007
    Posts
    35
    @iMalc:
    I didnt read your post carefully.So I do know how to write function and the idea behind recurssions.I have written a few of them.Also I am familiar with cin and cout.But the company insisted on more c++ usage which was what made me wonder.Even I thought with the given problem only cin and cout was the c++ part.

    For my recurssive solution I ended up in seg faults.

  10. #10
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Your recursion solution is what? You mean the one posted by VC15?

    Input checking is not hard. You just want K, N to be greater than zero and K <= N. So read numbers and check for those. Of course, tell the user that he made an error and what is the error and ask to input again. You know, make it nice since clarity is an issue

    Not, that recursion can cause stack overflow. Since you want any K, N, which might be big, this is not recommended. Are you required to do so?

    Correctness: very important
    Clarity: high value

    Recursion has clarity, but it can overflow the stack, which might not be consider very correct. So I would go without recursion.

    As to make it more C++, well the big difference is the class in C++. You can make one, just to show your skills. Not really necessary, but just for show-off.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by VC15 View Post
    To my mind the statement of the problem is incorrect. N is supposed to be infinte. So if N = 10^200 that's OK. And in this case there is an enormous amount of possible equations.
    Let's consider that N <= 100. Now we can write a beautiful C++ solution of the problem.
    Code:
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int n, k, total;
    
    void rec(int cur, int k, int last, vector < int >& items)
    {
    	if (k == 1)
    	{
    		++total;
    		items.push_back(cur);
    		for (size_t i = 0; i < items.size(); ++i)
    		{
    			cout << items[i] << " " << (i < items.size() - 1 ? "+ " : "= ");
    		}
    		cout << n << endl << endl;
    		items.pop_back();
    	}
    	else
    	{
    		for (int i = last; i <= cur / k; ++i)
    		{
    			items.push_back(i);
    			rec(cur - i, k - 1, i, items);
    			items.pop_back();
    		}
    	}
    }
    
    int main()
    {
    	cin >> k >> n;
    	total = 0;
    	vector < int > items;
    	items.reserve(k);
    
    	rec(n, k, 1, items);
    	cout << "Total unique equations = " << total << endl;
    
    	return 0;
    }
    Excuse me, but I haven't implemented input checking.
    Some tips about code posted:
    1. cin is used for input and cout for output. These classes are not as fast as scanf and printf. So we use them because we know that the input and output are not very large.
    2. We use vector<int> to keep numbers used in the current equation. vector is a standard C++ template, it is an array with variable length.
    3. The major idea of the recursive solution is as follows. We need to generate K numbers sum of which equals to N. Let's take a number 1 <= X <= N and generate (K - 1) numbers sum of which is (N - X).
    4. To make our program generate only unique euqations we use numbers not less than one used on the previous step.

    I hope that you will understand my explanation because I'm not sure in quality of my English
    Your English is fine, and that's a pretty impressive piece of code. I would make n and k locals to main rather than global though. I'm just not sure svaidya would be up to understanding it all. I'd have to run it myself to get a clear picture of how it works.
    Anyway, you're not supposed to hand over your own solutions for others to copy. The goal is to help the poster to produce something on their own, not allow them to cheat. Kinda makes it hard to help now that the whole answer is just sitting right there. Make sure you've read the rules of the site.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    May 2007
    Posts
    35
    My recurssive solution was different and dint use c++.I had same math concept.I was trying the follow:
    1.Allocate a 2 dim array with columns k(which user gives) by some Y (which is randomly very large).
    2.fill in the columns with each set of k values.For ex: if trying x1+x2+x3=N where k=3
    then first column of 2dim array are the possible x1 values and so on,by recursing and computing x2 and x3 .
    3.then print he array row by row.

    @imalc: Just to clarify... This is not a homework problem just something I picked up randomly to practice as its been a while.
    Last edited by svaidya; 09-26-2009 at 03:25 PM.

  13. #13
    Registered User VC15's Avatar
    Join Date
    Sep 2009
    Location
    Russia, Orel
    Posts
    2
    OK, I understand you and will take into account your notifications in my future posts.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 'Solution' and 'Project' usage in VC++
    By C+/- in forum C++ Programming
    Replies: 2
    Last Post: 01-13-2007, 08:50 AM
  2. anyone know the solution?
    By heeroyung in forum C Programming
    Replies: 15
    Last Post: 09-30-2005, 06:46 AM
  3. RFC: C++ "Hit any key to continue..." solution
    By flakier in forum C++ Programming
    Replies: 11
    Last Post: 09-02-2004, 10:56 AM
  4. My Unix/Linux SECURITY SOLUTION - pls read
    By bjdea1 in forum Linux Programming
    Replies: 3
    Last Post: 04-11-2004, 09:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21