当前位置:网站首页>Thinking construction and skill realization of recursion

Thinking construction and skill realization of recursion

2021-02-05 18:05:36 Geometric thinking

The article begins with the official account of WeChat : Geometric thinking

Recursion is a method of solving complex problems by repeated operations .

1. One dimensional recursion

1.1 Problem description

There is one \(n\) The stairs on the first floor , You can only climb up at a time 1 Layer or 2 layer , Ask after climbing \(n\) How many different ways are there ?

1.2 analysis

set up \(f(n)\) Express \(n\) There are totally different ways of building .
Let's say it's in the second \(i\) layer , Because you can only climb every time 1 Layer or 2 layer , So by the end of \(i\) Layer only 2 Ways of planting .

  • From \(i-1\) Climb up the floor .
  • From \(i-2\) Climb up the floor .

So the recurrence formula is \(f(n)=f(n-1)+f(n-2)\). front 2 The sum of terms is equal to 3 term , It's actually the Fibonacci sequence ,
\(1, 1, 2, 3, 5, 8, 13, 21 \cdots \cdots\)

1.3 Code implementation

f[0] = 1; f[1] = 1;
for (int i = 2; i < n; i++){
    f[i] = f[i - 1] + f[i - 2]
}
cout << f[n - 1] << endl;

1.4 Space optimization

The recursion of each step is only related to the previous 2 It's about , So just before recording 2 The number of steps , Using the scrolling array , Instead of driving \(o(n)\) Space .
Manual assignment

int f[3];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < 10; ++i) {
    f[2] = f[1] + f[0];
    f[0] = f[1];
    f[1] = f[2];
    cout << f[2] << endl;
}

Take the mold and roll

int f[3];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < 10; ++i) {
    f[i % 3] = f[(i - 1) % 3] + f[(i - 2) % 3];
    cout << f[i % 3] << endl;
}

If it's only related to the previous state , such as \(f[n]=f[n-1]+1\), It can be used 0,1 rolling , This is more commonly used in dynamic programming .

int f[2], t = 0;
f[0] = 1;
for (int i = 2; i < 10; ++i) {
    t = 1 - t;
    f[t] = f[1 - t] + 1;
    cout << f[t] << endl;
}

The biggest difference between recursive and dynamic programming : Each step of recursion is the sum of all the schemes , And dynamic programming in every step of recursion , Need to use max,min To choose an optimal strategy . In fact, the essence is to deduce large-scale results through repeated small-scale model problems .

1.5 Time optimization

The recurrence formula of Fibonacci sequence is very simple , But when the data is big , It's less efficient , Because recursion is \(O(n)\) Complexity .
Through matrix formula transformation, addition can be changed into multiplication
Let's put the recurrence formula into the matrix as follows :
\( \begin {bmatrix}1&1\\1&0\end {bmatrix} \times \begin{pmatrix}f(n-1) \\ f(n-2)\end{pmatrix} =\begin{pmatrix}f(n-1)+f(n-2) \\ f(n-1)\end{pmatrix} =\begin{pmatrix}f(n) \\ f(n-1)\end{pmatrix} \)
hypothesis :
\(A=\begin {bmatrix}1&1\\1&0\end {bmatrix}\)
be :
\(A^n \times \begin{pmatrix}f(1) \\ f(0)\end{pmatrix} = \begin{pmatrix}f(n+1) \\ f(n)\end{pmatrix} \)
\(A^n\) It can be solved quickly by matrix power multiplication , The time complexity is \(log_2N\), And then we can get the sequence value by bringing in the above formula .
See another article for details Recursive optimization - Matrix power multiplication

2. Multidimensional recursion

2.1 Problem description

Starting from the origin , It's going east at a time , To the north , Go west , And you can't go where you've been , Ask to leave \(n\) How many different ways are there ?

2.2 analysis

Let's assume that we have reached the third stage \(i\) Step , Because you can't walk where you've been , The way that this step can go is only related to the previous step . Because one step at a time , Make sure you don't go back , Just make sure you don't go where you've been .
Every time 3 A choice , To the East , To the north , To the West .

  • The first \(i-1\) Step East , So the first \(i\) We can only go north 、 To the east .
  • The first \(i-1\) Step West , So the first \(i\) We can only go north 、 To the West .
  • The first \(i-1\) Step North , So the first \(i\) Step North 、 To the east , To the West .

One dimensional \(f[n]\) Only one total can be recorded , Instead of recording the State , So one more dimension is needed to record the state of the last step .
set up \(f[n][0],f[n][1],f[n][2]\) respectively : The first \(n\) Step East 、 To the West 、 There are different ways to go north .
Then there is the following recurrence relation :

  • \(f[n][0] = f[n - 1][0] + f[n - 1][2];\)
  • \(f[n][1] = f[n - 1][1] + f[n - 1][2];\)
  • \(f[n][2] = f[n - 1][0] + f[n - 1][1] + f[n - 1][2];\)

2.3 Code implementation

int f[100][3] = {0};
f[0][0] = 1;
f[0][1] = 1;
f[0][2] = 1;

for (int i = 1; i < n; ++i) {
    f[i][0] = f[i - 1][0] + f[i - 1][2];
    f[i][1] = f[i - 1][1] + f[i - 1][2];
    f[i][2] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2];
}
cout << f[n - 1][0] + f[n - 1][1] + f[n - 1][2] << endl;

2.4 Further optimization

Set the first \(n\) The total number of steps is \(s[n], s[n]=f[n][0]+f[n][1]+f[n][2]\).
\(s[n]=2\times f[n-1][0]+2\times f[n-1][1]+3\times f[n-1][2]\).
\(s[n]=2\times s[n-1]+f[n-1][2]\).
and \(f[n-1][2]=f[n-2][0]+f[n-2][1]+f[n-2][2]=s[n-2]\).
have to \(s[n]=2\times s[n-1]+s[n-2]\).
So the formula is distorted , It can also be done recursively in one dimension , But this relationship cannot be constructed directly through modeling .

