当前位置:网站首页>Blue Bridge Cup zero Foundation National Championship - day 20
Blue Bridge Cup zero Foundation National Championship - day 20
2022-07-06 06:50:00 【Brother dog^_^】
List of articles
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 C^m_n Cnm
** 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 A^n_n Ann
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 .
边栏推荐
- ML之shap:基于adult人口普查收入二分类预测数据集(预测年收入是否超过50k)利用Shap值对XGBoost模型实现可解释性案例之详细攻略
- [English] Verb Classification of grammatical reconstruction -- English rabbit learning notes (2)
- [English] Grammar remodeling: the core framework of English Learning -- English rabbit learning notes (1)
- Day 245/300 JS foreach data cannot be updated to the object after multi-layer nesting
- Use shortcut LNK online CS
- Machine learning plant leaf recognition
- Phishing & filename inversion & Office remote template
- 中英对照:You can do this. Best of luck祝你好运
- A method to measure the similarity of time series: from Euclidean distance to DTW and its variants
- Introduction and underlying analysis of regular expressions
猜你喜欢
A method to measure the similarity of time series: from Euclidean distance to DTW and its variants
翻译公司证件盖章的价格是多少
云服务器 AccessKey 密钥泄露利用
Bitcoinwin (BCW): the lending platform Celsius conceals losses of 35000 eth or insolvency
Chinese English comparison: you can do this Best of luck
论文翻译英译中,怎样做翻译效果好?
红蓝对抗之流量加密(Openssl加密传输、MSF流量加密、CS修改profile进行流量加密)
Introduction and underlying analysis of regular expressions
今日夏至 Today‘s summer solstice
Use shortcut LNK online CS
随机推荐
It is necessary to understand these characteristics in translating subtitles of film and television dramas
What is the difference between int (1) and int (10)? Senior developers can't tell!
医疗软件检测机构怎么找,一航软件测评是专家
Data security -- 13 -- data security lifecycle management
ECS accessKey key disclosure and utilization
[ 英语 ] 语法重塑 之 英语学习的核心框架 —— 英语兔学习笔记(1)
Biomedical localization translation services
What are the characteristics of trademark translation and how to translate it?
BUU的MISC(不定时更新)
Automated test environment configuration
SAP SD发货流程中托盘的管理
Market segmentation of supermarket customers based on purchase behavior data (RFM model)
【软件测试进阶第1步】自动化测试基础知识
Map of mL: Based on the adult census income two classification prediction data set (whether the predicted annual income exceeds 50K), use the map value to realize the interpretable case of xgboost mod
How to reconstruct the class explosion caused by m*n strategies?
Reflex WMS中阶系列3:显示已发货可换组
一文读懂简单查询代价估算
攻防世界 MISC中reverseMe简述
ML之shap:基于adult人口普查收入二分类预测数据集(预测年收入是否超过50k)利用Shap值对XGBoost模型实现可解释性案例之详细攻略
19.段页结合的实际内存管理