第1章 程序設(shè)計(jì)基礎(chǔ)

第1章程序設(shè)計(jì)基礎(chǔ)

1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示

1.2算法及其表示

1.3程序設(shè)計(jì)語言

1.4結(jié)構(gòu)化程序設(shè)計(jì)1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示數(shù)制及其轉(zhuǎn)換常用計(jì)數(shù)方法十進(jìn)制計(jì)數(shù)法進(jìn)制計(jì)數(shù)法是“逢十進(jìn)一”的例如：(1234.56)10＝1×103＋2×102＋3×101＋4×100＋5×10－1＋6×10－2各位的權(quán)值分別為：103、102、101、100、10－1、10－2。二進(jìn)制計(jì)數(shù)法二進(jìn)制計(jì)數(shù)法是“逢二進(jìn)一”的。例如：(1001101.11)2=1×26＋0×25＋0×24＋1×23＋1×22＋0×21＋1×20＋1×2－1＋1×2－2各位的權(quán)值分別為：26、25、24、23、22、21、20、2－1、2－2、2－3。1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示八進(jìn)制數(shù)與十六進(jìn)制數(shù)八進(jìn)制計(jì)數(shù)法是“逢八進(jìn)一”的，數(shù)碼為：0、1、2、3、4、5、6、7。例如：(621)8=6×82＋2×81＋6×80

各位的權(quán)值分別為：82、81、80。十六進(jìn)制計(jì)數(shù)法是“逢十六進(jìn)一”的，數(shù)碼為0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F。例如：(8A1F)16=8×163＋10×162＋1×161＋15×160各位的權(quán)值分別為：163、162、161、160。1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示數(shù)制轉(zhuǎn)換任意進(jìn)制轉(zhuǎn)換為十進(jìn)制

由r制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)可按照如下公式進(jìn)行多項(xiàng)式展開求和即可：

KnKn－1…K1K0.K－1K－2…K－m＝Kn×rn＋Kn－1×rn－1＋…K1×r1＋K0×r0＋K－1×r－1＋K－2×r－2＋…K－m×r－m

十進(jìn)制轉(zhuǎn)換為任意進(jìn)制可以采用除基取余法將十進(jìn)制整數(shù)轉(zhuǎn)換為r進(jìn)制整數(shù)：將十進(jìn)制整數(shù)除以r，得到商和余數(shù)，余數(shù)對(duì)應(yīng)為r進(jìn)制數(shù)低位的值；繼續(xù)讓商再除以r，得到商和余數(shù)，……重復(fù)此操作，直至商為0，如此得到的一系列的余數(shù)就是相應(yīng)r進(jìn)制數(shù)的各位數(shù)字，先得到的是低位，后得到的是高位。

1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示例如，將(29)10轉(zhuǎn)換為二進(jìn)制整數(shù)：因此，(29)10＝(11101)22292141低位27023121101高位

1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示可采用乘基取整法將十進(jìn)制小數(shù)轉(zhuǎn)換為r進(jìn)制小數(shù)：將十進(jìn)制小數(shù)乘以r，去掉乘積的整數(shù)部分，再將余下的純小數(shù)乘以r，……重復(fù)此操作，直至乘積等于0或達(dá)到所需的精度為止，如此得到的一系列整數(shù)就是r進(jìn)制小數(shù)的各位數(shù)字，先得到的是高位，后得到的是低位。例如，將(0.625)10轉(zhuǎn)換為二進(jìn)制小數(shù)：0.625×2=1.251高位0.25×2=0.500.5×2=11低位因此，(0.625)10＝(0.101)2由于整數(shù)和小數(shù)的轉(zhuǎn)換方法截然不同，將十進(jìn)制數(shù)轉(zhuǎn)換為r進(jìn)制數(shù)時(shí)，整數(shù)部分和小數(shù)部分要分開來進(jìn)行轉(zhuǎn)換。r進(jìn)制小數(shù)能精確的轉(zhuǎn)換為十進(jìn)制小數(shù)，但十進(jìn)制小數(shù)通常不能精確的轉(zhuǎn)換為r進(jìn)制小數(shù)。1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示二進(jìn)制與八進(jìn)制、十六進(jìn)制之間的轉(zhuǎn)換對(duì)于一個(gè)二進(jìn)制數(shù)，只要依次（整數(shù)部分由低位到高位，小數(shù)部分由高位到低位）將其每3位或4位分成一組，就可以直接轉(zhuǎn)換為八進(jìn)制數(shù)或十六進(jìn)制數(shù)。例如，(1000101111010011.01101)2＝(105423.53)8

(1000101111010011.01101)2＝(8B13.B8)16將八進(jìn)制數(shù)中的每一位用3位二進(jìn)制數(shù)表示，將十六進(jìn)制數(shù)中的每一位用4位二進(jìn)制數(shù)表示，就能轉(zhuǎn)換為對(duì)應(yīng)的二進(jìn)制數(shù)。1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示

原碼，反碼及補(bǔ)碼

在計(jì)算機(jī)中，“位”是數(shù)據(jù)的最小單位。計(jì)算機(jī)中的存儲(chǔ)量是以字節(jié)來計(jì)算的，一個(gè)字節(jié)是8位二進(jìn)制位。

