nbhkdz.com冰点文库

算法实验二(题库)


南通大学

算法设计与分析 实验报告

姓 班 学 日

名: 级: 号: 期: 2014 . 12 . 16 软件工程

目录
Question-2 编程实现循环赛日程表(分治法)???????? 3 Question-3 编程实现最长公共子序列(动态规划)?????? 3 Questi

on-4 The Triangle(动态规划)????????????4 Question-5 超级台阶(动态规划)????????????? 5 Question-6 最大和(动态规划)?????????????? 6 Question-7 剑客决斗(动态规划)?????????????7 Question-8 最长上升子序列问题(动态规划)???????? 8 Question-9 独木舟上的旅行(贪婪法)??????????? 9 Question-10 背包问题(贪心算法)???????????? 10 Question-11 田忌赛马(动规中的贪心算法)???????? 10 Question-12 硬币问题(贪心算法)???????????? 11

附:源代码???????????????????????12

2

Question-2 编程实现循环赛日程表(分治法)
描述 设有 n=2 k 个运动员要进行网球循环赛,先要设计一个满足一下要求的比赛日常表: (1)每个选手必须与其他 n-1 个选手各赛一次 (2)每个选手一天只能赛一次 (3)循环赛一共进行 n-1 天 算法设计 将 n*n 个格子,也就是 n 阶方阵从中间十字划分,一次划分分成四块,令其右上角和左下角的数据完全相 同,右下角和左上角的数据完全相同;每次划分都得到了若干个 n/2 阶的方阵,然后对这些方阵进行操作, 继续令其右上角和左下角的数据完全相同,右下角和左上角的数据完全相同,如此循环下去,直至 n<2 时 结束递归。 运行结果

Question-3 编程实现最长公共子序列(动态规划)
描述 如题,需要你做的就是写一个程序,得出最长公共子序列。 tip:最长公共子序列也称作最长公共子串(不要求连续),英文缩写为 LCS(Longest Common Subsequence) 。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是 所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数 N(0<N<100)表示待测数据组数 接下来每组数据两行,分别为待测的两组字符串。每个字符串长度不大于 1000. 算法设计 由最长公共子序列问题的最优子结构性质可知, 要找出 X=<x1, x2, …, xm>和 Y=<y1, y2, …, yn>的最长公共 子序列,可按以下方式递归地进行:当 xm=yn 时,找出 Xm-1 和 Yn-1 的最长公共子序列,然后在其尾部 加上 xm(=yn)即可得 X 和 Y 的一个最长公共子序列。当 xm≠yn 时,必须解两个子问题,即找出 Xm-1 和 Y 的一个最长公共子序列及 X 和 Yn-1 的一个最长公共子序列。这两个公共子序列中较长者即为 X 和 Y 的一 个最长公共子序列。

3

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算 X 和 Y 的最长公共子序 列时,可能要计算出 X 和 Yn-1 及 Xm-1 和 Y 的最长公共子序列。而这两个子问题都包含一个公共子问题, 即计算 Xm-1 和 Yn-1 的最长公共子序列。 与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。用 c[i,j]记录序列 Xi 和 Yj 的最长公共子序列的长度。其中 Xi=<x1, x2, …, xi>,Yj=<y1, y2, …, yj>。当 i=0 或 j=0 时,空序列是 Xi 和 Yj 的最长公共子序列,故 c[i,j]=0。其他情况下,由定理可建立递归关系如下:

运行结果:

Question-4 The Triangle (动态规划)
描述 7 38 810 2744 45265 在上图所示的三角形中,从顶部到底部,找一条路线,使得它的和最大。当然,每一步只能走左下或者右 下。 算法分析 利用动态规划的基本步骤来分析,首先找出最优解结构,l[i]表示 1 到 i 层路径的最优解,则 l[i-1]亦为最优 解(证明:如果 l[i-1]不为最优解,则 1 到 i-1 层有另外一条路径使得 l[i-1]为最优解,这样就会致使 l[i]路径 不为最优解,矛盾)。最优解结构:

