C++ Recurssive solution

Hi
Was working on a problem:

Quote:

---

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

err we dont really need the prototype for the factorial function... it is never used for this code!

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.

Fix your indentation. I cant even bear to look at that as-is. Did the cat throw it up?

@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.

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.

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 :)

@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.

@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.

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.

Quote:

---

Originally Posted by VC15

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 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.

OK, I understand you and will take into account your notifications in my future posts.