算法實(shí)驗(yàn)二(題庫(kù))二

南通大學(xué)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告姓 名：鹿瑤班 級(jí)：軟件工程122學(xué) 號(hào)：1213042037日 期：2014.12.16目錄Question-2編程實(shí)現(xiàn)循環(huán)賽日程表（分治法）……3Question-3編程實(shí)現(xiàn)最長(zhǎng)公共子序列（動(dòng)態(tài)規(guī)劃）………………3Question-4TheTriangle（動(dòng)態(tài)規(guī)劃）………………4Question-5超級(jí)臺(tái)階（動(dòng)態(tài)規(guī)劃）…………………5Question-6最大和（動(dòng)態(tài)規(guī)劃）……6Question-7劍客決斗（動(dòng)態(tài)規(guī)劃）…………………7Question-8最長(zhǎng)上升子序列問題（動(dòng)態(tài)規(guī)劃）……8Question-9獨(dú)木舟上的旅行（貪婪法）……………9Question-10背包問題（貪心算法）………………10Question-11田忌賽馬（動(dòng)規(guī)中的貪心算法）……10Question-12硬幣問題（貪心算法）………………11附：源代碼……………12Question-2編程實(shí)現(xiàn)循環(huán)賽日程表（分治法）描述設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，先要設(shè)計(jì)一個(gè)滿足一下要求的比賽日常表：（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次（2）每個(gè)選手一天只能賽一次（3）循環(huán)賽一共進(jìn)行n-1天算法設(shè)計(jì)將n*n個(gè)格子，也就是n階方陣從中間十字劃分，一次劃分分成四塊，令其右上角和左下角的數(shù)據(jù)完全相同，右下角和左上角的數(shù)據(jù)完全相同；每次劃分都得到了若干個(gè)n/2階的方陣，然后對(duì)這些方陣進(jìn)行操作，繼續(xù)令其右上角和左下角的數(shù)據(jù)完全相同，右下角和左上角的數(shù)據(jù)完全相同，如此循環(huán)下去，直至n<2時(shí)結(jié)束遞歸。運(yùn)行結(jié)果Question-3編程實(shí)現(xiàn)最長(zhǎng)公共子序列（動(dòng)態(tài)規(guī)劃）描述如題，需要你做的就是寫一個(gè)程序，得出最長(zhǎng)公共子序列。tip：最長(zhǎng)公共子序列也稱作最長(zhǎng)公共子串(不要求連續(xù))，英文縮寫為L(zhǎng)CS（LongestCommonSubsequence）。其定義是，一個(gè)序列S，如果分別是兩個(gè)或多個(gè)已知序列的子序列，且是所有符合此條件序列中最長(zhǎng)的，則S稱為已知序列的最長(zhǎng)公共子序列。輸入第一行給出一個(gè)整數(shù)N(0<N<100)表示待測(cè)數(shù)據(jù)組數(shù)接下來每組數(shù)據(jù)兩行，分別為待測(cè)的兩組字符串。每個(gè)字符串長(zhǎng)度不大于1000.算法設(shè)計(jì)由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)xm≠yn時(shí)，必須解兩個(gè)子問題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的一個(gè)最長(zhǎng)公共子序列。

