算法分析与设计课程笔记

含itc本人所写代码，不同意复制粘贴等抄袭行为。

归纳法

多数元素

#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
#define ll long long
ll n,a[N];

ll f(int n){
	ll j=n,tem=a[n],cnt=1;
	
	while(j<n&&cnt>0){
		j++;
		if(a[j]==tem)cnt++;
		else cnt--;
	}
	
	if(j==n)return tem;
	else return f(j+1);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	 cout<<f(n);
}

全排列--归纳法

#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
#define ll long long
ll n ;int a[N];

void f(int cur){
	if(n==cur){
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" ";
		}
		cout<<"\n";
		return ;
	}
	else {
		for(int i=cur;i<=n;i++){
			swap(a[cur],a[i]);
			f(cur+1);
			swap(a[i],a[cur]);
		}
	}
}
	 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=i;
	f(1);
	
}

pow(x,n)--分治实现

#include<iostream>
#include<stdio.h>
using namespace std;
#define ll long long
double n,x;

double p (double x,int n){
     if(n==0)return 1;
	 if(n==1)return x;
	 else if(n > 1){
	 	if(n%2 ==0){
	 		double ans=p(x,n/2);
	 		return ans*ans;
		 }
		 else {
		 	double ans=p(x,(n-1)/2);
		 	return ans*ans*x;
		 }
	 }
	 
}
	 
int main(){
	cin>>x>>n;
	printf("%0.4f",p(x,n));
}
/*若n可以为负数，将n*（-1）参与运算，结果输出1/pow(n,x)*/

fib——递归

int fib(int x){
    if(x==1||x==0)return x;
    return fib(x-1)+fib(x-2);
}
    

最多约数问题

正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x) 。例如，1，2， 5，10 都是正整数10 的约数，且div(10)=4 。设a 和b 是2 个正整数，a≤b，找出a 和b 之间约数个数最多的数x。

暴力：

#include<bits/stdc++.h>
using namespace std;

int n=2,m=1,x=0,i,k,a,b;

int main()
{
     
    scanf("%d%d",&a,&b);
    if(a>=b)return 0;
    else{
    	for(i=a;i<=b;i++){
        n=2;
        for(k=2;k<i;k++){
            if(i%k==0) {n++;}
            m=max(n,m);
    	}
    }	
    cout<<m;
	}
	    
}

递归

就是将其用埃氏筛出约数

字典序问题

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1 次。例如，a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序字符串按照字典序排列并编码如下。

1 2

递归 逐渐固定一个长度再计算

暴力，猜结论

统计数字问题

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。

暴力

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int a[10];
int n;
 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		 int t=i;
		while(t){
			int ans=t%10;
			a[ans]++;
			t=t/10;
		}
	}
	for(int i=0;i<10;i++)cout<<a[i]<<endl;
	return 0;
}

分治

寻找数组中的第k小元素

给定一个长度为n的整数数组nums和整数k，输出数组中的第k小元素。要求不能对数组排序，使用分治的思想求解。

分到ab相比较，宝，知道归并排序吗

 快速排序

【问题描述】给定一个长度为n的整数数组nums，要求必须使用【快速排序】的方法将该数组升序排序。

sort。。。

大整数乘法

【问题描述】给定两个大整数，要求使用【分治策略】计算他们的乘积。由于整数可能太大，因此使用字符串进行表示，题目保证没有多余的前导0。

矩阵乘法

【问题描述】要求必须使用【分治策略】计算两个矩阵的乘法。nxm阶的矩阵A乘以mxk阶的矩阵B得到的矩阵C是nxk阶的。

最近点对问题

【问题描述】给定平面中的n个点，要求使用【分治策略】找到其中的一对点，使得在n个点对组成的所有点对中，该点对间的距离最小。

CDQ分治

整数因子分解问题

大于1 的正整数n 可以分解为：n=x1*x2*…*xm。

例如，当n=12 时，共有8 种不同的分解式：

12=12；

12=6*2；

12=4*3；

12=3*4；

12=3*2*2；

12=2*6；

12=2*3*2；

12=2*2*3 。

编程任务：

　　对于给定的正整数n，编程计算n 共有多少种不同的分解式。

