Blue Bridge Cup zero Foundation National Championship - day 20

Experience recursion

Title Description

When n by 1 when , The figure is as follows ：

X

When n by 2 when , The figure is as follows ：

X X
 X 
X X

When n≥2 when , The pattern is as follows ：

 graphics n-1     graphics n-1
     graphics n-1
 graphics n-1     graphics n-1

Given n Group data , Output the graph corresponding to each group of data .

Input

Input common n+1 That's ok , front n One number per line , Represents the size of the graph to be output , On the last line, enter −1 Represents the end of the program .（1≤n≤7）

Output

Input a number and output a group of graphics , And output a −−.

Be careful , The blank space should be filled after the figure .

Thinking process ： Requirement No n Group graphics , Then you can ask the number n - 1 Group graphics , seek n - 2 Group graphics , And so on , Until the first set of figures , There is only one graph in the first group ‘X’. So you can start with n The group begins to recurse to 1 Group get the position of the first group of each position , Then recurse from the first group of positions to the n Group , In the recursive process, save the first set of ‘X’. And it can be found that n The side length of the group graph shape is n - 1 Group graphic 3 times . That is to say Len[7] = {1, 3, 9,27,81,243,729}, And confirm the position ** The upper left corner of the figure in the upper left corner is (x,y), The upper left corner of the figure in the upper right corner is (x+Len[n]/3*2, y), The upper left corner of the middle figure is (x+Len[n]/3,y+Len[n]/3), The upper left corner of the figure in the lower left corner is (x,y+Len[n]/3 *2), The lower right corner is (x+Len[n]/3 2, y+Len[n]/3 2)

Give me an example n=3 Of , The upper left corner of the figure in the upper left corner is (1, 1), The upper left corner of the figure in the upper right corner is (1+9/3*2, 1), The upper left corner of the middle figure is (1+9/3,1+9/3), The upper left corner of the figure in the lower left corner is (1,1+9/3 *2), The lower right corner is (1+9/3 *2,1+9/3 *2)

(1,1)
X X   X X          
 X     X 
X X   X X     (1, 1)   (1+9/3*2, 1)  (1+9/3,1+9/3)  (1,1+9/3*2)  (1+9/3*2,1+9/3*2)
   X X           x x       x x            x x             x x        x x
    X      =>     x         x              x               x          x        
   X X           x x       x x            x x             x x        x x
X X   X X        top left corner       Upper right corner            middle             The lower left corner        The lower right corner 
 X     X 
X X   X X

The problem solving process ：

The data range given by the title is 7, Then put the first 7 Draw a group of pictures （ That is, save to the array ） Then output according to the input group . The recursive function is confirmed to recurse the position of the upper left corner of each group of graphs and the Group func(x, y, n).

Code demonstration ：

#include<iostream>
using namespace std;

char ans[1005][1005];
int nums[8] = {
    0, 1, 3, 9, 27, 81, 243, 729};

void func(int x, int y, int n) {
    
    if (n == 1) {
    
        ans[x][y] = 'X';
        return ;
    }
    func(x, y, n - 1);
    func(x, y + nums[n] * 2 / 3, n - 1);
    func(x + nums[n] / 3, y + nums[n] / 3, n - 1);
    func(x + nums[n] * 2 / 3, y, n - 1);
    func(x + nums[n] * 2 / 3, y + nums[n] * 2 / 3, n - 1);
}

int main() {
    
    func(1, 1, 7);
    int n;
    while (1) {
    
        cin >> n;
        if (n == -1) break;
        for (int i = 1; i <= nums[n]; i++) {
    
            for (int  j = 1; j <= nums[n]; j++) {
    
                if (ans[i][j] == 'X') {
    
                    cout << 'X';
                } else {
    
                    cout << ' ';
                }
                
            }
            cout << endl;
        }
        cout << '_' << endl;
        cout << endl;
    }
    return 0;
}

Recursive implementation of exponential enumeration

