《C++程序設(shè)計語言快速入門》校本課程

C++快速入門

以下將引導(dǎo)你快速進(jìn)入編程的世界。

前言：

學(xué)習(xí)編程，選何種語言不是關(guān)鍵點，能快速入門并使用它建立自己的

工程并解決問題是本課程考慮的重點。

C++本身的代碼簡潔性以及傳承于c的特性，便利的現(xiàn)成的代碼復(fù)用

使得其有很多優(yōu)勢，適合課堂教學(xué)的同時.，兼顧了工程開發(fā)應(yīng)用，就

選它吧。

第一部分：

1、學(xué)習(xí)環(huán)境的搭建：

為了方便學(xué)習(xí)，我們在windows系統(tǒng)下寫代碼，用在線評測系統(tǒng)OJ

評測。本教程使用評測練習(xí)。十一中0J的域名目前

為o

首先下載devc++安裝，裝完然后可以選擇Chinesesimple語言，以及

debug編譯模式，其他一切默認(rèn)。

2、第一個程序：1.HelloWorld!

noi題庫1.1.01

CtrlN新建文檔。

鍵入以丁代碼：〃為注釋語句，用于幫助閱讀代碼含義

#include<iostream>〃包含庫文件

#include<cstdio>〃包含庫文件，一些基本輸入輸出的語句定義在此

usingnamespacestd;〃聲明命名空間

intmain()〃主函數(shù)

(

printf("Hello,World!")；〃我們要編寫的代碼區(qū)域

return0;〃表示程序正常運行結(jié)束并返回

)

注意標(biāo)點符號，C++每一個語句以分號結(jié)尾”是英文狀態(tài)下的標(biāo)點

符號，否則會編譯錯誤。

C++編譯生成二進(jìn)制的可執(zhí)行exe文件。編譯運行(F11),將在屏幕

上輸出Hello,World!o

今后我們的主要工作就是編寫紅色部分內(nèi)容的代碼。

3、C++是函數(shù)式語言，利用函數(shù)實現(xiàn)各種功能操作

例子2.noi題庫1.3.01

:A+B問題

總時間限制:1000ms內(nèi)存限制：65536kB

描述

在大部分的在線題庫中，都會將A+B問題作為第一題，以幫助新手熟悉平臺的使

用方法。

A+B問題的題目描述如下：給定兩個整數(shù)A和B,輸出A+B的值。保證A、B

及結(jié)果均在整型范圍內(nèi)。

現(xiàn)在請你解決這一問題。

輸入

一行，包含兩個整數(shù)A,B,中間用單個空格隔開。A和B均在整型范圍內(nèi)。

輸出

一個整數(shù)，即A+B的值。保證結(jié)果在整型范圍內(nèi)，

樣例輸入

12

樣例輸出

3

^include<iostream>〃包含庫文件

ffinclude<cstdio>〃包含庫文件，一些基本輸入輸出的語句定義在此

usingnamespacestd;〃聲明命名空間

intmain()〃主函數(shù)

(

inta,b;〃定義兩個整數(shù)型變量

scanf("%d%d",&a,&b);//&取變量的地址，從鍵盤讀入，以空格分隔，分別賦值

給兩個變量a和b

printf("%d",a+b);〃偷出a+b的值

return0;〃表示程序正常運行返回

)

4、變量：

變量：可視為在計算機的內(nèi)存中開辟的一段用于臨時存儲數(shù)據(jù)的

容器。

約定：變量使用前要事先聲明數(shù)據(jù)類型。

標(biāo)識符就是程序員自己起的名字，除了變量名，后面還會講到函

數(shù)名、標(biāo)號等。不過，名字也不能隨便起，C語言規(guī)定，標(biāo)識符只能

由字母(A?Z,a?z)、數(shù)字(0~9)和下劃線(_)組成，并且第一個字符必

須是字母或下劃線。

以下標(biāo)識符是合法的：

a,x,x3,BOOK_1,sum5

以下標(biāo)識符是非法的：

