算法與程序設計實驗報告

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

2、個n個元素白序列<a1,a2,a3,an>,其中n個元素是按從小到大的順序排列的，查找是否存在給定的值X。實驗代碼：1、n!的遞歸算法的編寫。#include<stdio.h>intdigui(intn)if(n=1)return1;elsereturnn*digui(n-1);voidmain()intn;printf("請輸入待求階乘數(shù)(小于15的一個數(shù))：");scanf("%d",&n);printf("結果為：%dn",digui(n);2、計算Fib(n)的遞歸算法#include<s

3、tdio.h>longFib(intn)if(n=111n=2)/終止遞歸條件return1;elsereturnFib(n-1)+Fib(n-2);voidmain()intn;printf("請輸入裴波那契數(shù)列的待求項數(shù)：")；scanf("%d",&n);printf("裴波那契數(shù)列第d項值為ldn",n,Fib(n);3、二分查找法的實現(xiàn)。#include<stdio.h>intBinarySearch(inta,intn,intx)/*二分查找功能函數(shù)*/intl=0,r=n,i;while(l&l

4、t;=r)i=(l+r)/2;if(x=ai)returni;elseif(x<ai)r=i-1;elsel=i+1;return-1;|voidmaopao(inta口)/*冒泡排序功能函數(shù)*/inti,j;intn=10;for(i=0;i<n;i+)for(j=0;j<n-i-1;j+)if(aj>aj+1)1inttemp;temp=aj;aj=aj+1;aj+1=temp;:voidmain()inti,a10,x;intflag=-1;printf("請輸入10個帶查找數(shù)據(jù)(空格分隔)：")；for(i=0;i<10;i+)|sca

