Some help with recursion plz....

[Archimag]

Hello people......just wondering if i can get some help....
I need to solve the next problem: We insert a number of students "k" and a number of chairs "n".....we need to print on the screen all the possible seating arrengments.....as one space always got to exist between two students.......the formula for such arangment beeing true at least once is 'n>=2*k-1'.....Here is the catch.....NO LOOPS! NO FOR NO WHILE ANYWHERE....only RECURSION may be used....no need for malloc either....
example for n=5, k=2 (NOTE: the printing GOT to be in an increasing order):
00101
01001
01010
10001
10010
10100
example for n=6, k=3:
010101
100101
101001
101010

And another thing: A simple MergeSort, AGAIN with NO LOOPS!!!!!!!! RECURSION ONLY! no FOR no WHILE....FORBIDDEN or the grade will be 0! MERGESORT using only recursion is not so simple, having some trouble with it.....
Thanx a lot.........
Cheers

[Narue]

>NO LOOPS!!!!!!!! RECURSION ONLY! no FOR no WHILE....FORBIDDEN or the grade will be 0!
Uh, I think we get it. You can't use loops. There's no need to go overboard.

>Thanx a lot.........
Well, you're not going to get any help unless you show some proof of effort. Post your code that attempts to solve the problems and describe how it doesn't work. Then we'll help you get it working.

[Archimag]

#include <stdio.h>
#include <string.h>
 
void func(char arr[],int E,int L,int C,int k, int n,int N);


void main(){
	int k,n;	
	char arr[]={'0','0','0','0','0','0'};
	printf("k:");
	scanf("%d",&k);
	printf("n:");
	scanf("%d",&n);	
	func(arr,0,n-(k*2-1),n-1,k,n-1,n);


}
void func(char arr[],int E,int L,int C,int k, int n,int N){
	if (n>=2*k-1){
	if (!k)
	{
		arr[N]='\0';
		printf("%s\n",arr);
		return;
	}
	if (!E){ 
		arr[C]='1';
		func(arr,1,L,C-1,k-1,n,N);}

	arr[C]='0';
	func(arr,0,L,C-1,k,n-1,N);		
	}
	
}

This is the closest i got....it's a nightmare following recursion...
I need it by tomorrow...benn trying non-stop for 3 days......been following the wrong ideas for 2 out of the 3.....finally got something right but can't finish it of....dont mind the "L" parametr, it's left-over from previous attempts....it's useless here.

[sarehu]

One way to write this cleanly is to write a procedure that, given values for n and k, returns all the proper seating arrangements for these values. I would personally make a function with the declaration vector<vector<int> > arrangements(int n, int k) . Your algorithm would then be to find all the sub-arrangements (arrangements with n-1 seats) given your first value being 0, and append 0 to them -- then find all the sub-arrangements given your first value being 1 (the n-1, k-1 case), and appending 1 to them, returning the vectors. The arrangements are represented by vector<int>, a set of them represented by vector<vector<int> >.

It seems that you're not using these. Maybe you were never taught how to use vectors. That is a shame. In that case, instead of having a pure function that generates the values, the simplest way is to make a function that will fill a character array and print out all the combinations, reusing the same array. That seems to be the strategy you're following. The main difficulty is in specifying the function's behavior in a clean way, one that you can hold in your head and implement.

I recommend the following: Make a function with the following declaration: void func(char[] arr, int n, int k); . Its behavior will be to set the values in the range arr[0]..arr[n-1] to each combination of 0's and 1's with no adjacent 1's, and print these combinations out. Recursively, it will do this by setting arr[n-1] = '0' and calling func(arr,n-1,k) , and then by setting arr[n-1] = '1' , arr[n-2] = '0' , and calling func(arr,n-2,k-1) . The special cases would be n=1, k=1 (where you can't set arr[n-2] = 0 and don't need to) and n=0, k=0 (and also, any case where n < 2k-1).

So, I would pre-initialize arr[n] = '\0' and call the function, which fills the array recursively from right to left. You could also fill the array from left to right, if you added an extra parameter which told your index. The scheme I described above uses n both to mark our progress through the array and to see how many seats we had left.

The case of mergesort is similar, in that again, you must define your algorithm in terms of its own behavior. You'll need to think about what your algorithm is supposed to do, give your function the particular arguments it needs to do the things it must do, and then call it. You'll have two recursive functions in mergesort -- one for merging and the other for dividing the array you need to sort. Treat these tasks separately and independently. Write a merging algorithm first, since you'll need it for the mergesort algorithm.

[Archimag]

Thanx..
You are right....i haven't been taught vectors yet and don't think we will.....
It's a basic programming course for Ingeenering (don't mind the speeling...not my native language) departments....Right now i follow another lead!
It's basicly check every option availeble with '1' and '0' in an array of [n]!!!!
I know how to get all these options and it's very simple:

void func(char arr[],int last, int cur, int k, int n)
{
	if (cur==last)
	{
		
		arr[cur]='\0';
		printf("%s\n",arr);
		return;
	}

	arr[cur]='1';
	func(arr,last,cur+1,k,n);

	arr[cur]='0';
	func(arr,last,cur+1,k,n);
}

I need now a second function in side the if(cur==last) condition that will check for a VALID option, meaning keeps the rules, and prints it....if not...move on!!!!! I just can't find the stoping conditions for that second recursive func....

[Archimag]

Got it...finnished the students-seats problem......
NOW......a recursive "MERGE" func using NO loops......any ideas? The MergeSort....the dividing part is clear....

[sarehu]

The merge operation will take two arrays and your positions within the arrays and their length, right?

[Archimag]

Thanx....it's past sumbmission date....
i submitted it without the merge sort....did 6 out of 7 questions...
appriciate the help..
Forza