3s不能以數(shù)字開頭

S*T出現(xiàn)非法字符*

-3x不能以減號(-)開頭

bowy-1出現(xiàn)非法字符減號(-)

另一份a加b的代碼：例2.1

#include<iostream>

include<cstdio>〃包含庫文件，一些基本輸入輸出的語句定義在此

usingnamespacestd;〃聲明命名空間

intmain()〃主函數(shù)

(

inta,b,sum;〃定義兩個整數(shù)型變量

cin>>a?b;〃8J(Z變量的地址，從鍵盤讀入以空格分隔的數(shù)，分別賦值給變量a和b

sum=a+b;//a+b的和復(fù)制給變量sum

cout?sum;〃輸出sum的值

return0;〃表示程序正常運行返回

)

函數(shù)cin和cout功能類似于scanf和printf,為流式輸入輸出，函數(shù)

scanf和printf是格式化輸入輸出，使用時格式更嚴(yán)格。

注意這里的“二”是賦值語句操作符，不是數(shù)學(xué)上的等號。

第二部分：順序，分支，循環(huán)語言結(jié)構(gòu)

1、選擇結(jié)構(gòu)：

以上為順序執(zhí)行的一系列語句。

程序設(shè)計一般分為順序，分支，循環(huán)。

以下為分支語句代碼例子，以if語句為例

基本語法為：

ifelse語句的結(jié)構(gòu)為：

if（表達(dá)式）

（

語句塊1

}

else

（

語句塊2

）

意思是：如果表達(dá)式的值為真，則執(zhí)行語句塊1,否則執(zhí)行語句塊2o

其執(zhí)行過程可表示為下圖：

語句塊

1|語句塊2

可以只有if而沒有else,但要注意if和else的配對關(guān)系，最好利用縮

進(jìn)對齊，養(yǎng)成好的書寫代碼習(xí)慣，提高代碼可讀性，便于以后自己閱

讀調(diào)試，也利于在大型工程中便于協(xié)同合作。

可以嵌套：語句塊1和語句塊2中，可以包含if語句或者其他，稱為

嵌套。

例如：L4.03奇偶數(shù)判斷

總時間限制：1000ms

內(nèi)存限制：65536kB

描述

給定一個整數(shù)，判斷該數(shù)是奇數(shù)還是偶數(shù)。

輸入

輸入僅一行，一個大于零的正整數(shù)n。

輸出

輸出僅一行，如果n是奇數(shù)，輸出odd；如果n是偶數(shù)，輸出even。

樣例輸入

5

樣例輸出

odd

來源

北京大學(xué)計嵬概論06

參考源代碼

#include<cstdio>

#include<iostream>

usingnamespacestd;