在計(jì)算機(jī)內(nèi)，一般規(guī)定：用0表示正號(hào)“＋”，用1表示負(fù)號(hào)“－”；符號(hào)位放在數(shù)值位之前。

一個(gè)數(shù)連同其符號(hào)在機(jī)器中的二進(jìn)制表示形式稱為機(jī)器數(shù)，它所代表的數(shù)值稱為機(jī)器數(shù)的真值。機(jī)器數(shù)的一般格式為：

符號(hào)位數(shù)值位……1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示原碼原碼表示法是符號(hào)位用0表示正數(shù)，用1表示負(fù)數(shù)，數(shù)值位表示數(shù)值本身。例如：[＋27]原=00011011[－27]原=10011011在原碼表示法中，0的表示方法不唯一：

[＋0]原=00000000[－0]原=10000000。反碼反碼表示法中正數(shù)與負(fù)數(shù)的表示方法不同，正數(shù)的反碼與原碼同形，如：

[＋27]反=00011011負(fù)數(shù)的反碼為：符號(hào)位仍為1，數(shù)值位是對(duì)原碼取反，如：

[－27]反=11100100在反碼表示法中，0的表示也不唯一：

[＋0]反=00000000[－0]反=11111111。1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示補(bǔ)碼正數(shù)的補(bǔ)碼與原碼、反碼同形，如：

[＋18]原＝[＋18]反＝[＋18]補(bǔ)＝00010010負(fù)數(shù)的補(bǔ)碼為：符號(hào)位為1，數(shù)值位等于原碼的數(shù)值位取反，再加1，或者說：[x]補(bǔ)＝[x]反＋1；如：[－18]原＝10010010[－18]反＝11101101[－18]補(bǔ)＝11101110補(bǔ)碼形式的數(shù)據(jù)進(jìn)行運(yùn)算時(shí)，符號(hào)位和數(shù)值位一樣的參與運(yùn)算。

例如，計(jì)算－36＋58，[－36]補(bǔ)＝11011100[＋58]補(bǔ)＝00111010

11011100

＋00111010

溢出100010110在補(bǔ)碼表示法中，0的表示是唯一的，假設(shè)用一個(gè)字節(jié)存放數(shù)據(jù)

[0]補(bǔ)＝000000001.2算法及其表示

算法為解決一個(gè)問題而采取得方法和步驟，稱為算法。算法就是被精確定義的一組規(guī)則，規(guī)定先做什么，再做什么，以及判斷某種情況下做哪種操作。例如，下面是用自然語言表示的對(duì)三個(gè)數(shù)進(jìn)行從小到大排序的算法。①

輸入三個(gè)數(shù)x、y、z；②

將x與y比較，若x＞y，交換x與y的值；③

將x與z比較，若x＞z，交換x與z的值；④

將y與z比較，若y＞z，交換y與z的值；⑤

輸出此時(shí)的三個(gè)數(shù)x、y、z1.1計(jì)算機(jī)內(nèi)的數(shù)據(jù)表示算法的特性和目標(biāo)算法必須具有以下五個(gè)特性：確定性

算法中的每一步都必須有確切的含義，不允許存在二義性；對(duì)于相同的輸入數(shù)據(jù)，必須有相同的輸出結(jié)果?？尚行?/p>

算法中的每一步操作都能通過可以實(shí)現(xiàn)的基本運(yùn)算，執(zhí)行有限次來完成，并最終得到確定的結(jié)果。有窮性一個(gè)算法必須總是在執(zhí)行有限個(gè)操作步驟和可以接受的時(shí)間內(nèi)完成其執(zhí)行過程。也即是說，對(duì)于一個(gè)算法，要求其在時(shí)間和空間上均是有窮的。1.2算法及其表示輸入

一個(gè)算法有零個(gè)或多個(gè)輸入數(shù)據(jù)。有些算法需要提供輸入數(shù)據(jù)，有些算法則不需要。輸出

一個(gè)算法應(yīng)該有1個(gè)或多個(gè)輸出數(shù)據(jù)。算法應(yīng)達(dá)到的目標(biāo)正確性可讀性健壯性高效率與低存儲(chǔ)空間需求

1.2算法及其表示算法的表示

自然語言

傳統(tǒng)流程圖

傳統(tǒng)流程圖是用規(guī)定的一組圖形符號(hào)、流程線和文字說明來表示各種操作的算法表示方法。

1.2算法及其表示1.2算法及其表示流程圖只包括三種基本程序結(jié)構(gòu)

順序結(jié)構(gòu)

選擇結(jié)構(gòu)

真處理A處理B假條件選擇結(jié)構(gòu)處理A處理B順序結(jié)構(gòu)1.2算法及其表示循環(huán)結(jié)構(gòu)

真處理A假條件直到型循環(huán)結(jié)構(gòu)假真處理A條件當(dāng)型循環(huán)結(jié)構(gòu)開始輸入x,y,z結(jié)束輸出x、y、z對(duì)三個(gè)數(shù)進(jìn)行排序交換x、y假真x>y??交換x、z假真x>z?交換y、z假真y>z?1.2算法及其表示N-S流程圖順序結(jié)構(gòu)

