信息學(xué)奧賽課課通(C++)第5單元-電子課件

第5單元數(shù)組作者：林厚從信息學(xué)奧賽課課通（C++）第5單元數(shù)組作者：林厚從信息學(xué)奧賽課課通（C++）第1課一維數(shù)組的定義學(xué)習(xí)目標(biāo)1.理解數(shù)組的含義。2.學(xué)會(huì)一維數(shù)組的定義。3.掌握一維數(shù)組的元素引用和物理存儲(chǔ)方式。第1課一維數(shù)組的定義學(xué)習(xí)目標(biāo)數(shù)組數(shù)組就是一組相同類型的變量，它們往往都是為了表示同一批對(duì)象的統(tǒng)一屬性，如一個(gè)班級(jí)所有同學(xué)的身高、全球所有國(guó)家的人口數(shù)等。數(shù)組可以是一維的，也可以是二維或多維的。數(shù)組數(shù)組就是一組相同類型的變量，它們往往都是為了表示同一批對(duì)1.一維數(shù)組的定義定義一維數(shù)組的格式如下：類型標(biāo)識(shí)符數(shù)組名[常量表達(dá)式];其中，類型標(biāo)識(shí)符可以是任何基本數(shù)據(jù)類型，也可以是結(jié)構(gòu)體等構(gòu)造類型，相同類型的數(shù)組可以一起定義。數(shù)組名必須是合法的標(biāo)識(shí)符。常量表達(dá)式的值即為數(shù)組元素的個(gè)數(shù)。1.一維數(shù)組的定義定義一維數(shù)組的格式如下：2.一維數(shù)組的元素引用數(shù)組定義好后，就可以引用（調(diào)用）其中的任意一個(gè)元素。引用格式為：數(shù)組名[下標(biāo)]如：h[5]、h[i*2+1]等。其中，下標(biāo)只能為整型常量或整型表達(dá)式，值必須在數(shù)組定義的下標(biāo)范圍內(nèi)，否則會(huì)出現(xiàn)“下標(biāo)越界錯(cuò)誤”。需要注意的是，不能一次引用整個(gè)數(shù)組，只能逐個(gè)引用數(shù)組的單個(gè)元素。2.一維數(shù)組的元素引用數(shù)組定義好后，就可以引用（調(diào)用）其中3.一維數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組在計(jì)算機(jī)內(nèi)存單元中是連續(xù)存儲(chǔ)的。程序一旦執(zhí)行到數(shù)組的定義語(yǔ)句，就會(huì)開(kāi)辟出若干字節(jié)的內(nèi)存單元。3.一維數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組在計(jì)算機(jī)內(nèi)存單元中是連續(xù)存儲(chǔ)的。實(shí)踐鞏固實(shí)踐鞏固第2課一維數(shù)組的輸入與輸出學(xué)習(xí)目標(biāo)1.熟練掌握一維數(shù)組的輸入與輸出操作。2.學(xué)會(huì)應(yīng)用一維數(shù)組解決一些實(shí)際問(wèn)題。第2課一維數(shù)組的輸入與輸出學(xué)習(xí)目標(biāo)一維數(shù)組的輸入與輸出一維數(shù)組的輸入、輸出等操作，都是采用循環(huán)語(yǔ)句結(jié)合下標(biāo)變化，逐個(gè)元素進(jìn)行。一維數(shù)組的輸入與輸出一維數(shù)組的輸入、輸出等操作，都是采用循環(huán)批量數(shù)據(jù)一次性輸入到一維數(shù)組中（1）鍵盤逐個(gè)讀入數(shù)組元素值；（2）給每個(gè)數(shù)組元素直接賦值；批量數(shù)據(jù)一次性輸入到一維數(shù)組中（1）鍵盤逐個(gè)讀入數(shù)組元素值給數(shù)組“整體”賦值（1）memset函數(shù)memset函數(shù)是給數(shù)組“按字節(jié)”進(jìn)行賦值，一般用在char型數(shù)組中，如果是int類型的數(shù)組，一般賦值為0和-1。使用前需要包含頭文件：#include<cstring>。（2）fill函數(shù)fill函數(shù)是給數(shù)組“按元素”進(jìn)行賦值，可以是整個(gè)數(shù)組，也可以是部分連續(xù)元素，可以賦任何值。使用前需要包含頭文件：#include<algorithm>。給數(shù)組“整體”賦值（1）memset函數(shù)例1、閱讀并上機(jī)調(diào)試程序，體會(huì)memset和fill函數(shù)的作用。//p5-2-1#include<iostream>#include<cstring>usingnamespacestd;intmain(){inta[10],b[10],c[10],d[10],i;memset(a,0,sizeof(a));//將a數(shù)組所有元素均賦值為0for(i=0;i<9;i++)cout<<a[i]<<““;cout<<a[9]<<endl;memset(b,1,sizeof(b));//將b數(shù)組所有元素均賦值為//二進(jìn)制數(shù)2^0+2^8+2^16+2^24=16843009例1、閱讀并上機(jī)調(diào)試程序，體會(huì)memset和fillfor(i=0;i<9;i++)cout<<b[i]<<““;cout<<b[9]<<endl;memset(c,0,5);//將c數(shù)組前5個(gè)字節(jié)都賦值為0，所以只能確定c[0]//等于0，其他元素值不確定for(i=0;i<9;i++)cout<<c[i]<<““;cout<<c[9]<<endl;fill(d,d+5,8);//將d數(shù)組前5個(gè)元素都賦值為8，其他元素值不確定for(i=0;i<9;i++)cout<<d[i]<<““;cout<<d[9]<<endl;return0;}for(i=0;i<9;i++)cou例2、走樓梯【問(wèn)題描述】一個(gè)樓梯有n級(jí)，小蘇同學(xué)從下往上走，一步可以跨一級(jí)，也可以跨兩級(jí)。問(wèn)：他走到第n級(jí)樓梯有多少種走法？【輸入格式】一行一個(gè)整數(shù)n，0<n≤30?！据敵龈袷健恳恍衝個(gè)整數(shù)，之間用一個(gè)空格隔開(kāi)，表示走到第1級(jí)、第2級(jí)、……第n級(jí)分別有多少種走法?！据斎霕永?【輸出樣例】12例2、走樓梯【問(wèn)題描述】【問(wèn)題分析】假設(shè)f(i)表示走到第i級(jí)樓梯的走法，則走到第i(i>2)級(jí)樓梯有兩種可能：一種是從第i-1級(jí)樓梯走過(guò)來(lái)；另一種是從第i-2級(jí)樓梯走過(guò)來(lái)。根據(jù)加法原理，f(i)=f(i-1)+f(i-2)，邊界條件為：f(1)

=1，f(2)

