算法實驗報告

1、課程實驗報告書實驗：2015算法實驗 輸油管道問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。問題如圖：輸油管道問題Time Limit:2000MSMemory Limit:32768KDescription某石油公司計劃建造一條由東向西的主輸油管道。該管道要穿過一個有n 口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置,即它們的x 坐標(biāo)（東西向）和y 坐標(biāo)（南北向）,應(yīng)如何確定主管道的最優(yōu)位置, 即使

2、各油井到主管道之間的輸油管道長度總和最小的位置?證明可在線性時間內(nèi)確定主管道的最優(yōu)位置。 給定n 口油井的位置,計算各油井到主管道之間的輸油管道最小長度總和。要求使用快速排序.Input輸入的第1 行是油井?dāng)?shù)n，1<=n<=10000。接下來n 行是油井的位置，每行2個整數(shù)x和y，-10000<=x，y<=10000。Output輸出油井到主管道之間的輸油管道最小長度總和。Sample Input5 1 22 21 33 -23 3Sample Output6（1） 設(shè)計思路 本題經(jīng)過思考，我們可以很快發(fā)現(xiàn)輸入數(shù)據(jù)的x與題目要求沒有關(guān)系。并得出公式：設(shè)主管道的位置為k，

3、則(yi-k)的和即為答案，經(jīng)過思考，我們可以很快得出，當(dāng)主管道為中位數(shù)時，加和最小，因為如果設(shè)為其他值時，都會多增加過中位數(shù)的數(shù)值。（2）方案最基本的方法是直接快速排序，然后取中間樹，這樣子的時間復(fù)雜度為O（n），但是，仔細(xì)思考一下快速排序的性質(zhì)，我們可以很快發(fā)現(xiàn)更優(yōu)的做法。使用快速排序查找第n/2大的數(shù)值，因為每經(jīng)過一次變換后，我們都能將數(shù)值分成大于關(guān)鍵字的部分，和小于關(guān)鍵字的部分，每次進(jìn)行一次與中間位置的比較，便可以在 O（n）的時間內(nèi)找到第n/2大的值。2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#include<iostream>#inc

4、lude<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define maxn 12000int kmaxn; int Qsort(int a, int low, int high, int dis) if(low >= high) return alow; int first = low; int last = high; int key = afirst;/*用字表的第一個記錄作為樞軸*/ while(first < l

5、ast) while(first < last && alast >= key) -last; afirst = alast;/*將比第一個小的移到低端*/ while(first < last && afirst <= key) +first; alast = afirst; /*將比第一個大的移到高端*/ afirst = key;/*樞軸記錄到位*/if(first>dis) Qsort(a, low, first-1, dis); else Qsort(a, first+1, high, dis);int main()int

6、 n;while(cin>>n)int a,b;for(int i=1;i<=n;i+)cin>>a>>b;ki=b;int mid = Qsort(k, 1, n ,n/2); /找中位數(shù)int ans = 0;for(int i=1;i<=n;i+)ans += abs(ki-mid);cout<<ans<<endl;3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（1） 結(jié)果第一組第二組 數(shù)據(jù)太長，這里只給出結(jié)果（2） 分析、結(jié)論分析：每次運

7、用快速排序找出左邊和右邊，使得只須經(jīng)過O（n）就能找出第k個數(shù)，而不僅僅是中位數(shù)結(jié)論：運用快速排序的單步操作，從而簡化了運行步驟，加快了運行速度石子合并問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。石子合并問題Time Limit:2000MSMemory Limit:30000KDescription在一個圓形操場的四周擺放N堆石子(N100)，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得

8、分。編一程序，讀入堆數(shù)N及每堆石子數(shù)(100)選擇一種合并石子的方案，分別得到合并這N堆石子為一堆，可以得到的最大得分和最小得分Input輸入包含多個例子。第一行為N，即石子堆的數(shù)目，以下一行為N個整形，分別代表每堆石子的數(shù)目。當(dāng)N=0時，輸入結(jié)束。Output對每個例子，輸出其最小得分和最大得分，這兩個數(shù)值以空格間隔開，每個例子占一行。Sample Input630 35 15 5 10 20 31 2 3333 63 4 5 6 7 8 0Sample Output275 4753339 667184 125（2） 設(shè)計思路 由于每次只能選取相鄰的石子進(jìn)行合并，且最多合并n-1次，那么按照

