introduce
Suppose we want to calculate \(f(x) = x!\). Except for the simple for loop , We can also use recursive .
What does recursion mean ？ We can \(f(x)\) use \(f(x - 1)\) Express , namely \(f(x) = x \times f(x - 1)\). such , We can recurse continuously .
however , This will never stop . We need to set up a boundary condition ,\(f(0) = 1\). such , We can write the code .
int f(int x) {return x ? x * f(x - 1) : 1;}
actually , Recursion has two main points ：
- Call yourself ;
- Restore the scene in backtracking .
If you see here , You may already know recursion . that , What is recursion ？ Changing the recursion of factorial calculation above into recursion is like this ：
f[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = f[i - 1] * i;
An interesting example ： What is recursion ？
「 Example 」 Count the stairs
Link to the original title ：Link.
Let's think about it from the perspective of recursion . Suppose we go to the \(i\) Steps , How should we go ？
Remember to go No \(i\) The walking method of steps is \(f_i\), Obviously , We can start from \(i - 1\) Step up one step to step \(i\) Steps , You can also start with \(i - 2\) Step up the second step to step \(i\) Steps . According to the principle of addition , Yes \(f_i = f_{i - 1} + f_{i - 2}\).
The recurrence boundary can be obtained according to the meaning of the question . One step has \(1\) Seed walking method , The second step has \(2\) Seed walking method , namely \(f_1 = 1, f_2 = 2\).
// Python Version
n = int(input())
a, b = 1, 2
if n < 3:
print(n)
for i in range(n - 2):
c = a + b
a, b = b, c
if n >= 3:
print(c)
# You can use scrolling arrays to optimize , here a amount to f[i - 2],b amount to f[i - 1],c amount to f[i]
# Pay attention to special judgment
// C++ Version
#include <bits/stdc++.h>
using namespace std;
int n;
long long f[5005] = {0, 1, 2};
int main() {
cin >> n;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
cout << f[n] << endl;
return 0;
}
here C++ Can only get \(60\) branch . This is because our results exceed long long Representation range of , Need to use high precision .
Five recursive models
Fibonacci The sequence
Fibonacci The sequence , Generally translated as Fibonacci sequence .Fibonacci The boundary of the sequence is \(f_1 = f_2 = 1\), Recursive persimmon is \(f_i = f_{i - 1} + f_{i - 2}\). The stairs above are Fibonacci The sequence starts from \(2\) The sequence of items starting .
Fibonacci There is another form of expression of the sequence , It's a cute little rabbit .
「 Example 」 The number of Rabbits
Link to the original title ：Link.
It's easy to write code .
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int a[MAXN] = {0, 1, 1}, n;
int main() {
cin >> n;
for (int i = 3; i <= n; i++)
a[i] = a[i - 1] + a[i - 2];
cout << a[n] << endl;
return 0;
}
Fibonacci There is also a general term formula in the sequence ：\(f_n = \frac1{\sqrt5}[(\frac{1 + \sqrt5}{2}) ^ n - (\frac{1 - \sqrt5}{2}) ^ n]\).
Catalan Count
Catalan There are many practical applications of numbers . Here we come together NOIP To lead to Catalan Count .
「 Example 」 Stack
Link to the original title ：Link.
We can set \(i\) A little ball , The outlet mode is \(h_i\). We can then discuss it according to the last ball out of the tube . Suppose the last one out of the pipe is \(k\) A little ball , So \(k\) The small ball that enters the tube early is \(k - 1\) individual , Than \(k\) The small ball that enters the tube late is \(n - k\) individual . After all these little balls are out of the tube , The first \(k\) It takes a small ball to get out of the tube . According to the principle of multiplication , The last ball out of the tube is the \(k\) Time , The total number of methods taken is \(h_{k - 1} \times h_{n - k}\). and \(k\) Can take \(1\) To \(n\). So the total number of fetches is \(h_n = \sum_{i = 1} ^ n h_{i - 1} \times h_{n - i}\). This is it. Catalan The number of recurrence persimmons . The recursive boundary is obviously ：\(f_0 = f_1 = 1\).
#include <bits/stdc++.h>
using namespace std;
int n, h[20] = {1, 1};
int main() {
cin >> n;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
h[i] += h[j - 1] * h[i - j];
cout << h[n] << endl;
return 0;
}
Catalan Application of sequence ：
- Put a convex \(n\) The number of schemes for dividing the polygon into several triangles （ Disjoint ）.
- The stacking sequence of a stack is \(1, 2, 3, \dots, n\), Different stack sequence numbers .
- \(n\) How many different binary tree schemes can be constructed by nodes .
- Choose... On the circle \(2 \times n\) A little bit , Connect these points in pairs to get \(n\) The number of methods that a line segment does not intersect .
- From the point of \((0, 0)\) point-to-point \((n, n)\), The shortest number of walks that do not cross but can touch the diagonal .
Except recursion ,Catalan Count \(h_n\) It can also be obtained through the general term formula ：\(h_n = \frac{C_{2n} ^ n}{n + 1} = C_{2n} ^ n - C_{2n} ^ {n - 1}\).
Hanio tower
Hanio Tower is a very classic recursive （ recursive ） problem . Maybe many people are feeling C++ When you are strong , The first procedure shown by the coach is Hanio tower .
「 Example 」Hanio Tower problem
Link to the original title ：Link.
We set up \(h_i\) For moving \(i\) The number of times required for a plate . apparently , We can put the above \(i - 1\) The plates move to B On the column , And then put the \(i\) Move your plate to C On the column , Finally, put B On the plate \(i - 1\) Move a plate to C On the column . that , Push the persimmon and it comes out ：\(h_i = 2 \times h_{i - 1} + 1\), The border \(h_1 = 1\).Hanio Tower also has a general term formula \(h_n = 2 ^ n - 1\).
# Python Version
n = int(input())
# print(2 ** n - 1)
# In this way, you can directly output
a = 1
for i in range(n - 1):
a = a * 2 + 1
print(a)
// C++ version
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65;
long long a[MAXN] = {0, 1};
int n;
int main() {
cin >> n;
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] << 1 | 1;
cout << a[n] << endl;
return 0;
}
The second category Stirling Count
「 Example 」 Put the ball properly
Link to the original title ：Link.
We can set \(S_{n, m}\) by \(n\) Put a different ball into \(m\) The same box （ Not empty ） The total number of playing methods in .
Think about the \(n\) How to put a ball . We can put this number \(n\) Put one ball in a box alone , So the front one \(n - 1\) One ball is going to occupy \(m - 1\) Boxes , The number of programmes is \(S_{n - 1, m - 1}\); You can also put this number \(n\) A ball and other balls occupy a box , So the front one \(n - 1\) One ball is going to occupy \(m\) Boxes （ The first \(n\) A ball doesn't take up extra space in the box ）, So the number of schemes is \((n - 1) \times S_{n - 1, m}\). From the principle of addition ,\(S_{n, m} = S_{n - 1, m - 1} + (n - 1) \times S_{n - 1, m}\).
Recursive boundary ：\(S_{n, n} = S_{n, 1} = S_{1, m} = 1\).
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long S(int n, int m) {
if (n == 1 || m == 1 || n == m) return 1;
return S(n - 1, m - 1) + m * S(n - 1, m);
}
int main() {
scanf("%d %d", &n, &m);
printf("%lld\n", S(n, m));
return 0;
}
Split plane problem
Such problems are quite changeable , Sometimes it's difficult , The point is to find rules （ crap ）.
「 Example 」 Split plane
Brief introduction ： Equipped with \(n\) Draw a closed curve on a plane , And any two closed curves just intersect at two points , And any three closed curves do not intersect at the same point , Ask the number of areas these closed curves divide the plane into .
Data range ：\(1 \leq n \leq 46314\).
Look at the picture , You can find , If set \(f_n\) By \(n\) When a closed curve , The number of areas in the title , Then there are \(f_n = f_{n - 1} + 2 \times (i - 1)\).\(f_1 = 2\).
The proof is also quite obvious . When drawing the first \(n\) Curve , Will be compared with each of the previous paintings \(n - 1\) Curve formation \(2\) A point of intersection , One more intersection is one more region , It can be obtained. .
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 46350;
int n;
long long a[MAXN] = {0, 2};
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] + ((i - 1) << 1);
printf("%lld\n", a[n]);
return 0;
}
Let's look at another problem , Deepen the impression .
「 Example 」 Split plane two
Brief introduction ： There are... In the same plane \(n\) A straight line , It is known that \(p\) Two straight lines intersect at the same point , Then this \(n\) How many different areas can a line divide a plane into ？
Data range ：\(2 \leq p \leq n \leq 500\).
Similarly to the previous question, set \(f_n\). Drawing is easy to find \(p\) Lines intersecting at the same point will produce \(2p\) Regions , The first \(i\) Lines will intersect to produce \(i\) Regions , So there is \(f_i = f_{i - 1} + i (i > p)\), The boundary is \(f_p = 2p\).
#include <bits/stdc++.h>
using namespace std;
int n, p;
int f[505];
int main() {
cin >> n >> p;
f[p] = p << 1;
for (int i = p + 1; i <= n; i++)
f[i] = f[i - 1] + i;
cout << f[n] << endl;
return 0;
}
Memorize
Sometimes , Using recursion will timeout , The reason is that a large number of repeated operations lead to low efficiency . And memorization can improve efficiency . Even you can use memory search instead DP.
「 Example 」Function
Link to the original title ：Link.
We can easily write plain code according to the meaning of the topic ：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
#define LL long long
LL a, b, c;
int w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
while (~scanf("%lld %lld %lld", &a, &b, &c)) {
if (a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}
Try the example , wow , It only took \(22\) Milliseconds passed ！
And hand it in , happy TLE.
Why is that ？ If we put \(w\) Function plus cout << a << " " << b << " " << c << endl;, Run again , You will find that many lines are output , But many of them are repetitive .
This inspires us to , You can use an array \(f\) To store \(w_{a, b, c}\), If you have obtained this value, you can directly return , Avoid invalid operations . This is it. Memorize . In this question , We use \(-1\) It means that you have not calculated . To be specific , If \(f_{a, b, c} = -1\), Then I haven't calculated , Let's calculate directly , And store the results in \(f_{a, b, c}\) in ; Otherwise, it will be calculated directly return \(f_{a, b, c}\) that will do .
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
#define LL long long
int f[MAXN][MAXN][MAXN];
LL a, b, c;
int w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) {
if (f[a][b][c] != -1) return f[a][b][c];
// If the value has been obtained , Go straight back to
return f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
// Otherwise, calculate this value , And store it , Next time I won't continue recursion
}
if (f[a][b][c] != -1) return f[a][b][c];
// ditto
return f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
memset(f, -1, sizeof(f)); // All initialized to -1 Indicates that no value is obtained
while (~scanf("%lld %lld %lld", &a, &b, &c)) {
if (a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}
What about? , Did you stop learning ？
Let's take a look IOI The subject of （ Well, it is \(1994\) Year of ）.
「 Example 」 Digital triangle Number Triangles
Link to the original title ：Link.
Suppose you don't recurse . We can set \(f_{i, j}\) From \((i, j)\) Go to the bottom of the biggest and . that , Obviously there is \(f_{i, j} = w_{i, j} + \max(f_{i + 1, j}, f_{i + 1, j + 1})\). Writing code is like this ：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int w[MAXN][MAXN];
int f(int i, int j) {
if (i == n) return w[i][j]; // I can't go anymore , Go straight back to w[i][j]
return w[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
cout << f(1, 1) << endl;
return 0;
}
But it will still time out , What shall I do? ？
you 're right , We can use memorization . Similarly , We use it \(-1\) It means I haven't searched \((i, j)\), If not equal to \(-1\) direct return that will do .
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int w[MAXN][MAXN], ans[MAXN][MAXN];
int f(int i, int j) {
if (i == n) return w[i][j];
if (ans[i][j] != -1) return ans[i][j];
return ans[i][j] = w[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
int main() {
memset(ans, -1, sizeof(ans));
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
cout << f(1, 1) << endl;
return 0;
}
Actually , It's a little DP Means .
Miscellaneous questions
「 Example 」 Laying bricks
Brief introduction ： There is one \(2 \times n\) The aisle , Now use \(1 \times 2\),\(2 \times 2\) To cover with bricks . How many different paving methods are there ？
Data range ： Multiple sets of data ,\(0 \leq n \leq 250\).
Presuppose \(f_n\) Means paved \(2 \times n\) The number of walkway schemes .\(2 \times n\) How is the walkway paved ？ You can have one \(1 \times 2\) The bricks are laid vertically on the far right , The problem turns into laying the rest \(2 \times (n - 1)\) The aisle , The number of options is \(f_{n - 1}\); It can also be made up of two \(1 \times 2\) The bricks are laid horizontally on the far right , The problem turns into laying the rest \(2 \times (n - 2)\) The aisle , The number of options is \(f_{n - 2}\); It can also be directly controlled by a \(2 \times 2\) The bricks are laid on the far right , The problem turns into laying the rest \(2 \times (n - 2)\) The aisle , The number of schemes is also \(f_{n - 2}\). Sum up , We can get recursive persimmons \(f_i = f_{i - 1} + f_{i - 2} \times 2\). The boundary is obviously \(f_1 = 1, f_2 = 3\).
Note that here is multi test , So we can deal with it in advance \(f_3\) to \(f_{250}\), Just answer one by one . Need to use high precision .
「 Example 」 Count odd and even numbers 3
Link to the original title ：Link.
There are two dimensions ： Bits and parity . We can set these two dimensions ： set up \(f_{n, 0}\) Express \(n\) How many numbers in a positive integer contain even numbers \(3\),\(f_{n, 1}\) Express \(n\) How many numbers in a positive integer contain odd numbers \(3\).
\(n\) In a positive integer , Including even numbers \(3\) How does the number of come from ？ There are two situations ：
- front \(n - 1\) Bits contain odd numbers \(3\), The first \(n\) Is it \(3\). The number is \(f_{n - 1, 1}\).
- front \(n - 1\) Bits contain even numbers \(3\), The first \(n\) It's not \(3\)（ yes \(0, 1, 2, 4, 5, 6, 7, 8, 9\)）. The number is \(f_{n - 1, 0} \times 8\).
So you can get \(f_{n, 0} = f_{n - 1, 1} + f_{n - 1, 0} \times 8\). In the same way \(f_{n, 1} = f_{n - 1, 0} + f_{n - 1, 1} \times 8\).
「 Example 」 Spiral matrix
Link to the original title ：Link.
Think about how to recurse , I found that the circle outside the matrix can be calculated directly （ know \(n\)）. Then observe the remaining matrix after removing the outer circle , It turns out that just subtract \(4n - 4\) Then there is a new matrix .
Take this picture as an example ：
\(1 \sim 12\) You can directly calculate , And the rest of the \(13, 14, 15, 16\) Equivalent to \(12 + 1, 12 + 2, 12 + 3, 12 + 4\).
The code is as follows ：
#include <cstdio>
int n, i, j;
int f(int m, int x, int y) {
if (x == 1) return y;
if (x == m) return 3 * m - y - 1;
if (y == 1) return 4 * m - x - 2;
if (y == m) return m + x - 1; // Boundary situation , You can deduce it yourself
return f(m - 2, x - 1, y - 1) + 4 * m - 4;
// Downsizing , Remember to add 4 * m - 4
}
int main() {
scanf("%d %d %d", &n, &i, &j);
printf("%d\n", f(n, i, j));
return 0;
}
「 Example 」 Infinite Road
Link to the original title ：Link.
Give two points \((x_1, y_1), (x_2, y_2)\), The length of the broken line required to be connected , For the sake of calculation , We can unify to point \((0, 0)\) Broken line length , Subtracting the two will offset , The rest is the answer we asked .
Now? , The problem turns into giving a point \((x, y)\), Ask it to arrive \((0, 0)\) Broken line length .
We can find out （ It's better to eat with pictures ）：
- When \(x = 0\) when , We can \((0, y)\) Go to the \((y - 1, 0)\), Add a little more \((y - 1, 0)\) point-to-point \((0, 0)\) Broken line length .
- When \(y = 0\) when , We can \((x, 0)\) Go to the \((0, x)\), Add a little more \((0, x)\) point-to-point \((0, 0)\) Broken line length .
- When \(x \not= 0\) And \(y \not= 0\) when , We can \((x, y)\) Go to the \((0, x + y)\), Add a little more \((0, x + y)\) point-to-point \((0, 0)\) Broken line length .
Then use the straight-line distance between two points that we learned in grade two of primary school \(\sqrt{(x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2}\) That's it . The boundary is obviously \((0, 0)\).
Because this is double type , It's not good to memorize directly , So we can open one bool Array is marked . The code is as follows ：
#include <cstdio>
#include <cmath>
double ans[205][205];
bool flag[205][205];
double f(int x1, int my1, int x2, int y2) {
return sqrt(pow(x1 - x2, 2) + pow(my1 - y2, 2));
} // The straight distance between two points
int n, x1, x2, my1, y2; // y1 Is the key word , Just add a letter
double g(int x, int y) {
if (!x && !y) return 0; // (0, 0) The border
if (flag[x][y]) return ans[x][y]; // It's been searched
flag[x][y] = true;
if (!x) return ans[x][y] = g(y - 1, 0) + f(x, y, y - 1, 0);
if (!y) return ans[x][y] = g(0, x) + f(x, y, 0, x);
return ans[x][y] = g(0, x + y) + f(x, y, 0, x + y); // Three situations
}
int main() {
scanf("%d", &n);
while (n--) {
scanf("%d %d %d %d", &x1, &my1, &x2, &y2);
printf("%.3lf\n", fabs(g(x1, my1) - g(x2, y2))); // Remember to add absolute value
}
return 0;
}
「 Example 」 Maximum odd divisor
Link to the original title ：Link.
Every number can be expressed as \(x = 2 ^ k \times a\) In the form of （\(2 \nmid a\)）, This question is \(f(x)\) Equivalent to finding \(a\). The answer for \(\sum _ {i = 1} ^ n f(i)\).
If you honestly calculate \(\sum _ {i = 1} ^ N f(i)\) Will timeout , Plus memorization MLE, This inspires us to make a function \(g(n) = \sum _ {i = 1} ^ n f(i)\).
Then we deduce the formula .
- When \(2 \nmid n\), obviously \(g(n) = n + g(n - 1)\).
- When \(2 \mid n\), Find out \(f(i)\) It can be divided into two categories according to parity ,\(f(2k) = f(k)\), and \(f(2k + 1) = 2k + 1\). Thus, you can also put \(\sum _ {i = 1} ^ n f(i)\) Divided into two categories , One is \(f(1) + f(3) + f(5) + \dots + f(n - 1) = 1 + 3 + 5 + \dots + (n - 1)\), One is \(f(2) + f(4) + f(6) + \dots + f(n) = f(1) + f(2) + f(3) + \dots + f(\frac{n}{2})\); The former can sum up the arithmetic sequence , The latter discovery is equal to \(f(\frac{n}2)\), Direct recursion .
#include <cstdio>
int n;
long long f(int x) {
if (x == 1) return 1; // The boundary conditions
if (x & 1) return f(x - 1) + x;
return f(x >> 1) + (long long)x * x / 4;
// because x * x It might spill over , So first convert to long long cube
}
int main() {
scanf("%d", &n);
printf("%lld\n", f(n));
return 0;
}
「 Example 」Strange Towers of Hanoi
Link to the original title ：Link.
The topic asks us to ask for Hanoi The number of moving steps of the tower . This simple , The second ！—— Is it really that simple ？ ah , yes \(4\) tower ！（ General Hanoi Tower yes \(3\) seat .）
however , There is such a passage in the title ：
This algorithm is applicable to \(n \leq 12\)： tower A Upper \(k\)（\(k \geq 1\)） A plate is fixed , rest \(n - k\) A plate is made from A Move to B. Then use the three tower algorithm to A Upper \(k\) Move a plate to D, Finally, the four tower algorithm is used to B Upper \(n - k\) Plates move to D.
Can be set \(n\) Three towers are needed when using a plate \(g_n\) Step , We have such a plan ： hold A Uppermost \(n - 1\) Move a plate to B,A No \(n\) Move a plate to C, And then put B Upper \(n - 1\) Move a plate to C. Thus there are \(g_n = 2 \times g_{n - 1} + 1\).
Set up again \(n\) Four towers are needed for a plate \(f_n\) Step . Because the title has told us the formula , Traverse \(k\) take \(\min\) that will do , No need for white, no need for wow ：
\]
「 Example 」 Chess move
Link to the original title ：Link.
First , We found that \(n = 4\) There is only one fixed moving method ：
4,5-->9,10
8,9-->4,5
2,3-->8,9
7,8-->2,3
1,2-->7,8
This is obviously the recursive boundary . That's right \(n > 4\) When （ Let's set \(n = 5\)）？
〇〇〇〇〇●●●●●
Easy to think of , First move the middle one to the far right .
〇〇〇〇[ ][ ]●●●●〇●
Then move the two black chessmen on the far right to the empty seat .
〇〇〇〇●●●●[ ][ ]〇●
I found that the left side was reduced to \(n - 1 = 4\) The situation of , Continue recursion .
The code is very simple ：
#include <cstdio>
#include <iostream>
int n;
void print(int n) {
if (n == 4) {
puts("4,5-->9,10\n\n8,9-->4,5\n\n2,3-->8,9\n\n7,8-->2,3\n\n1,2-->7,8");
return;
}
std::cout << n << "," << n + 1 << "-->" << (n << 1 | 1) << "," << (n * 2 + 2) << std::endl << std::endl;
std::cout << 2 * n - 1 << "," << (n << 1) << "-->" << n << "," << n + 1 << std::endl << std::endl;
print(n - 1);
}
int main() {
std::cin >> n;
print(n);
return 0;
}
By the way, It is recommended that you use printf,cout It's going to kill ...
「 Example 」 Fractal 1
Link to the original title ：Link.
The title requires us to output a strange X Shape fractal . Observation found that , When the scale is \(n\) when , In fact, it is caused by \(5\) The scale is \(n - 1\) Of X Form a combination . Generally speaking, for this fractal image , We all recurse scales and coordinates .
The code is very simple ：
#include <bits/stdc++.h>
using namespace std;
int n;
char ch[735][735];
void print(int n, int x, int y) { // n It's scale ,(x, y) Is the coordinate of the upper left corner of the figure
if (n == 1) {
ch[x][y] = 'X';
return;
} // Boundary situation
int t = pow(3, n - 2); // n - 1 Length of scale graph （ wide ）
print(n - 1, x, y); // Print top left
print(n - 1, x + (t << 1), y); // Print bottom left
print(n - 1, x + t, y + t); // Print the middle
print(n - 1, x, y + (t << 1)); // Print top right
print(n - 1, x + (t << 1), y + (t << 1)); // Print bottom right
}
int main() {
while (cin >> n) {
memset(ch, 0, sizeof(ch)); // Remember to clear
print(n, 1, 1);
int len = pow(3, n - 1);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++)
if (ch[i][j]) putchar(ch[i][j]);
else putchar(' ');
// The default is 0, Direct output , The naked eye cannot see the difference with the blank , But will WA
// So here's a special sentence
putchar('\n');
}
putchar('-');
putchar('\n');
}
return 0;
}
Attach a strange fractal code ：
#include <iostream>
using namespace std;
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
putchar((i & j) ? '#' : ' ');
putchar('\n');
}
return 0;
}
Try recursive implementation .
「 Learning notes 」 Recurrence & More about recursion
- 「 Learning notes 」FFT The fast Fourier transform
Catalog 「 Learning notes 」FFT The fast Fourier transform What is FFT ah ? What can it do ? Essential cheese Point value means The plural Fourier transform Inverse Fourier transform FFT Code implementation of There will be NTT And three modulus NTT... 「 Learning pens ...
- 「 Learning notes 」Treap
「 Learning notes 」Treap Preface What is? Treap ? Binary search tree (Binary Search Tree/Binary Sort Tree/BST) Basic definition Look for the element Insert elements Remove elements Find successors ...
- 「 Learning notes 」Min25 sieve
「 Learning notes 」Min25 sieve Preface Today's simulation competition is five minutes and one second , In ten minutes, the second question is \(\text{Min25}\) Sieve plate , If it wasn't for the wrong data range of the third question , 15 minutes a week \(\text{AK ...
- 「 Learning notes 」FFT Optimization of ——NTT
Catalog 「 Learning notes 」FFT Optimization of --NTT Preface introduce Fast number theory transformation --NTT Some extended problems and solutions Three modulus NTT Disassembly coefficient FFT (MTT) 「 Learning notes 」FFT Optimization of --NTT Preface \(NT ...
- 「 Learning notes 」wqs Two points /dp Convex optimization
[ Learning notes ]wqs Two points /DP Convex optimization Let's start with a classic question : There is a length of \(n\) Sequence \(a\), Ask to find out exactly \(k\) Two disjoint continuous subsequences , Make this \(k\) The sum of sequences is the largest \(1 \l ...
- 「 Learning notes 」ST surface
Problem introduction Let's start with a simple question , Yes N Elements ,Q operations , Each operation needs to find the maximum... In a section / Small value . That's the famous one RMQ problem . RMQ There are many solutions to the problem , Such as line tree . A monotonous queue ( In some cases ).ST Table, etc . Here's the Lord ...
- 「 Learning notes 」 Dynamic programming I『 First time to know DP』
Write it at the front Be careful : This article is for reference only , If you find any error, please inform in time . Updated date :2018/3/16,2018/12/03 Introduction to dynamic planning Dynamic programming , abbreviation DP(Dynamic Programming) brief introduction 1 brief introduction 2 ...
- 「 Learning notes 」Fast Fourier Transform
Preface The fast Fourier transform (\(\text{Fast Fourier Transform,FFT}\) ) It's a way to \(O(n \log n)\) To complete the polynomial multiplication algorithm in less time , stay \(OI\) There are many applications in , yes ...
- 「 Learning notes 」FFT And NTT Introduction
Preface The fast Fourier transform (\(\text{Fast Fourier Transform,FFT}\) ) It's a way to \(O(n \log n)\) To complete the polynomial multiplication algorithm in less time , stay \(OI\) There are many applications in , yes ...
- 「 Learning notes 」 FHQ Treap
FHQ Treap FHQ Treap (%%% Inventor fan Haoqiang every year NOI gold medal ) Is a magical data structure , Also called non rotating Treap, It is not like Treap zig zag I don't know ( So it's called non rotation ), It's not like Splay Not at all ...
Random recommendation
- Extraterrestrial virtual hosts span web Directory file read vulnerability
Off board virtual host cross directory read file vulnerability , It needs certain conditions . The problem is in the following file , These files do not have strict execution permissions , Current IIS Users can use them to execute commands smoothly : c:\windows\7i24IISLOG.exe ...
- Android Compress and upload pictures of
Android It is common to upload pictures during development , Generally, in order to save traffic, compression will be carried out , This article records the methods of compression and upload . Image compression method : import java.io.ByteArrayOutputStream; i ...
- iis Path problems caused by virtual directories
stay iis Upper handle web The program is configured so that the site is ok Of , But configure it as a virtual directory , You will find Image path cannot , Style cannot be loaded , Link error . Solution : 1, To upload pictures ~/upload 2,cs Program , Link jump , Please use ~/index. ...
- linux File segmentation （ Split large log files into small ones ）【 Reprint 】
linux File segmentation ( Split large log files into small ones )linux File segmentation can be done through split Command to implement , You can specify two modes: split by number of rows and split by size .Linux The next file merge can be done through cat Command to implement , It's simple . stay Li ...
- version control ——TortoiseSVN （3） Multi release
================================= Copyright notice ================================= Copyright notice : Original article Prohibited reproduced Please click the “ Contact mail ...
- openlayer3 Related extensions
1 ol3 Expand http://viglino.github.io/ol-ext/ , It contains editors - Select control , typeface , Animation ,canvas Drawing and so on 2 ol3 Spatial topological relation library jsts, Yes jst Derived from h ...
- Application node Real debugging mobile web project
Many times when we test the mobile terminal , Yes pc End of the test , There are also tests on real machines ,pc I don't want to say much about it , Because basically everyone knows . There are also several methods for real machine testing , Here are three : Mobile terminal real machine debugging method chrome Real machine debugging ...
- 【MOOC EXP】Linux Kernel analysis experiment II report
Cheng Han The original blog <Linux Kernel analysis >MOOC Course http://mooc.study.163.com/course/USTC-1000029000 [ How the operating system works ] In teaching ...
- Java Realize online preview Word,Excel,Ppt file
design sketch :
- JAVA data type （ Reprint ）
JAVA Median type only short,char,byte,int,long,double,float,boolean Eight basic types , All other types are reference types . First of all, we all know the assignment operation in programming “=” It means ...
![[network security] what is emergency response? What indicators should you pay attention to in emergency response?](/img/ff/c733ffbb922760910ab09af3ae2886.jpg)
