算法分析与设计期末复习-04

算法分析与设计期末复习——伪代码2

1. 哈夫曼编码

伪代码实现：

    // a数组长度为len
	for(i=1;i<=n-1;i++){
        // 对a数组进行降序排序
		sort(a+1,a+1+len,cmp);
        // 取a数组中的最后一个和倒数第二个值，进行相加，得到新的数字，再次排序
		temp=a[len]+a[len-1];
        // 将相加结果记录到总结果里
        // ans表示最终结果
		ans+=temp;
        // 将数组长度减少一个
		len--;
		a[len]=temp;
	}

完整代码：

#include

using namespace std;

int n;
int a[110];
int i,j,k;
int temp;
int len;
int ans;

bool cmp(int x,int y){
	return x>y;
}

int main(){
	cin>>n;
	len=n;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}

    // a数组长度为len
	for(i=1;i<=n-1;i++){
        // 对a数组进行降序排序
		sort(a+1,a+1+len,cmp);
        // 取a数组中的最后一个和倒数第二个值，进行相加，得到新的数字，再次排序
		temp=a[len]+a[len-1];
        // 将相加结果记录到总结果里
        // ans表示最终结果
		ans+=temp;
        // 将数组长度减少一个
		len--;
		a[len]=temp;
	}
	
	cout<<ans<<endl;
	
//	sort(a+1,a+1+n);
//	for(i=1;i<=n;i++){
//		cout<
//	}
	
//	cout<
	return 0;
}

2.最长公共子序列

伪代码实现：

for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            // a数组和b数组是两个待比较的序列
            // 如果a当前的数和b当前的数相等
            if(a[i] == b[j]){
                // dp数组记录当前最长公共子序列的长度
                dp[i][j] = dp[i-1][j-1] + 1;
                // vis数组记录当前数组的状态
                vis[i][j] = 1;
            }
            // 假如上面比左边大
            else if(dp[i-1][j] >= dp[i][j-1]){
                dp[i][j] = dp[i-1][j];
                vis[i][j] = 2;
            }
            // 假如左边比上面大
            else{
                dp[i][j] = dp[i][j-1];
                vis[i][j] = 3;
            }
        }
    }

// 根据每个数的状态，输出最长公共子序列
void lcs(int x,int y){
    if(x == 0 || y ==0){
        return;
    }
    if(vis[x][y] == 1){
        lcs(x-1,y-1);
        cout<<b[x]<<" ";
    }
    else if(vis[x][y] == 2){
        lcs(x-1,y);
    }
    else{
        lcs(x,y-1);
    }
}

完整代码实现：

#include
using namespace std;
int a[110],b[110],dp[110][110],vis[110][110];


// 根据每个数的状态，输出最长公共子序列
void lcs(int x,int y){
    if(x == 0 || y ==0){
        return;
    }
    if(vis[x][y] == 1){
        lcs(x-1,y-1);
        cout<<b[x]<<" ";
    }
    else if(vis[x][y] == 2){
        lcs(x-1,y);
    }
    else{
        lcs(x,y-1);
    }
}