9、運用動態(tài)規(guī)劃的思想，我們可以十分輕松的想到第一維的狀態(tài)為合并石子的數(shù)量，但是一維對于這個問題來說是不夠的，假設(shè)我們要得到合并了k堆的石子，且合并石子的開始位置為i，那么這堆石子必然是以i為開頭，合并數(shù)量為j的石子，和以i+j為開頭，合并數(shù)量為k-j的兩堆石子的合并（當(dāng)然j<k且j從1取致k）狀態(tài)方程也十分容易思考，必然是mins( i , j ) = min mins( i , j ) , mins( ( i+k+1)%n, j-k-1) + i到j(luò)的石子數(shù)量之和 （2）方案運用一個二維數(shù)組對每一維的狀態(tài)進(jìn)行保存，如果覺得需要也可以將空間進(jìn)行壓縮，第一維的大小變?yōu)?，然后交替進(jìn)行數(shù)據(jù)的存

10、儲，這個我們稱為滾動數(shù)組。當(dāng)然也只是進(jìn)行了控件的優(yōu)化而已。2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int INF = 1 << 30; /表明無限大const int N = 105; int minsNN; int maxsNN; int sumN,aN; int minva

11、l,maxval; int n; int getsum(int i,int j) if(i+j >= n) return getsum(i,n-i-1) + getsum(0,(i+j)%n); else return sumi+j - (i>0 ? sumi-1:0); void Work(int a,int n) for(int i=0;i<n;i+) minsi0 = maxsi0 = 0; for(int j=1;j<n;j+) for(int i=0;i<n;i+) minsij = INF; maxsij = 0; for(int k=0;k<j

12、;k+) minsij = min(minsij,minsik + mins(i+k+1)%nj-k-1 + getsum(i,j); maxsij = max(maxsij,maxsik + maxs(i+k+1)%nj-k-1 + getsum(i,j); minval = mins0n-1; maxval = maxs0n-1; for(int i=0;i<n;i+) minval = min(minval,minsin-1); maxval = max(maxval,maxsin-1); int main() while(cin>>n) for(int i=0;i&l

13、t;n;i+) cin>>ai; sum0 = a0; for(int i=1;i<n;i+) sumi = sumi-1 + ai; Work(a,n); printf("%d %dn",minval,maxval); 3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（3） 結(jié)果（4） 分析、結(jié)論分析：運用動態(tài)規(guī)劃對狀態(tài)進(jìn)行存儲，并不斷的地推到下一項結(jié)論：動態(tài)規(guī)劃是一種無后效性的算法。但是能夠處理很多需要遞推的問題最優(yōu)合并1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的

14、設(shè)計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。最優(yōu)合并問題Time Limit:1000MSMemory Limit:30000KDescription給定k個序列s1,s2,s3,.,sk,用二路合并方法將k個序列合并為一個。假設(shè)將任意兩個長度分別為n和m的序列合并為一個需要的代價是m+n-1，設(shè)計一個算法來確定合并這些序列的合并為一個的最大代價和最小代價。Input輸入含有多個例子，每例占有兩行，第一行是一個整數(shù)N，表示序列共有N個，第二行為N個整數(shù)，代表各個序列的長度。N<1000,且每個序列長度都小于

15、1000;輸入以0結(jié)束。Output每個例子輸出占用一行，輸出包含最大代價和最小代價，以空格分離這兩個數(shù)。Sample Input4 5 12 11 2 0Sample Output78 52（3） 設(shè)計思路 我們可以很快發(fā)現(xiàn)，每次取兩個最大值，或者最小值合并后，所得出來的最終價值是最小的。跟哈弗曼編碼一個原因（2）方案運用兩個優(yōu)先隊列來存儲全部的數(shù)值，每次取兩個最大值，和兩個最小值進(jìn)行合并，由于優(yōu)先隊列需要建堆，故時間復(fù)雜度O（nlog（n）2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#include<iostream>#include<c

16、stdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<functional>using namespace std;#define maxn 1010priority_queue<int>q;/最小priority_queue<int,vector<int>,greater<int>>q2;/最大int amaxn;int main()int n;while(cin>&

17、gt;n)if(n=0)break;for(int i = 1; i <= n; i+)cin>>ai;q.push(ai);q2.push(ai);int ans1 = 0,ans2 = 0;for(int i = 1; i < n; i+)int a = q.top();q.pop();int b = q.top();q.pop();ans1+=a+b-1;q.push(a+b);a = q2.top();q2.pop();b = q2.top();q2.pop();q2.push(a+b);ans2+=a+b-1;q.pop();q2.pop();cout<

18、<ans1<<' '<<ans2<<endl;3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（5） 結(jié)果（6） 分析、結(jié)論分析：運用貪心算法，每次取兩個最小數(shù)，由于建堆的時間復(fù)雜度為O(nlog(n)，而pop操作的時間復(fù)雜度為O(log(n)，故總復(fù)雜度為 O(nlog(n)結(jié)論：貪心算法是由我們找出一種最佳途徑并加以證明，從而減小操作數(shù)量的一種算法，有些時候，貪心算法能夠取得很好的效果。 列車問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)

19、計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。列車問題Time Limit:2000MSMemory Limit:30000KDescription從A到B有若干個車站，編號從0到m，列車的最大載客量是n。每次列車開車之前，會從各個車站收集訂票信息。一共有t條訂票信息，一條訂票信息包括：起點站，終點站，人數(shù)。票價在數(shù)值上等于起點站與終點之間的車站數(shù)（包括終點站，不包括起點站）。由于列車的最大載客量是一定的，所以不一定能接受所有的訂票。對于一條訂票order，只能全部接受，或者是全部拒絕?，F(xiàn)在選擇接受訂票使之利潤最大，

20、輸出這個最大利潤.Input含多個例子，每個例子第一行為三個整數(shù)n,m,t,分別代表最大載客量、除A外的車站數(shù)量、訂票信息總量。接下去t行為訂票信息，每一行代表一條訂票信息，一條訂票信息包括三個整數(shù)，分別是起點站編號、終點站編號、人數(shù)。以0 0 0結(jié)束輸入.m<30,t<30。Output每個例子輸出一行，代表最大利潤值。Sample Input10 3 4 0 2 11 3 51 2 72 3 1010 5 43 5 102 4 90 2 52 5 80 0 0Sample Output1934（4） 設(shè)計思路 直接用深度優(yōu)先搜索列出所有情況，容易超時，需要進(jìn)行一些條件的判定，列

21、如，列車的總?cè)藬?shù)不能超過規(guī)定值（2）方案運用深度優(yōu)先搜索列出列車接收的所有情況，并對列車的總?cè)藬?shù)進(jìn)行限制，達(dá)到剪枝的目的2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define maxn 40int n,m,t;int nowmaxn;int maxx;struct ticketint start,end,num;ticmaxn;vo