選擇結(jié)構(gòu)

順序結(jié)構(gòu)處理A

處理B分支結(jié)構(gòu)條件

處理A

處理B成立不成立1.2算法及其表示循環(huán)結(jié)構(gòu)當(dāng)條件成立時(shí)繼續(xù)

處理A當(dāng)型循環(huán)結(jié)構(gòu)

處理A

直到條件成立時(shí)結(jié)束直到型循環(huán)結(jié)構(gòu)1.2算法及其表示輸入x,y,zx>y?Y

N

交換x、yx>z?Y

N

交換x、zy>z?Y

N

交換y、z

輸出x、y、z三個(gè)數(shù)進(jìn)行從小到大排序1.2算法及其表示偽碼偽碼是用一種介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法。例如，用偽碼描述上述算法：inputx,y,zx→maxify>maxtheny→maxifz>maxthenz→maxoutputmax1.3程序設(shè)計(jì)語言程序與程序設(shè)計(jì)語言

程序

計(jì)算機(jī)程序是指為讓計(jì)算機(jī)完成特定的任務(wù)而設(shè)計(jì)的指令序列。程序設(shè)計(jì)語言

機(jī)器語言匯編語言高級(jí)語言面向?qū)ο蟮恼Z言C語言簡介

C語言的歷史

1.3程序設(shè)計(jì)語言C程序的結(jié)構(gòu)

C程序是一種函數(shù)結(jié)構(gòu)，一般由一個(gè)或若干個(gè)函數(shù)組成;其中必有一個(gè)名為main()的主函數(shù)，程序的執(zhí)行就是從這里開始的。

【例1.1】編寫程序判斷一個(gè)整數(shù)是否是3的倍數(shù)，如果是輸出“YES”，否則輸出NO”。main() /*main函數(shù)的首部*/{/*main函數(shù)體的開始*/

intm; /*定義整型變量m*/

printf("\nPleaseinputainteger:");/*輸出提示信息*/

scanf("%d",&m); /*讀入變量的值*/

if((m%3==0))printf("YES");elseprintf("NO");/*如果flag值為0，輸出“YES”，否則輸出“N0”*/}1.3程序設(shè)計(jì)語言運(yùn)行情況如下：Pleaseinputainteger:20↙NO【例1.2】編寫程序求任意三個(gè)整數(shù)中的最小值。main()/*main函數(shù)的首部*/{/*main函數(shù)體的開始*/

intn1,n2,n3;/*定義三個(gè)整型變量*/

intminnum;/*定義變量minnum，用于存放最小值*/

printf("\nEnterthreeintegers:");/*輸出提示信息*/

scanf("%d,%d,%d",&n1,&n2,&n3);/*讀入變量的值*/

minnum=min(n1,n2,n3);/*調(diào)用自定義函數(shù)min，將所求的最小值賦給變量minnum*/printf("\nMaximumis:%d",minnum);/*輸出minnum值*/}1.3程序設(shè)計(jì)語言intmin(intx,inty,intz)/*num函數(shù)的首部*/{/*num函數(shù)體的開始*/

intm;m=x;/*默認(rèn)第一個(gè)數(shù)最小*/

if(y<m)m=y;/*如果第二個(gè)數(shù)更小，則修改m*/if(z<m)m=z;/*如果第三個(gè)數(shù)更小，則修改m*/returnm;/*將m的值作為函數(shù)值返回*/}/*max函數(shù)體的結(jié)束*/運(yùn)行情況如下：Enterthreeintegers:18,25,12↙Maximumis:121.3程序設(shè)計(jì)語言C程序的結(jié)構(gòu)特點(diǎn)

C程序是由函數(shù)構(gòu)成的。函數(shù)由函數(shù)首部和函數(shù)體兩部分組成。一般函數(shù)的格式如下：

類型名

函數(shù)名（函數(shù)參數(shù)表）

{聲明部分

執(zhí)行部分

}函數(shù)體中也可以沒有任何內(nèi)容，即構(gòu)成一個(gè)空函數(shù)。一個(gè)源程序有一個(gè)且只能有一個(gè)main函數(shù)（又稱主函數(shù)）。C程序的執(zhí)行總是從main函數(shù)開始的，在調(diào)用其它函數(shù)后，最后回到main函數(shù)中結(jié)束整個(gè)程序的執(zhí)行。1.3程序設(shè)計(jì)語言C程序書寫格式自由。既允許在一行內(nèi)寫多個(gè)語句，也允許將一個(gè)語句分寫在多行上，但每個(gè)語句必須以分號(hào)結(jié)束?！?*……*/”表示對(duì)函數(shù)或語句的功能作注釋。在“/”和“*”之間不能有空格，且“/*”和“*/”必須配對(duì)使用。注釋是供人閱讀的，并不參與編譯和運(yùn)行。注釋可以出現(xiàn)在程序的任何地方，添加必要的注釋可以提高程序的可讀性。源程序中可以使用預(yù)處理命令(如include命令、define命令)，預(yù)處理命令以“#”開頭，一般預(yù)處理命