計算概論B-馬思偉 Lecture 14 習題課

習題課

錯誤

floatP(floatx,intn){if(n==0)P=1;elseif(n==1)P=x;elseP=((2n-1)*x*P(x,n-1)-(n-1)*P(x,n-2))/n;returnP;}復習程序基本框架標識符與關(guān)鍵字標識符：以字母、下劃線開頭后跟字母下劃線數(shù)據(jù)類型與常量、變量char

c=5;

c++;

char

d=‘B’;

d-=1;

運算符與表達式if(i=5);if(i==5)j=i++;j=++Iif(c>=‘A’&&c<=‘Z’)if(a&b)if(a&&b)if(0)語句c=getchar();putchar(c);scanf(“%c”,&c);scanf(“%d”,&a);復習程序結(jié)構(gòu)順序結(jié)構(gòu)分支結(jié)構(gòu)：if-else,switch-caseswitch(c){case‘A’:case‘B’:total++;break;default: total++;}循環(huán)結(jié)構(gòu)：for,while,do-whilefor(i=0;i<10;i++)while(i<10)do{….}while(i<10)復習數(shù)組一維數(shù)組#defineN100

inta[N];inta[10];a[i];

(i=0..9)二維數(shù)組int

a[3][4];

for(j=0;j<3;j++)

for(i=0;i<4;i++)

a[j][i]=j*i;字符數(shù)組/字符串char

str[256];scanf(“%s”,str);gets(str);strlen(str),

strcpy(),

strcat(),復習函數(shù)函數(shù)說明、定義intadd(inta,intb);intadd(int

a,

int

b)

{

return

a+b;

}

main()

{

printf(“%d”,

add(2,

3));

}變量作用域：全局變量、局部變量int

total=0;

void

main()

{

count();

total++;

printf(“%d”,

total);

}

int

count()

{

int

total=0;

total++:

}函數(shù)遞歸調(diào)用內(nèi)容綱要程序設(shè)計過程編程時應該注意的問題編程調(diào)試時的部分錯誤信息的解釋代碼的優(yōu)化程序設(shè)計過程提出問題（明確程序的已知條件、原始數(shù)據(jù)、輸入、處理的數(shù)據(jù)類型、輸出的形式和精度）建立數(shù)學/計算模型（將原始問題簡化、抽象、轉(zhuǎn)換成適合計算機處理的數(shù)據(jù)結(jié)構(gòu)、公式等）設(shè)計算法（找到一個合適的能在計算機上實現(xiàn)的解題方法與步驟，并且精確、清楚地描述出來）編寫程序、調(diào)試運行、測試驗證、保存編譯等（對于滿足題意的任何輸入、在任何時候都能在規(guī)定的時間內(nèi)、得到正確的滿足要求的結(jié)果）程序設(shè)計過程提出問題建立數(shù)學模型設(shè)計算法程序?qū)崿F(xiàn)提出問題明確程序的已知條件、原始數(shù)據(jù)、輸入、處理的數(shù)據(jù)類型、輸出的形式和精度建立數(shù)學模型將原始問題簡化、抽象、轉(zhuǎn)換成適合計算機處理的數(shù)據(jù)結(jié)構(gòu)、公式選擇合適的數(shù)據(jù)類型以及存儲調(diào)用方式（需要注意的：數(shù)據(jù)的類型、數(shù)據(jù)的精度、數(shù)據(jù)的生命周期）建立數(shù)據(jù)之間的關(guān)系即公式設(shè)計算法使用計算機可以實現(xiàn)的方法描述數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系選擇合適的程序流，使用流程圖描述程序流程序?qū)崿F(xiàn)編寫程序、調(diào)試運行、測試驗證、保存編譯等良好程序風格輸入輸出聲明數(shù)據(jù)，申請存儲空間實現(xiàn)程序流約瑟夫環(huán)問題問題描述有

n個人，編號為

1,2,...,n,站成一圈。沿著圈順序數(shù)，每到第m個人就把他殺掉，這樣一直進行下去，直到只剩下一個人，那個人就活下來。約瑟夫很聰明，他總會想辦法站到一個合適的位置上，使得自己能夠成為最后一個，從而活下來。例如：n=6，

m=5時，被殺的順序是5,4,6,2,3，而

1最終活下來。

給定n,m,求出最后留下的人的編號位置12345612346123612313約瑟夫環(huán)問題(1)1。使用數(shù)組，刪除人移動數(shù)組2。使用數(shù)組，刪除人用一個標記表示，不用移動數(shù)據(jù)12345612346123612313startendstartendstartendendstartstartend123456startendstartendstartendendstartstartend1234-16123-1-16123-1-1-11-13-1-16約瑟夫環(huán)問題(1)3。數(shù)學解法，復雜度低n個人的序列1234……m-1mm+1…..n殺掉一個人的序列1234……m-1m+1…..n重排序列m+1….n12….m-1x’序號重新編號序列—n-1人序列123….n-1

x序號x’=(m+x)%n…….最后剩1個人1約瑟夫環(huán)問題(1)一直到最后剩一個人1---標號記為number上一層的number

