The Adventure Begins ⚓

BackTracking（DFS + BoundingFunction） #include <iostream> using namespace std; int n = 5; int x[6] = {0,1}; int G[6][6] = { {0,0,0,0,0,0}, {0,0,1,1,0,1}, {0,1,0,1,1,1}, {0,1,1,0,1,0}, {0,0,1,1,0,1}, {0,1,1,0,1,0} }; void NextVetex(int k){ do { x[k] = (x[k] + 1) % (n + 1); if(x[k] == 0){ return; } // 确保和前一个节点联通 if(G[x[k - 1]][x[k]] != 0){ int j = 1; // 确保节点不会重复 for(; j < k; ++j){ if(x[j] == x[k]){ break; } } if(j == k){ // 如果不是最后一个节点 // 或者是最后一个节点，并且最后一个节点和第一个节点是联通的 if((k < n) || (k == n && G[x[n]][x[1]] !...

state space tree Back Tracking (DFS) brute force recursion Branch and Bound (BFS) 算法一： #include <iostream>using namespace std; void permutation(char S[], int k){ static int A[10] = {0}; static char res[10] = {0}; if(S[k] == '\0'){ res[k] = '\0'; printf("%s\n", res); } else{ for(int i = 0; S[i] != '\0'; ++i){ if(A[i] == 0){ A[i] = 1; res[k] = S[i]; permutation(S, k+1); A[i] = 0; } } } } int main() { char S[] = "ABC"; permutation(S, 0); return 0; } output:...

#include <iostream> void shellSort(int A[], int n){ int gap, i, j, temp; for(gap = n/2; gap >= 1; gap /= 2){ for(i = gap; i < n; ++i){ temp = A[i]; j = i - gap; while(j >= 0 && A[j] > temp){ A[j+gap] = A[j]; j = j - gap; } A[j + gap] = temp; } } } int main() { int A[] = {8, 3, 7, 4, 9, 2, 6, 5, 1, 11, 10}; int n = 11; shellSort(A, n); for(int i = 0; i < n; ++i){ std::cout<<A[i] << " "; } return 0; }

#include <iostream> void Merge(int A[], int l, int mid, int h){ int i, j, k; i = l; j = mid + 1; k = l; int B[h+1]; while(i <= mid && j <= h){ if(A[i] < A[j]){ B[k++] = A[i++]; } else{ B[k++] = A[j++]; } } for(; i <= mid; i++){ B[k++] = A[i]; } for(; j <= h; j++){ B[k++] = A[j]; } for(i = l; i <= h; i++){ A[i] = B[i]; } } // 迭代 void IMergeSort(int A[], int n) { int p, i, l, mid, h; for(p = 2; p <= n; p = p * 2){ for(i = 0; i + p - 1 < n; i = i + p){ l = i; h = i + p -1; mid = (l + h) / 2; Merge(A, l, mid, h); } if(i < n){ l = i; h = n-1; mid = (l+h)/2; Merge(A,l,mid,h); } for(int i = 0; i < n; ++i){ std::cout<<A[i] << " "; } std::cout << "\n"; } if(p/2 < n){ Merge(A, 0, p/2-1, n-1); } } // 递归 void MergeSort(int A[], int l, int h){ int mid; if(l < h){ mid = (l + h) / 2; MergeSort(A, l, mid); MergeSort(A, mid+1, h); Merge(A, l, mid, h); } } int main() { int A[] = {8, 3, 7, 4, 9, 2, 6, 5, 1, 11, 10}; int n = 11; IMergeSort(A, n); for(int i = 0; i < n; ++i){ std::cout<<A[i] << " "; } return 0; } 输出：...

测试代码： #include <iostream> using namespace std; struct A{ long long a = 10; virtual void fa(){ cout << "A::fa()\n"; } virtual void faa(){ cout << "A::faa()\n"; } }; // 如果是虚继承，虚基类被放在了派生类的后面，每个基类都有自己的虚函数表指针存储单元，如果虚基类没有虚函数，则虚基类的虚函数表指针为 0 // 如果是非虚继承，基类在派生类的前面，每个基类都有自己的虚函数表指针存储单元，除了第一个基类（派生类与第一个基类共用一个存储单元） struct E: virtual A{ long long e = 2; virtual void fa(){ cout << "E::fa()\n"; } virtual void fe(){ cout << "E::fe()\n"; } }; int main() { typedef void(*FUNC)(); E e; cout << sizeof(e) << endl; long long* addr = (long long*)&e; long long* vfptre = (long long*)*(addr + 0); int eval = (int)*(addr + 1); cout << eval << endl; long long* vfptra = (long long*)*(addr + 2); int aval = (int)*(addr + 3); cout << aval << endl; cout << "---------------\n"; long long* faptr = (long long*)*(vfptre + 0); (FUNC(faptr))(); long long* feptr = (long long*)*(vfptre + 1); (FUNC(feptr))(); cout << "---------------\n"; long long* faptra = (long long*)*(vfptra + 0); // (FUNC(faptra))(); // 如果虚基类的虚函数被重写，此处则无法再如此执行 long long* faaptra = (long long*)*(vfptra + 1); (FUNC(faaptra))(); return 0; } 输出：...