[NEFU算法设计与分析] 代码汇总

PPT 看代码太难受了，重新格式化和整理，5月22日前完成更新

• 只包含 PPT 完整给出的算法 & 实验做的算法，没给的就没整理了
• 对标软工的要求（应该比计科和大数据简单）
• 主要进行了格式优化增加注释，非片段可运行

#include
using namespace std;
int fac(int n)
{
    if (n == 0)
        return 1;
    else
        return n * fac(n - 1);
}

int main() {
	cout << fac(10);
	return 0;
}

#include 
using namespace std;


typedef struct node {
	char data;
	struct node *lchild, *rchild;
} BinNode, *BinTree;

int LeafCount(const BinTree &T) {
	if (!T) {
		return 0;
	} else if (T->lchild == NULL && T->rchild == NULL) {
		return 1;
	} else {
		return LeafCount(T->lchild) + LeafCount(T->rchild);
	}
}


void CreateBinTree(BinTree &T){
    char ch;cin>>ch;
    if(ch=='@')T=NULL;
    else{
        T=new BinNode;
        T->data=ch;
        CreateBinTree(T->lchild);
        CreateBinTree(T->rchild);
    }
}




int main() {
	BinTree T = new BinNode;
	CreateBinTree(T);	
	cout << LeafCount(T);
	return 0;
}

在这里插入代码片

#include 
using namespace std;

void Perm(int list[], int k, int m)
{
    if (k == m) {
        for (int i = 0; i <= m; i++)
            cout << list[i];
        cout << endl;
    } else
        for (int i = k; i <= m; i++) {
            swap(list[k], list[i]);
            Perm(list, k + 1, m);
            swap(list[k], list[i]);
        }
}


int main() {
	int list[4] = {1,2,3,4};
	Perm(list,0,3);
	return 0;	
}

#include 
using namespace std;

const int N = 3005;
int board[N][N];

int tile;

void chessBoard(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) {
        return;
	}

    int t = tile++; 									// L型骨牌号
    int s = size / 2; 									// 分割棋盘
    
    if (dr < tr + s && dc < tc + s) {					// 覆盖左上角子棋盘
        chessBoard(tr, tc, dr, dc, s); 		        	// 特殊方格在此棋盘中
	} else { 											// 此棋盘中无特殊方格
        board[tr + s - 1][tc + s - 1] = t;  			// 用 t 号L型骨牌覆盖右下角
        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 { 											// 此棋盘中无特殊方格
        board[tr + s - 1][tc + s] = t;					// 用 t 号L型骨牌覆盖左下角
        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 { 											// 用 t 号L型骨牌覆盖左下角
        board[tr + s][tc + s - 1] = t;					// 用 t 号L型骨牌覆盖右上角
        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 { 
        board[tr + s][tc + s] = t;						// 用 t 号L型骨牌覆盖左上角
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);  // 覆盖其余方格
    }
}

int k,dr,dc,size;

int main() {
	while(cin >> k) {		//k表示阶数
		size = (1<> dr >> dc;
		
		chessBoard(1,1,dr,dc,size);

		for(int i = 1; i <= size; ++i) {
			for(int j = 1; j <=  size; ++j) {
				cout< 
合并排序 
#include 
using namespace std;
typedef int Type;

Type b[105];//临时存储合并结果

void Merge(Type a[], Type b[], int left, int mid, int right) {	//合并两个有序数组
	int p = left, q = mid+1;
	int pos = 0;
	while(p <= mid && q <= right) {
		if(a[p] < a[q]) {
			b[pos++] = a[p++];
		} else {
			b[pos++] = a[q++];
		}
	}

	while(p <= mid) b[pos++] = a[p++];
	while(q <= right) b[pos++] = a[q++];
}

void copy(Type a[], Type b[],int left,int right) {
	for(int i = left; i <= right; ++i) {
		a[i] = b[i-left];
	}
}

void MergeSort(Type a[], int left, int right) {
    if (left < right) { //至少有2个元素
        int i = (left + right) / 2; //取中点
        MergeSort(a, left, i);
        MergeSort(a, i + 1, right);
        Merge(a, b, left, i, right); //合并到数组b
        copy(a, b, left, right); //复制回数组a
    }
}

int main() {
	Type a[] = {13,1,3,7,10,2};
	MergeSort(a,0,5);
	for(int i = 0; i < 6; ++i) {
		cout << a[i] << " ";
	}
	return 0;
}
 
快速排序 
在这里插入代码片
 
循环赛日程表 
在这里插入代码片
 
动态规划算法 
矩阵连乘问题 
最大子段和 
最长公共子序列 
凸多边形最优三角剖分 
背包问题 
贪心算法 
活动安排问题 
最优装载问题 
哈夫曼编码 
回溯法 
01背包问题 
图的着色问题 
旅行商问题 
分支界限 
装载问题 
布线问题 
01背包问题 
最大团问题 
旅行售货员问题