22、id dfs(int u,int sum)if(sum>maxx)maxx=sum;if(u >= t)return;int i;for(i = ticu.start; i < ticu.end; i+)if(nowi+ticu.num > n)break;if(i >= ticu.end)for(i = ticu.start;i < ticu.end;i+)nowi += ticu.num;dfs(u+1, sum + (ticu.end-ticu.start)*ticu.num);for(i = ticu.start;i < ticu.end;i+

23、)nowi -= ticu.num;dfs(u+1,sum);int main()while(cin>>n>>m>>t)if(n=0)break;maxx=0;for(int i=0;i<t;i+)cin>>tici.start>>tici.end>>tici.num;dfs(0,0);cout<<maxx<<endl;3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（7） 結(jié)果（8） 分析、結(jié)論分析：運用深度優(yōu)先遍歷

24、，可以十分方便的列出所有情況，并進(jìn)行適當(dāng)?shù)募糁Σ僮?，從而減少沒必要的搜索數(shù)目，總的時間復(fù)雜度原為O（2n），但是經(jīng)過剪枝操作，可以在規(guī)定時間內(nèi)跑完。結(jié)論：枚舉所有做法，一般來說是十分無腦的，但是有些時候他能創(chuàng)造奇跡！ 列車問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。列車問題Time Limit:2000MSMemory Limit:30000KDescription從A到B有若干個車站，編號從0到m，列車的最大載客量是n。每次列車開車之前，會從各個車站

