Description

There are some binary sequences of length 2N, consisting of N zeroes and N ones. Your task is to write a program to list all the possible binary sequences in lexicographical order. For example, if N is 2, your program will print all the possible binary sequences as follows:

0011

0101

0110

1001

1010

1100

Note that

1.      This problem involves three files.

• function.h: Function declaration of list and show
• function.c: Function implementation of list and show.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.c.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose C compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

#ifndef FUNCTION_H_INCLUDED #define FUNCTION_H_INCLUDED int sequence[200]; void show(int len); void list(int numZero, int numOne, int cur, int len); #endif // FUNCTION_H_INCLUDED

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" int main() { int n; scanf("%d", &n); list(n, n, 0, 2*n); return 0; }

Hint:

The problem of listing the binary sequences of length 2N can be divided into the following two sub-problems:

   A. 1 zero followed by each binary sequence consisting of N-1 zeros and N ones.

   B. 1 one followed by each binary sequences consisting of N zeros and N-1 ones.

For example, if N is 2, we can derive the binary sequences as follows:

   A. 1 zero followed by each binary sequence consisting of 1 zero and 2 ones.

        0011

        0101

        0110

   B. 1 one followed by each binary sequence consisting of 2 zeros and 1 one.

        1001

        1010

        1100

You can use the following incomplete code to solve this problem.

#include <stdio.h> #include "function.h" void show(int len) { int i; for(i = 0 ; i < len ; i++) { printf("%d", sequence[i]); } printf("\n"); return; } void list(int numZero, int numOne, int cur, int len) { if((numZero+numOne) == 0) { /*Your code*/ } else { if(numZero != 0) { /*Your code*/ } if(numOne != 0) { /*Your code*/ } } }

Input

The input contains an integer N (0<N<=6) which represents the number of zeros and ones in a sequence.

Output

Display all the possible binary sequences in lexicographical order. Each line represents a sequence. Note that you need to print ‘\n’ at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10841.c

Partial Judge Header

10841.h

Tags

Discuss