結(jié)構(gòu)化程序設(shè)計(jì)歸納算法設(shè)計(jì)技術(shù)的應(yīng)用實(shí)驗(yàn)報(bào)告

1、福建工程學(xué)院計(jì)算機(jī)與信息科學(xué)系實(shí)驗(yàn)報(bào)告20112012 學(xué)年第 二 學(xué)期 任課老師：實(shí)驗(yàn)題目歸納算法設(shè)計(jì)技術(shù)的應(yīng)用實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)開始日期：2012/5/1報(bào)告提交日期：2012/5/5實(shí)驗(yàn)?zāi)康?、要求有些問題看來很復(fù)雜，但它們是有一定規(guī)律的。只要深入細(xì)致地進(jìn)行分析，找 到這些規(guī)律，然后按規(guī)律編制相應(yīng)的程序，問題就迎刃而解了。例有n個(gè)硬幣(n為偶數(shù))正面朝上排成一排，每次將n-1個(gè)硬幣翻過來放 在原位置，不斷地重復(fù)上述過程，直到最后全部硬幣翻成反面朝上為止。設(shè)計(jì)程序 讓計(jì)算機(jī)把翻幣的最簡(jiǎn)過程以及翻幣次數(shù)輸岀(用*表示正面，0表示反面)分析：最后全部硬幣翻成反面朝上為止，則每個(gè)硬幣都是翻轉(zhuǎn)奇數(shù)次，n個(gè)

2、奇數(shù) 之和為偶數(shù)次。假定最簡(jiǎn)單情況下共翻n輪，則n(n-1)為偶數(shù)，n為偶數(shù)。最簡(jiǎn)單情況下共翻n次，對(duì)于任意的硬幣x,應(yīng)該翻多少次呢？設(shè)為n(x)(奇數(shù))次，則除x外其他n-1個(gè)硬幣要一起翻轉(zhuǎn)n-n(x)次(奇數(shù)), n-n(x)=l, 3, 5,，nt考慮n-n(x) =3, 5, , n-1的情況,將nt個(gè)硬幣翻轉(zhuǎn) 3次或者更多次得到的結(jié)果與翻轉(zhuǎn)一次的結(jié)果完全相同，且比翻轉(zhuǎn)一次更麻煩，不 是最簡(jiǎn)單過程，因此，只有n-n(x)=l才滿足要求，即n(x)=n-l,又由于x的任意 性，可知，每個(gè)硬幣的翻轉(zhuǎn)次數(shù)都是葉1次，因此總的翻轉(zhuǎn)次數(shù)為n*(n-1),根據(jù) n (n-1) =n* (n_l)可

3、得：n*n-n=n*n-n得n二n.即共翻轉(zhuǎn)n次，其中每個(gè)硬幣翻轉(zhuǎn)次數(shù)為n-1。考慮到所有硬幣翻轉(zhuǎn)次數(shù)相同，因此可以將其看成一個(gè)環(huán)，從某個(gè)位置開始，先翻 轉(zhuǎn)n-1個(gè)，再前進(jìn)一步，翻轉(zhuǎn)n-1個(gè),直到完成翻轉(zhuǎn)n次。二、實(shí)驗(yàn)題目1、有n個(gè)碩幣(n為偶數(shù))止面朝上排成一排，每次將n-1個(gè)硬幣翻過來放 在原位置，不斷地重復(fù)上述過程，直到最后全部硬幣翻成反面朝上為止。設(shè)計(jì)程序 讓計(jì)算機(jī)把翻幣的最簡(jiǎn)過程以及翻幣次數(shù)輸出(用*表示正面，0表示反面)2、有n個(gè)硬幣(n為奇數(shù))正面朝上排成一排，每次將n-2個(gè)硬幣翻過來放 在原位置，不斷地重復(fù)上述過程，直到最后全部硬幣翻成反而朝上為止。設(shè)計(jì)程序 讓計(jì)算機(jī)把翻幣的最