number=(number+m)%2一般化表示，對有i個人的序列，序號為number[i]=(number[i-1]+m)%i約瑟夫環(huán)問題(1)int_tmain(intargc,_TCHAR*argv[]){ intn,m,i=0,j=0; inta[MAX]; printf("Pleaseinputn(<=1000):"); scanf("%d",&n); printf("Pleaseinputm:"); scanf("%d",&m); for(intk=0;k<n;k++) a[k]=k;

while(n>1)

{ j=(i+m-1)%n; for(intk=j;k<n;k++) a[k]=a[k+1]; i=j; n--;

} printf("JosephshouldstandatNo.%d\n",a[0]+1); return0;}約瑟夫環(huán)問題(2)假設(shè)有

k個好人和

k個壞人。在圈上前

k個是好人，后

k個是壞蛋?，F(xiàn)在讓你來確定一個最小的

m使得所有的壞蛋被殺掉后，才開始殺第1個好人。輸入輸入有若干個k。

最后1個值是0。假設(shè)

0<k<14。輸出對應每個輸入的k，輸出相應的m。樣例輸入樣例輸出

340530約瑟夫環(huán)問題(2)問題分析1)求最小的m值可以用枚舉的方法： 即依次看m=1，2，3，…時，是否滿足條件。2)枚舉的過程就是依次殺掉圈上的一半的人，并判斷該人是否是好人，如果是好人，則當前的m不滿足條件，否則m滿足條件。3)一共有2k個人。4)k可以取1，2，3，…,13。可以一次算出所有相應的m，存在一個數(shù)組中，這樣每次讀入一個k，就輸出相應的m。如何調(diào)用函數(shù)解決？編程中常出現(xiàn)的問題程序風格問題 規(guī)范程序格式；使用scanf時，參數(shù)必須取地址，不能有格式信息；

inta; scanf(“%d\n”,a);編程中常出現(xiàn)的問題左右括號不匹配 包括大括號，小括號，規(guī)范程序格式可以有效避免這種錯誤的發(fā)生。在使用循環(huán)的時候，對于每次循環(huán)都要獨立用到的變量，應該在每次循環(huán)前都重新賦值，所以對于這些變量的賦值應該放在循環(huán)體中。

編程中常出現(xiàn)的問題數(shù)據(jù)類型強制轉(zhuǎn)換 兩個int類型的整數(shù)相除仍然得到一個整數(shù)；所以當希望結(jié)果是浮點數(shù)的時候，需要在進行除法運算前將兩個整數(shù)轉(zhuǎn)換成浮點數(shù)；編程中常出現(xiàn)的問題使用數(shù)組錯誤：輸入時沒有加地址符，引用的時候數(shù)組下標越界。（C/C++不檢查地址越界，所以編譯不會有錯，但是運行時會有runtimeerror或者得不到正確結(jié)果）。對語句的格式不清楚，例如if,while等，出現(xiàn)if(condition);{}之類的錯誤。對for,while等語句的執(zhí)行順序不清楚。編程應該注意的問題——代碼風格好的編程風格：容易閱讀、調(diào)試、維護……#include voidmain(){ inti; for(i=0;i<20;i++){ /*………*/

………… } }編程應該注意的問題——運算符區(qū)別&和&&符號移位操作不改變操作數(shù)本身的值A(chǔ)++,++A地執(zhí)行順序的不同編程應該注意的問題——數(shù)組數(shù)組名是地址常量，訪問元素要使用下標數(shù)組元素下標從0開始，到n-1結(jié)束，對于多維數(shù)組，每一維都是從0開始。編程應該注意的問題——函數(shù)要正確返回需要的返回值函數(shù)的參數(shù)有值參和形參兩種，使用時要注意，巧妙使用可以方便解題。語句scanf需要的是地址作為參數(shù)VC編譯器的錯誤信息使用MicrosoftC以如下格式產(chǎn)生錯誤消息:filename(line-number):diagnosticCnumberMessage這里filename是遇到錯誤的源文件的名稱;line-number是編譯器檢測到錯誤的行號;diagnostic是“錯誤”或“警告”;number是一個唯一的標識錯誤或警告的4數(shù)字編號(前面有一個像該語法中標記的C);message是一個解釋的消息。例如：C:\temp\277062\Main.cpp(105)

:

error

C2084:

function

'int

__cdecl

main(void)'

already

has

a

body

VC編譯器的錯誤信息使用程序編譯后，編譯的結(jié)果信息會在輸出窗口輸出。雙擊一條錯誤信息，光標自動調(diào)到相應的出錯的地點。錯誤信息會指出產(chǎn)生錯誤的原因。根據(jù)這個原因可以到相應的位置去找到錯誤并改正。但是，有時候引起某個錯誤的原因，并不是錯誤信息給出的那樣，需要通過經(jīng)驗去判斷。代碼的優(yōu)化代碼的優(yōu)化分為編譯程序的自動優(yōu)化和編程者的手工優(yōu)化。編譯器優(yōu)化主要是通過常數(shù)合并，冗余表達式消除，循環(huán)內(nèi)優(yōu)化等方法，這些方法同樣適用于人工優(yōu)化。這里介紹一下人工優(yōu)化的方法。代碼的優(yōu)化使用效率高的語句：例如：a++要比a+1效率高，a<<2比a*2高暫存公共表達式例如:a=((b-c)*2-d)*3,f=((b-c)*2-d)*3-2寫成