算法设计实验6

zyqdfp / 2024-12-19 / 原文

p124 9

有一个8*8的棋盘，行号、列号均为0-7，一个特殊放个的位置是（5,6），给出采用L形骨牌覆盖其他全部方格的一种方案

 1 #include <ostream>
 2 #include <iostream>
 3 #define MAX_SIZE 8
 4 using namespace std;
 5 int k;
 6 int x,y;
 7 int board[MAX_SIZE][MAX_SIZE];
 8 int tile=1;
 9 void chessboard(int tr,int tc,int dr,int dc,int size){
10         if(size==1) return ;
11         int t = tile++;
12         int s=size/2;
13         //考虑左上角象限
14         if(dr<tr+s&&dc<tc+s)
15                 chessboard(tr,tc,dr,dc,s);
16         else{
17                 board[tr+s-1][tc+s-1]=t;
18                 chessboard(tr,tc,tr+s-1,tc+s-1,s);
19         }
20         //考虑右上角象限
21         if(dr<tr+s&&dc>=tc+s)
22                 chessboard(tr,tc+s,dr,dc,s);
23         else{
24                 board[tr+s-1][tc+s]=t;
25                 chessboard(tr,tc+s,tr+s-1,tc+s,s);
26         }
27         //考虑左下角象限
28         if(dr>=tr+s&&dc<tc+s)
29                 chessboard(tr+s,tc,dr,dc,s);
30         else{
31                 board[tr+s][tc+s-1]=t;
32                 chessboard(tr+s,tc,tr+s,tc+s-1,s);
33         }
34         //考虑右下角象限
35         if(dr>=tr+s&&dc>=tc+s)
36                 chessboard(tr+s,tc+s,dr,dc,s);
37         else{
38                 board[tr+s][tc+s]=t;
39                 chessboard(tr+s,tc+s,tr+s,tc+s,s);
40         }
41 }
42 void printBoard() {
43     for (int i = 0; i < MAX_SIZE; ++i) {
44         for (int j = 0; j < MAX_SIZE; ++j) {
45             if (board[i][j] == 0) {
46                 cout << "0  ";
47             } else {
48                 cout << board[i][j] << "  ";
49             }
50         }
51         cout << endl;
52     }
53 }
54 int main(){
55     int k=8;
56     int x=5,y=6;
57     board[x][y]=0;
58     chessboard(0,0,x,y,8);
59     printBoard();
60     return 0;
61 }

11 设计一个分治算法求数组a中元素x出现的次数

 1 #include<bits/stdc++.h> 
 2 using namespace std;
 3 vector<int>a;
 4 int countNum(int x,int l,int r){     
 5     if(l>r){
 6         return 0; 
 7     }
 8     if(l==r){
 9         return a[l]==x ? 1:0; 
10     }
11     int mid = l + (r - l)/2;
12     return countNum(x, l, mid) + countNum(x, mid + 1, r);
13 }
14 int main(){
15     int n;
16     cout << "请输入数组的大小：" <<endl;
17     cin >> n;
18     a.resize(n);
19     cout << "请输入数组：" << endl;
20     for (int i=0;i<n;i++) {  
21         cin >> a[i];  
22     } 
23     int x;
24     cout << "请输入x的值：";
25     cin >> x;
26     cout << "x出现的次数为：" << countNum(x,0,a.size() - 1) ;
27     return 0;
28 }

设有个n = 2^k个选手要进行网球循环赛，要求设计一个满足一下要求的比赛日程表

（1）每个选手必须与其他n-1个选手各赛一次（2）每个选手一天只能赛一次（3）循环赛在n-1天之内结束

 1 #include<iostream>
 2 #include <iomanip>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAX = 1e3+10;
 6 int a[MAX][MAX];
 7 void plan(int k){
 8     int n=2;
 9     a[1][1] = 1; a[1][2] = 2;
10     a[2][1] = 2; a[2][2] = 1;
11     for(int t = 1; t < k; t++){
12         int tmp = n;
13         n = n * 2;
14         for(int i = tmp+1; i <= n; i++){
15             for(int j = 1; j <= tmp;j++)
16                 a[i][j] = a[i-tmp][j] + tmp;            
17         }
18         for(int i = 1; i <= tmp; i++){
19             for(int j = tmp+1; j <= n;j++)
20                 a[i][j] = a[i+tmp][(j+tmp)%n];            
21         }
22         for(int i = tmp+1; i <= n; i++){
23             for(int j = tmp+1; j <= n;j++)
24                 a[i][j] = a[i-tmp][j-tmp];            
25         }
26     }
27 }
28 int main(){
29     int k = 3;
30     plan(k);
31     for(int i = 1; i <= pow(2,k); i++){
32         for(int j = 1; j <= pow(2,k); j++){
33             cout << setw(4) << a[i][j]; 
34         } 
35         cout << endl;
36     }
37     return 0;
38 }