5、nf("%d”,&ai);maopao(a);printf("帶查序列有序化后變?yōu)椋?quot;);for(i=0;i<10;i+)printf("%d,",ai);printf("n");printf("請輸入待查關鍵字：")；scanf("%d",&x);flag=BinarySearch(a,10,x);if(flag=-1)printf("未找到帶查關鍵字！n");elseprintf("找到關鍵字，位于有序序列的第個位置！n"

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

7、學模型來描述問題。2 .把求解的問題分成若干個子問題。3 .對每一子問題求解，得到子問題的局部最優(yōu)解。4 .把子問題的解局部最優(yōu)解合成原來解問題的一個解。實驗代碼：1 .鍵盤輸入一個高精度的正整數(shù)n(n<10位)去掉任意s個數(shù)字后剩下的數(shù)字按原左右次序組成一個新的正整數(shù)。編程對給定的n和s,尋找一種方案，使得剩下的數(shù)最小。#include<stdio.h>#include<string.h>#defineM100main()charchM;intrM,dM,l,s,i,j,k;printf("請輸入正整數(shù)：");gets(ch)；printf(

8、"請輸入刪除的位數(shù)：”)；scanf("%d",&s);l=0;for(i=0;chi!='0'i+)ri=i;l+;for(i=0;i<s;i+)for(j=0;j<l-i-1;j+)if(chj>chj+1)break;if(j=l-i)k=l-i-1;elsek=j;di=rk;for(j=k;j<l-i-1;j+)chj=chj+1;rj=rj+1;chj='0'printf("刪除后最小的整數(shù)為:%sn",s,ch);printf("刪除的數(shù)位為:")

9、;for(i=0;i<s;i+)printf("%dt",di+1);printf("n");return0;2 .設計實現(xiàn)超市收銀程序，假設顧客在超市購買各種商品，來到收銀臺結賬，收銀員具有面值為100,20,10,5和1元的紙幣和各種面值為5角、2角、1角的硬幣。設計程序計算顧客各種所買商品的錢數(shù)，并根據(jù)顧客所付的錢數(shù)輸出零錢的數(shù)目及要找的各種貨幣的數(shù)目。#include<stdio.h>#include<string.h>voidmain()doubleprice,total=0,givemoney,leamoney;

10、intn,i,k=0,m=0,x=0,y=0;printf("請輸入商品的數(shù)目：")；scanf("%d",&n);printf("輸入每件商品的價格：n");for(i=1;i<=n;i+)printf("第件:",i);scanf("%lf",&price);total=total+price;printf("總的價格=%5.2fn",total);printf("輸入顧客所給的錢：n");scanf("%lf"

11、;,&givemoney);leamoney=givemoney-total;printf("剩余的錢為5.2fn",leamoney);printf("n各種貨幣的數(shù)目如下：n");while(leamoney>=100)leamoney=leamoney-100;k+;if(leamoney<100)printf("100元=%d張n",k);while(leamoney>=20)leamoney=leamoney-20;x+;if(leamoney<20)printf("20元=%d張n

12、",x);while(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<1)printf("1元=%d張n",m);while(leamoney>=0.5)leamoney=leamoney-0.5;printf("5角

13、=1'n");while(leamoney>=0.2)leamoney=(float)(leamoney-0.2);y+;if(leamoney<0.2)printf("2角=%d張n",y);while(leamoney>=0.1)leamoney=(float)(leamoney-0.1);printf("1角=1張n");算法與程序設計實驗報告四(4學時)實驗目的：8、流程圖的繪制。9、背包問題求解。實驗內容：6、繪制下列各題的程序流程圖。1 .輸人一個數(shù)到變量a,輸出它的絕對值。(分別用單雙分支繪制)單分支結構

14、算法：(1)輸入任意數(shù)并賦值給變量a;(2)判斷a是否小于0,如果a小于0,取a的相反數(shù)；(3)輸出a。雙分支結構算法：(1)輸人任意數(shù)并賦值給變量a;(2)判斷a是否小于0,如果a小于0則輸出a的相反數(shù)，否則輸出a。2 .最值問題：(1)求輸人的兩個數(shù)中的最大值。(2)求輸人的三個數(shù)中的最大值。(3)求輸入的十個數(shù)中的最大值。3.循環(huán)求和(不同的控制循環(huán)方法)(1)求輸人20個數(shù)的和。計數(shù)法(知道循環(huán)次數(shù)，可以采用循環(huán)變量i來控制循環(huán)次數(shù))(2)求輸入的若干個學生成績的和，輸入-1表示結束。標志法(不能確定次數(shù)，可以用輸入的數(shù)據(jù)的值來進行控制)(3)對輸入的數(shù)據(jù)求和，當所求的和超過100則停

15、止輸入并輸出求和結果(設此題中輸人的數(shù)皆為正數(shù))。(沒有指出輸人數(shù)據(jù)的具體個數(shù)，且不能依據(jù)對輸入數(shù)據(jù)的值來控制循環(huán)，控制循環(huán)的關鍵就在于對循環(huán)體中變量s的判斷)7、利用貪心策略解決背包問題?，F(xiàn)有載重為M公斤的背包和n種貨物。第i種貨物的重量為Wi,它的總價值為Pi,假定MWi、Pi均為整數(shù)。設計程序給出裝貨方法，使裝入背包的貨物總價值達到最大。1.輸人一個數(shù)到變量 a ,輸出它的絕對值。(開始)/ 輸入a /實驗代碼:|ag*/輸出咆/輸而7“/赤/LJ'c結束)(結束)單分支結構算法流程圖雙分支結構算法流程圖2.最值問題：（1）求輸人的兩個數(shù)中的最大值。（2）求輸人的三個數(shù)中的最大值

16、。max一叫 iTmax*-xi-i+】_一f輸x/（3）求輸入的十個數(shù)中的最大值。3.循環(huán)求和1 .求輸人20個數(shù)的和。（知道循環(huán)次數(shù)，可以采用循 環(huán)變量i來控制循環(huán)次數(shù)）計數(shù)法2 .求輸入的若干個學生成績 的和，輸入-1表示結束。（不能確定次數(shù)，可以用輸入的數(shù)據(jù)的值來進行控制）標志法3 .對輸入的數(shù)據(jù)求和，當所求 的和超過 100則停止輸入并 輸出求和結果（設此題中輸人 的數(shù)皆為正數(shù)）。（沒有指出輸人數(shù)據(jù)的具體個 數(shù)，且不能依據(jù)對輸入數(shù)據(jù)的 值來控制循環(huán)，控制循環(huán)的關 鍵就在于對循環(huán)體中變量s的判斷）C開始）2.背包問題求解#include<stdio.h>voidmain()

17、inti,j,n,s=0;floatP20,W20,value20,x20,values=0;floatq=0,t=0,M=0;printf("請輸入貨物的數(shù)目n:n");scanf("%d",&n);printf("請輸入背包的負重M:'n");scanf("%f",&M);printf("請輸入各種貨物的重量：n");for(i=1;i<=n;i+)scanf("%f",&Wi);printf("請輸入各種貨物的價值：n&q

18、uot;);for(i=1;i<=n;i+)scanf("%f",&Pi);for(i=1;i<=n;i+)valuei=Pi/W叱計算貨物的單位重量價值for(i=1;i<=n;i+)for(j=1;j<=n-i;j+)if(valuej<valuej+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