算法作业一

发表于 | 分类于

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;
const int maxn=1e5+10;
int tmp[maxn];
int a[maxn];
void merge( int start, int mid, int end){
    int i = start;    
    int j = mid + 1;  
    int k = 0;     
    while(i <= mid && j <= end){
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
    while(i <= mid)
        tmp[k++] = a[i++];
    while(j <= end)
        tmp[k++] = a[j++];
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];
}
void mergeSort( int start, int end){
    if(start >= end)
        return ;
    int mid = (end + start)/2;
    mergeSort( start, mid);
    mergeSort( mid+1, end); 
    merge(start, mid, end);
}
int main(){
    int n;
	cin>>n;
	for (int i=1; i<=n; i++)
        cin>>a[i];
    mergeSort(1, n); 
    for (int i=1; i<=n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

棋盘覆盖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int m[maxn][maxn];
int n=0;
void chessboard(int x,int y,int tx,int ty,int s){
	if(s==1) return;
	s>>=1;
	int t=++n;
	if(tx<=x+s-1&&ty<=y+s-1) chessboard(x,y,tx,ty,s);
	else m[x+s-1][y+s-1]=t,chessboard(x,y,x+s-1,y+s-1,s);
	if(tx<=x+s-1&&ty>=y+s)  chessboard(x,y+s,tx,ty,s);
	else m[x+s-1][y+s]=t,chessboard(x,y+s,x+s-1,y+s,s);
	if(tx>=x+s&&ty<=y+s-1) chessboard(x+s,y,tx,ty,s);
	else m[x+s][y+s-1]=t,chessboard(x+s,y,x+s,y+s-1,s);
	if(tx>=x+s&&ty>=y+s) chessboard(x+s,y+s,tx,ty,s);
	else m[x+s][y+s]=t,chessboard(x+s,y+s,x+s,y+s,s);
}
int main(){
	while(true){
		int size;
		cin>>size;
		int x,y;
		cin>>x>>y;
		chessboard(1,1,x,y,size);
		for(int i=1;i<=size;i++){
			for(int j=1;j<=size;j++){
				printf("%3d ",m[i][j]);
			}
		    printf("\n");
		}
	}
}

循环日程表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int n,half=1,k=1;
int pic[100][100];
int main(){
    cin>>n;
    pic[0][0]=1;
    int m=1<<n; 
    while(k<=n){
        for(int i=0;i<half;i++){
            for(int j=0;j<half;j++){
                pic[i][j+half]=pic[i][j]+half;
            }
        }
        for(int i=0;i<half;i++){
            for(int j=0;j<half;j++){
                pic[i+half][j]=pic[i][j+half]; 
                pic[i+half][j+half]=pic[i][j]; 
            }
        }
        half*=2;
        k++;
    }
    for(int i=0;i<m;i++) {
        for(int j=0;j<m;j++){
            printf("%3d",pic[i][j]);
        }
        cout<<endl;
    }
    return 0;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
void quicksort(int left,int right){
    if(left>right) return ;
    int temp=a[left];
    int i=left;
    int j=right;
    while(i!=j){
        while(a[j]>=temp&&i<j) j--;
        while(a[i]<=temp&&i<j) i++;
        if(i<j){
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];
    a[i]=temp;
    quicksort(left,i-1);
    quicksort(i+1,right);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    quicksort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    puts("");
    return 0;
}