=2。具體實(shí)現(xiàn)時(shí)，定義一維數(shù)組f，用賦值語(yǔ)句從前往后對(duì)數(shù)組的每一個(gè)元素逐個(gè)賦值。本質(zhì)上，f(i)構(gòu)成了斐波那契數(shù)列。【問(wèn)題分析】//p5-2-2#include<cstdio>usingnamespacestd;intmain(){intn,i,f[31];scanf(“%d”,&n);f[1]=1;f[2]=2;for(i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];for(i=1;i<n;i++)printf(“%d“,f[i]);printf(“%d\n”,f[n]);return0;}//p5-2-2例3、幸運(yùn)數(shù)的劃分【問(wèn)題描述】判斷一個(gè)正整數(shù)n是否能被一個(gè)“幸運(yùn)數(shù)”整除。幸運(yùn)數(shù)是指一個(gè)只包含4或7的正整數(shù)，如7、47、477等都是幸運(yùn)數(shù)，17、42則不是幸運(yùn)數(shù)?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，1≤n≤1000?！据敵龈袷健恳恍幸粋€(gè)字符串，如果能被幸運(yùn)數(shù)整除輸出“YES”；否則，輸出“NO”?！据斎霕永?7【輸出樣例】YES例3、幸運(yùn)數(shù)的劃分【問(wèn)題描述】//p5-2-3#include<cstdio>usingnamespacestd;intmain(){intn,lucky[14]={4,7,44,47,74,77,444,447,474,477,744,747,774,777};//在數(shù)組定義時(shí)給數(shù)組賦值scanf(“%d”,&n);boolflag=false;for(inti=0;i<14;i++)if(n%lucky[i]==0)flag=true;if(flag)printf(“YES\n”);elseprintf(“NO\n”);return0;}【問(wèn)題分析】分析發(fā)現(xiàn)，1~1000范圍內(nèi)的幸運(yùn)數(shù)只有14個(gè)。于是，將這14個(gè)幸運(yùn)數(shù)直接存儲(chǔ)到一個(gè)數(shù)組lucky中，再窮舉判斷其中有沒(méi)有一個(gè)數(shù)能整除n。//p5-2-3【問(wèn)題分析】例4、陶陶摘蘋果【問(wèn)題描述】陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會(huì)結(jié)出10個(gè)蘋果。蘋果成熟的時(shí)候，陶陶就會(huì)跑去摘蘋果。陶陶有一張30厘米高的板凳，當(dāng)她不能直接用手摘到蘋果的時(shí)候，就會(huì)踩到板凳上再試試?，F(xiàn)在已知10個(gè)蘋果到地面的高度，以及陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度，請(qǐng)幫陶陶算一下她能夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會(huì)掉下來(lái)?！据斎敫袷健康谝恍邪?0個(gè)100~200之間（包括100和200）的整數(shù)（以厘米為單位）分別表示10個(gè)蘋果到地面的高度，兩個(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。第二行只包括一個(gè)100~120之間（包含100和120）的整數(shù)（以厘米為單位），表示陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度。【輸出格式】一行一個(gè)整數(shù)，表示陶陶能夠摘到的蘋果的數(shù)目。例4、陶陶摘蘋果【問(wèn)題描述】【輸入樣例】100200150140129134167198200111110【輸出樣例】5【問(wèn)題分析】定義一個(gè)數(shù)組保存10個(gè)蘋果到地面的高度，再根據(jù)陶陶踩在板凳上的高度來(lái)統(tǒng)計(jì)她能夠摘到的蘋果數(shù)目?！据斎霕永俊締?wèn)題分析】//p5-2-4#include<iostream>usingnamespacestd;intmain(){intapple[11],i,h,ans=0;for(inti=1;i<=10;i++)cin>>apple[i];cin>>h;for(i=1;i<=10;i++)if(h+30>=apple[i])ans++;cout<<ans<<endl;return0;}//p5-2-4實(shí)踐鞏固實(shí)踐鞏固第3課一維數(shù)組的插入刪除學(xué)習(xí)目標(biāo)1.學(xué)會(huì)一維數(shù)組的元素插入和刪除操作。2.應(yīng)用一維數(shù)組的插入和刪除操作解決一些實(shí)際問(wèn)題。第3課一維數(shù)組的插入刪除學(xué)習(xí)目標(biāo)一維數(shù)組的插入插入一個(gè)元素，需要先找到插入的位置(假設(shè)下標(biāo)為x)，將這個(gè)元素及其之后的所有元素依次往后移一位(注意要從后往前進(jìn)行操作)，再將給定的元素插入(覆蓋)到位置x，如圖5.3-1所示。一維數(shù)組的插入插入一個(gè)元素，需要先找到插入的位置(假設(shè)下標(biāo)為一維數(shù)組的刪除刪除某一個(gè)元素，也需要先找到刪除的位置(假設(shè)下標(biāo)為x)，將下標(biāo)為x+1及其之后的所有元素依次向前移一位，覆蓋原來(lái)位置上的元素，如圖5.3-2所示。一維數(shù)組的刪除刪除某一個(gè)元素，也需要先找到刪除的位置(假設(shè)下例1、插隊(duì)問(wèn)題【問(wèn)題描述】有n個(gè)人（每個(gè)人有一個(gè)唯一的編號(hào)，用1~n之間的整數(shù)表示）在一個(gè)水龍頭前排隊(duì)準(zhǔn)備接水，現(xiàn)在第n個(gè)人有特殊情況，經(jīng)過(guò)協(xié)商，大家允許他插隊(duì)到第x個(gè)位置。輸出第n個(gè)人插隊(duì)后的排隊(duì)情況?！据斎敫袷健康谝恍?個(gè)正整數(shù)n，表示有n個(gè)人，2<n≤100。第二行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示排在隊(duì)伍中的第1~第n個(gè)人的編號(hào)。第三行包含1個(gè)正整數(shù)x，表示第n個(gè)人插隊(duì)的位置，1≤x<n。例1、插隊(duì)問(wèn)題【問(wèn)題描述】【輸出格式】一行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示第n個(gè)人插隊(duì)后的排隊(duì)情況。【輸入樣例】772345613【輸出樣例】7213456【問(wèn)題分析】n個(gè)人的排隊(duì)情況可以用數(shù)組q表示，q[i]表示排在第i個(gè)位置上的人。定義數(shù)組時(shí)多定義一個(gè)位置，然后重復(fù)執(zhí)行：q[i+1]=q[i]，其中，i從n~x。最后再執(zhí)行q[x]=q[n+1]，輸出q[1]~q[n]?！据敵龈袷健俊締?wèn)題分析】//p5-3-1#include<cstdio>usingnamespacestd;intmain(){intn,i,x,q[102];scanf(“%d”,&n);for(i=1;i<=n;i++)scanf(“%d”,&q[i]);scanf(“%d”,&x);for(i=n;i>=x;i--)q[i+1]=q[i];q[x]=q[n+1];for(i=1;i<n;i++)printf(“%d“,q[i]);printf(“%d\n”,q[n]);return0;}//p5-3-1例2、隊(duì)伍調(diào)整【問(wèn)題描述】有n個(gè)人（每個(gè)人有一個(gè)唯一的編號(hào)，用1~n之間的整數(shù)表示）在一個(gè)水龍頭前排隊(duì)準(zhǔn)備接水，現(xiàn)在第x個(gè)人有特殊情況離開(kāi)了隊(duì)伍，求第x個(gè)人離開(kāi)隊(duì)伍后的排隊(duì)情況?！据斎敫袷健康谝恍?個(gè)正整數(shù)n，表示有n個(gè)人，2<n≤100。第二行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示排在隊(duì)伍中的第1個(gè)到第n個(gè)人的編號(hào)。第三行包含1個(gè)正整數(shù)x，表示第x個(gè)人離開(kāi)隊(duì)伍，1≤x≤n?！据敵龈袷健恳恍邪琻-1個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示第x個(gè)人離開(kāi)隊(duì)伍后的排隊(duì)情況。例2、隊(duì)伍調(diào)整【問(wèn)題描述】【輸入樣例】772345613【輸出樣例】724561【輸入樣例】//p5-3-2#include<cstdio>usingnamespacestd;intmain(){intn,i,x,q[102];scanf(“%d”,&n);for(i=1;i<=n;i++)scanf(“%d”,&q[i]);scanf(“%d”,&x);for(i=x;i<n;i++)q[i]=q[i+1];n--;for(i=1;i<n;i++)printf(“%d“,q[i]);printf(“%d\n”,q[n]);return0;}//p5-3-2實(shí)踐鞏固實(shí)踐鞏固第4課一維數(shù)組的查找統(tǒng)計(jì)學(xué)習(xí)目標(biāo)1.學(xué)會(huì)在一維數(shù)組中進(jìn)行順序查找和二分查找。2.熟練應(yīng)用查找和統(tǒng)計(jì)操作解決一些實(shí)際問(wèn)題。第4課一維數(shù)組的查找統(tǒng)計(jì)學(xué)習(xí)目標(biāo)一維數(shù)組的查找統(tǒng)計(jì)一維數(shù)組的查找操作，就是在一維數(shù)組中查找有沒(méi)有某個(gè)元素，它的值等于指定的值x。查找操作的結(jié)果可能是一個(gè)沒(méi)找到、找到一個(gè)或者找到很多個(gè)。常見(jiàn)的查找算法有“順序”查找和“二分”查找。順序查找就是按照從前往后的順序，將數(shù)組中的元素依次與要查找的數(shù)x進(jìn)行比較。二分查找又稱“折半”查找，其優(yōu)點(diǎn)是比較次數(shù)少、查找速度快。但是要求數(shù)據(jù)是遞增或遞減排序的。一維數(shù)組的查找統(tǒng)計(jì)一維數(shù)組的查找操作，就是在一維數(shù)組中查找有二分查找intleft=0，right=n-1;intfind=n;//find標(biāo)記找到的位置，初始化為n，表示沒(méi)找到while(left<=right){ intmid=(left+right)/2; if(a[mid]==x){//找到了，就標(biāo)記位置，并退出循環(huán) find=mid; break; } if(x<a[mid])right=mid-1;//x只能在左半部分 if(a[mid]<x)left=mid+1;//x只能在右半部分}if(find!=n)printf("%d\n",find);elseprintf("notfind\n");二分查找intleft=0，right=n-1例1、抽獎(jiǎng)1【問(wèn)題描述】公司舉辦年會(huì)，為了活躍氣氛，設(shè)置了搖獎(jiǎng)環(huán)節(jié)。參加聚會(huì)的每位員工都有一張帶有號(hào)碼的抽獎(jiǎng)券。現(xiàn)在，主持人依次公布n個(gè)不同的獲獎(jiǎng)號(hào)碼，小謝看著自己抽獎(jiǎng)券上的號(hào)碼num，無(wú)比緊張。請(qǐng)編寫一個(gè)程序，如果小謝獲獎(jiǎng)了，請(qǐng)輸出他中的是第幾個(gè)號(hào)碼；如果沒(méi)有中獎(jiǎng)，請(qǐng)輸出0?！据斎敫袷健康谝恍幸粋€(gè)正整數(shù)n，表示有n個(gè)獲獎(jiǎng)號(hào)碼，2<n≤100。第二行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示依次公布的n個(gè)獲獎(jiǎng)號(hào)碼。第三行一個(gè)正整數(shù)num，表示小謝抽獎(jiǎng)券上的號(hào)碼。1≤獲獎(jiǎng)號(hào)碼，num<10000。例1、抽獎(jiǎng)1【問(wèn)題描述】【輸出格式】一行一個(gè)整數(shù)，如果小謝中獎(jiǎng)了，表示中獎(jiǎng)的是第幾個(gè)號(hào)碼；如果沒(méi)有中獎(jiǎng)，則為0?！据斎霕永?172349555613【輸出樣例】3【輸出格式】//p5-4-1#include<cstdio>usingnamespacestd;intmain(){intn,i,num,f,g[101];scanf(“%d”,&n);for(i=1;i<=n;i++)scanf(“%d”,&g[i]);scanf(“%d”,&num);f=0;for(i=1;i<=n;i++)if(g[i]==num){f=i;break;}printf(“%d\n”,f);return0;}//p5-4-1例2、抽獎(jiǎng)2【問(wèn)題描述】公司舉辦年會(huì)，為了活躍氣氛，設(shè)置了搖獎(jiǎng)環(huán)節(jié)。參加聚會(huì)的每位員工都有一張帶有號(hào)碼的抽獎(jiǎng)券?，F(xiàn)在，主持人從小到大依次公布n個(gè)不同的獲獎(jiǎng)號(hào)碼，小謝看著自己抽獎(jiǎng)券上的號(hào)碼win，無(wú)比緊張。請(qǐng)編寫一個(gè)程序，如果小謝獲獎(jiǎng)了，請(qǐng)輸出他中獎(jiǎng)的是第幾個(gè)號(hào)碼；如果沒(méi)有中獎(jiǎng)，請(qǐng)輸出0。【輸入格式】第一行一個(gè)正整數(shù)n，表示有n個(gè)獲獎(jiǎng)號(hào)碼，2<n≤100。第二行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示依次公布的n個(gè)獲獎(jiǎng)號(hào)碼。第三行一個(gè)正整數(shù)win，表示小謝抽獎(jiǎng)券上的號(hào)碼。1≤獲獎(jiǎng)號(hào)碼，win<10000。例2、抽獎(jiǎng)2【問(wèn)題描述】【輸出格式】一行一個(gè)整數(shù)，如果小謝中獎(jiǎng)了，表示中獎(jiǎng)的是第幾個(gè)號(hào)碼；如果沒(méi)有中獎(jiǎng)，則為0?！据斎霕永?123461795553【輸出樣例】3【輸出格式】//p5-4-2#include<cstdio>usingnamespacestd;intmain(){intn,i,win,f,left,right,mid,g[101];scanf(“%d”,&n);for(i=1;i<=n;i++)scanf(“%d”,&g[i]);scanf(“%d”,&win);f=0;left=1;right=n;while(left<=right){mid=(left+right)/2;if(g[mid]==win){f=mid;break;}if(win<g[mid])right=mid-1;if(g[mid]<win)left=mid+1;}printf(“%d\n”,f);return0;}//p5-4-2例3、比身高【問(wèn)題描述】有N個(gè)人排成一排，假設(shè)他們的身高均為正整數(shù)，請(qǐng)找出其中符合以下條件的人：排在他前面且比他高的人數(shù)與排在他后面且比他高的人數(shù)相等?！据斎敫袷健康谝恍袨橐粋€(gè)正整數(shù)N，1<N<1000，表示有多少個(gè)人。下面N行，每行一個(gè)正整數(shù)，表示從前往后每個(gè)人的身高，假設(shè)每個(gè)人的身高≤10000?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示滿足這個(gè)條件的人數(shù)。例3、比身高【問(wèn)題描述】【輸入樣例】41213【輸出樣例】2【樣例說(shuō)明】第3、第4個(gè)人滿足條件?！据斎霕永?/p5-4-3#include<cstdio>usingnamespacestd;inth[1001],n,i,j,ans,t1,t2;intmain(){scanf(“%d”,&n);for(i=1;i<=n;i++)scanf(“%d”,&h[i]);for(i=1;i<=n;i++){t1=t2=0;for(j=1;j<i;j++)if(h[j]>h[i])t1++;//排在他前面且比他高的人數(shù)for(j=i+1;j<=n;j++)if(h[j]>h[i])t2++;//排在他后面且比他高的人數(shù)if(t1==t2)ans++;}printf(“%d\n”,ans);return0;}//p5-4-3實(shí)踐鞏固實(shí)踐鞏固第5課一維數(shù)組的元素排序?qū)W習(xí)目標(biāo)1.掌握選擇排序、冒泡排序和插入排序。2.應(yīng)用排序算法解決一些實(shí)際問(wèn)題。第5課一維數(shù)組的元素排序?qū)W習(xí)目標(biāo)一維數(shù)組的元素排序“排序”就是按照某個(gè)關(guān)鍵字的大小，將若干對(duì)象從小到大或者從大到小進(jìn)行重新排列。關(guān)鍵字是對(duì)象的某一個(gè)屬性，它可以是任何基本數(shù)據(jù)類型，甚至結(jié)構(gòu)體等。例如，體育課上我們會(huì)按照身高從矮到高站隊(duì)，這就是“升序”排序，身高是我們每個(gè)人的一個(gè)屬性，也就是排序的關(guān)鍵字。再如，將所有單詞按照“字典序”倒過(guò)來(lái)排序，如zoo,yes,most,key,computer,book,bad,apple等，就是“降序”排序，關(guān)鍵字的類型就是字符串。