分治的思想就是一步一步对其因数分解。然后记录每一个因数可以被分解几个，累加即可

12-》6-》3，2-》1

12-》4-》2》1

int get(int n){
	int ans=0;
	if(n==1)return 1;
	else {
		for(int i=2;i<=n;i++){
			if(n%i==0)ans+=get(n/i);
		}
		return ans;
	}
}

众数问题

思考：

1.首先对数组进行排序，推荐快速排序算法，这里默认是升序数组；

2.根据分治法思想，分解子问题；

3.计算数组的中位数，将数组分为左右两部分；若左边数组的个数大于中位数的个数，则递归左边数组，同理右边相同；

5.left记录数组第一个等于中位数的元素位置（即左边数组个数），right记录第一个（从left开始）

不等于中位数的元素位置（右边数组个数），记录right-left记录众数的重数。

6.经过多次递归，所求的中位数就是众数

void splid(int s[],int length,int &left,int &right)
{
    int mid=length/2;
 
    for(left=0; left<=mid; left++ )
    {
        if(s[left]==s[mid])
        {
            //cout<<"left="<<left<<endl;
            break;
        }
    }
 
    for(right=left+1; right<length; right++)
    {
        if(s[right]!=s[mid])
        {
            //cout<<"right="<<right<<endl;
            break;
        }
    }
}
 
void findMaxCnt(int &mid,int &MaxCnt,int s[],int length)
{
    int left;
    int right;
    splid(s,length,left,right);
 
    int num=length/2;
    int cnt=right-left;//表示重数
    /**利用（第一个）大于中位数的位置和小于中位数的位置之差得到。*/
 
    if(cnt>MaxCnt)
    {
        MaxCnt=cnt;//表示重数
        mid=s[num];
    }
 
    if(left>mid)
    {
        findMaxCnt(mid,MaxCnt,s,left+1);
    }
 
    if(right>mid)
    {
        findMaxCnt(mid,MaxCnt,s,length-right);
    }
 
}

集合划分问题

n个元素的集合{1,2,.,n }可以划分为若干个非空子集。例如，当n=4 时，集合{1,2,3,4}可以划分为15个不同的非空子集如下：
{1}，{2}，{3}，{4}}， {
{1，2}，{3}，{4}}，
{
{1，3}，{2}，{4}}， {
{1，4}，{2}，{3}}，
{
{2，3}，{1}，{4}}， {
{2，4}，{1}，{3}}，
{
{3，4}，{1}，{2}}， {
{1，2}，{3，4}}，
{
{1，3}，{2，4}}， {
{1，4}，{2，3}}，
{
{1，2，3}，{4}}， {
{1，2，4}，{3}}，
{
{1，3，4}，{2}}， {
{2，3，4}，{1}}，
{
{1，2，3，4}}
其中，集合{
{1，2，3，4}} 由1个子集组成；集合{
{1，2}，{3，4}}，{
{1，3}，{2，4}}，{
{1，4}，{2，3}}，{
{1，2，3}，{4}}，{
{1，2，4}，{3}}，{
{1，3，4}，{2}}，{
{2，3，4}，{1}} 由2个子集组成；集合{
{1，2}，{3}，{4}}，{
{1，3}，{2}，{4}}，{
{1，4}.{2}，{3}}，{
{2，3}，{1}，{4}}，{
{2，4}，{1}，{3}}，{
{3，4}，{1}，{2}} 由3 个子集组成；集合{
{1}，{2}，{3}，{4}} 由4个子集组成。
编程任务：
给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个
非空子集组成的集合。

设n个元素的集合可以划分为F(n,m)个不同的由m个非空子集组成的集合。

F(1,1)=1；

F(2,1)=1,F(2，2)=1;

当有三个元素时：

1. 一个子集的情况：{
   {1,2,3}}，F(3,1)=1;
2. 两个子集的情况:{
   {1,2},{3}},{
   {1,3},{2}},{
   {2,3},{1}},F(3,2)=F(2,1)+2*F(2,2)=3;
3. 三个子集的情况：{
   {1}，{2}，{3}}，F(3,3)=1。

当有四个元素时（即将元素4插入到三个元素分类的情况中）：

