1、算法與程序設計實驗報告二(4學時)實驗目的：1、掌握迭代算法的三方面工作；2、了解遞推算法，掌握遞推算法的思想；3、 掌握遞歸算法的程序編寫；。4、了解分治算法的思想；5、熟練使用二分查找方法實現代碼的編寫。實驗內容：1、n!的遞歸算法的編寫2、裴波那契(Fibonacci)數列的定義為：它的第 1項和第2項均為1，以后各項為其前兩項之和。若裴波那契數列中的第n項用Fib(n)表示，則計算公式為：.1(n=1 或 2)Fib( n)=“Fib( n-1)+Fib( n-2)(n=2)試編寫出計算Fib( n)的遞歸算法3、在一個給定的n個元素的有序序列中查找出與給定關鍵字x相同的元素的具體位置

2、。即輸入一個n個元素的序列,其中n個元素是按從小到大的順序排 列的，查找是否存在給定的值X。實驗代碼：1、n!的遞歸算法的編寫。#i ncludeint digu i(int n)if(n=1)return 1;elsereturn n *digu i(n-1);void mai n()sca nf(%d,&n); printf(結果為：%dn,digui(n);2、計算Fib(n)的遞歸算法1 / 11#i ncludelong Fib( int n ) if ( n=1 | n=2 )/終止遞歸條件return 1;elsereturnFib( n-1)+Fib( n-2); |scan