由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問題具有子問題重疊性質(zhì)。例如，在計(jì)算X和Y的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出X和Yn-1及Xm-1和Y的最長(zhǎng)公共子序列。而這兩個(gè)子問題都包含一個(gè)公共子問題，即計(jì)算Xm-1和Yn-1的最長(zhǎng)公共子序列。與矩陣連乘積最優(yōu)計(jì)算次序問題類似，我們來建立子問題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，故c[i,j]=0。其他情況下，由定理可建立遞歸關(guān)系如下：運(yùn)行結(jié)果：Question-4TheTriangle（動(dòng)態(tài)規(guī)劃）描述738810274445265在上圖所示的三角形中，從頂部到底部，找一條路線，使得它的和最大。當(dāng)然，每一步只能走左下或者右下。算法分析利用動(dòng)態(tài)規(guī)劃的基本步驟來分析，首先找出最優(yōu)解結(jié)構(gòu)，l[i]表示1到i層路徑的最優(yōu)解，則l[i-1]亦為最優(yōu)解(證明：如果l[i-1]不為最優(yōu)解，則1到i-1層有另外一條路徑使得l[i-1]為最優(yōu)解，這樣就會(huì)致使l[i]路徑不為最優(yōu)解，矛盾)。最優(yōu)解結(jié)構(gòu)：這里用一位數(shù)組存儲(chǔ)數(shù)字三角形。運(yùn)行結(jié)果Question-5超級(jí)臺(tái)階（動(dòng)態(tài)規(guī)劃）描述有一樓梯共m級(jí)，剛開始時(shí)你在第一級(jí)，若每次只能跨上一級(jí)或二級(jí)，要走上第m級(jí)，共有多少走法？注：規(guī)定從一級(jí)到一級(jí)有0種走法。輸入輸入數(shù)據(jù)首先包含一個(gè)整數(shù)n(1<=n<=100)，表示測(cè)試實(shí)例的個(gè)數(shù)，然后是n行數(shù)據(jù)，每行包含一個(gè)整數(shù)m，（1<=m<=40),表示樓梯的級(jí)數(shù)。輸出對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出不同走法的數(shù)量。（即有兩個(gè)不同的樓梯，一個(gè)樓梯有2級(jí)，一個(gè)樓梯有3級(jí)）算法設(shè)計(jì)只能說這題有一點(diǎn)DP的思想。。簡(jiǎn)單遞歸運(yùn)行結(jié)果Question-6最大和（動(dòng)態(tài)規(guī)劃）描述給定一個(gè)由整數(shù)組成二維矩陣（r*c），現(xiàn)在需要找出它的一個(gè)子矩陣，使得這個(gè)子矩陣內(nèi)的所有元素之和最大，并把這個(gè)子矩陣稱為最大子矩陣。例子：0-2-7092-62-41-41-180-2其最大子矩陣為：92-41-18其元素總和為15。輸入第一行輸入一個(gè)整數(shù)n（0<n<=100）,表示有n組測(cè)試數(shù)據(jù)；每組測(cè)試數(shù)據(jù)：第一行有兩個(gè)的整數(shù)r，c（0<r,c<=100），r、c分別代表矩陣的行和列；隨后有r行，每行有c個(gè)整數(shù)；輸出輸出矩陣的最大子矩陣的元素之和。算法分析用2維數(shù)組a[1:

m][1:

n]表示給定的m行n列的整數(shù)矩陣。子數(shù)組a[i1

:i2][j1

:j2]表示左上角和右下角行列坐標(biāo)分別為(i1,j1)和(i2,j2)的子矩陣，其各元素之和記為：（1）最大子矩陣和問題的最優(yōu)解即為：（2）（3）如果令：（4）那么式（4）就是我們熟悉的最大子序列和的問題。根據(jù)以上分析我們可得到最大子矩陣和問題的算法：運(yùn)行結(jié)果Question-7劍客決斗（動(dòng)態(tài)規(guī)劃）描述在路易十三和紅衣主教黎塞留當(dāng)權(quán)的時(shí)代，發(fā)生了一場(chǎng)決斗。n個(gè)人站成一個(gè)圈，依次抽簽。抽中的人和他右邊的人決斗，負(fù)者出圈。這場(chǎng)決斗的最終結(jié)果關(guān)鍵取決于決斗的順序?，F(xiàn)書籍任意兩決斗中誰(shuí)能勝出的信息，但“A贏了B”這種關(guān)系沒有傳遞性。例如，A比B強(qiáng)，B比C強(qiáng)，C比A強(qiáng)。如果A和B先決斗，C最終會(huì)贏，但如果B和C決斗在先，則最后A會(huì)贏。顯然，他們?nèi)酥械牡谝粓?chǎng)決斗直接影響最終結(jié)果。假設(shè)現(xiàn)在n個(gè)人圍成一個(gè)圈，按順序編上編號(hào)1~n。一共進(jìn)行n-1場(chǎng)決斗。第一場(chǎng)，其中一人（設(shè)i號(hào)）和他右邊的人（即i+1號(hào)，若i=n，其右邊人則為1號(hào)）。負(fù)者被淘汰出圈外，由他旁邊的人補(bǔ)上他的位置。已知n個(gè)人之間的強(qiáng)弱關(guān)系（即任意兩個(gè)人之間輸贏關(guān)系）。如果存在一種抽簽方式使第k個(gè)人可能勝出，則我們說第k人有可能勝出，我們的任務(wù)是根據(jù)n個(gè)人的強(qiáng)弱關(guān)系，判斷可能勝出的人數(shù)。輸入第一行是一個(gè)整數(shù)N(1<=N<=20)表示測(cè)試數(shù)據(jù)的組數(shù)。第二行是一個(gè)整數(shù)n表示決斗的總?cè)藬?shù)。(2<=n<=500)隨后的n行是一個(gè)n行n列的矩陣，矩陣中的第i行第j列如果為1表示第i個(gè)人與第j個(gè)人決斗時(shí)第i個(gè)人會(huì)勝出，為0則表示第i個(gè)人與第j個(gè)人決斗時(shí)第i個(gè)人會(huì)失敗。輸出對(duì)于每組測(cè)試數(shù)據(jù)，輸出可能勝出的人數(shù)，每組輸出占一行。算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃（弗洛伊德），可以把一圈人從x分為兩端都是x的一條線，x向中間打若最終x能遇到x則說明x可以取得勝利，中間得到meet[i][j]的轉(zhuǎn)移方程有點(diǎn)像弗洛伊德算法，從中間找可以作為媒介的點(diǎn)，然后更新meet數(shù)組。因?yàn)槭窃谌锼砸⒁?操作。運(yùn)行結(jié)果Question-8最長(zhǎng)上升子序列問題（動(dòng)態(tài)規(guī)劃）描述有一個(gè)長(zhǎng)為n的數(shù)列a0,a1,??,an-1。請(qǐng)求出這個(gè)序列中最長(zhǎng)的上升子序列的長(zhǎng)度。上升子序列指的是對(duì)于任意的i<j都滿足ai<aj的子序列。（1≤n≤1000，0≤ai≤1000000）。輸入第一行為n，下面一行為a0~an-1。輸出最長(zhǎng)上升子序列的長(zhǎng)度。算法設(shè)計(jì)我們依次遍歷整個(gè)序列，每一次求出從第一個(gè)數(shù)到當(dāng)前這個(gè)數(shù)的最長(zhǎng)上升子序列，直至遍歷到最后一個(gè)數(shù)字為止，然后再取dp數(shù)組里最大的那個(gè)即為整個(gè)序列的最長(zhǎng)上升子序列。我們用dp[i]來存放序列1-i的最長(zhǎng)上升子序列的長(zhǎng)度，那么dp[i]=max(dp[j])+1,(j∈[1,i-1]);顯然dp[1]=1,我們從i=2開始遍歷后面的元素即可。運(yùn)行結(jié)果：Question-9獨(dú)木舟上的旅行（貪婪法）描述進(jìn)行一次獨(dú)木舟的旅行活動(dòng)，獨(dú)木舟可以在港口租到，并且之間沒有區(qū)別。一條獨(dú)木舟最多只能乘坐兩個(gè)人，且乘客的總重量不能超過獨(dú)木舟的最大承載量。我們要盡量減少這次活動(dòng)中的花銷，所以要找出可以安置所有旅客的最少的獨(dú)木舟條數(shù)?，F(xiàn)在請(qǐng)寫一個(gè)程序，讀入獨(dú)木舟的最大承載量、旅客數(shù)目和每位旅客的重量。根據(jù)給出的規(guī)則，計(jì)算要安置所有旅客必須的最少的獨(dú)木舟條數(shù)，并輸出結(jié)果。輸入第一行輸入s,表示測(cè)試數(shù)據(jù)的組數(shù)；每組數(shù)據(jù)的第一行包括兩個(gè)整數(shù)w，n，80<=w<=200,1<=n<=300，w為一條獨(dú)木舟的最大承載量,n為人數(shù)；接下來的一組數(shù)據(jù)為每個(gè)人的重量（不能大于船的承載量）。輸出每組人數(shù)所需要的最少獨(dú)木舟的條數(shù)。算法設(shè)計(jì)先把各個(gè)人的體重排序，然后計(jì)算最重的人和最輕的人能否同乘一條舟，如果不能，則最重的人就要單獨(dú)乘坐一條舟，再求最輕的和第二重的人的和，依次比較。運(yùn)行結(jié)果Question-10背包問題（貪心算法）描述現(xiàn)在有很多物品（它們是可以分割的），我們知道它們每個(gè)物品的單位重量的價(jià)值v和重量w（1<=v,w<=10）；如果給你一個(gè)背包它能容納的重量為m（10<=m<=20）,你所要做的就是把物品裝到背包里，使背包里的物品的價(jià)值總和最大。輸入第一行輸入一個(gè)正整數(shù)n（1<=n<=5）,表示有n組測(cè)試數(shù)據(jù)；隨后有n測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)的第一行有兩個(gè)正整數(shù)s，m（1<=s<=10）;s表示有s個(gè)物品。接下來的s行每行有兩個(gè)正整數(shù)v，w。輸出輸出每組測(cè)試數(shù)據(jù)中背包內(nèi)的物品的價(jià)值和，每次輸出占一行。算法設(shè)計(jì)貪心原理，要求背包物品總價(jià)值最大，故盡可能多存放價(jià)值大的物品；如圖題目中給出的例子，背包可容納重量15，故先放價(jià)值最大的A，將10斤A全部放入背包，然后放入價(jià)值次大的C，此時(shí)背包容納量剩下15-10=5，而C還有9斤，因此剩下的全放C，總價(jià)值=（10*5）+（5*3）=65。運(yùn)行結(jié)果Question-11田忌賽馬（動(dòng)規(guī)中的貪心算法）描述田忌賽馬的故事大家應(yīng)該都聽過吧。田忌經(jīng)常與齊國(guó)眾公子賽馬，設(shè)重金賭注。孫臏發(fā)現(xiàn)他們的馬腳力都差不多，馬可分為上、中、下三等。于是孫臏對(duì)田忌說：“您只管下大賭注，我能讓您取勝?！碧锛上嘈挪⒋饝?yīng)了他，與齊王和諸公子用千金來賭注。比賽即將開始，孫臏說：“現(xiàn)在用您的下等馬對(duì)付他們的上等馬，拿您的上等馬對(duì)付他們的中等馬，拿您的中等馬對(duì)付他們的下等馬。”已經(jīng)比了三場(chǎng)比賽，田忌一場(chǎng)敗而兩場(chǎng)勝，最終贏得齊王的千金賭注。現(xiàn)在題目的要求是這樣的，給出田忌n匹馬的速度，再給出公子n匹馬的速度，運(yùn)用上述思想，求田忌最多能贏幾場(chǎng)比賽。我們規(guī)定，贏一場(chǎng)可得200兩黃金，輸一場(chǎng)就扣200量黃金。平局不得也不扣。求田忌最多能贏多少黃金。輸入測(cè)試數(shù)據(jù)有多個(gè)。每組測(cè)試數(shù)據(jù)的第一行是為n的正整數(shù)。(1<=n<=1000)，接下來的兩行為馬的速度。第一行為田忌的n匹馬的速度，第二行為公子的n匹馬的速度。輸出對(duì)于每一個(gè)測(cè)試用例，每行輸出一個(gè)數(shù)，該數(shù)為田忌所能贏的最多的黃金數(shù)。算法設(shè)計(jì)1如果田忌的慢馬比齊王的慢馬快，直接比賽。贏的代價(jià)?。?/p>