innmain()(

intn;

cin>>n;

if(n%2==l)cout<<noddn;

elsecout<<"even";

return0;

例如：期末考試成績出來了，我們把它分下類：90~100為“Great”；

70?89為“Good"；60~69為“Average"；0?59位“Poor”。

#include<cstdio>

usingnamespacestd;

intmain()

{inta;

scanf("%d",&a);

if(90<=a&&a<=100)

(

printf("Great");

)

else

(

if(70<=a&&a<=89)

(

printf("Good")；

)

else

(

if(60<=a&&a<=69)

(

printf("Average")；

}

else

(

if(0<=a&&a<=59)

(

printff'Poor");

)

)

)

)

return0;

}

注意邏輯表達(dá)式常常會用到&&表示且,||表示或，！表示取反。擔(dān)心

運算優(yōu)先級引起混亂的，可以用小括弧。

練習(xí)：十一中0J上的第7題，if語言題目。

對于switch語句，請自行閱讀了解。

另外一種多分支選擇的語句一一switch語句，它的基本語法格式如

下：

switch（表達(dá)式）｛

case常量表達(dá)式1:

語句塊1；

break;

case常量表達(dá)式2:

語句塊2;

break;

case常量表達(dá)式n:

語句塊n;

break;

default:

語句塊n+1;

）

它的執(zhí)行過程是：首先計算“表達(dá)式”的值，然后從第一個case開

始，與“常量表達(dá)式x”進(jìn)行比較，如果與當(dāng)前常量表達(dá)式的值不相

等，那么就不執(zhí)行冒號后邊的語句塊，一旦發(fā)現(xiàn)和某個常量表達(dá)式的

值相等了，那么它會執(zhí)行之后所有的語塊。注意每個語句塊后面要加

上break,否則會不判斷接下來是否相等一直執(zhí)行下去。如果直到最

后一個“常量表達(dá)式n”都沒有找到相等的值，那么就執(zhí)行default后

的“語句n+r\

一個更加簡潔的分支選擇方法，叫做條件運算符，語法格式為：

表達(dá)式1?表達(dá)式2:表達(dá)式3

條件運算符是C語言中唯一的一個三目運算符，其求值規(guī)則為：如果

表達(dá)式1的值為真，則以表達(dá)式2的值作為整個條件表達(dá)式的值，

否則以表達(dá)式3的值作為整個條件表達(dá)式的值。條件表達(dá)式通常用于

賦值語句之中。

例如求最值：

if(a>b)mymax=a;

elsemymax=b;

上面的ifelse語句等價于：

mymax-(a>b)?a:b;

該語句的語義是：如a>b為真，則把a賦予mymax,否則把b賦予

mymaxo

你可以認(rèn)為條件運算符是一種簡寫的ifelse,你完全可以用ifelse

代替條件運算符。

2、循環(huán)結(jié)構(gòu)：

例如，輸出1到100的所有整數(shù)之和。

語法：while(邏輯表達(dá)式)

循環(huán)體語句塊

)

注意循環(huán)條件，耍能夠正常結(jié)束循環(huán)，一般在循環(huán)體中不斷更新循環(huán)

條件，最終循環(huán)條件不滿足，跳出循環(huán)，否則死循環(huán)將導(dǎo)致程序不能

正常結(jié)束。同時循環(huán)體內(nèi)也可以有新的循環(huán)語句，構(gòu)成循環(huán)的嵌套。

例3.1

#include<cstdio>

#include<iostream>

usingnamespacestd;

intmain()

(

inta=l,s=O;〃變量要初始化，否則可能是個隨機的值

while(a<=100)〃循環(huán)條件

(

s=s+a;〃每循環(huán)一次，累加到變量s

a++;//a=a+l的簡寫

printf("%d\n",s);〃輸出s變量的值并換行

)

return0;

)

延伸：偶數(shù)和？

3、程序的調(diào)試，debug

點擊行號可以為程序添加斷點，使程序運行到某一步停下來，等待我

們手動執(zhí)行下一步，此時可以查看某些變量實時的值，或者在程序中

添加中間變量輸出，以判斷程序執(zhí)行中是否按我們的意愿執(zhí)行。

作業(yè)：完成十一中0J上的8號題目。

參考代碼：

#include<cstdio>

intmain()

(

intn,a,sum=O;

scanf("%d",&n);

inti=l;

while(i<=n)

(

scanf("%d",&a);

sum=sum+a;

i++；

)

printf("%d",sum);

re:urn0;

十一中0J上的13號題目

伊J：假設(shè)一個三位數(shù)x的百位、十位、個位上的數(shù)字分別為a、b、c,如果

a人3+b3+c人3恰好等于x,則稱x為水仙花數(shù)，如：153就是一個水仙花數(shù)，

1八3+5八3+3A3=1+125+27=153。請編寫程序判斷一個三位正整數(shù)是否是水仙

花數(shù)。

用到取余運算符％

參考代碼：

#include<iostr€am>

#include<cstdio>

usingnamespacestd;

intmain()

(

intnumber,gewei,shiwei,baiwei;

seanf("%d"^number);

gewei=number%10;

shiwei=number/10%10;

baiwei=number/100;

if

(gewei*gewei*gewei+shiwei*shiwei*shiwei+baiwei*baiwei*baiw

ei==number)

(

printf："TRUE");

)

else

(

printf；"FALSE");

)