这里用一位数组存储数字三角形。

4

运行结果

Question-5 超级台阶 (动态规划)
描述 有一楼梯共 m 级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第 m 级,共 有多少走法? 注:规定从一级到一级有 0 种走法。 输入 输入数据首先包含一个整数 n(1<=n<=100),表示测试实例的个数,然后是 n 行数据,每行 包含一个整数 m, (1<=m<=40), 表示楼梯的级数。 输出 对于每个测试实例, 请输出不同走法的数量。 (即有两个不同的楼梯, 一个楼梯有 2 级, 一个楼梯有 3 级) 算法设计 只能说这题有一点 DP 的思想。。简单递归 运行结果

5

Question-6 最大和 (动态规划)
描述 给定一个由整数组成二维矩阵(r*c) ,现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之 和最大,并把这个子矩阵称为最大子矩阵。 例子: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩阵为: 92 -4 1 -1 8 其元素总和为 15。 输入 第一行输入一个整数 n(0<n<=100),表示有 n 组测试数据; 每组测试数据: 第一行有两个的整数 r,c(0<r,c<=100) ,r、c 分别代表矩阵的行和列;随后有 r 行,每行有 c 个整数; 输出 输出矩阵的最大子矩阵的元素之和。 算法分析 用 2 维数组 a[1 : m][1 : n]表示给定的 m 行 n 列的整数矩阵。 子数组 a[i1 : i2][j1 : j2]表示左上角和右下角行列 坐标分别为(i1, j1)和(i2, j2)的子矩阵,其各元素之和记为:

(1)

最大子矩阵和问题的最优解即为:

(2)

(3 )

如果令: 那么式(4)就是我们熟悉的最大子序列和的问题。 根据以上分析我们可得到最大子矩阵和问题的算法:

(4)

6

运行结果

Question-7 剑客决斗 (动态规划)
描述 在路易十三和红衣主教黎塞留当权的时代, 发生了一场决斗。 n 个人站成一个圈, 依次抽签。抽中的人 和他右边的人决斗,负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜 出的信息,但“A 赢了 B”这种关系没有传递性。例如,A 比 B 强,B 比 C 强,C 比 A 强。如果 A 和 B 先决斗,C 最终会赢,但如果 B 和 C 决斗在先,则最后 A 会赢。显然,他们三人中的第一场决斗直接影 响最终结果。 假设现在 n 个人围成一个圈,按顺序编上编号 1~n。一共进行 n-1 场决斗。第一场,其中一人(设 i 号) 和他右边的人(即 i+1 号,若 i=n,其右边人则为 1 号) 。负者被淘汰出圈外,由他旁边的人补上他的 位置。已知 n 个人之间的强弱关系(即任意两个人之间输赢关系) 。如果存在一种抽签方式使第 k 个人 可能胜出, 则我们说第 k 人有可能胜出, 我们的任务是根据 n 个人的强弱关系,判断可能胜出的人数。 输入

7

第一行是一个整数 N(1<=N<=20)表示测试数据的组数。 第二行是一个整数 n 表示决斗的总人数。(2<=n<=500) 随后的 n 行是一个 n 行 n 列的矩阵,矩阵中的第 i 行第 j 列如果为 1 表示第 i 个人与第 j 个人决 斗时第 i 个人会胜出,为 0 则表示第 i 个人与第 j 个人决斗时第 i 个人会失败。 输出 对于每组测试数据,输出可能胜出的人数,每组输出占一行。 算法设计 动态规划(弗洛伊德),可以把一圈人从 x 分为两端都是 x 的一条线,x 向中间打若最终 x 能遇到 x 则说 明 x 可以取得胜利, 中间得到 meet[i][j]的转移方程有点像弗洛伊德算法, 从中间找可以作为媒介的点, 然后更新 meet 数组。因为是在圈里所以要注意%操作。 运行结果

