算法课程期末总结

教的不多，学的也不多，这东西真想学还是得自学，不过一个学期学了这么点，确实好像也太少了点。

声明

本文档的一切内容均为本地测试结果，受限于本人知识与能力，仅供参考，如因参照本文档操作而发生任何问题，无论是否严格参照本文档操作，请恕本人概不负责。

文档中的任何观点受限于本人知识、能力及眼界，不保证理智，公正，客观。如本文档中观点与您相左，以您的意见为准。

求最大公约数/最小公倍数

开课祭天问题，目测铁定不会考，写着玩，递归实现辗转相除法。

#include<stdio.h>

int solve(int a, int b){
    return a % b == 0 ? b : solve(b, a%b);
}

int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    //最大公约数
    printf("%d\n", solve(a, b));
    //最小公倍数
    printf("%d\n", a * b / solve(a, b));

    return 0;
}

串匹配算法KMP

我只能用优美来形容我第一次见到它时的感受，不过，，目测不会考，后面有时间的话，我来更新一下解释这段KMP代码，先占个坑在这吧。

#include<stdio.h>
#include<string.h>

void kmp_pre(char x[], int m, int next[]){
    int i, j;
    j = next[0] = -1;
    i = 0;
    while(i<m){
        while(-1 != j && x[i] != x[j]) j = next[j];
        next[++i] = ++j;
    }
}

int next[10010];
int kmp_count(char x[], int m, char y[], int n){
    int i, j;
    int ans = 0;
    kmp_pre(x, m, next);
    i = j = 0;
    while(i<n){
        while(-1 != j && y[i] != x[j]) j = next[j];
        i++; j++;
        if(j>=m){
            ans++;
            j = next[j];
        }
    }
    return ans;
}

int main(){
    char x[10010],y[10010];
    scanf("%s%s", x, y);
    printf("%d\n",kmp_count(x, strlen(x), y, strlen(y)));    

    return 0;
}

用分治法解决棋盘覆盖问题

目测会考，毕竟简单，适合手撸。

#include<stdio.h>

int matrix[100][100]={0};
int t=0;

void chessboard(int tr,int tc,int dr,int dc,int size);