25、收集訂票信息。一共有t條訂票信息，一條訂票信息包括：起點站，終點站，人數(shù)。票價在數(shù)值上等于起點站與終點之間的車站數(shù)（包括終點站，不包括起點站）。由于列車的最大載客量是一定的，所以不一定能接受所有的訂票。對于一條訂票order，只能全部接受，或者是全部拒絕?，F(xiàn)在選擇接受訂票使之利潤最大，輸出這個最大利潤.Input含多個例子，每個例子第一行為三個整數(shù)n,m,t,分別代表最大載客量、除A外的車站數(shù)量、訂票信息總量。接下去t行為訂票信息，每一行代表一條訂票信息，一條訂票信息包括三個整數(shù)，分別是起點站編號、終點站編號、人數(shù)。以0 0 0結(jié)束輸入.m<30,t<30。Output每個例子輸出

26、一行，代表最大利潤值。Sample Input10 3 4 0 2 11 3 51 2 72 3 1010 5 43 5 102 4 90 2 52 5 80 0 0Sample Output1934（5） 設(shè)計思路 直接用深度優(yōu)先搜索列出所有情況，容易超時，需要進(jìn)行一些條件的判定，列如，列車的總?cè)藬?shù)不能超過規(guī)定值（2）方案運用深度優(yōu)先搜索列出列車接收的所有情況，并對列車的總?cè)藬?shù)進(jìn)行限制，達(dá)到剪枝的目的2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#include<iostream>#include<cstdio>#include<

27、cstring>#include<algorithm>using namespace std;#define maxn 40int n,m,t;int nowmaxn;int maxx;struct ticketint start,end,num;ticmaxn;void dfs(int u,int sum)if(sum>maxx)maxx=sum;if(u >= t)return;int i;for(i = ticu.start; i < ticu.end; i+)if(nowi+ticu.num > n)break;if(i >= ticu.

28、end)for(i = ticu.start;i < ticu.end;i+)nowi += ticu.num;dfs(u+1, sum + (ticu.end-ticu.start)*ticu.num);for(i = ticu.start;i < ticu.end;i+)nowi -= ticu.num;dfs(u+1,sum);int main()while(cin>>n>>m>>t)if(n=0)break;maxx=0;for(int i=0;i<t;i+)cin>>tici.start>>tici.end

29、>>tici.num;dfs(0,0);cout<<maxx<<endl;3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（9） 結(jié)果（10） 分析、結(jié)論分析：運用深度優(yōu)先遍歷，可以十分方便的列出所有情況，并進(jìn)行適當(dāng)?shù)募糁Σ僮?，從而減少沒必要的搜索數(shù)目，總的時間復(fù)雜度原為O（2n），但是經(jīng)過剪枝操作，可以在規(guī)定時間內(nèi)跑完。結(jié)論：枚舉所有做法，一般來說是十分無腦的，但是有些時候他能創(chuàng)造奇跡！ 漢諾塔問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)計思路、方案/方法并進(jìn)行

