算法设计与分析---期末复习资料汇总--复习思路_C

算法设计与分析阶段整理

复习题汇总---不是nefu的但类型大差不差
- 概念题
- 综合题，算法补充题
- 第一章
- - 概念
  - 算法复杂性分析。
- 书上的一些简单算法题的实现-还有一些课后的我能做出来的
- - 全排列问题
  - 循环赛日程表
- 应用题
- - 贪心策略最优性证明
- 期末的时候额外训练的算法题
我的算法代码分析与总结

复习题汇总—不是nefu的但类型大差不差

可以关注这个博主

概念题

注意要把PPT上所有出现的概念性特征背下来
还要把各个算法的特征，运行结果特征理清楚，不是全靠你写代码的，算法过程理清这选择填空不是送分？
朋友们这是拿钱买的确定不给个关注！！！

我们应该也会有这种简答题，各位可以总结一下需要记的玩意

综合题，算法补充题

第一章概念

算法特性：有穷性，确定性，可行性，输入，输出
程序设计=数据结构加算法
算法是解决问题的一种方法或一个过程，由若干条指令组成的有穷序列
区别程序与算法

算法复杂性分析。书上的一些简单算法题的实现-还有一些课后的我能做出来的全排列问题

#include 
using namespace std;
void perm(int list[], int k, int m) {//k代表k之前的已经定了，m为数组总元素，递归思路每次确定一位
	if (k == m)//说明只剩一个元素没排了，直接输出这个元素,也说明此次确定了所有的元素
	{
		for (int i = 1; i <= m; i++)
		{
			cout << list[i];
		}
		cout << endl;
		return;
	}
	else//进入下一层递归
	{
		for (int i = k; i <= m; i++)//选择此次有序的数字是哪一个
		{
			swap(list[k], list[i]);//待选的元素为k以及其之后的元素在这一次给它定下来,怎么跟回溯法一样，做出选择，撤销选择
			perm(list, k + 1, m);//注意在非定义函数那一行，我们直接写函数名，无需加上函数类型
			swap(list[k], list[i]);
		}
	}

}
void swap(int a, int b)
{
	int temp = a;
	a = b;
	b = temp;
}
int main()
{
	int list[10];
	int m;
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> list[i];
	}
	perm(list, 1, m);//从第一个数字开始递归
}

循环赛日程表

说实话这道题确实用到了分治思想，不过代码部分的处理，就是从第一行开始向下将子问题扩展，说实话真抠二维数组的哪两个地方赋值，分多少次赋值挺无聊的

//2d11 分治法，循环赛事日程表
#include "stdafx.h"
#include     
#include 
using namespace std; 
 
void Table(int k,int n,int **a);
void input(int &k);
void output(int **a,int n);
 
int main()
{
	int k;
	input(k);//就是求n个学生整体分log2对上n次处理交换 *** 作
 
	int n=1;
	//n=2k(k>=1)个选手参加比赛
	for(int i=1; i<=k; i++)
		n *= 2;
 
	//根据n动态分配二维数组a
	int **a = new int *[n+1];
	for(int i=0;i<=n;i++)
	{
		a[i] = new int[n+1];
	}
 
 
	Table(k,n,a);
 
	cout<<"循环赛事日程表为："<<endl;
	output(a,n);
 
	//释放空间
	for(int i=0;i<=n;i++)
	{
		delete[] a[i];
	}
	delete[] a;
 
	return 0;
}
 
void input(int &k)
{
	cout<<"请输入k值："<<endl;
	cin>>k;
}
 
void output(int **a,int n)
{
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
}
 
void Table(int k,int n,int **a)
{
	for(int i=1; i<=n; i++)
		a[1][i]=i;//设置日程表第一行
 
	int m = 1;//每次填充时，起始填充位置
	for(int s=1; s<=k; s++)
	{
		n /= 2;
		for(int t=1; t<=n; t++)
		{
			for(int i=m+1; i<=2*m; i++)//控制行
			{
				for(int j=m+1; j<=2*m; j++)//控制列
				{
					a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m];//右下角等于左上角的值
					a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2];//左下角等于右上角的值
				}
				
			}
		}
		m *= 2;
	}
}