Question-8 最长上升子序列问题 (动态规划)
描述 有一个长为 n 的数列 a0,a1,??,an-1。请求出这个序列中最长的上升子序列的长度。上升子 序列指的是对于任意的 i<j 都满足 ai<aj 的子序列。 (1≤n≤1000,0≤ai≤1000000) 。 输入 第一行为 n,下面一行为 a0~an-1。 输出 最长上升子序列的长度。 算法设计 我们依次遍历整个序列,每一次求出从第一个数到当前这个数的最长上升子序列,直至遍历到最后一个数 字为止,然后再取 dp 数组里最大的那个即为整个序列的最长上升子序列。我们用 dp[i]来存放序列 1-i 的 最长上升子序列的长度,那么 dp[i]=max(dp[j])+1,(j∈[1, i-1]); 显然 dp[1]=1,我们从 i=2 开始遍历后 面的元素即可。 运行结果:

8

Question-9 独木舟上的旅行 (贪婪法)
描述 进行一次独木舟的旅行活动,独木舟可以在港口租到,并且之间没有区别。一条独木舟最多 只能乘坐两个人, 且乘客的总重量不能超过独木舟的最大承载量。 我们要尽量减少这次活动中的花销, 所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序,读入独木舟的最大承载量、旅客 数目和每位旅客的重量。根据给出的规则,计算要安置所有旅客必须的最少的独木舟条数,并输出结果。 输入 第一行输入 s,表示测试数据的组数; 每组数据的第一行包括两个整数 w,n,80<=w<=200,1<=n<=300,w 为一条独木舟的最大承载量,n 为人 数;接下来的一组数据为每个人的重量(不能大于船的承载量)。 输出 每组人数所需要的最少独木舟的条数。 算法设计 先把各个人的体重排序,然后计算最重的人和最轻的人能否同乘一条舟,如果不能,则最重的人就要单独 乘坐一条舟,再求最轻的和第二重的人的和,依次比较。 运行结果

9

Question-10 背包问题(贪心算法)
描述 现在有很多物品(它们是可以分割的) ,我们知道它们每个物品的单位重量的价值 v 和重量 w (1<=v,w<=10) ;如果给你一个背包它能容纳的重量为 m(10<=m<=20),你所要做的就是把物品装到背 包里,使背包里的物品的价值总和最大。 输入 第一行输入一个正整数 n(1<=n<=5),表示有 n 组测试数据;随后有 n 测试数据,每组测试数据的第一 行有两个正整数 s,m(1<=s<=10);s 表示有 s 个物品。接下来的 s 行每行有两个正整数 v,w。 输出 输出每组测试数据中背包内的物品的价值和,每次输出占一行。 算法设计 贪心原理,要求背包物品总价值最大,故尽可能多存放价值大的物品;如图 题目中给出的例子, 背包可 容纳重量 15,故先放价值最大的 A,将 10 斤 A 全部放入背包,然后放入价值次大的 C,此时背包容纳量 剩下 15-10=5,而 C 还有 9 斤,因此剩下的全放 C,总价值=(10*5)+(5*3)=65。 运行结果

Question-11 田忌赛马(动规中的贪心算法)
描述 田忌赛马的故事大家应该都听过吧。田忌经常与齐国众公子赛马,设重金赌注。孙膑发 现他们的马脚力都差不多,马可分为上、中、下三等。于是孙膑对田忌说:“您只管下 大赌注,我能让您取胜。”田忌相信并答应了他,与齐王和诸公子用千金来赌注。比赛 即将开始,孙膑说:“现在用您的下等马对付他们的上等马,拿您的上等马对付他们的 中等马, 拿您的中等马对付他们的下等马。 ”已经比了三场比赛, 田忌一场败而两场胜, 最终赢得齐王的千金赌注。现在题目的要求是这样的,给出田忌 n 匹马的速度,再给出 公子 n 匹马的速度,运用上述思想,求田忌最多能赢几场比赛。 我们规定,赢一场可 得 200 两黄金,输一场就扣 200 量黄金。平局不得也不扣。求田忌最多能赢多少黄金。 输入

10

