算法與程序設(shè)計(jì)實(shí)驗(yàn)報(bào)告

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

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

3、tdio.h>longFib(intn)if(n=111n=2)/終止遞歸條件return1;elsereturnFib(n-1)+Fib(n-2);voidmain()intn;printf("請輸入裴波那契數(shù)列的待求項(xiàng)數(shù)：")；scanf("%d",&n);printf("裴波那契數(shù)列第d項(xiàng)值為ldn",n,Fib(n);3、二分查找法的實(shí)現(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個(gè)帶查找數(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("請輸入待查關(guān)鍵字：")；scanf("%d",&x);flag=BinarySearch(a,10,x);if(flag=-1)printf("未找到帶查關(guān)鍵字！n");elseprintf("找到關(guān)鍵字，位于有序序列的第個(gè)位置！n"

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

7、學(xué)模型來描述問題。2 .把求解的問題分成若干個(gè)子問題。3 .對每一子問題求解，得到子問題的局部最優(yōu)解。4 .把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。實(shí)驗(yàn)代碼：1 .鍵盤輸入一個(gè)高精度的正整數(shù)n(n<10位)去掉任意s個(gè)數(shù)字后剩下的數(shù)字按原左右次序組成一個(gè)新的正整數(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 .設(shè)計(jì)實(shí)現(xiàn)超市收銀程序，假設(shè)顧客在超市購買各種商品，來到收銀臺結(jié)賬，收銀員具有面值為100,20,10,5和1元的紙幣和各種面值為5角、2角、1角的硬幣。設(shè)計(jì)程序計(jì)算顧客各種所買商品的錢數(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("輸入每件商品的價(jià)格：n");for(i=1;i<=n;i+)printf("第件:",i);scanf("%lf",&price);total=total+price;printf("總的價(jià)格=%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");算法與程序設(shè)計(jì)實(shí)驗(yàn)報(bào)告四(4學(xué)時(shí))實(shí)驗(yàn)?zāi)康模?、流程圖的繪制。9、背包問題求解。實(shí)驗(yàn)內(nèi)容：6、繪制下列各題的程序流程圖。1 .輸人一個(gè)數(shù)到變量a,輸出它的絕對值。(分別用單雙分支繪制)單分支結(jié)構(gòu)

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

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

16、。max一叫 iTmax*-xi-i+】_一f輸x/（3）求輸入的十個(gè)數(shù)中的最大值。3.循環(huán)求和1 .求輸人20個(gè)數(shù)的和。（知道循環(huán)次數(shù)，可以采用循 環(huán)變量i來控制循環(huán)次數(shù)）計(jì)數(shù)法2 .求輸入的若干個(gè)學(xué)生成績 的和，輸入-1表示結(jié)束。（不能確定次數(shù)，可以用輸入的數(shù)據(jù)的值來進(jìn)行控制）標(biāo)志法3 .對輸入的數(shù)據(jù)求和，當(dāng)所求 的和超過 100則停止輸入并 輸出求和結(jié)果（設(shè)此題中輸人 的數(shù)皆為正數(shù)）。（沒有指出輸人數(shù)據(jù)的具體個(gè) 數(shù)，且不能依據(jù)對輸入數(shù)據(jù)的 值來控制循環(huán)，控制循環(huán)的關(guā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("請輸入背包的負(fù)重M:'n");scanf("%f",&M);printf("請輸入各種貨物的重量：n");for(i=1;i<=n;i+)scanf("%f",&Wi);printf("請輸入各種貨物的價(jià)值：n&q

18、uot;);for(i=1;i<=n;i+)scanf("%f",&Pi);for(i=1;i<=n;i+)valuei=Pi/W叱計(jì)算貨物的單位重量價(jià)值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;按貨物的單位重量價(jià)值進(jìn)行q=Wj；Wj=Wj+1；Wj+1=q；/相應(yīng)的貨物重量進(jìn)行排序printf("單位價(jià)值量(從大到小)如下:n");for(i=1;i<=n;i+)printf("%5.2f",valuei);printf("n");printf("所對應(yīng)的貨物重量如下：n");for(i=1;i<=n;i+)printf("%5.2f",Wi);printf("n");i=1;while(M!=0)M-=Wi;背包負(fù)重遞減value