一.循环赛日程
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cmath>#define MAX 100using namespace std;int a[MAX][MAX];// 拷贝方阵// 从左上角顶点为（from_x, from_y)复制到左上角顶点为（to_x,to_y),行列式都为rvoid Copy(int tox, int toy, int fromx, int fromy, int r){for (int i=0; i<r; i++)for (int j=0; j<r; j++) a[tox+i][toy+j] = a[fromx+i][fromy+j];}// 人数是2^kvoid Table(int k){int i, r;int n = 1 << k;//构造正方形表格的第一行数据for (i=0; i<n; i++)a[0][i] = i + 1;// 分治，从第一行开始向下一行复制// 然后从已经产生的列表向下继续复制（原来又两行，就向下复制两行）for (r=1; r<n; r<<=1)for (i=0; i<n; i+=2*r){Copy(r, r + i, 0, i, r);//①Copy(r, i, 0, r + i, r);//②}}int main() {Table(3);for(int i = 0;i < 8;i++){for(int j = 0;j < 8;j++)cout << a[i][j] << " ";cout<<endl;}}
二.棋盘覆盖
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cmath>#define MAX 1025using namespace std;int board[MAX][MAX];static int tile = 1; // 骨牌编号 // (tr,tc)是棋盘中左上角的方格坐标//（dr,dc)是特殊方格坐标// size是棋盘的行数或列数 void ChessBoard(int tr,int tc,int dr, int dc, int size){if(size == 1) return; // 递归出口，如果边长是1的话，那他就是特殊方格int t = tile++;// 骨牌编号 int s = size/2;// 划分小的棋盘 // 覆盖左上角子棋盘if(dr < tr + s && dc < tc + s)// 特殊方格在这个棋盘中ChessBoard(tr,tc,dr,dc,s);// 去划分更小的棋盘 else{// 没有特殊方格，用一个L骨牌中的一小格覆盖右下角,将这个小格当成特殊方格 // 到时候这些小格会拼成一个完整的L形骨牌board[tr+s-1][tc+s-1] = t;// 覆盖其他方格ChessBoard(tr,tc,tr+s-1,tc+s-1,s); } // 覆盖右上角子棋盘if(dr < tr + s && dc >= tc + s)// 特殊方格在这个棋盘中ChessBoard(tr,tc+s,dr,dc,s);// 去划分更小的棋盘 else{// 没有特殊方格，用一个L骨牌中的一小格覆盖左下角,将这个小格当成特殊方格 // 到时候这些小格会拼成一个完整的L形骨牌board[tr+s-1][tc+s] = t;// 覆盖其他方格ChessBoard(tr,tc+s,tr+s-1,tc+s,s); }// 覆盖左下角子棋盘if(dr >= tr + s && dc < tc + s)// 特殊方格在这个棋盘中ChessBoard(tr+s,tc,dr,dc,s);// 去划分更小的棋盘 else{// 没有特殊方格，用一个L骨牌中的一小格覆盖右上角,将这个小格当成特殊方格 // 到时候这些小格会拼成一个完整的L形骨牌board[tr+s][tc+s-1] = t;// 覆盖其他方格ChessBoard(tr+s,tc,tr+s,tc+s-1,s); } // 覆盖右下角子棋盘if(dr >= tr + s && dc >= tc + s)// 特殊方格在这个棋盘中ChessBoard(tr+s,tc+s,dr,dc,s);// 去划分更小的棋盘 else{// 没有特殊方格，用一个L骨牌中的一小格覆盖左上角,将这个小格当成特殊方格 // 到时候这些小格会拼成一个完整的L形骨牌board[tr+s][tc+s] = t;// 覆盖其他方格ChessBoard(tr+s,tc+s,tr+s,tc+s,s); }}int main() {int k;int dr, dc;cout << "输入边长k，即size = 2^k" << endl; cin >> k;int size = pow(2, k);cout << "特殊方格坐标" << endl; cin >> dr >> dc;ChessBoard(0,0,dr,dc,size);for(int i = 0;i < size;i++){for(int j = 0;j <size;j++)cout << board[i][j] << " ";cout << endl;}}
三.选择问题
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cmath>#define NUM 1001using namespace std;int a[NUM];// 选择第k小的元素int select(int *a, int left, int right, int k){// 找到第k小的元素if(left >= right) return a[left];int i = left;int j = right + 1;// 将左边的元素化为分界点int pivot = a[left];// 把左侧>=pivot的元素和右侧<=pivot的原色交换while(true){// 在左侧寻找>=pivot的元素do {i += 1;} while(a[i] < pivot);// 在右侧寻找<=pivot的元素 do {j -= 1;} while(a[j] > pivot);//cout << i << " " << j << endl;if(i >= j) break;swap(a[i], a[j]);} // 快排中 num_left = j - leftif(j - left + 1 == k) return pivot;a[left] = a[j];// 交换pivot和a[j]，走到这一步，p后面的数据已经排好序了// i和j找的是离p最近的大的数字和小的数字 a[j] = pivot;//cout << "a[left]" << " " << a[left] << endl;//cout << "a[j]" << " " << a[j] << endl;//cout << "pivot" << " " << pivot << endl;//cout << endl;if(j - left + 1 < k)return select(a, j + 1,right, k - j + left - 1); // 往右边找elsereturn select(a, left, j - 1, k); // 往左边找 } int main() {int n , k;cout << "输入数组个数和查找的元素大小的次数" << endl;cin >> n >> k;cout << "输入元素" << endl; for(int i = 0;i < n;i++){cin >> a[i];} cout << select(a, 0, n-1, k); }
四.输油管问题
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cmath>#define NUM 1001using namespace std;int a[NUM];// 选择第k小的元素int select(int left, int right, int k){// 找到第k小的元素if(left >= right) return a[left];int i = left;int j = right + 1;// 将左边的元素化为分界点int pivot = a[left];// 把左侧>=pivot的元素和右侧<=pivot的原色交换while(true){// 在左侧寻找>=pivot的元素do {i += 1;} while(a[i] < pivot);// 在右侧寻找<=pivot的元素 do {j -= 1;} while(a[j] > pivot);//cout << i << " " << j << endl;if(i >= j) break;swap(a[i], a[j]);} // 快排中 num_left = j - leftif(j - left + 1 == k) return pivot;a[left] = a[j];// 交换pivot和a[j]，走到这一步，p后面的数据已经排好序了// i和j找的是离p最近的大的数字和小的数字 a[j] = pivot;//cout << "a[left]" << " " << a[left] << endl;//cout << "a[j]" << " " << a[j] << endl;//cout << "pivot" << " " << pivot << endl;//cout << endl;if(j - left + 1 < k)return select(j + 1,right, k - j + left - 1); // 往右边找elsereturn select(left, j - 1, k); // 往左边找 } int main() {int n; // 油井数量 int x;//x坐标，无用 // a[]是y坐标cin >> n;for(int k = 0;k < n;k++){cin >> x >>a[k];} // 快排找中位数 int y = select(0, n-1, n/2);int min = 0;for(int i = 0;i < n;i++){min += (int)fabs(a[i] - y);} cout << min << endl;}
五.整数因子分解
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cmath>#define NUM 1001using namespace std;int total;void solve(int n){if(n == 1) total++; // 获得一个分解else for(int i = 2;i <= n;i++)if(n % i == 0) solve(n/i);// i是n的一个因数 }int main() {int n;cin >> n;solve(n);cout << total; }
如果觉得《算法笔记 分治：循环赛日程 棋盘覆盖 选择问题 输油管问题 整数因子分解》对你有帮助，请点赞、收藏，并留下你的观点哦！