测试数据有多个。每组测试数据的第一行是为 n 的正整数。(1<=n<=1000),接下来的 两行为马的速度。第一行为田忌的 n 匹马的速度,第二行为公子的 n 匹马的速度。 输出 对于每一个测试用例,每行输出一个数,该数为田忌所能赢的最多的黄金数。 算法设计 1 如果田忌的慢马比齐王的慢马快,直接比赛。赢的代价小! 2 如果田忌的慢马比齐王的慢马慢,让他和齐王的快马比赛。输的值! 3 如果田忌的慢马的速度等于齐王的慢马 1 )如果田忌的快马比齐王的快马快 ,直接比赛。赢! 2 )如果田忌的慢马比齐王的快马慢,那让他和齐王最快的马比赛。输的值! 3 )其他情况,直接退出。统计比赛结果,算钱! 运行结果

Question-12 硬币问题(贪心算法)
描述 有 1 元、5 元、10 元、50 元、100 元、500 元的硬币各 C 1 、C 5 、C 10 、C 50 、C 100 、C 500 枚。 现在要用这些硬币来支付 A 元、 最少需要多少枚硬币?假定本题至少存在一种支付方案。 输入 第一行 n 为测试数据的组数。 以下各行依次为:C 1 C 5 C 10 C 50 C 100 C 500 A 输出 每行输出需要最少的硬币数 算法设计 由贪心算法可知尽量用大面值的硬币组合来找钱,可以使使用的硬币最少。而贪心算法对最少硬币问题的 解决总是可以得到最优解很好的近似解。 本算法就是用贪心策略枚举出所有近似最优解,然后从中寻找到 问题的最优解 寻找近似最优解群 。 (1)将硬币依面值大小排序 (2)按面值种类划分不同情况

11

有多少种面值就划分多少种情况. 每种情况的第一枚硬币面值各不一样,其后对剩余的硬币按面值从大到小 排列。 运行结果

附:源代码
Question-2
#include <iostream> using namespace std; #define MAX 100 //定义每组比赛成员的结构类型 typedef struct node { int p1; int p2; }team; team X[MAX][MAX/2+1];//X 为解向量 x[i][j]表示第 i 天 第 j 场次现在赛的情况 x[i][j].p1 和 x[i][j].p2 int num,t[MAX];//num 表示 比赛人数 t[]分别表示每天比赛的场次数初始化为 0 void Init() { cout<<"请输入运动员人数:"; cin>>num; for(int i=0;i<MAX;i++)t[i]=0; } void f(int from,int to, int day)//编号为 from 到 to 的 n(n=to-from+1)个人从第 day 天开始比赛,全部安排下去 的函数 { int n=to-from+1,i,k; if(n<2) return ; if(n==2)//只有两人,直接在第 day 天安排比赛,比赛场次为 ++t[day] { X[day][++t[day]].p1=from; X[day][t[day]].p2 =to; } if(n>2) //超过两人,才分成两组 { int mid=from+n/2-1; f(from,mid,day); //组内比赛

12

f(mid+1,to,day); //组内比赛 //以下是组间比赛 for(k=0;k<=n/2;k++) //在后 n/2 天内,分别与组 2 内队员(j+i+k)%(n/2)进行组间比赛 for(i=0;i<=n/2;i++) { X[n/2+k][++t[n/2+k]].p1 = from+i; X[n/2+k][t[n/2+k]].p2 = (i+k)%(n/2+1)+mid+1; } } } void Output() { cout<<"比赛安排如下:\n"; for(int i=1;i<=num;i++) { cout<<"第"<<i<<"天:"<<endl; for(int j=1;j<=t[i];j++) { cout<<j<<':'<<'('<<X[i][j].p1<<','<<X[i][j].p2<<')'<<' '; } cout<<endl; } } int main() { int z; Init();//初始化 f(1,num,1);//从 1 到 num 个人 从第一天开始 调用函数 Output(); cout<<"输入任意字符结束..."; cin>>z; return 0; }