3、f(%d,&n); printf(”裴波那契數列第 %d項值為%ldn,n,Fib(n);3、二分查找法的實現。#i ncludeint BinarySearch(int a,int n,int x) /* 二分查找功能函數 */int l=0,r =n ,i;while(l=r)i=(l+r)/2 ;if(x=ai) return i;else if (xai) r=i-1;else l=i+1;return -1;void maopao(int a)/*冒泡排序功能函數*/int i,j;int n=10;for(i=0;i n;i+)for(j=0;jaj+1)int temp;temp

4、=aj;aj=aj+1;aj+1=temp;void mai n()int i,a10,x;2 / 11int flag=-1;printf(請輸入10個帶查找數據(空格分隔)：”)； for(i=0;i10;i+) |scan f(%d,&ai);maopao(a);printf(帶查序列有序化后變?yōu)椋骸?； for(i=0;i10;i+)prin tf(%d,ai);prin tf(n);printf(請輸入待查關鍵字:);scan f(%d，& x);flag=B in arySearch(a,10,x);if(flag=-1)printf(未找到帶查關鍵字！n ”);elseprint

5、f(找到關鍵字，位于有序序列的第%d個位置！ n,flag+1);算法與程序設計實驗報告三（4學時）實驗目的：6、了解貪心算法思想7、掌握貪心法典型問題，如背包問題、作業(yè)調度問題等。實驗內容：4、鍵盤輸入一個高精度的正整數 n （*10位）去掉任意s個數字后剩下的數字按原左右次序組成一個新的正整數。編程對給定的n和s,尋找一種方案，使得剩下的數最小。5、設計實現超市收銀程序，假設顧客在超市購買各種商品，來到收銀臺結賬，收銀員具有面值為100，20， 10，5和1元的紙幣和各種面值為 5角、2角、1角的硬幣。 設計程序計算顧客各種所買商品的錢數，并根據顧客所付的錢數輸出零錢的數目及 要找的各種貨

6、幣的數目。算法思想：貪心算法的基本思路1建立數學模型來描述問題。2. 把求解的問題分成若干個子問題。3對每一子問題求解，得到子問題的局部最優(yōu)解。4. 把子問題的解局部最優(yōu)解合成原來解問題的一個解。實驗代碼：1鍵盤輸入一個高精度的正整數n (n10位)去掉任意s個數字后剩下的數字按原左右次序組成一個新的正整數。編程對給定的n和s,尋找一種方案，使得剩下的數最小。#in clude#in elude #define M 100main() char chM;int rM, dM,l, s,i,j,k;printf( 請輸入正整數： );gets(ch);printf( 請輸入刪除的位數： );sc

7、anf(%d,&s);l=0;for(i=0;chi!=0;i+)ri=i;l+;for(i=0;is;i+)for(j=0;jchj+1)break;if(j=l-i)k=l-i-1;else k=j;di=rk;for(j=k;jl-i-1;j+)chj=chj+1;rj=rj+1;chj=0;printf(”刪除%d后最小的整數為:%sn,s,ch);printf( 刪除的數位為 :);for(i=0;is;i+)printf(%dt,di+1);printf(n);return 0 ;2. 設計實現超市收銀程序,假設顧客在超市購買各種商品,來到收銀臺結賬,收銀員具有 面值為 100,

8、20, 10, 5和 1 元的紙幣和各種面值為 5 角、2角、1 角的硬幣。設計程序計 算顧客各種所買商品的錢數, 并根據顧客所付的錢數輸出零錢的數目及要找的各種貨幣的數目。#include#include void main()double price,total=0,givemoney,leamoney; int n,i,k=0,m=0,x=0,y=0;printf( 請輸入商品的數目 :); scanf(%d,&n);printf( 輸入每件商品的價格 :n); for(i=1;i=100) leamoney=leamoney-100;k+; if(leamoney=20) leamon

9、ey=leamoney-20; x+;if(leamoney=10) leamoney=leamoney-10;printf(10 元=1 張n); while(leamoney=5)leamoney=leamoney-5; printf(5 元=1 張 n);while(leamoney=1) leamoney=leamoney-1; m+;if(leamoney=0.5)leamoney=leamoney-0.5;printf(5 角 =1n);while(leamoney=0.2) leamoney=(float)(leamoney-0.2); y+;if(leamoney=0.1)le

10、amoney=(float)(leamoney-0.1); prin tf(1 角=1 張 n);算法與程序設計實驗報告四（ 4 學時）實驗目的：8、流程圖的繪制。9、背包問題求解。實驗內容：6、繪制下列各題的程序流程圖。1. 輸人一個數到變量 a ，輸出它的絕對值。 （分別用單雙分支繪制） 單分支結構算法：（1 ）輸入任意數并賦值給變量 a；（2）判斷 a 是否小于 0，如果 a 小于 0 ，取 a 的相反數；（3）輸出 a。雙分支結構算法：（1） 輸人任意數并賦值給變量a ;（2） 判斷a是否小于0 ,如果a小于0則輸出a的相反數，否則輸出a。2. 最值問題：（1 ）求輸人的兩個數中的最大

11、值。（2 ）求輸人的三個數中的最大值。（3 ）求輸入的十個數中的最大值。3. 循環(huán)求和（不同的控制循環(huán)方法）（1）求輸人20個數的和。 計數法（知道循環(huán)次數，可以采用循環(huán)變量i來控制循環(huán)次數）（2 ）求輸入的若干個學生成績的和，輸入-1表示結束。 標志法（不能確定次數，可以用輸入的數據的值來進行控制）（3）對輸入的數據求和，當所求的和超過 100則停止輸入并輸出求和結果 （設此 題中輸人的數皆為正數）。（沒有指出輸人數據的具體個數，且不能依據對輸入數據的值來控制循環(huán)，控制循 環(huán)的關鍵就在于對循環(huán)體中變量s的判斷）7、利用貪心策略解決背包問題。現有載重為M公斤的背包和n種貨物。第i種貨物的重量為

12、Wi,它的總價值為Pi，假定M Wi、Pi均為整數。設計程序給出裝貨方法， 使裝入背包的貨物總價值達到最大。實驗代碼:1.輸人一個數到變量 a，輸出它的絕對值。輸HW / 輸出a 單分支結構算法流程圖雙分支結構弟法流程圖10 / 112.最值問題:CSj/輸人/ 輸Aa.hc / 輸申h / 輸出c 輸岀b 7 / 檢序_CD（i）求輸人的兩個數中的最大值。C ）（2 ）求輸人的三個數中的最大值。max-x* i*-Imax*-xi T+/WfBx /c結束J（3 ）求輸入的十個數中的最大值。3.循環(huán)求和1.求輸人20個數的和。（知道循環(huán)次數，可以采用循 環(huán)變量i來控制循環(huán)次數）計數法2.求輸

13、入的若干個學生成績 的和，輸入-1表示結束。（不能確定次數，可以用輸入的數據的值來進行控制）標志法3.對輸入的數據求和，當所求 的和超過 100則停止輸入并 輸出求和結果（設此題中輸人 的數皆為正數）。（沒有指出輸人數據的具體個 數，且不能依據對輸入數據的 值來控制循環(huán)，控制循環(huán)的關 鍵就在于對循環(huán)體中變量s的判斷）2.背包問題求解#in clude void mai n ()int i,j,n ,s=0;float P20,W20,value20,x20,values=0;float q=0,t=0,M=0;printf(請輸入貨物的數目n :n);scan f(%d,&n);printf(

14、請輸入背包的負重M:n);scan f(%f,&M);printf(請輸入各種貨物的重量:n); for(i=1;i=n ;i+) scan f(%f,&Wi);printf(請輸入各種貨物的價值:n); for(i=1;i=n ;i+)scan f(%f,&Pi);for(i=1;i=n ;i+)valuei=Pi/Wi;計算貨物的單位重量價值for(i=1;i=n ;i+) for(j=1;j=n-i;j+) if(valuejvaluej+1) t=valuej; valuej=valuej+1; valuej+1=t; / 按貨物的單位重量價值進行 排序q=Wj; Wj=Wj+1; Wj+1=q;/ 相應的貨物重量進行排序printf( 單位價值量 ( 從大到小 ) 如下 :n);for (i=1;i=n;i+) printf(%5.2f ,valuei); printf(n);printf( 所對應的貨物重量如下 :n);for (i=1;i=n;i+) printf(%5.2f ,Wi); printf(n);i=1;while(M!=0)M-=Wi;/ 背包負重遞減 value