算法设计复习(一、二、递推、递归)

第一章 算法概述

什么是算法：是对特定问题求解步骤的一种描述，是指令的有限序列。
算法的五个重要特性：输入、输出、有穷性、确定性、可行性
一个算法的优劣可以用时间复杂性和空间复杂性来衡量
算法和程序的关系
1.程序是使用某种程序设计语言对算法的具体实现，是对算法的精确描述，可在计算机上运行；
2.程序可以是无穷的，而算法必须是有穷的；
3.程序设计的核心是算法。
常用的描述算法的方法:自然语言、流程图、程序设计语言、伪代码等
排序算法:在这里插入图片描述
直接插入排序:

第二章 STL简介

掌握有关vector的内容
vector（向量）从后面快速插入与删除,直接访问任何元素

vector和数组的区别
1.array 定义的时候必须定义数组的元素个数；而vector 不需要
2.array 定义后的空间是固定的了，不能改变；而vector 要灵活得多，可再加或减
3.vector有一系列的函数操作，非常方便使用
4.数组和vector不同，一个数组不能用另一个数组初始化，也不能将一个数组赋值给另一个数组；

知道set具有典型的特点： 内部的元素依据其值自动排序；set内的相同数值的元素只能出现一次

#include <bits/stdc++.h>

using namespace std;
int n;
map<string,int>mp;

int main()
{
    while(cin>>n)
    {
        string tmp;
        int g=0;
        for(int i=1;i<=n;i++)
        {
            string k;
            cin>>k;
            mp[k]++;
            if(mp[k]>g)
                tmp=k,g=mp[k];
        }
        cout<<"answer:"<<tmp<<endl;
    }
    return 0;
}

了解有关“优先队列”的内容，关键是会使用优先队列去解决问题（默认情况下是使用大顶堆，是从大到小排列）

#include <bits/stdc++.h>

using namespace std;
struct cmp
{
    bool operator()(int x,int y)
    {
        return x<y;
    }
};
//priority_queue<int,vector<int>,greater<int>>q;
priority_queue<int,vector<int>,cmp>q;

int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        q.push(x);
    }
    while(!q.empty())
    {
        cout<<q.top()<<endl;q.pop();
    }
    return 0;
}

STL其它内容不做要求

递推方法解决：
菲波那契数列:f[i]=f[i-2]+f[i-1]
汉诺塔移动次数:f(n)=2*f(n-1)+1
猴子吃桃:f[i]=2*f[i+1]+2
骨牌铺满方格

f(n)=f(n-1)+f(n-2)   （n>2）
f(1)=1 
f(2)=2

蜜蜂路线:f[i]=f[i-1]+f[i-2]
吃糖果:f[i] = f[i - 1] + f[i - 2]

昆虫繁殖:

b[i] = f[ i - x] * y; （成虫经过x月产卵 y个）
f[i] = f[ i - 1] + b[ i - 2]; （卵经过2个月长成成虫）

第3章 递归与分治策略

分治是一种算法思想，递归是实现这种思想的一种手段

n!

int fun(int n)
{
   if(n==1)
       return 1;
   return n*fun(n-1);
}

菲波那契数列

#include <bits/stdc++.h>

using namespace std;
int n;
int fibo(int x)
{
    if(x==1||x==2)
        return 1;
    return fibo(x-1)+fibo(x-2);
}
int main()
{
    while(cin>>n)
    {
        cout<<"fibo["<<n<<"]="<<fibo(n)<<endl;
    }
    return 0;
}

猴子摘桃问题

#include <bits/stdc++.h>

using namespace std;
int n;
int fun(int x)
{
    if(x==10)
        return 1;
    return 2*fun(x+1)+2;
}
int main()
{
    cout<<"请输入想知道的第几天的桃子数目: ";
    while(cin>>n)
    {
        cout<<"answer: "<<fun(n)<<endl;
    }
    return 0;
}

十进制转换为二进制

string s;
void fun(int n)
{
    if(n==0)
        return;
    fun(n/2);
    s+=n%2+'0';
}
int main()
{
    cin>>n;
    fun(n);
    cout<<s<<endl;
    return 0;
}

逆序（或正序）输出一个正数中的每一位数

void fun(int n)
{
    if(n==0)
        return;
    s+=n%10+'0'; //逆序
    fun(n/10);
    //s+=n%10+'0'; //正序
}