排序算法非常多，其中最基本的有選擇排序、冒泡排序和插入排序三種。其本質(zhì)上都是通過(guò)數(shù)組中的元素比較和交換來(lái)實(shí)現(xiàn)的，關(guān)鍵是數(shù)組下標(biāo)的分析。一維數(shù)組的元素排序“排序”就是按照某個(gè)關(guān)鍵字的大小，將若干對(duì)例1、站隊(duì)【問(wèn)題描述】給出n個(gè)同學(xué)的身高，請(qǐng)根據(jù)他們的身高升序排列并輸出排序結(jié)果。【輸入格式】第一行1個(gè)正整數(shù)n，表示有n個(gè)同學(xué)的身高，2<n≤100。第二行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示n個(gè)同學(xué)的身高。每個(gè)同學(xué)的身高都在150~200厘米之間。【輸出格式】一行n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示n個(gè)同學(xué)根據(jù)身高升序排列的結(jié)果?！据斎霕永?180170176160155150160【輸出樣例】150155160160170176180例1、站隊(duì)【問(wèn)題描述】【問(wèn)題分析】算法1、選擇排序選擇排序的基本思想是：每一趟從待排序的數(shù)據(jù)中，通過(guò)“打擂臺(tái)”比較選出最小元素，放在這些數(shù)據(jù)的最前面。這樣，第一趟把n個(gè)數(shù)中（第1個(gè)到第n個(gè)）最小的放在第一個(gè)位置，第二趟把剩余的n-1個(gè)數(shù)中（第2個(gè)到第n個(gè)）最小的放在第二個(gè)位置，第三趟把剩余的n-2個(gè)數(shù)中（第3個(gè)到第n個(gè)）最小的放在第三個(gè)位，……第n-1趟把剩下的2個(gè)數(shù)中（第n-1個(gè)到第n個(gè)）最小的放在第n-1個(gè)位置，剩下的最后一個(gè)數(shù)（第n個(gè)）一定最大，自然落在了第n個(gè)位置?！締?wèn)題分析】信息學(xué)奧賽課課通(C++)第5單元-電子課件//p5-5-1a，選擇排序#include<iostream>usingnamespacestd;intmain(){intn,i,j,k,temp,h[101];cin>>n;for(i=1;i<=n;i++)cin>>h[i];for(i=1;i<=n;i++){k=i;for(j=i+1;j<=n;j++)if(h[j]<h[k])k=j;//在i~n之間的最小元素temp=h[i];h[i]=h[k];h[k]=temp;//將i~n之間的最小元素放到第i個(gè)位置}for(i=1;i<n;i++)cout<<h[i]<<““;cout<<h[n]<<endl;return0;}//p5-5-1a，選擇排序算法2、冒泡排序冒泡排序的基本思想是：從第一個(gè)數(shù)開(kāi)始，依次不斷比較相鄰的兩個(gè)元素，如果“逆序”就交換。這樣，一趟排序結(jié)束后，最大的元素就放在了第n個(gè)位置了。對(duì)于樣例數(shù)據(jù)，第一趟冒泡排序的過(guò)程如下：算法2、冒泡排序用同樣的方法，第二趟把剩余的前n-1個(gè)數(shù)中最大的交換到第n-1個(gè)位置，第三趟把剩余的前n-2個(gè)數(shù)中最大的交換到第n-2個(gè)位置，……經(jīng)過(guò)n-1趟，排序結(jié)束。用同樣的方法，第二趟把剩余的前n-1個(gè)數(shù)中最大的交換到第//p5-5-1b，冒泡排序#include<iostream>usingnamespacestd;intmain(){intn,i,j,temp,h[101];cin>>n;for(i=1;i<=n;i++)cin>>h[i];for(i=1;i<n;i++)for(j=1;j<=n-i;j++)if(h[j]>h[j+1]){temp=h[j];h[j]=h[j+1];h[j+1]=temp;}for(i=1;i<n;i++)cout<<h[i]<<““;cout<<h[n]<<endl;return0;}

