2017算法設計與應用作業(yè)

1、1 有 52張牌，使它們?nèi)空娉?，第一輪是從? 張開始，凡是2 的倍數(shù)位置上的牌翻成正面朝下；第二輪從第3 張牌開始，凡是3 的倍數(shù)位置上的牌，正面朝上的翻成正面朝下的，正面朝下的翻成正面朝上的；以此類推，直到翻得牌超過104 張為止。統(tǒng)計最后有幾張牌正面朝上以及它們的位置號。問題分析 ： 52 張牌都有一個初始狀態(tài)，即全部朝上。第一輪開始時，2 的倍數(shù)位置改變， 非 2 的倍數(shù)保持原樣；第二輪開始時，3 的奇數(shù)倍朝下，3 的偶數(shù)倍朝上；第三輪開始時，4 的倍數(shù)朝上，即 2 的偶數(shù)倍朝下，以此類推，直到牌數(shù)超過104，則進行狀態(tài)統(tǒng)計。算法設計：根據(jù)題意，首先對第一輪進行記錄，算法則應該是

2、依次對位置進行改變，用循環(huán)求解翻轉問題。算法分析：這個算法使用循環(huán)對牌進行逐層比較，算法復雜度為O（ n+1） ，使用了 52 個空間的一維數(shù)組。數(shù)據(jù)結構設計： 用一維數(shù)組a52 表示 52 張牌， 設其初始狀態(tài)為0。 計數(shù)小于104時，第一輪開始進行翻轉，下一輪即n+1 輪開始分情況進行翻轉，用整型shang進行朝上個數(shù)的統(tǒng)計，位置則由i 來確定。S1While?S2S3算法如下： #include <stdio.h> int main()int a52 = 0; /int shang = 0; /int i = 0;int count= 0;/用一維數(shù)組表示52 張牌， 0 表

3、示正面朝上正面朝上的個數(shù)次數(shù)統(tǒng)計int n=1;while(count <=104)if(n = 1)for(i = n+1;i <=52;+i) if(i%(n+1) = 0) ai-1 = 1;/front-;+count;n+; elsefor(i = n+1 ;i <=52;+i) if(i%(n+1) = 0)(if(ai-1 = 0) ai = 1 ；+count;)else(ai = 0;+count;)n+;)for(i = 0;i < 52;+i)(if(ai = 0)(shang+;)printf(" 正面朝上的撲克有：%dn",

4、shang);printf(" 它們的位置號為：n");for(i = 0;i < 52; +i)if(ai = 0) printf("%dt",i);printf("n");return 0;運行結果如下：1. 鍵盤輸入n 個正整數(shù)，把它們看作一個“數(shù)圈”，求其中連續(xù)4 個數(shù)之和最大者。問題分析 ： 用數(shù) 1 到 n 表示鍵盤輸入的數(shù)，把連續(xù) 4 個數(shù)之和同前后進行比較，求出和最大，可利用二重循環(huán)把所有情況進行列舉。算法設計 ：用 1,2,3 n 代表輸入的數(shù)，其存儲的值代表連續(xù)4個數(shù)之和。第一層循環(huán)：范圍從n 到 n+4；第

5、二層循環(huán)：范圍從1 到 n；最后對和進行比較，然后輸出。算法分析 ：算法效率為O(4n)，存儲空間上有些浪費，可根據(jù)實際情況進行空間分配。數(shù)據(jù)結構設計：首先用一個一維數(shù)組表示鍵盤輸入的數(shù)，定義一個最大數(shù)，設置其初始狀態(tài)為0，把連續(xù) 4 個數(shù)的和用he 表示，再同max進行比較，輸出內(nèi)容就是問題的解。算法如下： #include<stdio.h> int main(void)int ch120, n, i, j, he=0, max=0, maxi;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",

6、&chi);for(i=n;i<n+4;i+) chi=chi-n;for(i=0;i<n;i+)he=chi+chi+1+chi+2+chi+3;if(he>max)max=he; maxi=i;i=maxi;printf(" 最大和 =%d+%d+%d+%d=%dn", chi,ch(i+1)%n,ch(i+2)%n,ch(i+3)%n,he);return 0;運行結果如下：2. 有一堆棋子，2 枚 2 枚地數(shù)，最后余1 枚； 3 枚 3 枚地數(shù)，最后余2 枚； 5 枚5 枚地數(shù)，最后余4 枚； 6 枚 6 枚地數(shù)，最后余5 枚； 7 枚 7

