y总的代码模板

基础算法数据结构二分查找搜索与图论数学知识求解斐波那契数列的若干方法

判断素数

int isPrime(int n) { if (n < 2) return 0; for (int i = 2; i <= (int)sqrt(n); ++i) if (n % i == 0) return 0; return 1; }

最大公约数

//递归 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } //循环 int gcd(int a, int b) { while(b ^= a ^= b ^= a %= b; return a; }

最小公倍数

int lcm(int a, int b) { return a / gcd(a, b) * b; }

斐波那契

int fabonaci(int n) { if (n == 0 || n == 1) return n; return fabonaci(n - 1) + fabonaci(n - 2); }

约瑟夫环

int ysf(int n, int m) { return n == 1 ? 0 : (ysf(n - 1, m) + m) % n; } #按顺序输出出圈编号 int ysf(int n, int m, int k) { return k == 1 ? (n + m - 1) % n : (ysf(n - 1, m, k - 1) + m) % n; } for (int i = 1; i <= n; ++i) cout << ysf(n, m, i) + 1 << endl; #################################################### int main() { int n, m, i, s = 0; cin >> n >> m; for (i = 2; i <= n; i++) { s = (s + m) % i; } cout << s + 1; }

进制转换

任意进制转化为10进制

int Atoi(string s,int radix) //s是给定的radix进制字符串 { int ans=0; for(int i=0;i<s.size();i++) { char t=s[i]; if(t>='0'&&t<='9') ans=ans*radix+t-'0'; else ans=ans*radix+t-'a'+10; } return ans; }

10进制转换为任意进制

内置函数： itoa(num, str, 2); num是一个int型的，是要转化的10进制数，str是转化结果，后面的值为目标进制。【c++中一般用_itoa】

string intToA(int n,int radix) //n是待转数字，radix是指定的进制 { string ans=""; do{ int t=n%radix; if(t>=0&&t<=9) ans+=t+'0'; else ans+=t-10+'a'; n/=radix; }while(n!=0); //使用do{}while（）以防止输入为0的情况 reverse(ans.begin(),ans.end()); return ans; }

c++按指定进制输出

#include <bitset> #include<iostream> using namespace std; int main() { cout << "35的8进制:" << std::oct << 35<< endl; cout << "35的10进制" << std::dec << 35 << endl; cout << "35的16进制:" << std::hex << 35 << endl; cout << "35的2进制: " << bitset<8>(35) << endl; //<8>：表示保留8位输出 return 0; }

十进制转二进制

void dectobin(int n) { if (n == 0 || n == 1) cout << n; else { dectobin(n / 2); cout << n % 2; } }

二进制转十进制

int toten(int x){ int ans = 0, cnt = 0; while(x){ ans += (pow(2,cnt++) * (x % 10)); x /= 10; } return ans; } ########################################### int toten(string s) { int ans = 0, len = s.size(); for (int i = 0; i < len; ++i) { ans += ((s[i] - '0') * pow(2, len - i - 1)); } return ans; }

十进制转八进制

void dectooct(int n) { if (n >=0 && n < 8) cout << n; else { dectooct(n / 8); cout << n % 8; } }

十进制转十六进制

string str="0123456789ABCDEF" void dectohex(int n) { if (n >=0 && n < 16) cout << str[n]; else { dectooct(n / 16); cout << str[n % 16]; } }

高精度加法

