算法设计与分析-贪心算法的应用动态规划算法的应用——沐雨先生

1． 理解贪心算法的概念；

2．掌握贪心算法的基本思想。

（1）删数问题

问题描述：给定 n 位正整数 a ，去掉其中任意 k ≤ n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的 n 位正整数 a 和正整数 k ，设计一个算法找出剩下数字组成的新数最小的删数方案。

输入（第一行为a，第二行为k）：

657943148
3

输出：

543148

（2）线段覆盖

问题描述：在一维空间中告诉你N 条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。

输入：

4//表示输入的线段个数
2 5//线段起始坐标 线段终止坐标
6 7
1 3
3 4

输出：

5

源程序

实验一

#include<stdio.h>
#include<cstring>
char n[200];
int s,i,len,flag=1;
int main(){
	printf("请输入一个n位正整数a：");
	scanf("%s",n);
	printf("请输入删除数字的个数：");
	scanf("%d",&s);
	len=strlen(n);
	while(s){
		i=0;
		while(n[i]<=n[i+1])
			i++;
		while(i<len-1){n[i]=n[i+1];i++;}
		len--;
		s--;
	}
	for(int i=0;i<len;i++){
		if(n[i]=='0' && i<len-1 && flag==1)
			continue;
		else
		{printf("%c",n[i]);flag=0;}
	}
	printf("\n");
	return 0;
}

实验二

#include <iostream>
using namespace std;

int main()
{
    int a[2][20];
    int flag[2];                                //定义标记线段，当前线段的两端点
    int n,len,tmp,i;
	printf("请输入线段个数：");
    scanf("%d",&n);
	printf("请输入线段始终坐标：\n");
    for(i=0;i<n;i++)
        scanf("%d %d",&a[0][i],&a[1][i]);             //按每个线段的左端点进行冒泡排序
    for(i=0;i<n;i++)       
        for(int j = 0; j < n - i - 1;j++)
            if(a[0][j] > a[0][j+1]){
                swap(a[1][j],a[1][j+1]);
                swap(a[0][j],a[0][j+1]);
            }
    len=a[1][0] - a[0][0];
    flag[0] = a[0][0];
    flag[1] = a[1][0];
    for(i=0;i<n;i++){
        if(a[0][i] >= flag[1]){                              //两线段无交集的情况 
            tmp = (a[1][i] - a[0][i]);
            len += tmp;
            flag[0] = a[0][i];
            flag[1] = a[1][i];
        }
        if(a[0][i] < flag[1]){
            if(a[1][i] > flag[1]){                           //有交集但不含于的情况
                tmp = (a[1][i] - flag[1]);
                len += tmp;
                flag[0] = a[0][i];
                flag[1] = a[1][i];
            }
        }
    }
    printf("覆盖的长度为：%d\n",len);
    return 0;
}