對(duì)于冒泡排序，我們還可以做些算法“優(yōu)化”。如果一趟排序下來(lái)，都沒(méi)有任何“逆序”數(shù)對(duì)，即沒(méi)有發(fā)生“交換”操作，則說(shuō)明已經(jīng)排好序了。此時(shí)，就可以立刻退出循環(huán)。//p5-5-1b，冒泡排序?qū)τ诿芭菖判?，?/p5-5-1c，優(yōu)化后的冒泡排序#include<iostream>usingnamespacestd;intmain(){intn,i,j,temp,h[101];cin>>n;for(i=1;i<=n;i++)cin>>h[i];for(i=1;i<n;i++){boolflag=true;for(j=1;j<=n-i;j++)if(h[j]>h[j+1]){temp=h[j];h[j]=h[j+1];h[j+1]=temp;flag=false;}if(flag)break;}for(i=1;i<n;i++)cout<<h[i]<<““;cout<<h[n]<<endl;return0;}//p5-5-1c，優(yōu)化后的冒泡排序算法3、插入排序插入排序的基本思想是：把所有待排序元素分成前后兩段，前一段是已經(jīng)排好序的，后一段是待排序的。每一趟都是把后一段的第一個(gè)數(shù)“插入”到前一段的某一個(gè)位置，保證前一段仍然是有序的。開(kāi)始時(shí)，第1個(gè)數(shù)作為前一段肯定是有序的；第一趟，把第2個(gè)數(shù)插入進(jìn)去，保證前2個(gè)數(shù)有序；第二趟，把第3個(gè)數(shù)插入進(jìn)去，保證前3個(gè)數(shù)有；……第n-1趟，把第n個(gè)數(shù)插入進(jìn)去，保證n個(gè)數(shù)都有序。算法3、插入排序//p5-5-1d，插入排序#include<iostream>usingnamespacestd;intmain(){intn,i,j,k,temp,h[101];cin>>n;for(i=1;i<=n;i++)cin>>h[i];for(i=2;i<=n;i++){temp=h[i];k=1;while(h[k]<=temp&&k<i)k++;for(j=i-1;j>=k;j--)h[j+1]=h[j];h[k]=temp;}for(i=1;i<n;i++)cout<<h[i]<<““;cout<<h[n]<<endl;return0;}//p5-5-1d，插入排序?qū)嵺`鞏固實(shí)踐鞏固第6課一維數(shù)組的應(yīng)用舉例學(xué)習(xí)目標(biāo)1.學(xué)會(huì)跟蹤數(shù)組元素調(diào)試程序。2.綜合應(yīng)用一維數(shù)組的基本操作解決一些實(shí)際問(wèn)題。第6課一維數(shù)組的應(yīng)用舉例學(xué)習(xí)目標(biāo)例1、學(xué)習(xí)對(duì)象【問(wèn)題描述】n個(gè)信息學(xué)選手站在一排，每個(gè)選手的位置依次用1~n表示，第i個(gè)信息學(xué)選手的編程能力用一個(gè)整數(shù)Hi表示。每個(gè)信息學(xué)選手都希望找一個(gè)編程能力比自己高但又與自己編程能力最接近的選手學(xué)習(xí)，如果有多個(gè)符合條件的選手則選擇位置在最前面的選手學(xué)習(xí)。請(qǐng)編程輸出每位選手學(xué)習(xí)對(duì)象的位置，如果沒(méi)有學(xué)習(xí)對(duì)象，則輸出0?！据斎敫袷健康?行一個(gè)正整數(shù)n，1≤n≤1000；第2~n+1行共n個(gè)正整數(shù)，依次表示每位選手的編程能力，1≤Hi≤1000000?！据敵龈袷健縩行，每行輸出一個(gè)整數(shù)表示每個(gè)選手學(xué)習(xí)對(duì)象的位置。例1、學(xué)習(xí)對(duì)象【問(wèn)題描述】【輸入樣例】6326112【輸出樣例】310221【輸入樣例】【問(wèn)題分析】第i個(gè)選手的學(xué)習(xí)對(duì)象就是從前往后查找一個(gè)選手j，要求Hi<Hj且Hj要盡可能小（打擂臺(tái)），如果j可以取多個(gè)值，則選取最小的值（保留前面）。//p5-6-1#include<iostream>usingnamespacestd;intn,i,j,ans,maxh,h[1001];intmain(){cin>>n;for(i=1;i<=n;i++)cin>>h[i];for(i=1;i<=n;i++){ans=0;maxh=1000001;for(j=1;j<=n;j++)if(h[j]>h[i]&&h[j]<maxh){ans=j;maxh=h[j];}cout<<ans<<endl;}return0;}【問(wèn)題分析】例2、商品排序【問(wèn)題描述】某商場(chǎng)的倉(cāng)庫(kù)中有n件商品，每件商品的價(jià)格在0~1000之間（價(jià)格為0的商品為贈(zèng)品）?，F(xiàn)在商場(chǎng)經(jīng)理要求將這n件商品按價(jià)格由低到高排序。請(qǐng)編程輸出n件商品排序后的情況?！据斎敫袷健康谝恍幸粋€(gè)正整數(shù)n，表示有n件商品，1≤n≤100000。接下來(lái)的n行，每行一個(gè)整數(shù)，表示第i件商品的價(jià)格?！据敵龈袷健縩行，每行輸出一個(gè)整數(shù)。例2、商品排序【問(wèn)題描述】【輸入樣例】518122【輸出樣例】11228【輸入樣例】【問(wèn)題分析】本題可以選用學(xué)過(guò)的任意一種排序算法實(shí)現(xiàn)，但是測(cè)試程序發(fā)現(xiàn)會(huì)“超時(shí)”，因?yàn)楸绢}最多有100000件商品，三種排序都需要兩層循環(huán)嵌套。其實(shí)，分析數(shù)據(jù)發(fā)現(xiàn)一個(gè)重要特征：數(shù)據(jù)雖然很多，但是數(shù)據(jù)范圍比較小。這種情況下，可以使用另外一種排序算法——桶排序。定義一個(gè)int型數(shù)組num[1001]，num[x]記錄整數(shù)x出現(xiàn)的次數(shù)，初始化都為0，每讀到一個(gè)數(shù)x，就執(zhí)行num[x]=num[x]+1。輸出時(shí)，從0~1000窮舉x，每個(gè)x輸出num[x]次。【問(wèn)題分析】//p5-6-2，桶排序#include<iostream>usingnamespacestd;intn,i,j,number,num[1001];intmain(){cin>>n;for(i=1;i<=n;i++){cin>>number;num[number]++;//記錄整數(shù)number出現(xiàn)的次數(shù)}for(i=0;i<1001;i++)for(j=1;j<=num[i];j++)cout<<i<<endl;//輸出num[i]次ireturn0;}//p5-6-2，桶排序例3、素?cái)?shù)大酬賓【問(wèn)題描述】某商場(chǎng)的倉(cāng)庫(kù)中有n種商品，每件商品按1~n依次編號(hào)?，F(xiàn)在商場(chǎng)經(jīng)理突發(fā)奇想，決定將編號(hào)為素?cái)?shù)（質(zhì)數(shù)）的所有商品拿出來(lái)搞優(yōu)惠酬賓活動(dòng)。請(qǐng)編程幫助倉(cāng)庫(kù)管理員將編號(hào)為素?cái)?shù)的商品選出來(lái)。【輸入格式】一行一個(gè)正整數(shù)n，表示有n種商品，2≤n≤100000?！据敵龈袷健恳恍腥舾蓚€(gè)正整數(shù)，表示若干種商品編號(hào)且每個(gè)編號(hào)均為素?cái)?shù)，請(qǐng)從小到大輸出，每?jī)蓚€(gè)數(shù)之間有一個(gè)空格?！据斎霕永?0【輸出樣例】235711131719例3、素?cái)?shù)大酬賓【問(wèn)題描述】【問(wèn)題分析】算法1、窮舉法窮舉商品編號(hào)2~n，判斷每個(gè)編號(hào)是否為素?cái)?shù)。這種方法效率不高，一旦n過(guò)大，程序就會(huì)超時(shí)。//p5-6-3a#include<iostream>#include<cmath>usingnamespacestd;intmain(){intn,i,j;boolflag;cin>>n;cout<<2;for(i=3;i<=n;i++){flag=true;for(j=2;j<=sqrt(i);j++)if(i%j==0){flag=false;break;}if(flag)cout<<““<<i;}cout<<endl;return0;}【問(wèn)題分析】算法2、篩選法篩選法又稱為篩法，是由希臘著名數(shù)學(xué)家埃拉托色尼（Eratosthenes）提出的。相比窮舉法，篩選法的效率更高。以求1~20之內(nèi)素?cái)?shù)為例，具體步驟如下：（1）將所有數(shù)（2~n）放入“篩子”中，把1刪除；（2）2在篩中，將2的倍數(shù)2，4，…，20刪除（篩去）；（3）3在篩中，將3的倍數(shù)6，9，…，18刪除（篩去）；（4）4不在篩中，不執(zhí)行刪除（篩去）操作；……（10）10不在篩中，不執(zhí)行刪除（篩去）操作。算法2、篩選法輸出20以內(nèi)的素?cái)?shù)，篩子中的元素變化情況如下：輸出20以內(nèi)的素?cái)?shù)，篩子中的元素變化情況如下：//p5-6-3b#include<iostream>#include<cmath>usingnamespacestd;intmain(){intn,i,j;boolp[100001];for(i=0;i<=100000;i++)p[i]=true;p[1]=false;cin>>n;cout<<2;for(i=2;i<=sqrt(n);i++)if(p[i])for(j=2;i*j<=n;j++)p[i*j]=false;for(i=3;i<=n;i++)if(p[i])cout<<““<<i;cout<<endl;return0;}//p5-6-3b例4、約瑟夫問(wèn)題【問(wèn)題描述】有m個(gè)人，其編號(hào)分別為1~m。按順序圍成一個(gè)圈，現(xiàn)在給定一個(gè)數(shù)n，從第一個(gè)人開(kāi)始依次報(bào)數(shù)，報(bào)到n的人出圈，然后再?gòu)南乱粋€(gè)人開(kāi)始，繼續(xù)從1開(kāi)始依次報(bào)數(shù)，報(bào)到n的人再出圈，……如此循環(huán)，直到最后一個(gè)人出圈為止。編程輸出所有人出圈的順序?！据斎敫袷健恳恍袃蓚€(gè)正整數(shù)m和n，之間用一個(gè)空格隔開(kāi)，1≤m<100，1≤n≤32767?！据敵龈袷健枯敵鰉行，每行一個(gè)正整數(shù)，表示依次出圈的人的編號(hào)。【輸入樣例】85【輸出樣例】52871463例4、約瑟夫問(wèn)題【問(wèn)題描述】【輸入樣例】【問(wèn)題分析】定義bool型數(shù)組p，表示每個(gè)人在圈中的狀態(tài)。假設(shè)p[i]為true表示第i個(gè)人還在圈中，p[i]為false表示第i個(gè)人已出圈。模擬報(bào)數(shù)的過(guò)程，從第一個(gè)人（i=1）開(kāi)始報(bào)數(shù)，定義計(jì)數(shù)器j，初始化為0，如果p[i]為true，則j加1，當(dāng)j為n時(shí)，報(bào)到的這個(gè)人出圈（p[i]=false，且j=0），……直到所有人都已出圈。程序?qū)崿F(xiàn)時(shí)，另外設(shè)計(jì)一個(gè)計(jì)數(shù)器t，記錄圈中的剩余人數(shù)，初始化為m?！締?wèn)題分析】//p5-6-4#include<iostream>usingnamespacestd;intmain(){intm,n,i,j,t;boolp[100];cin>>m>>n;for(i=0;i<100;i++)p[i]=true;t=m;i=0;j=0;while(t>0){i++;if(i==m+1)i=1;//實(shí)現(xiàn)圈的效果if(p[i]){j++;if(j==n){cout<<i<<endl;p[i]=false;j=0;t--;}}}return0;}結(jié)合本題，學(xué)會(huì)跟蹤一維數(shù)組，調(diào)試代碼。//p5-6-4結(jié)合本題，學(xué)會(huì)跟蹤一維數(shù)組，調(diào)試代碼。實(shí)踐鞏固實(shí)踐鞏固第7課二維數(shù)組的定義和操作學(xué)習(xí)目標(biāo)1.理解二維數(shù)組及其存儲(chǔ)結(jié)構(gòu)。2.掌握二維數(shù)組的初始化、輸入輸出等基本操作。第7課二維數(shù)組的定義和操作學(xué)習(xí)目標(biāo)1.二維數(shù)組的定義和初始化定義二維數(shù)組的一般格式為：類型標(biāo)識(shí)符數(shù)組名[常量表達(dá)式1][常量表達(dá)式2];常量表達(dá)式1的值表示第一維大小，常量表達(dá)式2的值表示第二維大小，常量表達(dá)式1和常量表達(dá)式2的乘積就是二維數(shù)組的元素個(gè)數(shù)。