Title Description

from 1−n this n Randomly select any number of integers , The numbers in each scheme are arranged from small to large , Output all possible options in dictionary order .

---

Input

Enter an integer n.（1≤n≤10）

Output

Each line has a set of schemes , The two numbers in each group are separated by spaces .

Note that there is no space after the last number in each line .

The sample input

4

Sample output

1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

Thinking process ： You can find four columns of answers , The first column will appear 1 To 4 Number of numbers , The second column will appear 2 To 4 Number of numbers , The third column will appear 3 To 4 Number of numbers , The fourth column will appear 4 To 4 Number of numbers , That is to say, traversing each column can get the column order number of this column to n Number of numbers , Then traverse to change the number of the first column . Because the number of columns traverses to n Go back to traversal n - 1 Column , therefore Use recursion and recursion , Recursion to n Column , Recursion back to the first line .

such as

// Recursion to n Column 
1
1 2
1 2 3
1 2 3 4
// Recursion goes back to the n - 1 Column and change to No n - 1 The next value of the column , For example, the previous one is 3, Now is 4. because 4 That is n, So the cycle ends 
1 2 4
// Recursion goes back to the n - 2 Column and change to No n - 2 The next value of the column , For example, the previous one is 2, Now is 3, because 3<n, So we have to traverse to 4
1 3
1 3 4
// Recursion goes back to the n - 3 Column and change to No n - 3 The next value of the column , For example, the previous one is 1, Now is 2, because n<2, So we have to traverse to 4, The process of traversal is recursive 
2    
2
2 3
2 3 4
2 4
3
3 4
4

The problem solving process ： Set an array , Record the column position traversed each time and output the entire array . Recursive function func(strat, idx), among strat Is the value of the first column ,idx Is the subscript of the array ,idx That is, the number of columns traversed

#include<iostream>
using namespace std;

int ans[15];
int n;

void print(int idx) {
    
    for(int i = 0; i <= idx; i++) {
    
        i && cout << ' ';
        cout << ans[i];
    }
    cout << endl;
}
void func(int strat, int idx) {
    
    for (int i = strat; i <= n; i++) {
    
        ans[idx] = i;
        print(idx);
        func(i + 1, idx + 1);
    }
}
int main() {
    
    cin >> n;
    func(1, 0);
    return 0;
}

Increase recursive backtracking ：

#include<iostream>
using namespace std;
int n, ans[15], cnt;
void print() {
    
    for (int i = 0; i <= cnt; i++) {
    
        i && cout << ' ';
        cout << ans[i];
    }
    cout << endl;
}
void func(int strat) {
    
    for (int i = strat; i <= n; i++) {
    
        ans[cnt] = i;
        print();
        // The recursive process adds array subscripts , Form a push down feeling 
        cnt++;
        func(i + 1);
        cnt--;// Retrospective feeling , Backtracking array subscripts during recursion 
    }
}
int main() {
    
    cin >> n;
    func(1);
    return 0;
}

Recursive implementation of combinatorial enumeration

$$C_n^m$$

** Title Description **

from 1−n this n Random selection of integers m individual , The numbers in each scheme are arranged from small to large , Output all possible options in dictionary order .

---

Input

Enter two integers n,m.（1≤m≤n≤10）

Output

Each line has a set of schemes , The two numbers in each group are separated by spaces .

Note that there is no space after the last number in each line .

---

The sample input

5 3

Sample output

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Thinking process ： This question is in n Pick any number m Count them out . Observe the example above , You will find a periodic phenomenon ： Now put these numbers down

[1 1 1 1 1 1]     [2 2 2][3]
[[2 2 2][3 3][4]] [[3 3 4][4]]
[[3 4 5][4 5][5]] [[4 5 5][5]]