return0;

)

我國古代算術(shù)問題，百錢百雞問題:

#include<iostream>

#include<cstdio>

usingnamespacestd;

intmain()

(

inta,b,c;

a=l；

while(a<=100)

(

b=l;

while(b<=100)

(

c=3;

while(c<=99)

(

if((5*a+3*b+c/3==100)&&(a+b+c==100))

(

printf("公雞=%匕母雞=%d,小雞=%d\n”,a,b,c);

)

c=c+3;

)

b++;

)

a++;

}

return0;

)

綜合練習(xí)：計算1到100能被3整除或者能被5整除的所有數(shù)之和。

#include<cstdio>

#include<iostream>

usingnamespacestd;

intmain()

(

inta=l,s=0;

while(a<=100)

(

if(a%3==0||a%5==0)

s+=a;

a++;

)

printf("%d\n",s);

return0;

)

邏輯運算符||&&

scant()語句和printf()語句是標(biāo)準(zhǔn)格式化輸入輸出語句

參考

scanf和printf這兩個函數(shù)分別稱為格式輸入函數(shù)和格式輸出函數(shù)。其意義是按指定的格式輸

入愉出值。因此，這兩個函數(shù)在括號中的參數(shù)都由以下兩部分組成：

1)格式控制審：格式控制串是一個字符串，必須用雙引號括起來，它表示了輸入輸出量的數(shù)

據(jù)類型。

在printf函數(shù)中可以在格式控制串內(nèi)出現(xiàn)非格式控制字符，這時在顯示屏幕上會顯示源字符

串。各種類型的格式表示方式請參考：C語言格式輸出函數(shù)printf。詳解C語言格式輸出函

數(shù)prirtfO詳解

在scanf函數(shù)中也可以在格式控制串內(nèi)出現(xiàn)非格式控制符，這時會將輸入的數(shù)據(jù)以該字符為

分隔。各種類型的格式表示方式請參考：C語言scanf()函數(shù)。C語言scanf()函數(shù)。

2)參數(shù)表：參數(shù)表中給出了輸入或輸出的變量。當(dāng)有多個變量時，用英文逗號(,)分開。例如：

printf("sineof%lfis%lf\n",xzs);

〃％lf為格式字符，表示按雙精度浮點數(shù)處理，它在格式串中兩次現(xiàn)，對應(yīng)了x和s兩個變量

//其余字符為非格式字符則照原樣輸出在屏幕上。

scanf("%d%fa%c",&intNum,&floatNum,&c);

〃％d,%f,%c為格式字符

//表示將輸入的數(shù)據(jù)分別以整數(shù)、浮點數(shù)和字符形式賦值給變量intNum,floatNum,c

//其中的空格和a為分隔符

〃變量intNum,floatNum,c都有一個'&'符號，表示取地址

例如計算兩個實數(shù)的和a+b,cin和cout更簡潔一些

ffinclude<iostream>#include<iostream>

#include<cstdio>#include<cstdio>

usingnamespacestd.usingnamespacestd;

intmain()intmain()