一維數(shù)組的元素可以是任何基本數(shù)據(jù)類型，也可以是結(jié)構(gòu)體。那么，如果一維數(shù)組的每一個(gè)元素又是一個(gè)一維數(shù)組呢？我們稱這種數(shù)組為“二維數(shù)組”。1.二維數(shù)組的定義和初始化定義二維數(shù)組的一般格式為：1.二維數(shù)組的定義和初始化

在定義二維數(shù)組時(shí)，可以省略第一維的大小，但是第二維的大小不能省略。例如，“inta[][5];”是允許的，被省略的第一維大小根據(jù)初值的個(gè)數(shù)由系統(tǒng)來(lái)確定。例如：inta[][4]={1,2,3,4,5,6,7,8,9,10,11,12};

系統(tǒng)根據(jù){}中的元素個(gè)數(shù)，自動(dòng)確定a數(shù)組的第一維大小為3。

在二維數(shù)組定義的同時(shí)，可以進(jìn)行初始化賦值。例如：inta[2][3]={{1,2,3},{4,5,6}};//分行初始化

也可以給數(shù)組中的部分元素初始化。例如：inta[2][3]={{1,2},{4}};

第一行只有2個(gè)初值,按順序分別賦值給a[0][0]和a[0][1],第二行的初值4賦給a[1][0]，其它元素默認(rèn)為0。1.二維數(shù)組的定義和初始化在定義二維數(shù)組時(shí)2.二維數(shù)組的存儲(chǔ)及元素引用二維數(shù)組本質(zhì)上是一維數(shù)組的每一個(gè)元素又是一個(gè)一維數(shù)組，而計(jì)算機(jī)內(nèi)部存儲(chǔ)一維數(shù)組采用的是連續(xù)存儲(chǔ)單元。所以，二維數(shù)組的存儲(chǔ)方式是“行優(yōu)先”的連續(xù)存儲(chǔ)，先逐個(gè)存儲(chǔ)第0行上的所有元素，再逐個(gè)存儲(chǔ)第1行上的所有元素，依此類推。引用二維數(shù)組的某一個(gè)元素，格式為：數(shù)組名[下標(biāo)1][下標(biāo)2]2.二維數(shù)組的存儲(chǔ)及元素引用二維數(shù)組本質(zhì)上是一維數(shù)組的每一3.二維數(shù)組的輸入輸出二維數(shù)組的輸入、輸出操作也是針對(duì)每一個(gè)元素進(jìn)行，結(jié)合兩個(gè)維度的下標(biāo)變化，用循環(huán)嵌套實(shí)現(xiàn)。3.二維數(shù)組的輸入輸出二維數(shù)組的輸入、輸出操作也是針對(duì)每一例1、回型方陣【問(wèn)題描述】輸入一個(gè)正整數(shù)n，輸出n×n的回型方陣。例如，n=5時(shí)，輸出：1111112221123211222111111【輸入格式】一行一個(gè)正整數(shù)n，2≤n≤9。【輸出格式】共n行，每行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)。例1、回型方陣【問(wèn)題描述】【輸入樣例】5【輸出樣例】1111112221123211222111111【輸入樣例】【問(wèn)題分析】定義一個(gè)二維數(shù)組a[n][n]存儲(chǔ)回型方陣。方法1、先給左上角的a[n/2][n/2]賦值，a[i][j]=min(i，j)，右上角、左下角、右下角三部分，通過(guò)下標(biāo)的對(duì)稱性復(fù)制過(guò)去即可。例如，a[i][n+1-j]=a[n+1-i][j]=a[n+1-i]