int main(){
    // x代表a数组的长度，y代表b数组的长度
    int x,y;
    cin>>x>>y;
    for(int i=1;i<=x;i++){
        cin>>a[i];
    }
    for(int i=1;i<=y;i++){
        cin>>b[i];
    }
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            // a数组和b数组是两个待比较的序列
            // 如果a当前的数和b当前的数相等
            if(a[i] == b[j]){
                // dp数组记录当前最长公共子序列的长度
                dp[i][j] = dp[i-1][j-1] + 1;
                // vis数组记录当前数组的状态
                vis[i][j] = 1;
            }
            // 假如上面比左边大
            else if(dp[i-1][j] >= dp[i][j-1]){
                dp[i][j] = dp[i-1][j];
                vis[i][j] = 2;
            }
            // 假如左边比上面大
            else{
                dp[i][j] = dp[i][j-1];
                vis[i][j] = 3;
            }
        }
    }

    lcs(x,y);

    cout<<endl;
    cout<<endl;
    for(int i=0;i<=x;i++){
        for(int j=0;j<=y;j++){
            cout<<vis[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

3. 0/1背包问题，用动态规划求解

伪代码实现：

    // dp矩阵用来记录最大价值
    // w数组记录每个物品的体积
    // v数组记录每个物品的价值
    // n代表物品的数量，c代表背包容量
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            // 装
            if(w[i] <= j){
                dp[i][j] = max(dp[i-1][j],v[i] + dp[i-1][j-w[i]]);
            }
            // 不装
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

完整代码：

#include
using namespace std;

int dp[110][110];
int w[110],v[110];

int main(){
    int n,c;
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    // dp矩阵用来记录最大价值
    // w数组记录每个物品的体积
    // v数组记录每个物品的价值
    // n代表物品的数量，c代表背包容量
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            // 装
            if(w[i] <= j){
                dp[i][j] = max(dp[i-1][j],v[i] + dp[i-1][j-w[i]]);
            }
            // 不装
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    for(int i=0;i<=n;i++){
        for(int j=0;j<=c;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;

}

4. 单源顶点最短路径，djistra算法

伪代码：

// vis数组记录顶点是否被访问过
    // d数组记录原点到各个点的最短距离
    d[1]=0;
    for(int i=1;i<=n;i++){
        // mi记录与已访问过点最近的点d
        int mi = -1;
        for(int j=1;j<=n;j++){
            if(!vis[j] && (mi == -1 || d[j] < d[mi])){
                mi = j;
            }
        }

        // 将mi点标记为已访问
        vis[mi] = true;
        // 更新最短路径
        for(int j=1;j<=n;j++){
            if(!vis[j] && a[mi][j] !=0 && d[mi] + a[mi][j] < d[j]){
                d[j] = d[mi] + a[mi][j];
            }
        }
    }

完整代码：

#include
using namespace std;
const int N = 10;
const int INF = 0x3f3f3f3f;
int a[N][N];
int d[N];
bool vis[N];
int main(){
    int n,m;
    cin>>n>>m;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        a[u][v] = w;
    }
    memset(d,0x3f,sizeof(d));

    // vis数组记录顶点是否被访问过
    // d数组记录原点到各个点的最短距离
    d[1]=0;
    for(int i=1;i<=n;i++){
        // mi记录与已访问过点最近的点d
        int mi = -1;
        for(int j=1;j<=n;j++){
            if(!vis[j] && (mi == -1 || d[j] < d[mi])){
                mi = j;
            }
        }

        // 将mi点标记为已访问
        vis[mi] = true;
        // 更新最短路径
        for(int j=1;j<=n;j++){
            if(!vis[j] && a[mi][j] !=0 && d[mi] + a[mi][j] < d[j]){
                d[j] = d[mi] + a[mi][j];
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
    return 0;
}
/*
5 10
1 2 10
1 3 5
2 3 2
2 4 1
3 2 3
3 4 9
3 5 2
4 5 4
5 1 7
5 4 6
*/

5. 快速排序

伪代码：

// a为待排序数组
void quick(int left,int right){
    int i,j,mid;
    i = left;
    j = right;

    // mid用来确定轴值
    mid = a[(left + right)/2];
    while(i<=j){
        while(a[i]<mid){
            i++;
        }
        while(a[j]>mid){
            j--;
        }
        if(i<=j){
            // 如果左边有比轴值大的数，右边有比轴值小的数，则交换
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }

    // 对轴值左边的数进行排序
    if(j>=left){
        quick(left,j);
    }
    // 对轴值右边的数进行排序
    if(i<=right){
        quick(i,right);
    }
}

完整代码：

#include 
using namespace std;

int n,a[20];

// a为待排序数组
void quick(int left,int right){
    int i,j,mid;
    i = left;
    j = right;

    // mid用来确定轴值
    mid = a[(left + right)/2];
    while(i<=j){
        while(a[i]<mid){
            i++;
        }
        while(a[j]>mid){
            j--;
        }
        if(i<=j){
            // 如果左边有比轴值大的数，右边有比轴值小的数，则交换
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }

    // 对轴值左边的数进行排序
    if(j>=left){
        quick(left,j);
    }
    // 对轴值右边的数进行排序
    if(i<=right){
        quick(i,right);
    }
}
int main(){
    int i;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    quick(0,n-1);
    for(i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
}