{floata,b;{floata,b;

scanf("%f%f",&c,&b);cin?a?b;

printf("%f\n",a+b);cout?a+b?endl;

return0;return0;

)

4、for循環(huán)結(jié)構(gòu)

格式：for（語句1；邏輯表達(dá)式2；語句3）

語句塊：循環(huán)體

）

先執(zhí)行語句1,然后邏輯表達(dá)式2,分兩種情況：如為真（非0）,則

執(zhí)行循環(huán)體，然后執(zhí)行語句3；如為假，則不執(zhí)行循環(huán)體，結(jié)束循環(huán)。

注意：表達(dá)式1僅在第一次循環(huán)時求解，以后都不會再執(zhí)行，可以認(rèn)

為這是一個初始化語句。

1）for循環(huán)中的“表達(dá)式1（循環(huán)變量賦初值）”、“表達(dá)式2（循環(huán)條件）”

和“表達(dá)式3（循環(huán)變量增量）”都是選擇項，即可以缺省，但分號（;）

不能缺省。

2）省略了“表達(dá)式1（循環(huán)變量賦初值）”，表示不對循環(huán)控制變量賦

初值。

3）省略了“表達(dá)式2（循環(huán)條件）”，如果不做其它處理就會成為死循環(huán)。

for循環(huán)的執(zhí)行過程可用下圖表示:

高斯求和問題循環(huán)代碼對比:

#include<cstdio>#include<cstdio>

#include<iostream>#include<iostream>

usingnamespacestd;usingnamespacestd;

intmain()intmain()

((

inta=l,s=0;inti,s~O;

while(a<=100)for(i=l;i<=100;i++)

((

s+=a;//s=s+as+=i;

a++;

)

)cout?s;

printf("%d\n",s);return0;

return0;

)

)

練習(xí)使用for語句改寫百錢百雞問題求解。

樣例代碼：

^include<iostream>

ffinclude<cstdio>

usingnamespacestd;

intmain(){

for(inta=l;a<=20;a++){

fur(inlb=l;b<=33;b++){

for(intc=3;c<=99;c=c+3){

if((5*a+3*b+c/3==100)&&(a+b+c==10C))

(

cout?a?""?b?""?c?endl;

)

return0;

)

請自行學(xué)習(xí)和驗證break和continue語句。

break語句

break可以用來跳出switch語句。當(dāng)break語句用于while、for循環(huán)

語句中時，會終止循環(huán)而執(zhí)行循環(huán)語句后面的代碼。break語句通常

和if語句一起使用，卻滿足條件時便跳出循環(huán)。

continue語句

continue語句的作用是跳過循環(huán)體中剩余的語句而強行執(zhí)行下一次

循環(huán)。continue語句只用在while、for循環(huán)中，常與if條件語句一

起使用，判斷條件是否成立。

第三部分?jǐn)?shù)組和指針

數(shù)組問題：

觀察以下代碼：并運行之。

#include<cstdio>

/include<iostream>

usingnamespacestd;

inta[110];

intmain()

(

inti,s=O;

for(i=l;i<=100;i++)

(

a[i]=i；

)

for(i=l;i<=100;i++)

(

s=s+a(i);

)

cout?s;

return0;

)

該代碼表示開一個大小為110的數(shù)組(相當(dāng)于110個變量)，分別給

a[l]=l;a[2]=2;a[3]=3;……a[100]=100燃后將這100各變量的值累加。

定義數(shù)組就是定義一批變量，然后通過下標(biāo)序號方便地引用變量。數(shù)

組可以是多維的，如3維數(shù)組arr[1000][1000][1000],其包含的變量數(shù)

為le9.

注意定義數(shù)組要放在主函數(shù)之外，以免內(nèi)存不足，特別注意的是，數(shù)

組內(nèi)第一個元素是而不是同理也要注意最后一個元素

arr[O],arr[l]o

的編號。

完成H^一中上的習(xí)題15,數(shù)組練習(xí)。

有n個整數(shù)，分別為a(l),a(2),a(3)...a(n)o

現(xiàn)在詢問你m次，第i次洵問一個整數(shù)q(i),問你a(q(i))是什么？

參考代碼：

#include<cstdio>

#include<iostream>

usingnamespacestd;

constintkN=le5+10;

intarr[kN];

intmaini)

(

intn,m;

cin?n?m;

for(inti=1;i<=n;i++)

(

cin?arr[i];

)

for(inti=1;i<=m;i++)

(

intx;

cin?x;

cout?arr[x]?endl;

)

return0;

)

數(shù)組名為該數(shù)組的首地址。數(shù)組名字退化為指針，所以數(shù)組名arr實

際指的是數(shù)組的第一個元素的地址，初學(xué)者建議使用&arr[number]訪

問數(shù)組的地址。

變量的內(nèi)存地址：系統(tǒng)分配內(nèi)的變量編號。類似于學(xué)籍號或者身份證

號，變量名是我們給變量起的昵稱，便于我們?nèi)四X的閱讀和識別。