2如果田忌的慢馬比齊王的慢馬慢，讓他和齊王的快馬比賽。輸?shù)闹担?/p>

3如果田忌的慢馬的速度等于齊王的慢馬

1）如果田忌的快馬比齊王的快馬快，直接比賽。贏！

2）如果田忌的慢馬比齊王的快馬慢，那讓他和齊王最快的馬比賽。輸?shù)闹担?/p>

3）其他情況，直接退出。統(tǒng)計(jì)比賽結(jié)果，算錢！運(yùn)行結(jié)果Question-12硬幣問題（貪心算法）描述有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚?，F(xiàn)在要用這些硬幣來支付A元、最少需要多少枚硬幣？假定本題至少存在一種支付方案。輸入第一行n為測(cè)試數(shù)據(jù)的組數(shù)。以下各行依次為：C1C5C10C50C100C500A輸出每行輸出需要最少的硬幣數(shù)算法設(shè)計(jì)由貪心算法可知盡量用大面值的硬幣組合來找錢，可以使使用的硬幣最少。而貪心算法對(duì)最少硬幣問題的解決總是可以得到最優(yōu)解很好的近似解。

本算法就是用貪心策略枚舉出所有近似最優(yōu)解，然后從中尋找到問題的最優(yōu)解

尋找近似最優(yōu)解群

