OpenJudge算法设计与分析习题解答

1、1、硬币面值组合描述使用1角、2角、5角硬币组成 n角钱。设1角、2角、5角的硬币各用了 a、b、c个，列出所有可能的 a, b, c组合。输出顺序为：先按 c的值从小到大，若 c相同则按b的值从小到大。输入一个整数n （1 <= n <= 100），代表需要组成的钱的角数。输出输出有若干行，每行的形式为：i a b c第1歹U i代表当前行数（行数从 001开始，固定3个字符宽度，宽度不足 3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。样例输入10样例输出001100000281000362000

2、4430005240006050007501008311009121010002源代码：#include<>#include<>int main()int t=1;int i,j,k；int n;scanf("%d",&n);int A=n,B=n/2,C=n/5;for(i=0;i<=C;i+)for(j=0;j<=B;j+)for(k=0;k<=A;k+)if(i*5+j*2+k*1=n)printf("%03d%12d%12d%12dn",t,k,j,i);t+；getchar();return 0

3、;2 、比赛排名描述5 名运动员参加100 米赛跑，各自对比赛结果进行了预测：A 说： E 是第 1 名。B 说：我是第2 名。C 说：A 肯定垫底。D 说：C 肯定拿不了第1 名。E 说： D 应该是第 1 名。比赛结束后发现， 只有获第 1 名和第 2 名的选手猜对了， E 不是第 2 名和第 3 名， 没有出现名次并列的情况。请编程判断5 位选手各是第几名。输入无输出输出要求：按ABCDE 的顺序输出 5 行，其中第 1 行是 A 的名次，第2 行是 B 的名次，第 3 行是 C 的名次，第4 行是 D 的名次，第5 行是 E 的名次。样例输入样例输出源代码：#include<&g

4、t;int main()printf("5n");printf("2n");printf("1n");printf("3n");printf("4n");return 0;3 、鸡兔同笼描述一个笼子里面关了鸡和兔子(鸡有2 只脚，兔子有4 只脚，没有例外)。已经知道了笼子里面脚的总数 a ，问笼子里面至少有多少只动物，至多有多少只动物。输入一行，一个正整数 a (a < 32768)。输出一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满

5、足要求的答案，则输出两个0 ，中间用一个空格分开。20样例输出5 10源代码：#include <>int main()int n;scanf("%d",&n);if(n % 4= 0)printf("%d %d",n/4,n/2);else if(n % 4!= 0&&n % 2= 0)printf("%d %d",n/4 +1, n/2);elseprintf("0 0");return 0;4、谁是你的潜在朋友描述臭味相投“一这是我们描述朋友时喜欢用的词汇。两个人是朋友通常

6、意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了 一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,N,把M 本书依次编号为1,2,。,M时，按照 臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。输入第一行两个整数 N,M , 2 <= N , M<= 200 。接下来有 N行，第i(i = 1,2,N)行每一行有一个 数，表示读者i- 1最喜欢的图书的编号 P(1&

7、lt;=P<=M)输出包才N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的 书，则输出“BeiJu”(即悲剧，人人)样例输入4 52321样例输出1 BeiJu1 BeiJu源代码：#include <>#include <> int b 222 ; int a 222 ;int n, m;int main()scanf("%d%d", &n, &m);for(int i = 1; i <= n; i+ )scanf("%d", &a i );b a i +;

8、for( int i = 1; i <= n; i+ )if( b a i = 1 )printf("BeiJun");else if( b a i >= 2 )printf("%dn", b a i - 1 );return 0;5 、称体重描述赵、钱、孙、李四个人中既有大人也有小孩，给他们称体重时发现，他们每个人的体重都不一样，且体重(单位：公斤)恰好是10 的整数倍，且他们的体重都不高 于 50 公斤，已知赵、钱两人的体重之和恰好等于孙、 李两人的体重之和； 赵、 李两人的体重之和大于孙、 钱两人的体重之和， 并且赵、孙俩人的体重之和还

9、小于钱的体重。请编写一个程序，按照体重从小到大的顺序，打印出四人的姓氏的首字母和体重数。输入无输出打印出四人的姓氏的首字母（小写）和体重数（每人一行，姓名首字母和体重数之间用空格隔开）。样例输入无样例输出z 10q 20s 30l 40（以上输出仅用于说明格式） #include<>#include<>int main()int a4,b4=123,4,c4='z','q','s',T;int i,j,t；for(a0=1;a0<=5;a0+)for(a1=1;a1<=5;a1+)for(a2=1;a2<

10、=5;a2+)for(a3=1;a3<=5;a3+)if(a1!=a0&&a2!=a1&&a2!=a0&&a3!=a2&&a3!=a1&&a3!=a0)&&(a0+a1=a2+a3)&&(a0+a3>a1+a2)&&(a0+a2<a1)for(i=0;i<4;i+)bi=ai；)for(i=0;i<4;i+)ai=bi；)for(i=0;i<4;i+)for(j=i+1;j<4;j+)if(bi>bj)t=bi;bi=b