第四部分：文件輸入輸出重定向：以十一中第8題為例：

freopen函數(shù)，源程序*.cpp和讀入數(shù)據(jù)文件*.in放在同一層目錄下,

否則需加路徑。將樣例數(shù)據(jù)寫入data.in,運行程序后，將會把結(jié)果輸

出到文件result.out

主要用于本地測試。在調(diào)試環(huán)境中運行程序，輸入測試數(shù)據(jù)，當(dāng)能得

到正確運行結(jié)果后，才將程序提交到oj中

#include<cstdio>

intmain()

(

freopenf'data.in'V'r'^stdin);

freopen("result.out","w",stdout);

intn,b,sum=O;

scanf("%d",&b);

inti=l;

while(i<=b)

{scanf("%d",&n];

sum+=n;

i++;

)

printf("%d",sum);

fclose(stdin);

fclose(stdout);

return0;

)

在使用完一個文件后應(yīng)該關(guān)閉它，這應(yīng)該成為一個習(xí)慣。如果不關(guān)閉

文件，可能會丟失數(shù)據(jù)。因為在向文件寫數(shù)據(jù)時，實現(xiàn)將數(shù)據(jù)輸?shù)骄?/p>

沖區(qū)，待緩沖區(qū)充滿后才正式輸出給文件，如果當(dāng)數(shù)據(jù)未充滿緩沖區(qū)

而程序結(jié)束運行，就會將緩沖區(qū)中的數(shù)據(jù)丟失。用fclose函數(shù)關(guān)閉義

件，他先將緩沖區(qū)中的數(shù)據(jù)輸出到磁盤文件然后才釋放文件指針變

量，從而避免了數(shù)據(jù)丟失。

第五部分：0記號

排序：一排n個正整數(shù)，要求由小到大排序。

1、冒泡算法

經(jīng)典排序算法?冒泡排序Bubblesort

原理是臨近的數(shù)字兩兩進(jìn)行比較，按照從小到大或者從大到小的順序進(jìn)行交換,

這樣一趟過去后,最大或最小的數(shù)字被交換到了最后一位，

然后再從頭開始進(jìn)行兩兩比較交換，直到倒數(shù)第二位時結(jié)束，其余類似看例子

例子為從小到大排序，

原始待排序數(shù)組［612141115191

第一趟排序（外循環(huán)）

第一次兩兩比較6>2交換（內(nèi)循環(huán)）

交換前狀態(tài)I61214|1|5|9|

交換后狀態(tài)I21614|1|5|9|

第二次兩兩比較,6>4交換

交換前狀態(tài)|2I6I4I1|5|9|

交換后狀態(tài)I2I4I6I1|5|9|

第三次兩兩比較,6>1交換

交換前狀態(tài)I2|416111519|

交換后狀態(tài)|2|411161519|

第四次兩兩比較,6>5交換

交換前狀態(tài)I2|4|1I6I5I9|

交換后狀態(tài)I2|4|1I5I6I9|

第五次兩兩比較,6<9不交換

交換前狀態(tài)I2|4|1|5I6I9I

交換后狀態(tài)I2|4|1|5I6I9I

第二趟排序（外循環(huán)）

第一次兩兩比較2v4不交換

交換前狀態(tài)I21411|5|6|9

交換后狀態(tài)I21411|5|6|9

第二次兩兩比較,4>1交換

交換前狀態(tài)|2I4I1I5|6|9

交換后狀態(tài)|2I1I4I5|G|9

第三次兩兩比較,4<5不交換

交換前狀態(tài)|2|114151619

交換后狀態(tài)|2|1I4I5I6|9

第四次兩兩比較,5<6不交換

交換前狀態(tài)|2|1|4I5I6I9

交換后狀態(tài)|2|1|4|5I6I9

第三趟排序（外循環(huán)）

第一次兩兩比較2>1交換