4、簡(jiǎn)過程以及翻幣次數(shù)輸出(用*表示正面，0表示反面)三、實(shí)驗(yàn)要求1.該實(shí)驗(yàn)的課內(nèi)學(xué)吋是4個(gè)課吋。加強(qiáng)要求：1)將1、2題集成為一個(gè)程序，根據(jù)用戶輸入判斷奇數(shù)還是偶數(shù)，執(zhí)行相應(yīng) 的過程。實(shí)驗(yàn)設(shè)計(jì)內(nèi)容(1)實(shí)驗(yàn)殺針的救據(jù)移構(gòu)(i)運(yùn)用數(shù)組存儲(chǔ)硬幣狀態(tài)，初始值都為i,表示正面朝上，顯示的結(jié)果都是* intslloooj;各個(gè)函數(shù)分析 翻硬幣偶數(shù)，外循環(huán)i標(biāo)記笫幾個(gè)保持狀態(tài)不變的硬幣，內(nèi)循環(huán)變量j判斷每次翻硬幣前都 需要判斷是否為保持不變的硬幣，若是則不變，若不是則與上次的翻轉(zhuǎn)狀態(tài)相反。/*翻硬幣(偶數(shù))*/int upcoineven(int coins_number) int i, j；for(i

5、= 0; i < coins_number; i+)printf(h第 %d 次翻硬幣:n”,i+l);getchar();for(j = 0; j < coins_number; j+)if(j != i)sj = !sj;printf(n%3cn, sj?,*,:,o,);/l 為真,0 為假 翻硬幣奇數(shù)，外循環(huán)i標(biāo)記第兒個(gè)保持狀態(tài)不變的硬幣，內(nèi)循環(huán)變量j判斷每次翻硬幣前都 需要判斷是否為保持不變的硬幣，若是則不變，若不是則與上次的翻轉(zhuǎn)狀態(tài)相反。當(dāng)翻到最后 一趟的時(shí)候，把全部的狀態(tài)輸出為反面。/*翻硬幣(奇數(shù))*/int upcoino(kl(int coins_number)

6、int i,j;/i標(biāo)記第幾趟硬幣的for(i = 0; i < coins_number; i+)printf(”第 %d 次翻硬幣：n”,i+l);getchar();for(j = 0; j < coins_number; j+)if(j 匸 i&& j!=i+l)sj = !sfj；printf(”3c”, sfjl?綽丫0)；)printf(hnh);if(i=coins_number-2)getchar();prinrft第 %d 次翻硬幣:n”,i+2); for(j = 0; j < coins_number; j+) printf(“3c”,

7、'0);printf(hnn);break; 實(shí)現(xiàn)翻硬幣奇數(shù)或偶數(shù)的判斷，調(diào)用相應(yīng)的翻硬幣過程 int main()int coins_number; intj;char choice2;while(l)printf(h請(qǐng)輸入硬幣的個(gè)數(shù):n”)；scanf("%d",&coins_number);printf(”初始狀態(tài):nh);for(j = 0; j < coins_number; j+)sj = 1;所有硬幣初始狀態(tài)設(shè)置，設(shè)置正面向上printf(”3c“, printf("nn");if (coins_number%2=0)

8、upcoineven(coins_number)；elseupcoinodd(coins_number);print”是否繼續(xù)進(jìn)行翻硬幣，若退出請(qǐng)按n或n,否則按任意鍵繼續(xù):“); scanf("%s",choice);if(strcmp(choice,"n',)=0|strcmp(choice,n,')=0)break;開始每次翻轉(zhuǎn)n-1個(gè) 硬幣t11r返冋卜*/5:x1fq每次翻轉(zhuǎn)n-2個(gè) 、硬幣，/1輸入硬幣 個(gè)數(shù)n/輸出每次 /翻轉(zhuǎn)情況 / 和為數(shù)調(diào)試過程記錄 for(i = 0; i < coins_number; i+)print

9、f(”第 %d 次翻硬幣：n”,i+l); getchar();for(j = 0; j < coins_number; j+)if(j 匸 i&& j!=i+l) sj = !sj; prmtf(n%3cn, sj?printf(hnu); if(i=coins_number-2) getchar(); printf(”第 %d 次翻硬幣:n”,i+2); for(j = 0; j < coins_number; j+) printf(n%3c,0,);printf(hnu);break;當(dāng)n為奇數(shù)時(shí)，要進(jìn)行判斷，當(dāng)正面?zhèn)€數(shù)等于n2時(shí)，經(jīng)過最后一次翻轉(zhuǎn)結(jié)束。最 后一趟正面朝上分別在頭尾，開始想用環(huán)來做，可是覺得鏈表麻煩，最后一趟的時(shí) 候做了個(gè)判斷剛開始沒有進(jìn)行判斷，所以出錯(cuò)。實(shí)驗(yàn)結(jié)果記錄以及與預(yù)期結(jié)果比較以及分析 翻硬幣奇數(shù)過程翻硬幣奇數(shù)過程若始狀態(tài):第1次翻硬幣:* * 0 0第2次翻硬幣:0 m 0 m m第3次翻硬幣：*00*0第4次翻硬幣：第5次翻硬幣:是否繼續(xù)進(jìn)行翻硬