1.矩阵运算
#include <iostream>
#include <algorithm>#include <vector>
using namespace std;#define Debug_ 1//galobal value
#define N 2 //matrix invvector<vector<int>> Matrixmulti(vector<vector<int>> a, vector<vector<int>> b)
{int RowA = a.size();int ColA = a[0].size();int RowB = b.size();int ColB = b[0].size();vector<vector<int>> c(RowA, vector<int>(ColB, 0));int s=0;#if Debug_if (ColA != RowB){cout << "Matrix is not correct!" << endl;return c;}
#endiffor (int i = 0; i < RowA; i++){for (int m = 0; m <ColB; m++){for (int j = 0; j < ColA; j++){s = s + a[i][j] * b[j][m];}c[i][m] = s;s = 0;}}return c;
}vector<vector<int>> matrix_transpose(vector<vector<int>> a)
{int m = a.size();int n = a[0].size();vector<vector<int>> c= a;#if Debug_cout << "矩阵行列为" << m<<" " << n << endl;if (m != n){cout << "矩阵行列不一致！" << endl;return c;}
#endifint i, j;for (i = 1; i<m; i++){for (j = 0; j<i; j++)std::swap(c[i][j], c[j][i]);}return c;
}//LUP分解
void LUP_Descomposition(double A[N*N], double L[N*N], double U[N*N], int P[N]){int row = 0;for (int i = 0; i<N; i++){P[i] = i;}for (int i = 0; i<N - 1; i++){double p = 0.0;for (int j = i; j<N; j++){if (abs(A[j*N + i])>p){p = abs(A[j*N + i]);row = j;}}if (0 == p){cout << "矩阵奇异，无法计算逆" << endl;return;}//交换P[i]和P[row]int tmp = P[i];P[i] = P[row];P[row] = tmp;double tmp2 = 0.0;for (int j = 0; j<N; j++){//交换A[i][j]和 A[row][j]tmp2 = A[i*N + j];A[i*N + j] = A[row*N + j];A[row*N + j] = tmp2;}//以下同LU分解double u = A[i*N + i], l = 0.0;for (int j = i + 1; j<N; j++){l = A[j*N + i] / u;A[j*N + i] = l;for (int k = i + 1; k<N; k++){A[j*N + k] = A[j*N + k] - A[i*N + k] * l;}}}//构造L和Ufor (int i = 0; i<N; i++){for (int j = 0; j <= i; j++){if (i != j){L[i*N + j] = A[i*N + j];}else{L[i*N + j] = 1;}}for (int k = i; k<N; k++){U[i*N + k] = A[i*N + k];}}}
double * LUP_Solve(double L[N*N], double U[N*N], int P[N], double b[N]){double *x = new double[N]();double *y = new double[N]();//正向替换for (int i = 0; i < N; i++){y[i] = b[P[i]];for (int j = 0; j < i; j++){y[i] = y[i] - L[i*N + j] * y[j];}}//反向替换for (int i = N - 1; i >= 0; i--){x[i] = y[i];for (int j = N - 1; j > i; j--){x[i] = x[i] - U[i*N + j] * x[j];}x[i] /= U[i*N + i];}return x;}
/* 转置，即循环处理所有环 */
/* 后继 */
int getNext(int i, int m, int n)
{return (i%n)*m + i / n;}/* 前驱 */int getPre(int i, int m, int n){return (i%m)*n + i / m;}/* 处理以下标i为起点的环 */void movedata(double *mtx, int i, int m, int n){double temp = mtx[i]; // 暂存int cur = i; // 当前下标int pre = getPre(cur, m, n);while (pre != i){mtx[cur] = mtx[pre];cur = pre;pre = getPre(cur, m, n);}mtx[cur] = temp;}void transpose(double *mtx, int m, int n)
{for (int i = 0; i<m*n; ++i){int next = getNext(i, m, n);while (next > i) // 若存在后继小于i说明重复,就不进行下去了（只有不重复时进入while循环）next = getNext(next, m, n);if (next == i) // 处理当前环movedata(mtx, i, m, n);}}vector<vector<double>> LUP_solve_inverse(vector<vector<int>> a) //LUP 方程{//创建矩阵A的副本，注意不能直接用A计算，因为LUP分解算法已将其改变int m = a.size();int n = a[0].size();vector<vector<double>> out_ (m,vector<double>(n,0));double *A_mirror = new double[N*N]();double *inv_A = new double[N*N]();//最终的逆矩阵（还需要转置）double *inv_A_each = new double[N]();//矩阵逆的各列//double *B =new double[N*N]();double *b = new double[N]();//b阵为B阵的列矩阵分量for (int i = 0; i<N; i++){double *L = new double[N*N]();double *U = new double[N*N]();int *P = new int[N]();//构造单位阵的每一列for (int i = 0; i<N; i++){b[i] = 0;}b[i] = 1;//每次都需要重新将A复制一份for (int i = 0; i<N*N; i++){A_mirror[i] = (double) a[i/N][i%N];}LUP_Descomposition(A_mirror, L, U, P);inv_A_each = LUP_Solve(L, U, P, b);memcpy(inv_A + i*N, inv_A_each, N * sizeof(double));//将各列拼接起来}transpose(inv_A, N, N);//由于现在根据每列b算出的x按行存储，因此需转置for (int i = 0; i<N*N; i++){out_[i / N][i%N] = inv_A[i];}return out_;}int main(void)
{int NumOfRowA=2, NumOfColA=2, NumOfRowB=2, NumOfColB=2;cin>> NumOfRowA >> NumOfColA>> NumOfRowB >> NumOfColB;vector<vector<int>> a(NumOfRowA, vector<int>(NumOfColA, 0));vector<vector<int>> b(NumOfRowB, vector<int>(NumOfColB, 0));//outputvector<vector<int>> a_mul_b(NumOfRowA, vector<int>(NumOfColB, 0));vector<vector<int>> a_trans(NumOfRowA, vector<int>(NumOfRowA, 0));vector<vector<double>> a_inv(NumOfRowA, vector<double>(NumOfRowA, 0));cout << "请输入A矩阵：" << endl;//inputfor (int i = 0; i < NumOfRowA; i++){for (int j = 0; j < NumOfColA; j++){cin >> a[i][j];cout << a[i][j] << " ";}cout <<endl;}cout << "请输入B矩阵" << endl;for (int j = 0; j < NumOfColB; j++){for (int m = 0; m < NumOfColB; m++){cin >> b[j][m];cout << b[j][m] << " ";}cout << endl;}a_mul_b = Matrixmulti(a, b);cout << "矩阵乘法的结果：" << endl;for (int i = 0; i < NumOfRowA; i++){for (int j = 0; j < NumOfColB; j++){cout << a_mul_b[i][j] << "\t";}cout << endl;}a_trans = matrix_transpose(a);cout << "矩阵A转置的结果：" << endl;for (int i = 0; i < NumOfRowA; i++){for (int j = 0; j < NumOfColA; j++){cout << a_trans[i][j] << "\t";}cout << endl;}a_inv = LUP_solve_inverse(a);cout << "矩阵A求逆的结果：" << endl;for (int i = 0; i < NumOfRowA; i++){for (int j = 0; j < NumOfRowA; j++){cout << a_inv[i][j] << "\t";}cout << endl;}while (1);return 0;
}2.一步状态转移矩阵
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;#define udirection 1 //无向图
#define direction 0 //有向图
#define Freach 0 //第一次到达
#define FindAll 1 //遍历所有节点vector<vector<int>> Matrixmulti(vector<vector<int>> a, vector<vector<int>> b)
{int RowA = a.size();int ColA = a[0].size();int RowB = b.size();int ColB = b[0].size();vector<vector<int>> c(RowA, vector<int>(ColB, 0));int s=0;if (ColA != RowB){cout << "Matrix is not correct!" << endl;return c;}for (int i = 0; i < RowA; i++){for (int m = 0; m <ColB; m++){for (int j = 0; j < ColA; j++){s = s + a[i][j] * b[j][m];}c[i][m] = s;s = 0;}}return c;
}int main(void)
{int NumOfRowA = 4, NumOfColA = 4;cin >> NumOfRowA;vector<vector<int>> a(NumOfRowA, vector<int>(NumOfRowA, 0));// row(start) col(end)vector<vector<int>> a_mul_b(NumOfRowA, vector<int>(NumOfRowA, 0));vector<int> findip(NumOfRowA);cout << "连接关系：" << endl; //4节点 3条线for (int i = 0; i < NumOfRowA - 1; i++){int one, two;cin >> one >> two; //两个节点的连接线
#if udirectiona[one-1][two-1] = 1;a[two-1][one-1] = 1;
#endif
#if directiona[one - 1][two - 1] = 1;
#endif}
#if FindAll/*for (int i = 0; i < NumOfRowA - 1; i++)a[i][i]=1;*/
#endif//inputcout << "一步状态转移矩阵为:" << endl;for (int i = 0; i < NumOfRowA; i++){for (int j = 0; j < NumOfRowA; j++){cout << a[i][j] << " ";}cout <<endl;}cout << endl;a_mul_b = a;for (int step =1;step<5; step++){cout << "step "<<step<<":"<< endl<<endl;for (int i = 0; i < NumOfRowA; i++){for (int j = 0; j < NumOfRowA; j++){cout << a[i][j] << "\t";}cout << endl;}#if Freachif (a[0][3] == 1){cout << "从节点 1 出发第一次到达节点 4 经过 " << step << " 步;" << endl;break;}
#endif#if FindAllint count_ = 0;//for (int i = 0; i < NumOfRowA; i++)// if (a[0][i] != 0) //a[0][i]表示从节点1出发// findip[i]++;//for (int i = 0; i < NumOfRowA; i++)if (a[0][i] != 0) //a[0][i]表示从节点1出发count_++;if (count_ == NumOfRowA){cout << "从节点 1 出发遍历全部节点最小需要 " << step << " 步;" << endl;// break;}
#endifa = Matrixmulti(a_mul_b,a); }while (1);return 0;
}字符串子串
#include<iostream>
#include <string>
#include<math.h>
#include<vector>
using namespace std;int main()
{int k;string a, b;cin >> k;cin >> a;cin >> b;int len = a.length();vector<string> str;for (int i = 0; i < len - k+1; i++){string s = a.substr(i, k);// cout << s << endl;bool fh = false;for (int j = 0; j < str.size(); j++)if (s == str[j])fh = true;if (!fh)str.push_back(s);}for (int j = 0; j < str.size(); j++)cout << str[j] << endl;int num = 0;for (int j = 0; j < str.size(); j++){for (int i = 0; i < b.length() - k+1; i++){string s = b.substr(i, k);if (s == str[j])num++;}}cout << num;//while (1);return 0;}