交換后狀態(tài)I21114|5|6|9

交換后狀態(tài)I11214|5|6|9

第二次兩兩比較,2<4不交換

交換后狀態(tài)|1I2I4I5|6|9

交換后狀態(tài)I1121415|6|9

第三次兩兩比較,4<5不交換

交換后狀態(tài)|1|2I4I5I6|9

交換后狀態(tài)|1|2I4I5I6|9

第四趟排序（外循環(huán)）無交換

第五趟排序（外循環(huán)）無交換

排序完畢,輸出最終結(jié)果124569

復(fù)雜度分析:

n+n2+n

#include<cstdio>

#include<iostream>

usingnamespacestd;

intmain()

(

intarray(10]={15,225,34,42,52,6,7856,865,

954,10);

inti,j;

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

(

〃每一次由底至上地上升

for(j=0;j<9-i;j++)

(

if(arrayO+l]<array[j]l〃大數(shù)往后移

(

inttemp;

temp=array[j+l]；

array[j+l)=array[j]；

array[j]=temp;

)

)

)

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

(

printf("%d\n",array[i]);

)

return0;

//解法一：口泡排序

//空間復(fù)雜度:0(n),時間復(fù)雜度:0(M2)

//預(yù)計得分：70

ttinclude<cstdio>

usingnamespaces:d;

constintkN=le5+10;

intarr[kN],N;

intmain()

(

scanfC%d",&N);

for(inti=1;i<=N;i++)

(

scanfC^d",&arr[i]);

)

for(inti=1;i<=N;i++)

{

for(intj=N;j>i;j--)

(

if(arr[j]<arr[j-l])〃小數(shù)往前移

(

intt=arr[j];

arr[j]=arr[j-l]；

arr[j-l]=t;

)

)

}

for(inti=1;i<=N;i++)

(

printf("%d",arr[i]);

)

return0;

)

Debug兩份代碼，查看數(shù)組元素中的值是如何交換的。

2、桶排序。

桶排序顧名思義是把數(shù)據(jù)按照大小//解法二：桶排序

//空間復(fù)雜度:0(m),時間復(fù)雜

分塊，每一塊的放到一個桶里，第二度：O(n+m)m為需要排序的數(shù)字

的最大值

個桶的所有數(shù)大于第一個桶的所有//預(yù)計等分：100

#include<cstdio>

數(shù)，第三個桶的所有數(shù)大于第二個桶usingnamespacestd;

constintkM=5e5+10;

所有的數(shù)……這一步的實現(xiàn)有多種方intcnt[kM],N;

intmain{)

法，如果要在0（n）內(nèi)一般要用類似于(

scanf("%d",&N);

建立哈希表的方法（但并不完全相for；inti=1;i<=N;i++)

(

同，桶排序要求桶之間是有大小順序intx;

scanf("%d",&x);

的）。然后每個桶里的數(shù)據(jù)然后再進(jìn)cnt(x]+=1;

}

行排序，排序方法任選，當(dāng)然也可以

for；inti=0;i<kM;i++)

再用桶排序（例如先以最高位為鍵值{

for(intj=0;j<cnt(i];j++)

進(jìn)行桶排序，再以次高位為鍵值進(jìn)行(

printf("%d",i);

桶排序，直到個位）。}

}

return0;

)

字符：chardata

字符數(shù)組：chararr[UO]

字符串：strings

數(shù)據(jù)類型為字符型的變量，在內(nèi)存中和int型變量的存儲是一樣的。

數(shù)組名是字符數(shù)組的首地址，和數(shù)組首元素的地址相等。

例如chara