Question-3
#include<iostream> #include<cstring> #define N 100 using namespace std; int a[N][N]; char s1[N],s2[N]; int max(int a,int b) { return a>=b?a:b; } int main() { int count,i,j,length1,length2,z; cout<<"请输入需要测试几组数据:"; cin>>count; while(count--) { int count=1; cout<<"请输入第"<<count<<"组待测序列:"<<endl; cin>>s1+1>>s2+1; length1=strlen(s1+1); length2=strlen(s2+1); for(i=0;i<=length1;i++) { a[i][0]=0; } for(i=0;i<=length2;i++) { a[0][i]=0;

13

} for(i=1;i<=length1;i++) { for(j=1;j<=length2;j++) { if(s1[i]==s2[j]) { a[i][j]=a[i-1][j-1]+1; } else a[i][j]=max(a[i-1][j],a[i][j-1]); } } cout<<"最长公共子序列长度为:"<<a[length1][length2]<<endl<<endl; count++; } cout<<"输入任意字符结束..."; cin>>z; return 0; }

Question-4
#include<iostream> #define N 105 using namespace std; int a[N][N],dp[N][N],z; int main() { int n,i,j,min; cout<<"输入行数:"; while(cin>>n) { for(i=1;i<=n;i++) for(j=1;j<=i;j++) { cin>>a[i][j]; dp[i][j]=0; } dp[1][1]=a[1][1]; for(i=2;i<=n;i++) { dp[i][1]=a[i][1]+dp[i-1][1]; for(j=2;j<=i;j++) { min=dp[i-1][j-1]>dp[i-1][j]?dp[i-1][j-1]:dp[i-1][j]; dp[i][j]=a[i][j]+min; } } int ans=0; for(i=1;i<=n;i++) if(ans<dp[n][i]) ans=dp[n][i]; cout<<"自上而下路径最大和为:"<<ans<<endl;//最大和 } cout<<"输入任意字符结束..."; cin>>z; return 0; }

Question-5
#include <iostream> using namespace std; int main() { int N; cout<<"请输入测试实例个数:"; cin>>N; __int64 array[1024]; memset(array,0,1024); cout<<"请输入每个实例的楼梯级数:"; while (N--)

14

{ int sum=0; cin>>sum; array[2]=1; array[1]=1; for(int index=3;index<=sum;index++) { array[index]=array[index-1]+array[index-2]; } cout<<array[sum]<<' '; } cout<<endl; system("pause"); return 0; }

Question-6
#include<stdio.h> #include<string.h> #include <iostream> #include <string> using namespace std; int a[102][102]; int main() { int i,j,k,m,r,c,max,temp,z,n; cout<<"请输入待测矩阵个数 n:"; cin>>n; for(int count=0;count<n;count++) { cout<<"输入第"<<count+1<<"个矩阵行数:"; cin>>r; cout<<endl; cout<<"输入第"<<count+1<<"个矩阵列数:"; cin>>c; for(i=1;i<=r;i++) { for(j=0;j<c;j++) { cin>>a[i][j]; a[i][j]=a[i][j]+a[i-1][j]; } } for(i=1,m=a[1][0];i<=r;i++) for(j=i;j<=r;j++) { for(k=max=0;k<c;k++) { temp=a[j][k]-a[i-1][k]; max=(max>=0?max:0)+temp; m=max>m?max:m; } } cout<<"矩阵的最大和为:"<<m<<endl<<endl; } cout<<"输入任意字符结束..."; cin>>z; }

Question-7
#include <stdio.h> #include <string.h> #include <stdlib.h> int fight[501][501], meet[501][501], n; //fight[i][j]: i 与 j PK 能否获胜, meet[i][j]:i,j 能否遇到

15