30、方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。漢諾塔時間限制：3000 ms  |  內(nèi)存限制：65535 KB描述漢諾塔的規(guī)則這里就不再多說了現(xiàn)在假設(shè)規(guī)定要把所有的金片移動到第三個針上，給你任意一種處于合法狀態(tài)的漢諾塔，你能計算出從當(dāng)前狀態(tài)移動到目標(biāo)狀態(tài)所需要的最少步數(shù)嗎？輸入第一行輸入一個整數(shù)N，表示測試數(shù)據(jù)的組數(shù)(0<N<20)每組測試數(shù)據(jù)的第一行是一個整數(shù)m表示漢諾塔的層數(shù)(0<m<32)，隨后的一行有m個整數(shù)Ai,表示第i小的金片所在的針的編號。（三根針的編號分別為1

31、，2，3）輸出輸出從當(dāng)前狀態(tài)所所有的金片都移動到編號為3的針上所需要的最少總數(shù)樣例輸入231 1 131 1 3樣例輸出73（6） 設(shè)計思路 運用遞推的思想，對于漢諾塔問題，首先我們要關(guān)注的是漢諾塔最大的那塊是否在第三根針上，如果在，則可以直接考慮下一根針。如果不在，我們便要把他移到第三根針上，假設(shè)我們現(xiàn)在要將第k大的移到第三根針上，那么必然我們需要把前k-1個移到第二根針上，這樣，我們只需要增加2(k-1)+1的步數(shù)便可以將全部的移到第三根針上，而如何將前k-1個針移到第二根針上，我們便只需要將第二根針和第三根的位置進(jìn)行調(diào)換，并考慮到下一個狀態(tài)就好了（2）方案遞歸，用一個數(shù)組，記錄所有金片的

32、位置2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std;int ans50;int hanno(int a,int b,int c,int m) if(m=1) if(ansm=c) return 0; else return 1; else if(ansm=c) retu