string add(string a, string b) { string c; int la = a.size(), lb = b.size(); if (la < lb) //前面补0 for (int i = 0; i < lb - la; ++i) a = "0" + a; else for (int i = 0; i < la - lb; ++i) b = "0" + b; int tmp = 0; for (int i = a.size() - 1; i >= 0; --i) { c = char((a[i] - '0' + b[i] - '0' + tmp) % 10 + '0') + c; //第i位的进位 tmp = (a[i] - '0' + b[i] - '0' + tmp) / 10; //第i位的值 } if (tmp) //最高位补位 c = char(tmp + '0') + c; return c; }

高精度减法

int arr[MAX], brr[MAX], c[MAX]; void substract(string a, string b) { int flag = 0; if (a.size() < b.size() || a.size() == b.size() && a < b) { swap(a, b); flag = 1; } for (int i = a.size(); i > 0; --i) arr[i] = a[a.size() - i] - '0'; for (int i = b.size(); i > 0; --i) brr[i] = b[b.size() - i] - '0'; int c_size = max(a.size(), b.size()); for (int i = 1; i <= c_size; ++i) { if (arr[i] < brr[i]) { arr[i + 1]--; arr[i] += 10; } c[i] = arr[i] - brr[i]; } while (!c[c_size]) { c_size--; } if (flag) cout << "-"; for (int i = c_size; i > 0; --i) cout << c[i]; if (c_size < 1) cout << 0; }

大数乘法

#define MAX 1000000 int a[MAX], b[MAX], c[MAX]; void multiply(string A, string B) { int flag = 0; if (A[0] == '-' && b[0] != '-') { flag++; A = A.substr(1); } if (A[0] != '-' && B[0] == '-') { flag++; B = B.substr(1); } int LA = A.size(), LB = B.size(); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); for (int i = 0; i < LA; ++i) a[i] = A[LA - 1 - i] - '0'; for (int i = 0; i < LB; ++i) b[i] = B[LA - 1 - i] - '0'; for (int i = 0; i < LB; ++i) for (int j = 0; j < LA; ++j) c[i + j] += b[i] * a[j]; for (int i = 0; i < LA + LB; ++i) if (c[i] >= 10) { c[i + 1] += c[i] / 10; c[i] %= 10; } int i = LA + LB; while (c[i] == 0) --i; if (flag == 1) cout << '-'; if (i < 0) cout << 0; else for (; i >= 0; --i) cout << c[i]; }

分治法求最大值（类比求最小值）

int find_max(int* a, int low, int hight) { int max; if (low == hight) return a[low]; else { int mid = (low + hight) / 2; int left_max = find_max(a, low, mid); int right_max = find_max(a, mid + 1, hight); return max = left_max > right_max ? left_max : right_max; } }

冒泡排序

void Bubble_Sort(int* a, int n) { for (int i = n - 1; i > 0; --i) for(int j=0;j<i;++j) if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } }

选择排序（升序）

void Selection_Sort(int *a, int n) { for (int i = 0; i < n - 1; ++i) { int min_index = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[min_index]) min_index = j; } int tmp = a[i]; a[i] = a[min_index]; a[min_index] = tmp; } }

插入排序

void Insertion_Sort(int *a, int n) { for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) if (a[i] < a[j]) { int tmp = a[i]; for (int k = i; k > j; --k) a[k] = a[k - 1]; a[j] = tmp; break; } } }

归并排序

//合并 void Merge(int *a, int L,int M,int R) { int left_size = M - L, right_size = R - M + 1, *left = new int[left_size], *right = new int[right_size]; for (int i = L; i < M; ++i) left[i - L] = a[i]; for (int i = M; i <= R; ++i) right[i - M] = a[i]; int i = 0, j = 0, k = L; while (i<left_size&&j<right_size) { if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; } while (i<left_size) { a[k++] = left[i++]; } while (j<right_size) { a[k++] = right[j++]; } } //分治 void Merge_Sort(int* a, int L, int R) { if (L == R) return; int M = (L + R) / 2; Merge_Sort(a, L, M); Merge_Sort(a, M + 1, R); Merge(a, L, M + 1, R); }

后序中序构建二叉树

Node* buildTree(int* post, int* in, int n) { if (n == 0) return NULL; int* mid = in; while (*mid != *(post + n - 1)) mid++; Node* T = new Node; T->data = *mid; int m = mid - in; T->lc = buildTree(post, in, m); T->rc = buildTree(post + m, mid + 1, n - m - 1); return T; }

前序序中序构建二叉树

Node* buildTree(int* pre, int* in, int n) { if (n == 0) return 0; int* mid = in; while (*pre != *mid)mid++; Node* T = new Node; T->data = *mid; int m = mid - in; T->lc = buildTree(pre + 1, in, m); T->rc = buildTree(pre + 1 + m, mid + 1, n - m - 1); return T; }

汉诺塔问题

//递归 void hanoiTower(int n, char a, char b, char c) { if (n == 1) cout << a << " -> " << c << endl; else { hanoiTower(n - 1, a, c, b); cout << a << " -> " << b << endl; hanoiTower(n - 1, b, a, c); } }