You will find in the first column 1 In an array of , The second column appears from 1+1 To 1+m Number of numbers , That is to say 2、3、4, In the second is 2 In an array of , The third column appears 2+1 To 2+m Number of numbers . And the first column appears from 1 To n - m + 1 Number of numbers . It shows that now I only need to control the number of the first column and the number of columns that will appear later , Because the second column to the second m Each column in the column will be controlled by the previous column , For example, the second column will be controlled by the first column （ The first column appears 1, Then the second column can only be 1+1 To 1+m）.

The problem solving process ：

Because the number of the first column is an inner loop using recursion . First define a recursive function func(start, left),start Is the value of the number in the first column , According to the above analysis , The first column will appear 1 To n-m+1 Number of numbers , So loop recursion .left For it has arrived m - left Column , as long as left by 0 Just cut off the number of columns .

Code demonstration ：

int n, m, cnt;
int nums[15];

void print() {
    
    for (int i = 0; i < m; i++) {
    
        i && cout << " ";
        cout << nums[i];
    }
    cout << endl;
}

void func(int start, int left) {
    
    if (left == 0) {
    
        print();
        return 0;
    }
    for (int i = start; i <= n; i++) {
    
        nums[cnt] = i;
        cnt++;
        func(i+1, left-1);// Replace the value appearing in the first column and check the row , When it comes to m The number of rows is up to the number of columns , When the number of columns is cut off, this m All values for column 
        cnt--;
    }
}

int main() {
    
    cin >> n >> m;
    func(1, m);
    return 0;
}

Recursively implement permutation enumeration

$$A_n^n$$

Title Description

from 1−n this n Arrange integers in a row and disorder the order , Output all possible options in dictionary order .

---

Input

Enter an integer n.（1≤n≤8）

Output

Each line has a set of schemes , The two numbers in each group are separated by spaces .

Note that there is no space after the last number in each line .

---

The sample input

3

Sample output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Thinking process ： The difference between combinatorial problem and permutation problem is , Every column of the full permutation problem will appear 1 To n Number of numbers , So as long as each column is traversed 1-n Can , Because each column is an inner loop , So recursion is used .

The problem solving process ：

Define a recursive function func(), The meaning of recursion is to increase the number of columns during recursion , Recursion changes the value of the number of columns , because n The value of each column in the column is different , So use an array of tags mark To record n The number that has appeared in the column

Code demonstration ：

int n, cnt;
int nums[15], mark[15];

void print() {
    
    for (int i = 0; i < n; i++) {
    
        i && cout << " ";
        cout << nums[i];
    }
    cout << endl;
}

void func() {
    
    if (cnt == n) {
    
        print();
        return ;
    }
    for (int i = 1; i <= n; i++) {
    
        if (mark[i] == 0) {
    
            nums[i] = i;
            mark[i] = 1;
            cnt++;
            func();
            cnt--;
            mark[i] = 0;
        }
    }
}

int main() {
    
    cin >> n;
    fun();
    return 0;
}

Permutation and combination application

The output of the above three permutation and combination problems is a pile of numbers , What is the use of these figures ？ In fact, these numbers are subscripts , As long as you put these numbers into each array that is not a number, you can get other permutations .

For example, combination problem ： In five people A、B、C、D、E Choose three people

int cnt;
string people[5] = {
    'A','B','C','D','E'};
int nums[5];

void func(int start, int left) {
    
    if (left == 0) {
    
        for (int i = 0; i < n; i++) {
    
            i && cout << " ";
            cout << people[nums[i]];
        }
        cout << endl;
        return 0;
    }
    for (int i = start; i < n; i++) {
    
        nums[cnt] = i;
        cnt++;
        func(i + 1, left - 1);
        cnt--;
    } 
}

int main() {
    
    func(0, 3);
}

summary ： Circular recursion will be used in combination and arrangement problems （ Recursively nested a loop ）, The difference between the three enumerations is ： Exponential type is output in the enumeration process , Combination is to limit the number of output columns and output , Full Permutation means that every value may appear in every column and there is no limit to the number of columns until all numbers appear .