1. 一个子集的情况：{
   {1,2,3,4}},F(4,1)=1;
2. 两个子集的情况：{
   {1,2,3}，{4}}，{
   {1,2,4}，{3}}，{
   {1,2}，{3,4}}，{
   {1,3,4}，{2}}，{
   {1,3}，{2,4}}，{
   {2,3,4}，{1}}，{
   {2,3}，{1,4}}，F(4,2)=F(3,1)+2*F(3,2)=7;
3. 三个子集的情况：{
   {1,2}，{3}，{4}}，{
   {1,3}，{2}，{4}}，{
   {2,3}，{1}，{4}}，{
   {1,4}，{2}，{3}}，{
   {1}，{2,4}，{3}}，{
   {1}，{2}，{3,4}}，F(4,3)=F(3,2)+3*F(3,3)=6;
4. 四个子集的情况：{
   {1},{2},{3},{4}},F(4,4)=1。

可得到递推公式F(n,m)=F(n-1,m-1)+m*F(n-1,m)，当m=1或n=m时F(n,m)=1。

邮局选址问题

选中位数就好了

数学预备知识

数学归纳法

• 对于1，n+1成立推出对n成立

底函数：小于等于x的最大整数

顶函数：大于等于x的最小整数

Cnk=n!/k!*(N-K)!

鸽巢原理

• K+1个东西放入K个盒子，至少有一个是有两个东西的
• n个球，m个盒子，必定有一个盒子至少中有大于等于n/m个球，最多装少于等于n/m个球

和式

• j：n^2
• j^2:n^3
• j^i:j^n

递推关系

线性齐次递推可解

 非齐次递推关系的解

分治 递推求解

堆 

什么是堆——几乎完全的二叉树

表示：数组h【i】的左子是h【2*i】，右子h【2*i+1】，父节点在h【i/2】向下

key(h[j/2]x)>=key(h[i])

运算

delete_max

def heap_extract_max(S):
	max = heap_maximum(S)
	A[0] = A[len(A) - 1]
	max_heap(A)
	return max
/*heap_extract_max(S)的时间复杂度为
O ( lg ⁡ n ) O(\lg n)O(lgn)。
因为除了时间复杂度为O ( lg ⁡ n ) O(\lg n)O(lgn)的max_heap(A)以外，
它的其他操作都是常数阶的。*/

insert

void heap_increase_key(S, i, k){
	if k < A[i]:
		print('New key is smaller than current key.')
		return k
	A[i] = k
	while i > 0 and A[parent(i)] < A[i]:
		A[i], A[parent(i)] = A[parent(i)], A[i]
		i = parent(i)
}
/*在包含n nn个元素的堆上，
heap_increase_key(S, i, k)的时间复杂度是
O ( lg ⁡ n ) O(\lg n)O(lgn)。*/
void heap_insert(S, x){
	A[len(A)] = A[len(A) - 1] - 1
	heap_increase_key(S, len(A), x);
}

delete

void delete(int x){

    int t=h[x];
    n=n-1;
    if(x==n+1)return ;
    h[x]=y;
    if(h[x]>t)siftup(H，i);
    else sift-down(H,i);
}

makeheap

void makeheap(*arr, i):{

    largest = i  ;
    l = 2 * i + 1;     # left = 2*i + 1 
    r = 2 * i + 2 ;    # right = 2*i + 2 
  
    if (l < len(arr) && arr[i] < arr[l]) 
        largest = l ;
  
    if r < len(arr) &&arr[largest] < arr[r]: 
        largest = r ;
  
    if (largest != i){ 
        arr[i],arr[largest] = arr[largest],arr[i];  # 交换
        heapify(arr, largest);
    }
}
void  max_heap(*A){
	for (int i= (len(A)/2) + 1;i>0;i--)
		heapify(A, i)
}/*包含n nn个元素的堆的高度为⌊ lg ⁡ n ⌋ \lfloor \lg n\rfloor⌊lgn⌋。所以我们可以得到max_heap(A)的时间复杂度为O ( n ) O(n)O(n)。*/

sift-up