集合的全排列

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,a[N],k=0;
void perm(int x)
{
    if(x==n+1)
    {
        k++;
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=x;i<=n;i++)
    {
        swap(a[x],a[i]);
        perm(x+1);
        swap(a[x],a[i]);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i;
    perm(1);
    cout<<k<<endl;
    return 0;
}

递归求平方和函数（openjudge题目）

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,a[N],k=0,ans;
int fun(int n)
{
   if(n==1)
       return 1;
   return n*n+fun(n-1);
}
int main()
{
    cin>>n;
    cout<<fun(n)<<endl;
    return 0;
}

棋盘覆盖

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int tp,board[N][N];
void CB(int tr,int tc,int dr,int dc,int sz)
{
    if(sz==1) return;
    int t=++tp,s=sz/2;
    //处理左上角
    if(dr<tr+s&&dc<tc+s)
        CB(tr,tc,dr,dc,s);
    else
    {
        board[tr+s-1][tc+s-1]=t;
        CB(tr,tc,tr+s-1,tc+s-1,s);
    }
    //处理右上角
    if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中
        CB(tr, tc+s, dr, dc, s);
    else
    {
        board[tr + s - 1][tc + s] = t;
        CB(tr,tc+s,tr+s-1,tc+s, s);
    }
    //处理左下角
    if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中
        CB(tr+s, tc, dr, dc, s);
    else
    {
        board[tr + s ][tc + s-1] = t;
        CB(tr+s,tc,tr+s,tc+s-1, s);
    }
    //处理右下角
    if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中
        CB(tr+s, tc+s, dr, dc, s);
    else
    {
        board[tr + s ][tc + s] = t;
        CB(tr+s,tc+s,tr+s,tc+s, s);
    }
}
int main()
{
    CB(0,0,1,3,4);
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
            cout<<board[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

找出这n个元素中第k小的元素（掌握线性时间选择法解决此问题）

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int n,a[N];
int select(int l,int r,int k)
{
    if(l>=r) return a[l];
    int pivot=a[l],i=l,j=r+1;
    while(1)
    {
        do{i=i+1;}while(a[i]<a[pivot]);
        do{j=j-1;}while(a[j]>a[pivot]);
        if(i>=j) break;
        swap(a[i],a[j]);
    }
    if(j-l+1==k)
        return pivot;
    a[l]=a[j];
    a[j]=pivot;
    if(j-l+1>k)
        return select(l,j-1,k); //左半区找
    else
        return select(j+1,r,k-j+l-1); //右半区找
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cout<<select(0,n-1,2)<<endl;
    return 0;
}

半数集问题

int comp(int x)
{
    int ans=1;
    for(int i=1;i<=x/2;i++)
        ans+=comp(i);
    return ans;
}

int comp(int x)
{
    if(a[x]) return a[x];
    int ans=1;
    for(int i=1;i<=x/2;i++)
        ans+=comp(i);
    a[x]=ans;
    return ans;
}

整数因子分解问题

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int n,ans;
void fun(int x)
{
    if(x==1)
    {
        ans++;return;
    }
    for(int i=2;i<=x;i++)
        if(x%i==0)
            fun(x/i);
}
int main()
{
    cin>>n;
    fun(n);
    cout<<ans<<endl;
    return 0;
}

汉诺塔移动次数：移动次数为(2^n-1)

#include <bits/stdc++.h>

using namespace std;
int x;
void move(char from ,char to)
{
    x++;
    cout<<"Move "<<from<<","<<to<<endl;
}
void hanoi(int n, char first, char second,  char third)
{
    if(n==1)
    {
        move(first,third);
        return;
    }
    hanoi(n-1,first,third,second);  //n-1个盘子通过第三个托到第二个托上
    move(first,third);
    hanoi(n-1,second,first,third);

 }

int main()
{
    int m;
    cout<<"the number of diskes:";
    cin>>m;
    cout<<"move  "<<m<<" diskes:\n";
    hanoi(m,'A','B','C');
    cout<<"result: "<<x<<endl;
    return 0;
}

n个数的划分：

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,a[N],k=0;
void perm(int x)
{
    if(x==n+1)
    {
        k++;
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=x;i<=n;i++)
    {
        swap(a[x],a[i]);
        perm(x+1);
        swap(a[x],a[i]);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i;
    perm(1);
    cout<<k<<endl;
    return 0;
}

递归对有序序列 实现去重

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,a[N],k=0,ans;
void fun(int l,int r) //递归对有序序列 实现去重
{
    if(l>r) return;
    int mid=(l+r)/2;
    int num=a[mid];
    int i=mid-1,j=mid+1;
    while(a[i]==a[mid]&&i>=l)
        i--;
    while(a[j]==a[mid]&&j<=r)
        j++;
    fun(l,i);
    cout<<a[mid]<<" ";
    fun(j,r);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    fun(0,n-1);cout<<endl;
    return 0;
}

循环赛日程表

#include <bits/stdc++.h>

using namespace std;
const int N=1e3+5;
int n,a[N][N],k=0,ans;

void Copy(int tox, int toy, int fromx, int fromy, int r) //一个行列数为r的矩形的拷贝
{
	for(int i=0;i<r;i++)
		for(int j=0;j<r;j++)
			a[tox+i][toy+j]=a[fromx+i][fromy+j];
}

void Table(int k) //k为分割次数
{
	int i,r;
	int n=1; //n为参赛人数
	for(i=1;i<=k;i++) n=n*2;
	for(i=0;i<n;i++) a[0][i]=i+1;
	//k次拷贝,r矩形区域的宽度
	for(r=1;r<n;r=r*2)
 	  for(i=0;i<n;i+=2*r)	 //1次拷贝，通过多对矩阵的拷贝完成
        {
			Copy(r, r+i, 0,  i  , r);     //左上角拷贝到右下角
			Copy(r, i  , 0,  r+i, r);     //右上角拷贝到左下角
		}
}
int main()
{
    Table(3);
	for(int i=0;i<=7;i++)
    {
		for(int j=0;j<=7;j++)
			cout<<a[i][j]<<"  ";
		cout<<endl;
	}
    return 0;
}