11、j；bj=t;)for(j=0;j<4;j+)for(i=0;i<4;i+)if(ai=bj)printf("%c %dn",ci,bj*10);)getcharQ;return 0;6、比饭量描述3个人比饭量，每人说了两句话：？A说：B比我吃的多，C和我吃的一样多？B说：A比我吃的多，A也比C吃的多？C说：我比B吃得多，B比A吃的多。？事实上，饭量和正确断言的个数是反序的关系。？请编程按饭量白大小输出 3个人的顺序。输入无输入输出按照饭量大小输出 3人顺序，比如:ABC样例输入样例输出#include<>#include<>int ma

12、in()int A,B,C;int a,b,c;for(A=1 ;A<=3;A+)for(B=1;B<=3;B+)for(C=1;C<=3;C+)a=(B>A)+(C=A);b=(A>B)+(A>C);c=(C>B)+(B>A);if( (A>B&&a<b)|(A=B&&a=b)|(A<B&&a>b)+ (A>C&&a<c)|(A=C&&a=c)|(A<C&&a>c)+ (B<C&&

13、b>c)|(B=C&&b=c)|(B>C&&b<c) =3)if(a>b&&a>c)if(b>c) printf("ABC");else printf("ACB");)if(b>a&&b>c)if(a>c) printf("BAC");else printf("BCA");)if(c>a&&c>b)if(a>b) printf("CAB");el

14、se printf("CBA");getchar();return 0;7 、求排列的逆序数描述在 Internet 上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑 1,2,n的排列ii, i2,，in,如果 其中存在j,k，满足j < k 且ij> i k,那么就称(ij,ik)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有 8 个逆序(2,1),(6,3),(6,4),(6,

15、5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由 1,2,，n构成的所有n!个排列中，最小的逆序数是0,对应的排列就是1,2,n ;最大的逆序数是n(n-1)/2,对应的排列就是n,(n- 1),2,1。逆序数越大的排列与原始排列的差异度就越大。现给定1,2,n的一个排列，求它的逆序数。输入第一行是一个整数 n ，表示该排列有n 个数( n <= 100000)。第二行是 n 个不同的正整数，之间以空格隔开，表示该排列。输出输出该排列的逆序数。样例输入样例输出提示1 .利用二分归并排序算法(分治)；2 .注意结果可能超过int的范围，需要用long

16、 long 存储。#include <cstdio>using namespace std;const int MAX_NUM = 100000 + 5;long long seqMAX_NUM;int N;long long ans;void reSeq(long long* seq, int lef, int righ) ,&numi.y);int ans;sort(num,num+t,cmp);if(t%2=1)ans=0;int zong=numt/2.y;for(i=0;i<t;i+)ans+=abs(numi.y -zong);elseint zong=n

17、umt/2.y+numt/2 -1.y;zong/=2;ans=0;for(i=0;i<t;i+)ans+=abs(numi.y -zong);printf("%dn",ans);return 0;12 、 0/1 背包问题描述给定n种物品和一个背包，物品i(1 wiwn)重量是Wi,其价值为vi,背包的容量为C,对每种物品只有两种选择：装入背包或者不装入背包。如何选择装入背包的物品，使得装入背包中物品的总价值最大输入输入包含一组或多组测试例。每组测试例的第一行是物品的数量n和背包的容量 C,之后的n行是每个物品的重量及其价值。输出输出第一行是装入背包中物品的总价值，

18、后面 n行是各个物品装入背包的情况。样例输入5 102 62 36 55 44 6样例输出1511001源代码：#include <>#includealgorithmusing namespace std;int dp1101010;int n, c, ans110;int w110, v110;void print()int i, j, k;k=c;for(i=n; i>=1; i -)if(dpik!=dpi -1k)ansi=1;k=k-wi;elsereturn;int main()int i, j, k;scanf("%d%d", &n

19、, &c);for(i=1; i<=n; i+)scanf("%d%d", &wi, &vi);for(i=1; i<=n; i+)for(j=1; j<=c; j+)dpij=dpi -1j;if(j>=wi)dpij=max(dpi -1j-wi+vi, dpij);printf("%dn", dpnc);print();for(i=1; i<=n; i+) printf("%dn", ansi); return 0;13 、最少硬币问题描述设有 n 种不同面值的硬币，各硬币的

20、面值存于数组 T1:n 中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins1:n中。对任意钱数0Wmc20001，设计一个用最少硬币找钱 m 的方法。对于给定的iwnwio,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins ,以及钱数m ,0 < m< 20001,计算找钱 m的最少硬币数。输入由文件提供输入数据，文件的第一行中只有1 个整数给出 n 的值，第 2 行起每行 2 个数，分别是Tj 和 Coinsj 。最后 1 行是要找的钱数m 。-1。输出将计算出的最少硬币数输出到文件中。问题无解时输出样例输入31 32 35 318样例输出5

