本文主要是介绍计算机算法设计与分析 第四章 贪心算法 作业题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 一、判断题
• • 1-1
  • 1-2
  • 1-3
  • 1-4
  • 1-5
• 二、单选题
• • 2-1
• 三、编程题
• • 7-1 汽车加油问题 (20 分)
  • • 题目描述
    • 基本思路
    • 参考代码
  • 7-3 排队接水 (15 分)
  • • 题目描述
    • 基本思路
    • 参考代码
  • 7-10 选点问题 (15 分)
  • • 题目描述
    • 基本思路
    • 参考代码
  • 7-4 程序存储问题 (90 分)
  • • 题目描述
    • 基本思路
    • 参考代码

一、判断题

1-1

只有当局部最优跟全局最优解一致的时候，贪心法才能给出正确的解。
T F

1-2

令S为活动选择问题（Activity Selection Problem）中所有活动的集合。则一定存在S的某个最大相容活动子集是包含了最早结束的活动a_m的。
T F

1-3

令S为活动选择问题（Activity Selection Problem）中所有活动的集合。则最早结束的活动a_m一定被包含在S的所有最大相容活动子集中。
T F

1-4

在活动选择问题（Activity Selection Problem）中，令 S 为活动的集合。以“每次收集最迟开始的活动”为贪心原则，可以正确找到 S 中相互兼容活动的最大规模的子集合。
T F

1-5

令 C 为字母集，其中每个字符 c 有对应频率 c.freq。若 C 的大小为 n，则其中任一字符 c 的最优前缀编码长度都不会超过 n−1.
T F

二、单选题

2-1

给定一段文本中的4个字符(a, b, c, d)。设a和b具有最低的出现频率。下列哪组编码是这段文本可能的哈夫曼编码？
A. a: 000, b:001, c:01, d:1
B.a: 000, b:001, c:01, d:11
C.a: 000, b:001, c:10, d:1
D.a: 010, b:001, c:01, d:1

2-2
给定一段文本中的 4 个字符 (u,v,w,x) 及其出现频率 (f_u,f_v,f_w,f_x)。若对应的哈夫曼编码为 u: 00, v: 010, w: 011, x: 1，则下列哪组频率可能对应
(f_u,f_v,f_w,f_x)?
A.15, 23, 16, 45
B.30, 21, 12, 33
C.41, 12, 20, 32
D.55, 22, 18, 46

三、编程题

7-1 汽车加油问题 (20 分)

题目描述

题目来源：王晓东《算法设计与分析》

一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。

输入格式:
第一行有 2 个正整数n和 k（k<=1000 )，表示汽车加满油后可行驶n公里，且旅途中有 k个加油站。 第二行有 k+1 个整数，表示第 k 个加油站与第k-1 个加油站之间的距离。 第 0 个加油站表示出发地，汽车已加满油。 第 k+1 个加油站表示目的地。

输出格式:
输出最少加油次数。如果无法到达目的地，则输出“No Solution!”。

输入样例:

7 7
1 2 3 4 5 1 6 6 

输出样例:

4

基本思路

cnt_res记录需要加油次数
each表示到每个车站时油量
若each足够到达下一站，则该站不用加油
若each不够，加满后够到下一站，则该站加油
若each不够，加满后也不够，则输出"No Solution!"

参考代码

#include <iostream>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	int a[k+1];
	for(int i=0;i<=k;i++)
	{
		cin>>a[i];
	 } 
	 int cnt_res=0;
	 int each=n;
	 bool flag=true;
	 for(int i=1;i<k;i++)
	 {
	 	each-=a[i];
	 	if(each>=a[i+1])
	 	{
	 		continue;
		 }
		 else if(n>=a[i+1])
		 {
		 	cnt_res++;
		 	each=n;
		 	
		 }
		 else{
		 	cout<<"No Solution!";
		 	flag=false;
		 	break;
		 }
	 }
	 if(flag) cout<<cnt_res;
 } 

7-3 排队接水 (15 分)

题目描述

有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入格式:
共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出格式:
输出为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入样例:

10
56 12 1 99 1000 234 33 55 99 812

输出样例:

291.90

基本思路

排序后存每个人的等待时间，求和后求平均

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
struct peo{
	int each_time;
	int wait_time=0;
};
bool cmp(peo a,peo b){
	return a.each_time<b.each_time;
}
int main()
{
	int n;
	cin>>n;
	peo people[n];
	for(int i=0;i<n;i++)
	{
		cin>>people[i].each_time;
	}
	sort(people,people+n,cmp);
	int each=0;
	for(int i=0;i<n;i++)
	{
		
		people[i].wait_time+=each;
		each+=people[i].each_time;
	}
	double sum=0;
	for(int i=0;i<n;i++)
	{
		sum+=people[i].wait_time;
		
//		cout<<people[i].wait_time<<" ";
	}
	
	printf("%.2lf",sum/n);
 } 

7-10 选点问题 (15 分)

题目描述

数轴上有n个闭区间[ai, bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

输入格式:
第一行一个数字n，表示有n个闭区间。 下面n行，每行包含2个数字，表示闭区间[ai, bi]

输出格式:
一个整数，表示至少需要几个点

输入样例:
在这里给出一组输入。例如：

3
1 3
2 4
5 6

输出样例:
在这里给出相应的输出。例如：

2

基本思路

从头开始循环，看能同时相交的最大区间数，与前面有相交的区间visit设为1，具体可参考上机题中的会场安排问题，不过那个是要不相交，这个是要相交

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
struct p{
	int start;
	int end;
	int visited=0;
};
bool cmp(p a,p b)
{
	if(a.start==b.start)
	{
		return a.end<b.end;
	}
	else{
		return a.start<b.start;
	}
}
int main()
{
	int n;
	cin>>n;
	p point[n];
	for(int i=0;i<n;i++)
	{
		cin>>point[i].start>>point[i].end;
	}
	sort(point,point+n,cmp);
	int cnt_res=0;
	for(int i=0;i<n;i++)
	{
		if(point[i].visited==0)
		{
			cnt_res++;
			for(int j=i+1;j<n;j++)
			{
				if(point[j].start<=point[i].end&&point[j].visited==0)
				{
					point[j].visited=1;
				}
			}
		}
	}
	cout<<cnt_res;
}

7-4 程序存储问题 (90 分)

题目描述

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。

输入格式:
第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。

输出格式:
输出最多可以存储的程序数。

输入样例:
在这里给出一组输入。例如：

6 50 
2 3 13 8 80 20

输出样例:
在这里给出相应的输出。例如：

5

基本思路

排序后遍历，相加直到超过所能存储的最大值

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int n,l;
	cin>>n>>l;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	int sum=0;
	int cnt_res=0;
	for(int i=0;i<n;i++)
	{
		
		if(sum+a[i]<=l)
		{
			sum+=a[i];
			cnt_res++;
		}
		else{
			break;
		}
	}
	cout<<cnt_res;
}

这篇关于计算机算法设计与分析 第四章 贪心算法 作业题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！