int main() { printf("请输入测试数据的组数和决斗的总人数:\n"); int i, j, k, m, t, cnt,z; scanf("%d", &t); while(t--) { memset(fight, 0, sizeof(fight)); //初始化 memset(meet, 0, sizeof(meet)); scanf("%d", &n); for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { scanf("%d", &fight[i][j]); } } for(i = 0; i < n; i++) //初始化(相邻的两个人一定能相遇) { meet[i][(i+1)%n] = 1; } for(i = 2; i <= n; i++) //间隔的人数 { for(j = 0; j < n; j++) //起始位置 { k = (j + i) % n; //结束位置 for(m = (j+1)%n; m != k; m = (m+1)%n) { if(meet[j][m] && meet[m][k] && (fight[j][m] || fight[k][m])) //注意当 i 和 m 相 遇且 j 和 m 相遇时只要 i 和 j 有一个赢 i,j 就可相遇(就算有一个败了另一个也能赢得 m 遇见它) { meet[j][k] = 1; break; } } } } cnt = 0; for(i = 0; i < n; i++) { if(meet[i][i]) //能和自己相遇就可能胜利 { cnt++; } } printf("可能胜出的人数为:%d\n", cnt); } printf("输入任意字符结束..."); scanf("%d", &z); return 0; }

Question-8
#include<iostream> using namespace std; int main(){ int a[100], f[100], n ,i, j,z; cin>>n; for(int i=0; i<n; i++) cin>>a[i]; int max = 1; f[0] = 1; for(i=1; i<n; i++) { int tm = 0; for(j=i-1; j>=0; j--) { if(a[j] < a[i] && f[j]>tm ) tm = f[j];

16

} f[i] = tm + 1; if (f[i] > max) max = f[i]; } cout<<"最长上升子序列长度为:"<<max<<endl; cout<<"输入任意字符结束..."; cin>>z; return 0; }

Question-9
#include<stdio.h> int main() { int n,w,m,i,a[300],t,z; printf("请输入为一条独木舟的最大承载量和人数:"); scanf("%d",&n); while(n--) { scanf("%d%d",&w,&m); int k=0,j=0; printf("请输入每个人的重量:"); for(i=0;i<m;i++) scanf("%d",&a[i]); for(i=0;i<m;i++) for(j=i+1;j<m;j++) if(a[i]>a[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } /*对体重排序*/ for(i=0,j=m-1;i<=j;) { if(a[i]+a[j]<=w) { i++; j--; k++; } /*如果可以,让他们两个同乘一条,再比较第二轻和第二重的人,以此类推*/ else if(i==j) k++; /*就剩一个人的时候,他自己单独一条*/ else { j--; k++; } /*重的人自己单独一条舟*/ } printf("要安置所有旅客必须的最少的独木舟条数为:%d\n",k); } printf("输入任意字符结束..."); scanf("%d",&z); return 0; }

Question-10
#include #include #include #include <iostream> <algorithm> <cstdio> <cstdlib>

using namespace std; typedef struct GOODS {

17

int v,w;//价值和重量都比较小<256 }GOODS; GOODS goods [10]; int cmp(const void * a,const void *b) { return (*(GOODS *)a).v< (*(GOODS *)b).v ? 1: -1; } int main() { int s,n,m,i,z; int value,weight; printf("请输入共几组待测数据:"); scanf("%d",&n); while(n--) { scanf("%d%d",&s,&m); for(i=0;i<s;i++) scanf("%d%d",&goods[i].v,&goods[i].w); qsort(goods,s,sizeof(goods[0]),cmp); //将物品按价值从大到小排序 //for(i=0;i<s;i++) printf("%d %d\n",goods[i].v,goods[i].w); value = weight = i = 0; while(m) { if(goods[i].w <= m)//这种物品的总质量 还小与目前背包容纳量,则全部装入 { m -= goods[i].w; value += goods[i].v *goods[i].w; //w 重量的单价为 v 的物品价值 } else//将背包剩下的容量全部装这种物品 { value += goods[i].v * m; m=0; } i++; } printf("此组测试数据中背包内的物品的价值和为:%d\n",value); } // system("pause"); printf("输入任意字符结束..."); scanf("%d",&z); return 0; }

Question-11
#include<iostream> #include<algorithm> using namespace std; int tian[1005],king[1005]; bool cmp(int a,int b) { return a>b; } int match(int n) { sort(tian,tian+n,cmp); sort(king,king+n,cmp); int tl=0,tr=n-1,kl=0,kr=n-1,win=0,lose=0; while(tl<=tr) { if(tian[tl]>king[kl]) { win++; tl++; kl++; }

18

else if(tian[tr]>king[kr]) { win++; tr--; kr--; } else { if(tian[tr]<king[kl]) lose++; tr--; kl++; } } return (win-lose)*200; } int main() { int n,i,k; cout<<"请输入共比几场:"; cin>>n; cout<<"请输入田忌每场马的速度值:"; for(i=0;i<n;i++) cin>>tian[i]; cout<<"请输入齐王每场马的速度值:"; for(i=0;i<n;i++) cin>>king[i]; cout<<"田忌最多能赢"<<match(n)<<"两。"<<endl; cout<<"输入任意字符结束..."; cin>>k; return 0; }