scanf("％c，&a);〃表示由控制臺讀入一個字符

字符在計算機中是以二進(jìn)制存儲的，

ASCII碼規(guī)定了128個英文字符與二進(jìn)制的對應(yīng)關(guān)系，占用一個字節(jié)(實際上只占用了一個

字節(jié)的后面7位，最前面1位統(tǒng)一規(guī)定為0\例如，字母a的的ASCU碼為01100001,

那么你暫時可以理解為字母a存儲到內(nèi)存之前會被轉(zhuǎn)換為01100001,讀取時遇

到01100001也會轉(zhuǎn)換為a0

請嘗試編程輸出表中的字符。

延伸知識:ASCII碼和Unicode碼

include<cstdio>

#include<iostream>

usingnamespacestd;

intmain()

(

for(inti=0;i<128;i++)

(

printf("%c\n",char(i));

)

return0;

第六部分：自定義函數(shù)

函數(shù)

Max函數(shù)的實現(xiàn)#include<cstdio>

#include<iostream>

usingnamespacestd;

intmax(intm,intn){

if(m>n)

returnm;

else

returnn;

)

intmain(){

inta,b,ans;

printf("lnputtwonumber:");

scanf("%d%d",&a,&b);

ans=max(a,b);

printf("Thebigeris%d\n",ans);

return0;

也可用三元運算符返回，比如max=(m>n)?m:n;

例：將組成單詞的字母反序輸出：

"include<cstdio>

^include<iostream>

usingnamespacestd;

chars[100];

intmain(){

intlen=O;

while(cin?s[len])

len++;

for(inti=len-l;i>=O;i-)

cout?s[i];

return0;

不例：計算l+2+3+...+(n-l)+n的值。

#include<cstdio>

#include<iostream>

usingnamespacestd;

intsum(intn){

inti;

for(i=n-l;i>=l;i-)

(

n+=i;

)

prin:f("Theinnern=%d\n",n);

returnn;

)

intmain(|{

int「，total;

scanf("%d",&n);

total=sum(n);

prin^("l+2+3+...+(n-l)+n=%d\n",total);

return0,

}

階乘函數(shù)

一個函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱為遞歸調(diào)用，這種函數(shù)稱為遞歸函數(shù)。

執(zhí)行遞歸函數(shù)將反復(fù)調(diào)用其自身,每調(diào)用一次就進(jìn)入新的一層。

【示例】用遞歸計算出。階夷n!的計算公式如下：

,(1(H=0.1]

n，[n*(n-1)!(n>1)

根據(jù)公式編程：

/include<cstdio>

#include<iostream>

usingnamespacestd;

longlongfac(intn)

(

longlongf;

if(n==l)

f=l；

else

f=n*fac(n-l);

returnf;

)

intmain()

(

inta,

longlongresult;

cin?a;

for(inti=l;i<=a;i++)

(

result=fac(i);

cout?result?endl;

}

return0;

}

第七部分：遞歸

一般來說，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)

邊界條件不滿足時，遞歸前進(jìn)；當(dāng)邊界條件滿足時，遞歸返回。

注意：遞歸就是調(diào)用自身，在使用遞歸策略時，必須有一個

明確的遞歸結(jié)束條件，稱為遞歸出口。

遞歸算法一般用于解決三類問題：

（1）數(shù)據(jù)的定義是按遞歸定義的。（Fibonacci函數(shù)）

⑵問題解法按遞歸算法實現(xiàn)。（回溯）

⑶數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。（樹的遍歷，圖的搜索）

*遞歸的缺點：

遞歸算法解題的運行效率較低。在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為

每一層的返回點、局部量等開辟了棧來存儲。遞歸次數(shù)過多容

易造成棧溢出等。

練習(xí)：的第20題。

階乘，一個正整數(shù)的階乘(英語：factorial)是所有小于及等于該數(shù)的正整數(shù)的枳，并且有

。的階乘為1。自然數(shù)n的階乘寫作n!。1808年，基斯頓?卡曼引進(jìn)這個表示法。

任何大于1的自然數(shù)n階乘表示方法：

n!=lx2x3x---(n-l)n

參考代碼:#include<cstdio>

#include<iostream>

usingnamespacestd;

longlongfactfintn){

longlongf=l;

for(inti=l;i<=n;i++)

(

f=fi;

)

returnf;

)

intmain(){

inta;

cin?a;

cout?fact(a)?endl;

return0;