3. Graph recursion

3.1 Problem description

In a \(n\times m\) In a two-dimensional map of , A person goes from the upper left corner to the lower right corner , You can only go right or down at a time , How many different ways to get to the end ?

3.2 analysis

Suppose you're already in a position , Because you can only go right or down , The last step can only come from the top or from the left .
set up \(f[i][j]\) It means to go to the coordinates \((i,j)\) The total number of programs .
be \(f[i][j]=f[i-1][j]+f[i][j-1]\).

3.3 Code implementation

int f[10][10] = {0};
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        if (i - 1 >= 0) {
            f[i][j] += f[i - 1][j];
        }
        if (j - 1 >= 0) {
            f[i][j] += f[i][j - 1];
        }
    }
}

3.4 Further reflection

To get to the end , Be sure to go down \(n-1\) Step , turn right \(m-1\) Step .
Put each step together to see , In fact, the problem is equivalent to \(n+m-2\) Choose in the step \(n-1\) Step down , Or choose \(m-1\) Step right , Through permutation and combination formula \(C_{n+m-2}^{n-1}\) You can get the results directly .

4. State compression recursion

4.1 Problem description

In a \(n\times n\) Put pieces on your chessboard , There are some places that can't be placed . It is required to place the pieces at will 2 A piece can't be in the same 1 Line or same as 1 Column , Question placement \(k\) How many different ways are there for a chess piece ?

4.2 analysis

For each 1 A place , There will only be 2 In this case , Is to put or not to put . In the case of small data scale, you can use DFS( Depth-first search ) Just enumerate all the cases .

Is there a better way ?
This is ultimately the total number of required solutions , It's not necessary to consider whether you need to choose the best in each step , So it's consistent with the recursive model , The next step is to find out the recurrence relationship .

Let's first analyze some implied laws , Make things clearer :

  • Every time 1 OK or every 1 Columns can only be placed 1 A chess piece , So enumerate the placement methods on each line .
  • In trying the second \(i\) Line time , Every position \((i,j)\) Can you place it , It's not just about keeping up with the industry , It's about all the previous lines . This means that you need to record the method you placed before , That is the state .

How to record the status of the scheme placed before , This requires state compression .
State compression : The essence is to record the corresponding position in binary system 2 States ,0 I won't let go ,1 It means to put .

about \(n\) A place , You can use it \(2^n\) A decimal number to represent all the placement schemes .

Go back to the question above , In trying the second \(i\) Line time , Can you place it with the previous \(i-1\) It's all about business , It means that you need to record the status of all previous rows placed .
But look below 2 In this case , chart 1 Sum graph 2 For trying to place 3 Line time , It's actually equivalent , front 2 Columns cannot be placed . That is to say 2 The number of schemes can be combined directly , Because each 1 There can only be one column , So the placed scheme states can also be directly merged into one line .

use \(f[i][j]\) Before presentation \(i\) That's ok , The placement scheme is \(j\) The total number of programs .
The first 0 The process is as follows :

The first 1 The process is as follows :

So we can deduce \(n\) That's ok ,\(2^n\) The total number of placement schemes ,\(f[n][2^n]\). Because it can only be placed \(k\) A chess piece , So in \(2^n\) It's just that \(k\) A chess plan , That is, the corresponding state \(j\) When converted to binary , Yes \(k\) individual 1.

4.3 Tips : How to find the corresponding binary inclusion of decimal number quickly 1 How many are there ?

Target number \(n\), adopt \(n \& (n-1)\) operation , How many are included 1 Just how many times the operation is performed , You can quickly find out 1 The number of .

4.4 Code implementation

Calculation \(n\) Contained in the 1 The number of

int countOne(int n) {
    int total = 0;
    while (n > 0) {
        total++;
        n &= n - 1;
    }
    return total;
}

Variable definition and initialization

int i, n, k, line[8], f[2][256], num[256];

for (i = 0; i < 256; ++i) num[i] = countOne(i);

memset(f, 0, 2 * 256 * 4);
f[0][0] = 1;
int j, c, now = 0;

//  The chessboard reads 
for (i = 0; i < n; ++i) {
    int t = 0;
    for (int j = 0; j < n; ++j) {
        t <<= 1;
        cin >> ch;
        if (ch == '.') t += 1;
    }
    line[i] = t;
}

Core recursion

for (i = 0; i < n; ++i) {
    now = 1 - now;
    for (j = 0; j < 256; ++j)
        if (num[j] <= k) {
            // The first i You can't let go of the pieces 
            f[now][j] += f[1 - now][j];
            // The first i All right, put the pieces 
            for (c = 0; c < n; ++c) {
                if ((j & 1 << c) == 0 && (line[i] & 1 << c) == 0) {
                    f[now][j | 1 << c] += f[1 - now][j];
                }
            }
        }
}

//  Enumerate all the objects that contain k The number of chess pieces 
int ans = 0;
for (i = 0; i < 256; ++i) {
    if (num[i] == k) {
        ans += f[now][i];
    }
}
cout << ans << endl;

5. summary

The most important idea of recursion , It's through every little step , Find out the relationship with the next step . The key is to think about the nature of the problem , Model the problem . Commonly used \(f[i][j][k]\) And so on , One more dimension can record one-dimensional state information , Think about how many factors in the previous step will affect the current step , Generally, these are the information that must be recorded .


Scan the bottom two dimensional code to pay attention to the official account , Get updated information at the first time !

版权声明
本文为[Geometric thinking]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/02/20210205160813540O.html

随机推荐