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

Add Tag

Discuss