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 名。比賽結束后發(fā)現， 只有獲第 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、意味著他們存在著許多共同的興趣。然而作為一個宅男，你發(fā)現自己與他人相互了解的機會并不太多。幸運的是，你意外得到了 一份北大圖書館的圖書借閱記錄，于是你挑燈熬夜地編程，想從中發(fā)現潛在的朋友。首先你對借閱記錄進行了一番整理，把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 、稱體重描述趙、錢、孫、李四個人中既有大人也有小孩，給他們稱體重時發(fā)現，他們每個人的體重都不一樣，且體重(單位：公斤)恰好是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。逆序數越大的排列與原始排列的差異度就越大?，F給定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 中?，F要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存于數組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、提示運用動態(tài)規(guī)劃法進行算法設計并編程實現。源代碼：#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提示小規(guī)模問題可不必用動態(tài)規(guī)劃方法編程求解，僅用遞歸就可以求解。計算中不必考慮計算結果超出整數表達范圍的問題，給出的數據能保證計算結果的有效性。在給的例子中，計算過程為 (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