int heap[size],n;
void up(int p){ //插入到末尾，再向上调整
    while(p>1){
        if(heap[p]<heap[p/2]){
            swap(heap[p],heap[p/2]);
            p=p/2;
        }
        else
            break;
    }
}

sift-down

void up(int u)
{
    while (u / 2 && w[u / 2] > w[u])
    {
        swap(w[u], w[u / 2]);
        u /= 2;
    }
}
void down(int u)
{
    int t = u;
    if (u * 2 <= n && w[u * 2] >= w[u]) t = u * 2;
    if (u * 2 + 1 <= n && w[u * 2 + 1] >= w[u]) t = u * 2 + 1;
    if (t != u) swap(w[u], w[t]), down(t);
}

for (int i = n / 2; i; i -- ) down(i);//向下建堆

sort

def heap_sort(arr): 
    n = len(arr) 
  
    # Build a maxheap. 
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
  
    # 一个个交换元素
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   # 交换
        heapify(arr, i, 0)

并查集

void Init()
{
    for(int i = 1;i <= n;i++)
        parent[i] = i;
    return;
}

int get (int v)
{
    if(parent[v] == v)
        return v;
    else
    {
        //路径压缩(使搜索祖宗的过程中，路径中搜索的结点的父亲的变为祖宗)
      return parent[v]= get (parent[v]);
    }
}

void union(int v,int u)
{
    return get(v)=get(t);
}

按秩合并

包括根节点的树节点个数至少是2^rank(x)。

f[u]+=1;

f[v]=f[u];

对于任意整数r>=0，秩的节点树最多是n/2^r

秩最大是 xia logn

单源最短路径

int Dijkstra(){
    memset(d,0x3f,sizeof(d));
    d[1]=0;
  
    for(int i=0;i<n;i++){
        int t=-1;
        //找到当前未在（已找到最短距离的）集合中的距离1号点最近的点，肯定是需要遍历所有点才能找到的
        //所以这里会有一个for循环
        for(int j=1;j<=n;j++){
            if(!s[j]&&(t==-1||d[j]<d[t])){
                t=j;
            }
        }
      
        s[t]=true;
        
        //用刚刚找到的点更新其余点到1号点的距离
        for(int j=1;j<=n;j++){
            d[j]=min(d[j],d[t]+map[t][j]);
        }
    }
    
    if(d[n]==0x3f3f3f3f){
        return -1;
    }
    
    return d[n];
}

最小生成树

struct Edge {
	int v1, v2, w;
	bool operator < (const Edge &W) const {//重载 < 号 结构体比较按照的是边权重的大小 
	  return w < W.w;
	}
}edges[M];
int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);//路径压缩 
	return p[x]; 
}
int kruskal() {
	sort(edges, edges + m);//将所有边按照权重大小进行排序。 
	for (int i = 1; i <= n; i ++ ) p[i] = i;//初始化并查集 
	int res  = 0, cnt = 0;
	for (int i = 0; i < m; i ++ ) {
		int v1 = edges[i].v1, v2 = edges[i].v2, w = edges[i].w;
		v1 = find(v1), v2 = find(v2);
		if (v1 != v2) {
			p[v1] = v2;
			res += w;
			cnt ++ ;
		} 
	} 
	if (cnt < n - 1) return INF;
	return res;
}
void init() {
	cin >> n >> m;
	for (int i = 0; i < m; i ++ ) {
		int v1, v2, w;
		cin >> v1 >> v2 >> w;
		edges[i] = {v1, v2, w}; 
	}
	int t = kruskal();
}

Prim

int prim() {
	memset(dist, 0x3f, sizeof(dist));
	int res = 0;
	for (int i = 0; i < n; i ++ ) {
		int t = -1;
		for (int j = 1; j <= n; j ++ ) {
			if (!st[j] && (t == -1 || dist[t] > dist[j])) 
			  t = j;
		}
		if (i && dist[t] == INF) return INF;//当前找到的最短距离为INF说明图不连通无最小生成树 
		if (i) res += dist[t];//计算最小生成树的权重和 
		st[t] = true;//将t点加入最小生成树点集中 
		for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);//更新 因为dist表示是距离点集的距离所以只需更新点集外的边权最小的那条边即可 
	}
	return res; 
}