[n+1-j]=a[i][j]。方法2、通過(guò)“一圈一圈”賦值的方法做，先給a[1][1]~a[n][n]全部賦值1，然后給a[2][2]~a[n-1][n-1]全部賦值2，……共n/2圈(如果n是奇數(shù)，則最后一圈就是一個(gè)數(shù))。【問(wèn)題分析】//p5-7-1a#include<iostream>usingnamespacestd;intn,i,j,k,mi,ma,a[10][10];intmain(){cin>>n;for(i=1;i<=(n+1)/2;i++)for(j=1;j<=(n+1)/2;j++){a[i][j]=min(i,j);a[i][n+1-j]=a[n+1-i][j]=a[n+1-i][n+1-j]=a[i][j];}for(i=1;i<=n;i++){for(j=1;j<=n-1;j++){cout<<a[i][j]<<““;}cout<<a[i][n]<<endl;}return0;}//p5-7-1a//p5-7-1b#include<iostream>usingnamespacestd;intn,i,j,k,a[10][10];intmain(){cin>>n;for(k=1;k<=(n+1)/2;k++)for(i=k;i<=n+1-k;i++)for(j=k;j<=n+1-k;j++)a[i][j]=k;for(i=1;i<=n;i++){for(j=1;j<n;j++)cout<<a[i][j]<<““;cout<<a[i][n]<<endl;}return0;}//p5-7-1b實(shí)踐鞏固實(shí)踐鞏固第8課二維數(shù)組應(yīng)用舉例學(xué)習(xí)目標(biāo)綜合應(yīng)用二維數(shù)組的基本操作解決一些實(shí)際問(wèn)題。第8課二維數(shù)組應(yīng)用舉例學(xué)習(xí)目標(biāo)例1、楊輝三角形【問(wèn)題描述】輸入正整數(shù)n，輸出楊輝三角形的前n行。例如，n=5時(shí)，楊輝三角形如下：111121133114641【輸入格式】一行一個(gè)正整數(shù)n，1≤n≤20。【輸出格式】共n行，第i行包含i個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)。例1、楊輝三角形【問(wèn)題描述】【輸入樣例】5【輸出樣例】111121133114641【問(wèn)題分析】定義一個(gè)二維數(shù)組tri存儲(chǔ)楊輝三角形（其實(shí)只用到二維數(shù)組的左下部分）。對(duì)于第i行（1≤i≤n），共有i個(gè)數(shù)，其中第一個(gè)數(shù)和最后一個(gè)數(shù)都是1，其他數(shù)tri[i][j]=tri[i-1][j-1]+tri[i-1][j]。具體實(shí)現(xiàn)，采用“遞推法”，逐行逐列給每個(gè)數(shù)組元素賦值。參考程序見(jiàn)教材171頁(yè)?！据斎霕永俊締?wèn)題分析】例2、數(shù)字三角形【問(wèn)題描述】讀入一個(gè)正整數(shù)n，輸出如下形式的數(shù)字三角形（具體見(jiàn)樣例）?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，1≤n<100?！据敵龈袷健抗瞡行，第i行包含i個(gè)正整數(shù)，每個(gè)正整數(shù)占5列?！据斎霕永?【輸出樣例】123451234123121例2、數(shù)字三角形【問(wèn)題描述】【問(wèn)題分析】定義二維數(shù)組a存儲(chǔ)所求的數(shù)字三角形，初始化為0。對(duì)于右上角的每一個(gè)元素a[i][j]，分析發(fā)現(xiàn)：a[i][j]=j-i+1。具體實(shí)現(xiàn)采用“賦值法”。參考程序見(jiàn)教材172頁(yè)?！締?wèn)題分析】例3、獎(jiǎng)學(xué)金問(wèn)題描述見(jiàn)教材172頁(yè)?！締?wèn)題分析】本題涉及“多關(guān)鍵字”排序。用一個(gè)二維數(shù)組stu保存n位同學(xué)的學(xué)號(hào)、語(yǔ)文、數(shù)學(xué)、英語(yǔ)、總分成績(jī)，然后以總分成績(jī)?yōu)榈谝魂P(guān)鍵字（降序）、語(yǔ)文成績(jī)?yōu)榈诙P(guān)鍵字（降序）、學(xué)號(hào)為第三關(guān)鍵字（升序）排序。最后輸出排序后的前5個(gè)同學(xué)的學(xué)號(hào)和總分。參考程序見(jiàn)教材173-174頁(yè)。例3、獎(jiǎng)學(xué)金問(wèn)題描述見(jiàn)教材172頁(yè)?！締?wèn)題分析】實(shí)踐鞏固實(shí)踐鞏固第9課數(shù)字方陣學(xué)習(xí)目標(biāo)應(yīng)用二維數(shù)組解決一些數(shù)字方陣問(wèn)題，體會(huì)數(shù)組的下標(biāo)運(yùn)算。第9課數(shù)字方陣學(xué)習(xí)目標(biāo)數(shù)字方陣數(shù)字方陣就是一個(gè)行列數(shù)相等的二維數(shù)組，其中的每個(gè)元素都是數(shù)字。解決數(shù)字方陣問(wèn)題，一般有兩種方法：解析法和模擬法。解析法就是找出每一個(gè)方陣元素f[i][j]與i、j和數(shù)組規(guī)模n的通項(xiàng)公式，然后直接用兩重循環(huán)給數(shù)組元素賦值，相對(duì)比較容易，一般用在初始化等場(chǎng)合。模擬法就是把數(shù)字方陣看成一個(gè)動(dòng)態(tài)的填數(shù)過(guò)程，把n^2個(gè)數(shù)依次填入數(shù)組中，每填好一個(gè)數(shù)，就定位好下一個(gè)數(shù)的位置i和j。數(shù)字方陣數(shù)字方陣就是一個(gè)行列數(shù)相等的二維數(shù)組，其中的每個(gè)元素例1、n階奇數(shù)幻方【問(wèn)題描述】行列數(shù)相等的矩陣稱為方陣。把正整數(shù)1~n2