int main(){
    int size;
    int dr,dc;
    int i,j;
    scanf("%d",&size);
    scanf("%d %d",&dr,&dc);
    chessboard(0,0,dr,dc,size);
    for(i=0;i<size;i++){
        for(j=0;j<size;j++){
            printf("%2d ",matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

void chessboard(int tr,int tc,int dr,int dc,int size){
    if(size==1)return;
    int s=size/2;
    int cnt;
    cnt=t+1;
    t++;  
    //特殊方格在左上部分 
    if(dr<tr+s&&dc<tc+s){
        chessboard(tr,tc,dr,dc,s);
    }
    else {
        matrix[tr+s-1][tc+s-1]=cnt;
        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 {
        matrix[tr+s-1][tc+s]=cnt;
        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 {
        matrix[tr+s][tc+s-1]=cnt;
        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 {
        matrix[tr+s][tc+s]=cnt;
        chessboard(tr+s,tc+s,tr+s,tc+s,s);
    } 
}

减治法解决假币问题

这个我觉得也会考，毕竟难度和前面差不多，很有可能时这两个的其中之一考一题。

#include <stdio.h>
#define N  8	                  //假设求解8枚硬币问题
int a[N] = {2, 2,  1, 2, 2, 2, 2, 2}; 
int Coin(int low, int high, int n);

int main()
{
	int i;
	i=Coin(0,N-1,N);
	printf("假币是第%d个",i);
	return 0;
}//真币的重量是2，假币的重量是1

int Coin(int low, int high, int n)           //在a[low]~a[high]中查找假币
{
	int i, num1, num2, num3;      // num1、num2和num3存储3组硬币的个数
	int add1 = 0, add2 = 0;        //add1和add2存储前两组硬币的重量和

	if (n == 1)                              //递归结束的条件
		return low + 1;                         //返回的是序号，即下标加1
	if (n % 3 == 0)                           //3组硬币的个数相同
		num1 = num2 = n / 3;
	else                                    //前两组有 枚硬币
		num1 = num2 = n / 3 + 1;
	num3 = n - num1 - num2;


	for (i = 0; i < num1; i++)                    //计算第1组硬币的重量和
		add1 = add1 + a[low + i];
	for (i = num1; i < num1 + num2; i++)          //计算第2组硬币的重量和
		add2 = add2 + a[low + i];

	if (add1 < add2)             //在第1组查找，下标范围是low~low+num1-1
		return Coin(low, low + num1 - 1, num1);
	else if (add1 > add2)  		//在第2组查找，下标范围low+num1~low+num1+num2-1
		 return Coin(low + num1, low + num1 + num2 - 1, num2);
	else						//在第3组查找，下标范围low+num1+num2~high
		Coin(low + num1 + num2, high, num3);
}

动态规划解决0-1背包问题

#include <iostream> 
using namespace std;
#define C 10
int V[6][11];
int x[5];
int KnapSack(int n, int w[ ], int v[ ]);
int max(int x,int y);

int main()
{
	int w[]={2,2,6,5,4};
	int v[]={6,3,5,4,6};
	cout<<"背包获得的最大价值是："<<KnapSack(5,w,v)<<endl;
	cout<<"装入背包的物品是：";
	for(int i=0;i<5;i++)
		if (x[i] == 1) cout<<"物品"<<i+1<<"  ";
	cout<<endl;
	return 0;
}
int max(int x,int y)
{
	if (x > y) return x;
	else return y;
}
int KnapSack(int n, int w[ ], int v[ ])
{
	int i, j;
	for (i = 0; i <= n; i++)                    //初始化第0列
		V[i][0] = 0;
	for (j = 1; j <= C; j++)                    //初始化第0行
		V[0][j] = 0;
	for (i = 1; i <= n; i++)                    //计算第i行，进行第i次迭代
	{
		for (j = 1; j <= C; j++)
		{
			if (j < w[i-1]) V[i][j] = V[i-1][j];
			else V[i][j] = max(V[i-1][j], V[i-1][j-w[i-1]]+v[i-1]);
		}
	}
	for (j = C, i = n; i > 0; i--)                 //求装入背包的物品
	{
		if (V[i][j] > V[i-1][j]) {
			x[i-1] = 1; j = j - w[i-1];
		}
		else x[i-1] = 0;
	}


   return V[n][C];                //返回背包取得的最大价值
}

八皇后问题

#include <iostream>   
using namespace std;                             //使用库函数printf、scanf
#include <math.h>                                    //使用绝对值函数abs
const int N = 100;                                //假定最多求100皇后问题
int x[N] = {0};               //由于数组下标从0开始，将数组x[N]初始化为-1
void Queue(int n);                                              //函数声明
int Place(int k);                                                //函数声明

                                                   //空行，以下是主函数
int main( )
{
	int n;
	cout<<"请输入皇后的个数:";                    //输出提示信息
	cin>>n;                                      //输入皇后的个数
	Queue(n);                                  //函数调用，求解n皇后问题
	return 0;                         //将0返回操作系统，表明程序正常结束
}
                                            //空行，以下是其他函数定义
void Queue(int n)                              //函数定义，求解n皇后问题
{
	int k = 0;                                   //num存储解的个数
	while (k >= 0)                               //摆放皇后k，注意0≤k＜n
	{
		//x[k]++;                                       //在下一列摆放皇后k
		while (x[k] < n && Place(k) == 1)                           //发生冲突
		x[k]++;                                       //皇后k试探下一列
		if (x[k] < n && k == n - 1 )                         //得到一个解，输出
		{
			for (int i = 0; i < n; i++)
				cout<<x[i]+1<<"  ";         //数组下标从0开始，打印的列号从1开始
			cout<<endl;
			return;                         //只求出一个解即可
		}
		else if (x[k] < n && k < n - 1)                         //尚有皇后未摆放
				k = k + 1;                               //准备摆放下一个皇后
			else
				x[k--] = 0;                  //重置x[k]，回溯，重新摆放皇后k
        for(int i=0; i<n; i++){
            printf("%d ", x[i]);
        }printf("\n");
	}
	cout<<"无解"<<endl;
}
int Place(int k)                    //考察皇后k放置在x[k]列是否发生冲突
{
	for (int i = 0; i < k; i++)   
		if (x[i] == x[k] || abs(i - k) == abs( x[i] - x[k]))             //违反约束条件
			return 1;                                          //冲突，返回1
	return 0;                                            //不冲突，返回0
}

素数环问题

#include <iostream>
using namespace std;
#include <math.h>
const int n = 20;
int a[n];
void PrimeCircle(int n);
int Check(int k);
int Prime(int x);

int main( )
{
	int n;
	cout<<"请输入一个整数；";
	cin>>n;
	PrimeCircle(n);
	return 0;
}

void PrimeCircle(int n)
{ 
	int i, k;
	for (i = 0; i < n; i++ )               //将数组a[n]初始化为0
		a[i] = 0;
	a[0] = 1; k = 1;           //指定第1个位置填写1，注意数组下标从0开始
	while (k >=1)
	{
		a[k] = a[k]+1;
		while (a[k] <= n)
			if (Check(k) == 1) break;         //位置k可以填写整数a[k]
			else a[k] = a[k] + 1;              //试探下一个数

		for (i = 0; i < n; i++) 
			cout<<a[i]<<"  ";
		cout<<endl;

		if (a[k] <= n && k == n - 1) {        //求解完毕，输出解
			return; 
		}

			
		if (a[k] <= n && k < n - 1) 
			k = k + 1;               //处理下一个位置
		else {
			a[k] = 0; k = k - 1;        //回溯
		}
	}
}
int Check(int k)                    //判断位置k的填写是否满足约束条件
{
	int flag = 0;
	for (int i = 0; i < k; i++)           //判断是否重复
		if (a[i] == a[k]) return 0;
    flag = Prime(a[k] + a[k - 1]);
    if (flag == 1 && k == n - 1) flag = Prime(a[k] + a[0]);
	return flag;
}
int Prime(int x)                   //判断是否素数
{
	int i, n;
	n = (int)sqrt(x);
	for (i = 2; i <= n; i++)
		if (x % i == 0) return 0;
	return 1;
}