。將硬幣依面值大小排序

(2)按面值種類劃分不同情況

有多少種面值就劃分多少種情況.

每種情況的第一枚硬幣面值各不一樣,其后對(duì)剩余的硬幣按面值從大到小排列。運(yùn)行結(jié)果附：源代碼Question-2#include<iostream>usingnamespacestd;#defineMAX100//定義每組比賽成員的結(jié)構(gòu)類型typedefstructnode{intp1;intp2;}team;teamX[MAX][MAX/2+1];//X為解向量x[i][j]表示第i天第j場(chǎng)次現(xiàn)在賽的情況x[i][j].p1和x[i][j].p2intnum,t[MAX];//num表示比賽人數(shù)t[]分別表示每天比賽的場(chǎng)次數(shù)初始化為0voidInit(){cout<<"請(qǐng)輸入運(yùn)動(dòng)員人數(shù):";cin>>num;for(inti=0;i<MAX;i++)t[i]=0;}voidf(intfrom,intto,intday)//編號(hào)為from到to的n（n=to-from+1）個(gè)人從第day天開始比賽，全部安排下去的函數(shù){intn=to-from+1,i,k;if(n<2)return;if(n==2)//只有兩人，直接在第day天安排比賽，比賽場(chǎng)次為++t[day]{X[day][++t[day]].p1=from;X[day][t[day]].p2=to;}if(n>2)//超過兩人，才分成兩組{intmid=from+n/2-1;f(from,mid,day);//組內(nèi)比賽f(mid+1,to,day);//組內(nèi)比賽//以下是組間比賽for(k=0;k<=n/2;k++)//在后n/2天內(nèi)，分別與組2內(nèi)隊(duì)員(j+i+k)%(n/2)進(jìn)行組間比賽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;}}}voidOutput(){cout<<"比賽安排如下:\n";for(inti=1;i<=num;i++){cout<<"第"<<i<<"天："<<endl;for(intj=1;j<=t[i];j++){cout<<j<<':'<<'('<<X[i][j].p1<<','<<X[i][j].p2<<')'<<'';}cout<<endl;}}intmain(){intz;Init();//初始化f(1,num,1);//從1到num個(gè)人從第一天開始調(diào)用函數(shù)Output();cout<<"輸入任意字符結(jié)束...";cin>>z;return0;}Question-3#include<iostream>#include<cstring>#defineN100usingnamespacestd;inta[N][N];chars1[N],s2[N];intmax(inta,intb){returna>=b?a:b;}intmain(){intcount,i,j,length1,length2,z; cout<<"請(qǐng)輸入需要測(cè)試幾組數(shù)據(jù)：";cin>>count;while(count--){intcount=1; cout<<"請(qǐng)輸入第"<<count<<"組待測(cè)序列:"<<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; }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;}elsea[i][j]=max(a[i-1][j],a[i][j-1]);}}cout<<"最長(zhǎng)公共子序列長(zhǎng)度為："<<a[length1][length2]<<endl<<endl; count++;} cout<<"輸入任意字符結(jié)束..."; cin>>z;return0;}Question-4#include<iostream>#defineN105usingnamespacestd;inta[N][N],dp[N][N],z;intmain(){intn,i,j,min;cout<<"輸入行數(shù):";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; } }intans=0;for(i=1;i<=n;i++)if(ans<dp[n][i]) ans=dp[n][i];cout<<"自上而下路徑最大和為："<<ans<<endl;//最大和} cout<<"輸入任意字符結(jié)束..."; cin>>z;return0;}Question-5#include<iostream>usingnamespacestd;intmain(){intN;cout<<"請(qǐng)輸入測(cè)試實(shí)例個(gè)數(shù)：";cin>>N;__int64array[1024];memset(array,0,1024);cout<<"請(qǐng)輸入每個(gè)實(shí)例的樓梯級(jí)數(shù)：";while(N--){intsum=0;cin>>sum;array[2]=1;array[1]=1;for(intindex=3;index<=sum;index++){array[index]=array[index-1]+array[index-2];}cout<<array[sum]<<'';}cout<<endl;system("pause");return0;}Question-6#include<stdio.h>#include<string.h>#include<iostream>#include<string>usingnamespacestd;inta[102][102];intmain(){inti,j,k,m,r,c,max,temp,z,n; cout<<"請(qǐng)輸入待測(cè)矩陣個(gè)數(shù)n："; cin>>n;for(intcount=0;count<n;count++) { cout<<"輸入第"<<count+1<<"個(gè)矩陣行數(shù)：";cin>>r; cout<<endl; cout<<"輸入第"<<count+1<<"個(gè)矩陣列數(shù)："; 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<<"輸入任意字符結(jié)束..."; cin>>z;}Question-7#include<stdio.h>#include<string.h>#include<stdlib.h>intfight[501][501],meet[501][501],n;//fight[i][j]:i與jPK能否獲勝，meet[i][j]：i，j能否遇到intmain(){ printf("請(qǐng)輸入測(cè)試數(shù)據(jù)的組數(shù)和決斗的總?cè)藬?shù)：\n");inti,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++)//初始化（相鄰的兩個(gè)人一定能相遇） { meet[i][(i+1)%n]=1; }for(i=2;i<=n;i++)//間隔的人數(shù) {for(j=0;j<n;j++)//起始位置 { k=(j+i)%n;//結(jié)束位置for(m=(j+1)%n;m!=k;m=(m+1)%n) {if(meet[j][m]&&meet[m][k]&&(fight[j][m]||fight[k][m]))//注意當(dāng)i和m相遇且j和m相遇時(shí)只要i和j有一個(gè)贏i，j就可相遇（就算有一個(gè)敗了另一個(gè)也能贏得m遇見它） { meet[j][k]=1;break; } } } } cnt=0;for(i=0;i<n;i++) {if(meet[i][i])//能和自己相遇就可能勝利 { cnt++; } } printf("可能勝出的人數(shù)為：%d\n",cnt); } printf("輸入任意字符結(jié)束..."); scanf("%d",&z);return0;}Question-8#include<iostream>usingnamespacestd;intmain(){inta[100],f[100],n,i,j,z; cin>>n;for(inti=0;i<n;i++) cin>>a[i];intmax=1;f[0]=1;for(i=1;i<n;i++) {inttm=0;for(j=i-1;j>=0;j--) {if(a[j]<a[i]&&f[j]>tm) tm=f[j]; } f[i]=tm+1;if(f[i]>max) max=f[i]; } cout<<"最長(zhǎng)上升子序列長(zhǎng)度為："<<max<<endl; cout<<"輸入任意字符結(jié)束..."; cin>>z;return0;}Question-9#include<stdio.h>intmain(){intn,w,m,i,a[300],t,z; printf("請(qǐng)輸入為一條獨(dú)木舟的最大承載量和人數(shù)："); scanf("%d",&n);while(n--){scanf("%d%d",&w,&m);intk=0,j=0; printf("請(qǐng)輸入每個(gè)人的重量：");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;}/*對(duì)體重排序*/for(i=0,j=m-1;i<=j;){if(a[i]+a[j]<=w){i++;j--;k++;}/*如果可以，讓他們兩個(gè)同乘一條，再比較第二輕和第二重的人，以此類推*/elseif(i==j)k++;/*就剩一個(gè)人的時(shí)候，他自己?jiǎn)为?dú)一條*/else{j--;k++;}/*重的人自己?jiǎn)为?dú)一條舟*/}printf("要安置所有旅客必須的最少的獨(dú)木舟條數(shù)為：%d\n",k);} printf("輸入任意字符結(jié)束..."); scanf("%d",&z);return0;}Question-10#include<iostream>#include<algorithm>#include<cstdio>#include<cstdlib>usingnamespacestd;typedefstructGOODS{intv,w;//價(jià)值和重量都比較小<256}GOODS;GOODSgoods[10];intcmp(constvoid*a,constvoid*b){return(*(GOODS*)a).v<(*(GOODS*)b).v?1:-1;}intmain(){ints,n,m,i,z;intvalue,weight; printf("請(qǐng)輸入共幾組待測(cè)數(shù)據(jù)：");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);//將物品按價(jià)值從大到小排序//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)//這種物品的總質(zhì)量還小與目前背包容納量，則全部裝入 { m-=goods[i].w; value+=goods[i].v*goods[i].w;//w重量的單價(jià)為v的物品價(jià)值 }else//將背包剩下的容量全部裝這種物品 { value+=goods[i].v*m; m=0; } i++; } printf("此組測(cè)試數(shù)據(jù)中背包內(nèi)的物品的價(jià)值和為：%d\n"