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

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?

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.

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.