Question-12
#include <iostream> using namespace std; const int V[6] = {1, 5, 10, 50, 100, 500}; int C[6] = {3, 2, 1, 3, 0, 2}; int A,z; // 定义面值 // 各面值的数量 // 要凑齐面值

int main() { cout<<"请输入要支付的钱数:"; cin>>A; cout<<"各面值纸币需要的数量为:"<<endl; int ans = 0; for(int i = 5; i >= 0; i--) { int t = min( A/V[i], C[i]); //尽可能多地使用大面值 A -= t * V[i]; // cout << t << "*" << V[i] << endl; cout << V[i] << ": " << t << endl; ans += t; } cout << endl; cout << "ans: " << ans << endl; cout<<"输入任意字符结束..."; cin>>z; return 0; }

19


算法实验二(题库)二

算法实验二(题库)二_IT认证_资格考试/认证_教育专区。南通大学 算法设计与分析 实验报告 姓班学 名: 级: 号: 鹿 瑶 软件工程 122 1213042037 日 期: 2014...

算法实验二(题库)

算法实验二(题库)_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 算法实验二(题库)_数学_高中教育_教育专区。今日推荐 ...

算法分析实验二报告

算法设计与分析》实验报告 目 录 一、实验内容描述和功能分析. 二、算法过程...2.邮局选址问题通过题目给定的意思,可以知道其数学算法,通过调用库函数来 实现...

算法导论与体系结构--实验二

算法导论与体系结构--实验二_化学_自然科学_专业资料。实验题目: 快速排序的 c 算法实现。 /*快速排序算法*/ #include<stdio.h> void main() { void sort(...

算法实验报告(二)

实验教师 上机地点 西南大学计算机与信息科学学院 2014 年 9 月 1 《算法设计与分析》课程实验报告(一)实验题目 实验时间 一、实验目的及要求 使用递归与分治策略...

实验二 贪心算法的应用

3.学会利用贪心算法解决实际问题。 二、实验内容 1.问题描述:题目二 实验二一、实验目的 贪心算法的应用 1.掌握贪心算法的基本概念和两个基本要素 2.熟练掌握...

实验二 算法

实验二 算法_电脑基础知识_IT/计算机_专业资料。实验二:算法初步【课时安排】 ...(写出计算的公式后, 参考第 4 题的程序进行修改),运行程序,并观察程序的运行...

算法实验二

二、 实验内容: 掌握贪心算法、动态规划和回溯算法的概念和基本思想,分析并掌握"0-1" 背包问题的三种算法,并分析其优缺点。 三、 实验题 1. "0-1"背包问题...

《算法设计与分析》实验二

b 压缩包内为一个“ 《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹...题目分析 利用分治策略将待排序进行快速排序。 首先设置初始比较基准数据和定义...

实验二贪心算法实验

3.学会利用贪心算法解决实际问题。 二、实验内容 1.问题描述:题目实验二一、实验目的 贪心算法的应用 1.掌握贪心算法的基本概念和两个基本要素 2.熟练掌握贪心...