（n為奇數(shù)）排成一個(gè)n×n方陣，使得方陣中的每一行、每一列以及兩條對(duì)角線上的數(shù)之和都相等，這樣的方陣稱為“n階奇數(shù)幻方”。編程輸入n，輸出n階奇數(shù)幻方?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，1≤n<20，n為奇數(shù)。【輸出格式】共n行，每行n個(gè)正整數(shù)，每個(gè)正整數(shù)占5列。例1、n階奇數(shù)幻方【問(wèn)題描述】【輸入樣例】5【輸出樣例】17241815235714164613202210121921311182529【輸入樣例】【問(wèn)題分析】定義一個(gè)二維數(shù)組模擬填數(shù)的過(guò)程。分析樣例發(fā)現(xiàn)，n階奇數(shù)幻方可以按下列方法生成：先把數(shù)字1填在第1行的正中間a[1][n/2+1]，然后用一個(gè)循環(huán)窮舉k，填入數(shù)字2~n2

，每次先找位置再填數(shù)，找位置的規(guī)律如下：如果數(shù)k填在第i行第j列，那么一般情況下，下一個(gè)數(shù)k+1應(yīng)該填在它的右上方，即第i-1行第j+1列。但是，有兩種特殊情況：如果右上方無(wú)格子，也就是越界了（i-1=0或j+1=n+1），那么就應(yīng)該把下一個(gè)數(shù)放到第n行或者第1列；如果右上方已經(jīng)有數(shù)了（a[i][j]不等于初值），那么下一個(gè)數(shù)k+1就應(yīng)該填在第k個(gè)數(shù)的正下方。參考程序見(jiàn)教材177頁(yè)。【問(wèn)題分析】例2、螺旋方陣【問(wèn)題描述】一個(gè)n行n列的螺旋方陣按如下方法生成：從方陣的左上角（第1行第1列）出發(fā)，初始時(shí)向右移動(dòng)；如果前方是未曾經(jīng)過(guò)的格子，則繼續(xù)前進(jìn)；否則，右轉(zhuǎn)。重復(fù)上述操作直至經(jīng)過(guò)方陣中所有格子。根據(jù)經(jīng)過(guò)順序，在格子中依次填入1，2，3，…，n，便構(gòu)成了一個(gè)螺旋方陣。下面是一個(gè)n=4的螺旋方陣。例2、螺旋方陣【問(wèn)題描述】