21、提示运用动态规划法进行算法设计并编程实现。源代码：#include<>#include<vector>using namespace std;int w110, v110;int dp11020010)int n, m;void init()for(int i=0; i<110; i+)for(int j=0; j<20010; j+)int main()int i, j, k;int t, x, cnt=1;scanf("%d", &n);for(i=1; i<=n; i+)scanf("%d%d",

22、&t, &x);for(j=1; j<=x; j+)wcnt=t;vcnt=1;cnt+;scanf("%d", &m);init();for(i=0; i<cnt; i+).,An ， 考察这 n 个矩阵的连乘积A1A2.An。 由于矩阵乘法满足结合律， 故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算3 个矩阵 A1,A2,A3 连乘积的例子。设这 3 个矩阵的维数分别为 10*100， 100*5 ，和 5*50 。若按 (A1A2)A3 计算

23、， 3 个矩阵连乘积需要的数乘次数为 10*100*5+10*5*50 = 7500 。若按 A1(A2A3) 计算，则总共需要 100*5*50+10*100*50 = 75000次数乘。现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。输入输入数据由多组数据组成。每组数据格式如下：第一行是一个整数n (1 wnW26),表示矩阵的个数。接下来 n 行，每行有一个大写字母，表示矩阵的名字，后面有两个整数 a,b ，分别表示该矩阵的行数 和列数，其中 1<a,b<100 第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式 中没有括

24、号则按照从左到右的顺序计算，输入的括号保证能够配对。输出对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error样例输入3A 10 100B 100 5C 5 50A(BC)样例输出75000源代码：# include <># include <string># include <iostream># include <># include <># include <stack>using namespace s

25、td;int n, ans;string exp, str;int x, y;struct nodeint x,y;node s200;int flage;stack<char> ope;stack<node> v;string change(string t)int length=();string des=""for(int i=0; i<length -1; i+)if(isalpha(ti)if(ti+1=')')des=des+ti;elsedes=des+ti+'*'else if(ti='(

26、')des=des+ti;elseif(ti+1=')')des=des+ti;elsedes=des+ti+'*'des=des+tlength -1+'='return des;node calc(node a, node b)if!=flage=1;node t;ans=ans+*;=;=;return t;char compare(char i, char j)if(i='=')if(j!='=')return '<'elsereturn '='if(j=

27、9;)')return)elsereturn)if(i='*')return)elsereturn)int main()int i, j, k;string e;while(cin»n)for(i=1; i<=n; i+)cin»str»x»y;sstrO.x=x;sstrO.y=y;cin>>e;flage=0;ans=0;exp=change(e);while(!()();while(!()();('=');int l=();for(k=0; k<=l -1; )if(isalpha(e

28、xpk)(sexpk);k+;elseif(compare(), expk)='=')();k+;else if(compare(), expk)='<')(expk);k+;elsenode a=();();node b=();();(calc(b, a);();if(!flage)cout<<ans<<endl;elsecout<<"error"<<endl;return 0;15 、多边形游戏描述一个多边形， 开始有 n 个顶点。 每个顶点被赋予一个正整数值， 每条边被赋予一个运算符

29、“+”或 “*所有边依次用整数从 1 到 n 编号。？现在来玩一个游戏，该游戏共有n 步：？第1步，选择一条边，将其删除?随后n-1步，每一步都按以下方式操作：(1 )选择一条边E以及由E连接着的2个顶点v1和v2 ; (2 )用一个新的顶点取代边 E以及由E连接着的2个顶点v1和v2 ,将顶点v1和v2的整 数值通过边E上的运算得到的结果值赋给新顶点。？最后，所有边都被删除，只剩一个顶点，游戏结束。游戏得分就是所剩顶点上的整数值。那么这个整数值最大为多少输入第一行为多边形的顶点数 n (nw 20 ),其后有n行，每行为一个整数和一个字符，整数为顶点上的正整数值，字符为该顶点到下一个顶点间连

30、边上的运算符“+”或“*”(最后一个字符为最后一个顶点到第一个顶点间连边上的运算符)。输出输出仅一个整数，即游戏所计算出的最大值。样例输入44 *5 +6 +3 +样例输出70提示小规模问题可不必用动态规划方法编程求解，仅用递归就可以求解。计算中不必考虑计算结果超出整数表达范围的问题，给出的数据能保证计算结果的有效性。在给的例子中，计算过程为 (3+4)*(5+5)=70。源代码:#include<>#include<iostream>#include<string>#include<algorithm>using namespace std;typedef long long int ll;int n;string s;char op110110;ll dp110110, dpmin110110;ll a110;ll calc(ll a, ll b, char ch)if(ch='*')re