7、 枚地數(shù)，最后正好數(shù)完，編程完成這堆棋子最少有多少枚棋子。問題分析 ：用 n 表示棋子數(shù)，要求可以7 枚 7 枚的數(shù)，因此棋子數(shù)至少為7，問題可以用條件語句進行求解。算法設計 ：用 7 到 n 表示棋子數(shù)，余數(shù)表示剩余的棋子數(shù)。設置棋子數(shù)的范圍， 因為不知道具體有多少，所以盡可能的大一點，然后進行情況判別。算法分析：算法比較簡單，但由于預先不知道棋子數(shù)，因此效率比較差。數(shù)據(jù)結構分析：首先預確定一個棋子數(shù)的范圍，分別對2、 3、 5、 7 進行取余，符合情況則輸出棋子數(shù)n，不符合則加1，繼續(xù)進行判斷，輸出結構符合問題要求。算法如下 ：#include<stdio.h>int main

8、(void)int n=7;while(n<1000)if(n%2=1&&n%3=2&&n%5=4&&n%6=5&&n%7=0)printf("%dn",n);break;else n+;return 0;運行結果如下：3. 利用分治法求一組數(shù)據(jù)中最大的兩個數(shù)和最小的兩個數(shù)。問題分析：用n 表示輸入的數(shù)，最大的兩個數(shù)和最小的兩個數(shù)可用循環(huán)進行情況列舉。算法設計：用分治法可以用較少的比較次數(shù)解決上述問題。問題可以簡化為求最大值和最小值，再把這種情況除外，再求其最大值和最小值。算法分析：算法中需要n-1 次比

9、較，才能得到第一個最大最小值，需要n-2 次比 較得到第二個最大最小值。數(shù)據(jù)結構設計：把輸入的數(shù)存入一維數(shù)組ch ，首先對兩個數(shù)進行比較，然后大的數(shù)或者小的數(shù)同下一個比較，直到輸出最大的數(shù)max1和最小的數(shù)min1；下一次繼續(xù)進行循環(huán)比較，輸出最大的數(shù)max2和最小的數(shù)min2。算法如下 ：#include <stdio.h>int main(void)int ch20, n,i,max1=0,max2=0,min1=0,min2=0;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&c

10、hi);for(i=0;i<n;i+)if(chmax1<chi)max1=i;if(chmin1>chi)min1=i;if(max1=0)max2=1;if(min1=0)min2=1;for(i=0;i<n;i+)if(i=max1|i=min1)continue;if(chmax2<chi)max2=i;if(chmin2>chi)min2=i;printf("max1=%d max2=%d min1=%d min2=%d",chmax1,chmax2,chmin1,chmin2);return 0;4. 等分液體，在一個瓶子中裝

11、有8N（ N 為偶數(shù)）升汽油，要平均分成兩份，但只有一個裝3（ N/2-1 ）升的量杯和裝5（ N/2+1）升的量杯（都沒有刻度）。打印出所有把汽油分成兩等份的操作過程。若無解打印“NO”，否則打印操作過程 。問題分析 ： 將 8 升汽油平分裝入兩個不同容量的容器，在沒有刻度的情況下，一次就平分是不行的，需要利用容器的差異性多次進行最后達到平分，可以通過分析具體情況達到目的。算法設計： 利用深度優(yōu)先算法進行搜索，不滿足均分條件時則及時進行回溯，當滿足問題的解則結束。算法分析：這個算法比較簡單，利用條件分支進行判斷，來保證不漏判。數(shù)據(jù)結構分析：將三個容器的容量定義為常量，在定義兩個變量b 和 c 來確定瓶中實際的重量。根據(jù)確定量的不同情況進行分配，最后達到均分的效果。算法如下：#include <stdio.h>int p=4;int main（）int a=8,y=3,z=5;void fen(int a,int y,int z);fen(a,y,z);fen(a,z,y);return 0;void fen(int a,int y,int z)int b=0,c=0;printf("a ： %d b：