33、rn hanno(a, b, c, m-1); else if(ansm=a) return hanno(a, c, b, m-1)+(1<<(m-1); else return hanno(b, c, a, m-1)+(1<<(m-1); int main()int t,n;cin>>t;while(t-) memset(ans,0,sizeof(ans); cin>>n; for(int i=1;i<=n;i+) int x; cin>>x; ansi=x; cout<<(hanno(1,2,3,n)<&l

34、t;endl;3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（11） 結(jié)果（12） 分析、結(jié)論分析：運用回溯法，通過底層的狀態(tài)一步一步遞推到我們要求的狀態(tài)。 算法復(fù)雜度O（n）結(jié)論：回溯法能夠求出一些具有遞推性質(zhì)的問題，理論上講，是可以用動態(tài)規(guī)劃進(jìn)行處理。 數(shù)字計數(shù)問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。數(shù)字計數(shù)問題時間限制：3000 ms  |

35、60; 內(nèi)存限制：65535 KB描述一本書的頁碼從自然數(shù)1開始順序編碼到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6頁用數(shù)字6表示，而不是06或者006等。數(shù)字計數(shù)問題要求對給定書的總也碼n，分別計算出0,1，,9總共出現(xiàn)的次數(shù)輸入給定的頁碼n （0<n<10000000）輸出分別輸出0,1，,9出現(xiàn)的總次數(shù)樣例輸入99樣例輸出9 20 20 20 20 20 20 20 20 20要求不能直接從1循環(huán)到n，對每個數(shù)字計算09出現(xiàn)的次數(shù)。（7） 設(shè)計思路 運用遞推的想法由第一位數(shù)字推到最高位（2）方案運用一個數(shù)字記錄數(shù)字的2.過程：實

36、驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std;int ans50;int len, i, k, h, m;int cnt10;int pow1012 = 1,10,100,1000,10000,100000,1000000,10000000,100000000,100000000

37、0;int main()int n;while(cin>>n)memset(cnt,0,sizeof(cnt);char d16;len = log10(n); /* len表示當(dāng)前數(shù)字的位權(quán) */m = len;sprintf(d, "%d", n);k = 0; h = dk - '0' n %= pow10len; while(len > 0) if(h = 0) cnt0 += n + 1;h = d+k - '0'-len;n %= pow10len;continue;for(i = 0; i < 10; i

38、+) cnti += h * len * pow10len-1;for(i = 0; i < h; i+) cnti += pow10len;cnth += n + 1;-len;h = d+k - '0'n %= pow10len;for(i = 0; i <= h; i+) cnti += 1;for(i = 0; i <= m; i+) cnt0 -= pow10i;for(i = 0; i < 10; i+) printf("%d ", cnti);cout<<endl;3.結(jié)果：結(jié)果分析備注：對研究過程中所獲得的

39、主要的數(shù)據(jù)、現(xiàn)象進(jìn)行定性或定量分析，得出結(jié)論和推論。包括但不限于數(shù)據(jù)表、截圖等。（13） 結(jié)果（14） 分析、結(jié)論分析：依舊是遞推，算法復(fù)雜度為O(10) 環(huán)形旅游問題1.思路：實驗所采用的設(shè)計思路和方案/方法備注：說明實驗的設(shè)計思路、方案/方法并進(jìn)行方案選擇。闡明為什么要選擇這個設(shè)計思路和方案/方法完成該實驗，以及所采用設(shè)計思路和方案/方法的特點。環(huán)形旅游描述Arca Carania Mountain國立公園將要開放旅游交通。這個公園有許多值得欣賞的景點，某些景點之間有道路相連。為了方便旅客旅游，公園中設(shè)計了許多環(huán)形的旅游路線，每個環(huán)形旅游路線都是由一個景點開始，經(jīng)過一些其它的不重復(fù)的景點后

40、又回到了最開始的景點。每個環(huán)形旅游路線最少包含三個景點，公園中最少有一條環(huán)形旅游路線。公園執(zhí)行官決定，對于公園中的所有道路，每條道路上的所有汽車都有一個公司負(fù)責(zé)，而且為了公平起見，對于每個環(huán)形線路，每個公司都管理相同數(shù)量的道路。他們發(fā)現(xiàn)要實現(xiàn)這樣的分配非常困難，所以，他們想知道公司數(shù)目為多少時可以滿足以上的分配要求。如樣例輸入1，如下圖所示，總共有3條環(huán)形路線，如果道路1-3被分配了某個公司，同時在環(huán)形路線1-2-3-4-1上也需要分配給該公司最少一條道路，假如這條道路是2-3，那么該公司在環(huán)形線路1-2-3-1上面占據(jù)了兩條道路，因而無法加入其它的公司。在樣例輸入2中，只有一條環(huán)形路線，所以

41、可以將該環(huán)形路線上的道路平均的分配給多個公司。圖-1，樣例輸入1輸入第一行包含兩個整數(shù)，其中表示景點的數(shù)目，表示道路的數(shù)目，隨后有行，每行有兩個整數(shù)，表示景點由一條雙向的道路連接。輸出打印所有的整數(shù)k，滿足按照設(shè)定的方式將公路分配給k個公司，這些整數(shù)按照增序排列。樣例輸入14 51 22 33 41 41 3樣例輸出11樣例輸入26 61 22 31 31 42 53 6樣例輸出21 3（8） 設(shè)計思路 這道題類似與著色問題，但是因為證明沒看懂，只知道做法。 運用tarjon算法找出所有的橋，然后去除這些橋，因為這些去除這些橋后對最終結(jié)果不會又任何影響。接下來我們需要找每條邊的等價類（先去除這

42、條邊，然后找出橋）的規(guī)模（橋的數(shù)量+1）。然后求出所的等價類的規(guī)模后，求出最大公約數(shù)（2）方案同上2.過程：實驗過程備注：重點說明該實驗/設(shè)計是如何實現(xiàn)的，以及其他的實驗過程。#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>using namespace std;const int maxn=1010;int cnt,cnt2,cnt3;int premaxn, dfs_clock, lowmaxn, n, m;bool iscutmaxn;vector<int>gmaxn;pair<int,int>isbri1010;int ansmaxn; /尋找共同類int ans2maxn; /找出除數(shù)void div(int a)for(int i=1;i*i<=a;i+)if(a%i=0)ans2cnt3+=i;if(a/i!=