編程輸入一個(gè)正整數(shù)n，生成一個(gè)n×n的螺旋方陣?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，1≤n≤20?！据敵龈袷健抗瞡行，每行n個(gè)正整數(shù)，每個(gè)正整數(shù)占5列?！据斎霕永?【輸出樣例】12345161718196152425207142322218131211109編程輸入一個(gè)正整數(shù)n，生成一個(gè)n×n的螺【問(wèn)題分析】定義一個(gè)二維數(shù)組模擬填數(shù)的過(guò)程。根據(jù)題意，設(shè)置一個(gè)變量d用來(lái)表示填數(shù)的方向，d=0~4，依次表示向右、向下、向左、向上填數(shù)。再定義兩個(gè)常量數(shù)組，表示各個(gè)方向上前進(jìn)一步帶來(lái)的行、列坐標(biāo)的變化值。把數(shù)字1填在第1行第1列，然后向右填數(shù)字2，……填到不能填的位置（越界或者已經(jīng)填了數(shù)），就換個(gè)方向（++d%4）接著填。參考程序見(jiàn)教材178頁(yè)。【問(wèn)題分析】例3、蛇形方陣【問(wèn)題描述】輸入一個(gè)正整數(shù)n，生成一個(gè)n×n的蛇形方陣（具體見(jiàn)樣例）?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，1≤n≤20。【輸出格式】共n行，每行n個(gè)正整數(shù)，每個(gè)正整數(shù)占5列?！据斎霕永?【輸出樣例】12671535814164913172210121821231119202425例3、蛇形方陣【問(wèn)題描述】【問(wèn)題分析】可以把蛇形方陣看成一條一條的直線（從右上到左下的斜線），每條直線上的數(shù)的個(gè)數(shù)為：1，2，3，…n-1，n，n-1，…3，2，1。每條直線上的元素位置有一個(gè)重要特點(diǎn)：行號(hào)和列號(hào)相加為定值，從2到2×n。同時(shí)，可以分析出對(duì)稱性，以最中間的直線為界，左上角和右下角的兩個(gè)區(qū)域里的所有數(shù)的位置都是對(duì)稱的，滿足a[i][j]+a[n+1-i][n+1-j]等于n×n+1。因此，只需要模擬填出前n條直線上的數(shù)字，另外n-1條的元素值直接通過(guò)對(duì)稱性來(lái)賦值。參考程序見(jiàn)教材179-180頁(yè)?！締?wèn)題分析】實(shí)踐鞏固實(shí)踐鞏固第10課字符數(shù)組學(xué)習(xí)目標(biāo)1.掌握字符數(shù)組的輸入輸出方法。2.應(yīng)用字符數(shù)組解決一些實(shí)際問(wèn)題。第10課字符數(shù)組學(xué)習(xí)目標(biāo)字符數(shù)組數(shù)組中的每個(gè)元素都是一個(gè)字符的數(shù)組稱為“字符數(shù)組”。有時(shí)，把一維字符數(shù)組又稱為“字符串”。定義字符數(shù)組的方法與定義其他類型數(shù)組的方法類似。對(duì)于字符數(shù)組的定義“chars[10]

={'H'，'e'，'l'，'l'，'o'}；”其在計(jì)算機(jī)內(nèi)部的存儲(chǔ)方式如下：也就是說(shuō)，字符串的末尾都會(huì)有一個(gè)空字符'\0'。

字符數(shù)組數(shù)組中的每個(gè)元素都是一個(gè)字符的數(shù)組稱為“字符數(shù)組”。字符數(shù)組賦值方法用字符常量逐個(gè)初始化：charletter［5］={'a'，'e'，'i'，'o'，'u'}；用賦值語(yǔ)句逐個(gè)元素賦值：letter［0］='a'；…用scanf讀入整個(gè)數(shù)組：scanf（"%s"，letter）；用scanf逐個(gè)元素讀入：scanf（"%c"，&letter［0］）；…用cin輸入整個(gè)數(shù)組：cin>>letter；用cin逐個(gè)元素輸入：cin>>letter［0］；…用gets讀入整個(gè)數(shù)組：gets（letter）；用getchar逐個(gè)讀入：letter［0］=getchar（）；…字符數(shù)組賦值方法用字符常量逐個(gè)初始化：charletter字符數(shù)組輸出方法用cout輸出整個(gè)數(shù)組：cout>>letter；用cout逐個(gè)元素輸出：cout>>letter［0］；…用printf輸出整個(gè)數(shù)組：printf（"%s"，letter）；用printf逐個(gè)元素輸出：printf（"%c"，letter［0］）；…用puts輸出整個(gè)數(shù)組：puts（letter）；用putchar逐個(gè)元素輸出：putchar（letter［0］）；…字符數(shù)組輸出方法用cout輸出整個(gè)數(shù)組：cout>>例1、閱讀以下程序，體會(huì)各種字符串輸入輸出方式的區(qū)別。p5-10-1a#include<cstdio>usingnamespacestd;intmain(){chars1[20],s2[20];scanf(“%s”,s1);scanf(“%s”,s2);printf(“%s\n”,s1);printf(“%s\n”,s2);return0;}運(yùn)行程序，輸入“Helloworld!”。輸出為：Helloworld!例1、閱讀以下程序，體會(huì)各種字符串輸入輸出方式的區(qū)別。p5-【問(wèn)題分析】scanf函數(shù)讀取一個(gè)字符串時(shí)，是把回車符、空格符、Tab符作為字符串的結(jié)束符號(hào)。所以，輸入“Helloworld!”，第一個(gè)scanf語(yǔ)句只會(huì)讀取“Hello”，而第二個(gè)scanf語(yǔ)句會(huì)接著讀入“world!”。

如果程序改為用gets輸入、puts輸出：//p5-10-1b#include<cstdio>usingnamespacestd;intmain(){chars1[20],s2[20];gets(s1);gets(s2);puts(s1);puts(s2);return0;}運(yùn)行程序，輸入：Helloworld!Test2則輸出為：Helloworld!Test2【問(wèn)題分析】運(yùn)行程序，輸入：如果程序改為用getchar輸入、putchar輸出：//p5-10-1c#include<cstdio>usingnamespacestd;intmain(){chars1[20],s2[20],i;i=0;while((s1[i]=getchar())!=‘\n’)i++;s1[i]=‘\0’;i=0;while(s1[i]!=‘\0’){putchar(s1[i]);i++;}如果程序改為用getchar輸入、putchar輸出：putchar(‘\n’);i=0;while((s2[i]=getchar())!=‘\n’)i++;s2[i]=‘\0’;i=0;while(s2[i]!=‘\0’){putchar(s2[i]);i++;}putchar(‘\n’);return0;}對(duì)比、測(cè)試、分析以上程序，總結(jié)字符數(shù)組的輸入操作。putchar(‘\n’);對(duì)比、測(cè)試、分析快速讀入數(shù)字字符串函數(shù)intscan(){intres=0,flag=0;charch;if((ch=getchar())=='-')flag=1;elseif(ch>='0'&&ch<='9')res=ch-'0';while((ch=getchar())>='0'&&ch<='9')res=res*10+(ch-'0');returnflag?-res:res;}快速讀入數(shù)字字符串函數(shù)intscan(){例2、數(shù)字和【問(wèn)題描述】輸入一個(gè)整數(shù)n，求各位上的數(shù)字和?！据斎敫袷健恳恍幸粋€(gè)整數(shù)n，n最多200位。【輸出格式】一行一個(gè)整數(shù)，表示整數(shù)n的各位數(shù)字之和?！据斎霕永?234【輸出樣例】10例2、數(shù)字和【問(wèn)題描述】【問(wèn)題分析】由于n可能到200位，任何整數(shù)類型都是不可能存儲(chǔ)的。因此，定義一個(gè)一維字符數(shù)組讀取、存儲(chǔ)這個(gè)超大數(shù)，然后把每個(gè)字符轉(zhuǎn)換成數(shù)值累加求和。參考程序見(jiàn)教材185頁(yè)?！締?wèn)題分析】例3、掃雷游戲【問(wèn)題描述】

參見(jiàn)教材186頁(yè)?！締?wèn)題分析】定義一個(gè)二維字符數(shù)組存儲(chǔ)雷區(qū)，再定義一個(gè)二維整型數(shù)組存儲(chǔ)每個(gè)位置周圍地雷的個(gè)數(shù)。輸入雷區(qū)時(shí)，可以用gets逐行讀入，也可以用getchar逐個(gè)讀入字符。輸出字符數(shù)組時(shí)，可以用putchar逐個(gè)字符輸出。參考程序見(jiàn)教材186-187頁(yè)。例3、掃雷游戲【問(wèn)題描述】【問(wèn)題分析】例4、最大整數(shù)【問(wèn)題描述】

參見(jiàn)教材187頁(yè)?！締?wèn)題分析】字符串比較函數(shù)：strcmp（s1，s