1、排列论文
#include<bits/stdc++.h> using namespace std; const int N=105; vector<int>g[N]; int a[N]; int n,m; int flag; int topSort(){ queue<int>q; for(int i=1;i<=n;i++){ if(a[i]==0){ q.push(i); } } int cnt=0; flag=1; while(!q.empty()){ int t=q.front(); q.pop(); cnt++; if(!q.empty())flag=2; for(int i=0;i<g[t].size();i++){ int x=g[t][i]; a[x]--; if(a[x]==0)q.push(x); } } if(cnt<n)flag=0; return flag; } int main(){ while(cin>>n>>m){ for(int i=1;i<=n;i++){ g[i].clear(); a[i]=0; } for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; a[v]++; g[u].push_back(v); } int result=topSort(); if(result==0)cout<<"0\n"; else if(result==1)cout<<"1\n"; else if(result==2)cout<<"2\n"; } return 0; }
2、十进制到二进制的转换
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; if(n<0){ cout<<0<<endl; return 0; } int a[45]; int idx=0; while(n>0){ a[idx]=n%2; n=n/2; idx++; } for(int i=idx-1;i>=0;i--){ cout<<a[i]; } cout<<endl; return 0; }
3、周末舞会
#include<bits/stdc++.h> using namespace std; int main(){ int boy,girl,k; cin>>boy>>girl>>k; queue<int>b_q,g_q; for(int i=1;i<=boy;i++){ b_q.push(i); } for(int i=1;i<=girl;i++){ g_q.push(i); } while(k--){ int x,y; x=b_q.front(); b_q.pop(); y=g_q.front(); g_q.pop(); cout<<x<<" "<<y<<endl; b_q.push(x),g_q.push(y); } return 0; }
4、哥德巴赫猜想
#include<bits/stdc++.h> using namespace std; bool ss(int x){ if(x<2)return false; for(int i=2;i*i<=x;i++){ if(x%i==0){ return false; } } return true; } int main(){ int n,ans; while(cin>>n){ ans=0; if(n==0)break; for(int i=2;i<=n/2;i++){ if(ss(i)&&ss(n-i)){ ans++; } } cout<<ans<<endl; } return 0; }
5、查找二叉树
#include<bits/stdc++.h> using namespace std; const int N=105; struct node{ int value; int left; int right; }a[N]; int n; int target; int cnt=0; int result=-1; void zhongxu(int idx){ if(idx==0)return; zhongxu(a[idx].left); cnt++; if(a[idx].value==target){ result=cnt; } zhongxu(a[idx].right); } int main(){ cin>>n; cin>>target; for(int i=1;i<=n;i++){ cin>>a[i].value>>a[i].left>>a[i].right; } zhongxu(1); cout<<result<<endl; return 0; }
6、图的遍历------广度优先搜索
#include <bits/stdc++.h> using namespace std; const int MAXN = 55; int vis[MAXN]; int a[MAXN][MAXN]; queue<int> q; // 广度优先搜索函数 void bfs(int n) { q.push(0); vis[0] = 1; cout << 0 << " "; while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i < n; i++) { if (a[x][i] == 1 && vis[i] == 0) { vis[i] = 1; q.push(i); cout << i << " "; } } } } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } bfs(n); return 0; }
7、图的遍历------深度优先搜索
#include<bits/stdc++.h> using namespace std; int vis[55]; int a[55][55]; int n; void dfs(int k){ vis[k]=1; cout<<k<<" "; for(int i=0;i<n;i++){ if(vis[i]==0&&a[k][i]==1)dfs(i); } } int main(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } } dfs(0); return 0; }
8、FBI树（二叉树）
#include <bits/stdc++.h> using namespace std; int a[2048+10]; int len; // 构建FBI树 void buildTree(int root) { if(root>=len)return; buildTree(2*root); buildTree(2*root+1); if(a[2*root]==1&&a[2*root+1]==1)a[root]= 1; else if(a[2*root]==0&&a[2*root+1]==0)a[root]=0; else a[root]=2; } // 后序遍历FBI树 void dfsTree(int root) { if(root>=2*len)return; dfsTree(2*root); dfsTree(2*root+1); if (a[root]==1)cout<<"I"; else if(a[root]==0)cout<<"B"; else cout<<"F"; } int main() { int n; string str; cin>>n; cin>>str; len=1<<n; // 将输入的字符串存储到数组中 for(int i=len;i<=2*len-1;i++){ a[i]=str[i-len]-'0'; } buildTree(1); dfsTree(1); return 0; }
9、图着色问题
#include<bits/stdc++.h> using namespace std; const int N=510,M=N*N; int color[N]; vector<int> g[M]; int v,m,k,n; void add(int a,int b){ g[a].push_back(b); g[b].push_back(a); } int judge(int cnt){ if(cnt!=k)return 0; for(int i=1;i<=v;i++){ for(int j=0;j<g[i].size();j++){ int t=g[i][j]; if(color[i]==color[t])return 0; } } return 1; } int main(){ cin>>v>>m>>k; while(m--){ int a,b; cin>>a>>b; add(a,b),add(b,a); } cin>>n; for(int i=0;i<n;i++){ set<int> se;//set具有去重功能 for(int j=1;j<=v;j++){ cin>>color[j]; se.insert(color[j]); } if(judge(se.size()))cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
10、地下迷宫探索
#include <bits/stdc++.h> using namespace std; const int N = 1005; int vis[N]; int g[N][N]; stack<int> stk; int n, m, src; // 深度优先搜索函数 void dfs(int k) { vis[k] = 1; if (vis[src]) cout << k; else cout << " " << k; stk.push(k); for (int i = 1; i <= n; i++) { if (!vis[i] && g[k][i] == 1) { cout << " "; dfs(i); } } stk.pop(); if(!stk.empty()){ cout<<" "<<stk.top(); } } int main() { memset(vis, 0, sizeof(vis)); cin >> n >> m >> src; // n代表节点数，m代表边数，src代表初末位置 int s, d; for (int i = 1; i <= m; i++) { cin >> s >> d; g[s][d] = g[d][s] = 1; } dfs(src); bool connected = true; for (int i = 1; i <= n; i++) { if (!vis[i]) { connected = false; break; } } if (!connected) cout << " " << 0; return 0; }
11、寻宝图
#include<bits/stdc++.h> using namespace std; const int N=1e5+1; int n,m,flag=0; string map_m[N]; int cnt=0,cns=0;//cnt代表岛屿的数量，cns代表宝藏的数量 int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dfs(int x,int y){ if(x<0||x>=n||y<0||y>=m||map_m[x][y]=='0')return; if(map_m[x][y]>'1'){ flag=1; } map_m[x][y]='0'; for(int i=0;i<4;i++){ dfs(x+dx[i],y+dy[i]); } } int main(){ cin>>n>>m; for(int i=0;i<n;i++)cin>>map_m[i]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(map_m[i][j]>'0'){ cnt++; flag=0; dfs(i,j);//查看是否有宝藏 if(flag)cns++; } } } cout<<cnt<<" "<<cns; return 0; }
12、信使
#include<bits/stdc++.h> using namespace std; const int N=105; int n,m; int g[N][N]; int dist[N]; bool st[N]; const int INF=0x3f3f3f3f; int dij(){ memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=1;i<n;i++){ int t=0; for(int j=1;j<=n;j++){ if(!st[j]&&dist[j]<dist[t]){ t=j; } } st[t]=true; for(int k=1;k<=n;k++){ dist[k]=min(dist[k],dist[t]+g[t][k]); } } int res=0; for(int i=1;i<=n;i++){ if(dist[i]==INF) return -1; res=max(res,dist[i]); } return res; } int main(){ cin>>n>>m; memset(g,0x3f,sizeof g); for(int i=1;i<=n;i++){ g[i][i]=0; } for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; g[u][v]=min(g[u][v],w); g[v][u]=min(g[v][u],w); } cout<<dij()<<endl; return 0; }
13、求先序排列（后中求先）
#include<bits/stdc++.h> using namespace std; struct node{ char value; node* left; node* right; node(char x):value(x),left(NULL),right(NULL){} }; //post表示后序，idx表示中序 node* buildtree(string post, string idx){ if(post.empty() || idx.empty()) return NULL; // 后序遍历的最后一个字符是根节点 char rootv = post.back(); node* root = new node(rootv); // 在中序遍历中找到根节点的位置 int rootidx = idx.find(rootv); // 分割中序遍历为左子树和右子树 string leftidx = idx.substr(0, rootidx); string rightidx = idx.substr(rootidx + 1); // 分割后序遍历为左子树和右子树 string leftpost = post.substr(0, leftidx.length()); string rightpost = post.substr(leftidx.length(), rightidx.length()); // 修正递归调用的参数顺序：(后序, 中序) root->left = buildtree(leftpost, leftidx); root->right = buildtree(rightpost, rightidx); return root; } void xianxu(node* root){ if(root == NULL) return; //直接返回，不返回值 cout << root->value; xianxu(root->left); xianxu(root->right); } int main(){ string post, idx; // 修正变量名以反映实际用途 cin >> idx >> post; //先输入中序，再输入后序 node* root = buildtree(post, idx); xianxu(root); cout << endl; return 0; }
14、还原二叉树
#include<bits/stdc++.h> using namespace std; struct node{ char value; node* left; node* right; // 添加构造函数 node(char val) : value(val), left(NULL), right(NULL) {} }; int n; node* buildtree(string pre, string idx){ if(pre.empty() || idx.empty()){ return NULL; } char vroot = pre[0]; node* root = new node(vroot); int idxroot = idx.find(vroot); string leftidx = idx.substr(0, idxroot); string rightidx = idx.substr(idxroot+1); string leftpre = pre.substr(1, leftidx.length()); string rightpre = pre.substr(1 + leftidx.length()); root->left = buildtree(leftpre, leftidx); root->right = buildtree(rightpre, rightidx); return root; } // 修正函数名和返回值类型 int treeHeight(node* root){ if(root == NULL) return 0; int leftheight = treeHeight(root->left); int rightheight = treeHeight(root->right); return max(leftheight, rightheight) + 1; } int main(){ cin >> n; string pre, idx; cin >> pre >> idx; node* root = buildtree(pre, idx); // 构建二叉树 int h = treeHeight(root); // 调用修正后的函数名 cout << h << endl; return 0; }
15、求二叉树的叶子结点
#include<bits/stdc++.h> using namespace std; const int N=1e3+5; char a[N]; int cnt=0; string str; void dfs(int r){ if(a[2*r]!=-1)dfs(2*r); cout<<a[r]; if(a[2*r]==-1&&a[2*r+1]==-1){ cnt++; } if(a[2*r+1]!=-1){ dfs(2*r+1); } } int main(){ cin>>str; stack<int>st; st.push(1); for(int i=0;i<str.size();i++){ int p=st.top(); st.pop(); if(str[i]!='#'){ a[p]=str[i]; st.push(2*p+1); st.push(2*p); } else{ a[p]=-1; } } dfs(1); cout<<"\n"<<cnt; return 0; }
16、二叉树非叶子
#include<bits/stdc++.h> using namespace std; const int N=105; struct node{ int value; int left; int right; }a[N]; int n; void xianxu(int idx){ if(idx==0)return; cout<<a[idx-1].value<<" "; xianxu(a[idx-1].left); xianxu(a[idx-1].right); } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i].value>>a[i].left>>a[i].right; } for(int i=0;i<n;i++){ if(a[i].left!=0&&a[i].right!=0){ a[i].value+=1; } } xianxu(1); cout<<endl; return 0; }
17.约瑟夫问题
#include<iostream> #include<queue> using namespace std; int n,m; int main(){ cin>>n>>m; queue<int>q; for(int i=1;i<=n;i++){ q.push(i); } int i=1; while(!q.empty()){ if(i==m){ cout<<q.front()<<" "; q.pop(); i=1; } else{ q.push(q.front()); q.pop(); i=i+1; } } return 0; }
18、二叉树求高度
#include<bits/stdc++.h> using namespace std; const int N=105; struct node{ int data; int left; int right; }a[N]; int n; int dfs(int root){ if(root==0)return 0; int h1=dfs(a[root].left); int h2=dfs(a[root].right); return max(h1,h2)+1; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].data>>a[i].left>>a[i].right; } cout<<dfs(1); return 0; }
19、完全二叉树的权值
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; int n,x; int main(){ int h=0,nn=0; cin>>n; for(int i=1;i<=n;i++){ if(i>nn){ nn+=pow(2,h); h++; } cin>>x; a[h]+=x; } int max_a=0,maxh=0; for(int i=1;i<=h;i++){ if(a[i]>max_a){ max_a=a[i]; maxh=i; } } cout<<maxh<<endl; return 0; }
20、围圈报数
#include<bits/stdc++.h> using namespace std; int main(){ queue<int>cl; int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ cl.push(i); } while(!cl.empty()){ int x; for(int i=1;i<=m-1;i++){ x=cl.front(); cl.pop(); cl.push(x); } x=cl.front(); cl.pop(); cout<<x<<" "; } return 0; }
21、走出迷宫
#include <iostream> #include <queue> using namespace std; char a[105][105]; int b[105][105]; int n, m; struct Node { int r, c; int step; }; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 检查坐标是否在网格内 bool isValid(int r, int c) { return r >= 1 && r <= n && c >= 1 && c <= m; } void bfs(int sr, int sc, int er, int ec) { queue<Node> dl; Node q, next; q.r = sr; q.c = sc; q.step = 0; dl.push(q); b[q.r][q.c] = 1; while (!dl.empty()) { q = dl.front(); dl.pop(); if (q.r == er && q.c == ec) { cout << q.step << endl; // 如果当前点是终点 return; } for (int i = 0; i < 4; i++) { next.r = q.r + dir[i][0]; next.c = q.c + dir[i][1]; // 1可走 2未走过 3不出边界 if (a[next.r][next.c] == '.' && b[next.r][next.c] == 0 && isValid(next.r, next.c)) { next.step = q.step + 1; b[next.r][next.c] = 1; dl.push(next); } } } cout << "No path found!" << endl; // 未找到路径 } int main() { int sr, sc, er, ec; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; if (a[i][j] == 'S') { sr = i; sc = j; } if (a[i][j] == 'T') { er = i; ec = j; a[i][j] = '.'; // 将终点状态记为可走 } } } bfs(sr, sc, er, ec); return 0; }
 —— 基于QR分解的最小惯性参数集提取与观测矩阵重构)
