信息學(xué)奧賽之?dāng)?shù)組2

數(shù)組信息學(xué)奧賽課課通（C）第1課一維數(shù)組的定義學(xué)習(xí)目標(biāo)1理解數(shù)組的含義。2學(xué)會一維數(shù)組的定義。3掌握一維數(shù)組的元素引用和物理存儲方式。數(shù)組數(shù)組就是一組相同類型的變量，它們往往都是為了表示同一批對象的統(tǒng)一屬性，如一個班級所有同學(xué)的身高、全球所有國家的人口數(shù)等。數(shù)組可以是一維的，也可以是二維或多維的。1一維數(shù)組的定義定義一維數(shù)組的格式如下：類型標(biāo)識符數(shù)組名;其中，類型標(biāo)識符可以是任何基本數(shù)據(jù)類型，也可以是結(jié)構(gòu)體等構(gòu)造類型，相同類型的數(shù)組可以一起定義。數(shù)組名必須是合法的標(biāo)識符。常量表達式的值即為數(shù)組元素的個數(shù)。2一維數(shù)組的元素引用數(shù)組定義好后，就可以引用（調(diào)用）其中的任意一個元素。引用格式為：數(shù)組名等。其中，下標(biāo)只能為整型常量或整型表達式，值必須在數(shù)組定義的下標(biāo)范圍內(nèi)，否則會出現(xiàn)“下標(biāo)越界錯誤”。需要注意的是，不能一次引用整個數(shù)組，只能逐個引用數(shù)組的單個元素。3一維數(shù)組的存儲結(jié)構(gòu)數(shù)組在計算機內(nèi)存單元中是連續(xù)存儲的。程序一旦執(zhí)行到數(shù)組的定義語句，就會開辟出若干字節(jié)的內(nèi)存單元。第2課一維數(shù)組的輸入與輸出學(xué)習(xí)目標(biāo)1熟練掌握一維數(shù)組的輸入與輸出操作。2學(xué)會應(yīng)用一維數(shù)組解決一些實際問題。一維數(shù)組的輸入與輸出一維數(shù)組的輸入、輸出等操作，都是采用循環(huán)語句結(jié)合下標(biāo)變化，逐個元素進行。批量數(shù)據(jù)一次性輸入到一維數(shù)組中（1）鍵盤逐個讀入數(shù)組元素值；（2）給每個數(shù)組元素直接賦值；給數(shù)組“整體”賦值（1）memset函數(shù)memset函數(shù)是給數(shù)組“按字節(jié)”進行賦值，一般用在char型數(shù)組中，如果是int類型的數(shù)組，一般賦值為0和-1。使用前需要包含頭文件：#include<cstring>。（2）fill函數(shù)fill函數(shù)是給數(shù)組“按元素”進行賦值，可以是整個數(shù)組，也可以是部分連續(xù)元素，可以賦任何值。使用前需要包含頭文件：#include<algorithm>。例1、閱讀并上機調(diào)試程序，體會memset和fill函數(shù)的作用。//esain{inta,i;memseta,0,sieofa;//將a數(shù)組所有元素均賦值為0fori=0;i<9;icout<<a<<endl;memsetb,1,sieofb;//將b數(shù)組所有元素均賦值為//二進制數(shù)2^02^82^162^24=16843009fori=0;i<9;icout<<b<<endl;memsetc,0,5;//將c數(shù)組前5個字節(jié)都賦值為0，所以只能確定c//等于0，其他元素值不確定fori=0;i<9;icout<<c<<endl;filld,d5,8;//將d數(shù)組前5個元素都賦值為8，其他元素值不確定fori=0;i<9;icout<<d<<endl;return0;}例2、走樓梯【問題描述】一個樓梯有n級，小蘇同學(xué)從下往上走，一步可以跨一級，也可以跨兩級。問：他走到第n級樓梯有多少種走法？【輸入格式】一行一個整數(shù)n，0<n≤30。【輸出格式】一行n個整數(shù)，之間用一個空格隔開，表示走到第1級、第2級、……第n級分別有多少種走法?！据斎霕永?【輸出樣例】12【問題分析】假設(shè)fi表示走到第i級樓梯的走法，則走到第ii>2級樓梯有兩種可能：一種是從第i-1級樓梯走過來；另一種是從第i-2級樓梯走過來。根據(jù)加法原理，fi=fi-1fi-2，邊界條件為：f1=1，f2=2。具體實現(xiàn)時，定義一維數(shù)組f，用賦值語句從前往后對數(shù)組的每一個元素逐個賦值。本質(zhì)上，fi構(gòu)成了斐波那契數(shù)列。//esain{intn,i,f=1;f=2;fori=3;i<=n;if;fori=1;i<n;iprintf“%d“,f;return0;}例3、幸運數(shù)的劃分【問題描述】判斷一個正整數(shù)n是否能被一個“幸運數(shù)”整除。幸運數(shù)是指一個只包含4或7的正整數(shù)，如7、47、477等都是幸運數(shù)，17、42則不是幸運數(shù)?！据斎敫袷健恳恍幸粋€正整數(shù)n，1≤n≤1000?！据敵龈袷健恳恍幸粋€字符串，如果能被幸運數(shù)整除輸出“YES”；否則，輸出“NO”?！据斎霕永?7【輸出樣例】YES//esain{intn,lucy={4,7,44,47,74,77,444,447,474,477,744,747,774,777};//在數(shù)組定義時給數(shù)組賦值scanf“%d”,&n;boolflag=false;forinti=0;i<14;iifn%lucy==0flag=true;ifflagprintf“YES\n”;elseprintf“NO\n”;return0;}【問題分析】分析發(fā)現(xiàn)，1~1000范圍內(nèi)的幸運數(shù)只有14個。于是，將這14個幸運數(shù)直接存儲到一個數(shù)組lucy中，再窮舉判斷其中有沒有一個數(shù)能整除n。例4、陶陶摘蘋果【問題描述】陶陶家的院子里有一棵蘋果樹，每到秋天樹上就會結(jié)出10個蘋果。蘋果成熟的時候，陶陶就會跑去摘蘋果。陶陶有一張30厘米高的板凳，當(dāng)她不能直接用手摘到蘋果的時候，就會踩到板凳上再試試?，F(xiàn)在已知10個蘋果到地面的高度，以及陶陶把手伸直的時候能夠達到的最大高度，請幫陶陶算一下她能夠摘到的蘋果的數(shù)目。假設(shè)她碰到蘋果，蘋果就會掉下來?！据斎敫袷健康谝恍邪?0個100~200之間（包括100和200）的整數(shù)（以厘米為單位）分別表示10個蘋果到地面的高度，兩個整數(shù)之間用一個空格隔開。第二行只包括一個100~120之間（包含100和120）的整數(shù)（以厘米為單位），表示陶陶把手伸直的時候能夠達到的最大高度?！据敵龈袷健恳恍幸粋€整數(shù)，表示陶陶能夠摘到的蘋果的數(shù)目?！据斎霕永?00200150140129134167198200111110【輸出樣例】5【問題分析】定義一個數(shù)組保存10個蘋果到地面的高度，再根據(jù)陶陶踩在板凳上的高度來統(tǒng)計她能夠摘到的蘋果數(shù)目。//esain{intapple,i,h,ans=0;forinti=1;i<=10;icin>>apple;cin>>h;fori=1;i<=10;iifh30>=appleans;cout<<ans<<endl;return0;}第3課一維數(shù)組的插入刪除學(xué)習(xí)目標(biāo)1學(xué)會一維數(shù)組的元素插入和刪除操作。2應(yīng)用一維數(shù)組的插入和刪除操作解決一些實際問題。一維數(shù)組的插入插入一個元素，需要先找到插入的位置假設(shè)下標(biāo)為，將這個元素及其之后的所有元素依次往后移一位注意要從后往前進行操作，再將給定的元素插入覆蓋到位置，如圖53-1所示。一維數(shù)組的刪除刪除某一個元素，也需要先找到刪除的位置假設(shè)下標(biāo)為，將下標(biāo)為1及其之后的所有元素依次向前移一位，覆蓋原來位置上的元素，如圖53-2所示。例1、插隊問題【問題描述】有n個人（每個人有一個唯一的編號，用1~n之間的整數(shù)表示）在一個水龍頭前排隊準(zhǔn)備接水，現(xiàn)在第n個人有特殊情況，經(jīng)過協(xié)商，大家允許他插隊到第個位置。輸出第n個人插隊后的排隊情況?！据斎敫袷健康谝恍?個正整數(shù)n，表示有n個人，2<n≤100。第二行包含n個正整數(shù)，之間用一個空格隔開，表示排在隊伍中的第1~第n個人的編號。第三行包含1個正整數(shù)，表示第n個人插隊的位置，1≤<n?！据敵龈袷健恳恍邪琻個正整數(shù)，之間用一個空格隔開，表示第n個人插隊后的排隊情況?！据斎霕永?72345613【輸出樣例】7213456【問題分析】n個人的排隊情況可以用數(shù)組q表示，q表示排在第i個位置上的人。定義數(shù)組時多定義一個位置，然后重復(fù)執(zhí)行：q，其中，i從n~。最后再執(zhí)行q。//esain{intn,i,,q;scanf“%d”,&n;fori=1;i<=n;iscanf“%d”,&q;scanf“%d”,&;fori=n;i>=;i--q;fori=1;i<n;iprintf“%d“,q;return0;}例2、隊伍調(diào)整【問題描述】有n個人（每個人有一個唯一的編號，用1~n之間的整數(shù)表示）在一個水龍頭前排隊準(zhǔn)備接水，現(xiàn)在第個人有特殊情況離開了隊伍，求第個人離開隊伍后的排隊情況?！据斎敫袷健康谝恍?個正整數(shù)n，表示有n個人，2<n≤100。第二行包含n個正整數(shù)，之間用一個空格隔開，表示排在隊伍中的第1個到第n個人的編號。第三行包含1個正整數(shù)，表示第個人離開隊伍，1≤≤n?！据敵龈袷健恳恍邪琻-1個正整數(shù)，之間用一個空格隔開，表示第個人離開隊伍后的排隊情況?！据斎霕永?72345613【輸出樣例】724561//esain{intn,i,,q;scanf“%d”,&n;fori=1;i<=n;iscanf“%d”,&q;scanf“%d”,&;fori=;i<n;iq;n--;fori=1;i<n;iprintf“%d“,q;return0;}第4課一維數(shù)組的查找統(tǒng)計學(xué)習(xí)目標(biāo)1學(xué)會在一維數(shù)組中進行順序查找和二分查找。2熟練應(yīng)用查找和統(tǒng)計操作解決一些實際問題。一維數(shù)組的查找統(tǒng)計一維數(shù)組的查找操作，就是在一維數(shù)組中查找有沒有某個元素，它的值等于指定的值。查找操作的結(jié)果可能是一個沒找到、找到一個或者找到很多個。常見的查找算法有“順序”查找和“二分”查找。順序查找就是按照從前往后的順序，將數(shù)組中的元素依次與要查找的數(shù)進行比較。二分查找又稱“折半”查找，其優(yōu)點是比較次數(shù)少、查找速度快。但是要求數(shù)據(jù)是遞增或遞減排序的。二分查找intleft=0，right=n-1;intfind=n;//find標(biāo)記找到的位置，初始化為n，表示沒找到whileleft<=right{ intmid=leftright/2; ifa=={//找到了，就標(biāo)記位置，并退出循環(huán) find=mid; brea; } if<aright=mid-1;//只能在左半部分 ifa<left=mid1;//只能在右半部分}iffind!=nprintf"%d\n",find;elseprintf"notfind\n";例1、抽獎1【問題描述】公司舉辦年會，為了活躍氣氛，設(shè)置了搖獎環(huán)節(jié)。參加聚會的每位員工都有一張帶有號碼的抽獎券?，F(xiàn)在，主持人依次公布n個不同的獲獎號碼，小謝看著自己抽獎券上的號碼num，無比緊張。請編寫一個程序，如果小謝獲獎了，請輸出他中的是第幾個號碼；如果沒有中獎，請輸出0?！据斎敫袷健康谝恍幸粋€正整數(shù)n，表示有n個獲獎號碼，2<n≤100。第二行包含n個正整數(shù)，之間用一個空格隔開，表示依次公布的n個獲獎號碼。第三行一個正整數(shù)num，表示小謝抽獎券上的號碼。1≤獲獎號碼，num<10000?！据敵龈袷健恳恍幸粋€整數(shù)，如果小謝中獎了，表示中獎的是第幾個號碼；如果沒有中獎，則為0?！据斎霕永?172349555613【輸出樣例】3//esain{intn,i,num,f,g;scanf“%d”,&n;fori=1;i<=n;iscanf“%d”,&g;scanf“%d”,#f=0;fori=1;i<=n;iifg==num{f=i;brea;}printf“%d\n”,f;return0;}例2、抽獎2【問題描述】公司舉辦年會，為了活躍氣氛，設(shè)置了搖獎環(huán)節(jié)。參加聚會的每位員工都有一張帶有號碼的抽獎券?，F(xiàn)在，主持人從小到大依次公布n個不同的獲獎號碼，小謝看著自己抽獎券上的號碼win，無比緊張。請編寫一個程序，如果小謝獲獎了，請輸出他中獎的是第幾個號碼；如果沒有中獎，請輸出0?！据斎敫袷健康谝恍幸粋€正整數(shù)n，表示有n個獲獎號碼，2<n≤100。第二行包含n個正整數(shù)，之間用一個空格隔開，表示依次公布的n個獲獎號碼。第三行一個正整數(shù)win，表示小謝抽獎券上的號碼。1≤獲獎號碼，win<10000?！据敵龈袷健恳恍幸粋€整數(shù)，如果小謝中獎了，表示中獎的是第幾個號碼；如果沒有中獎，則為0。【輸入樣例】7123461795553【輸出樣例】3//esain{intn,i,win,f,left,right,mid,g;scanf“%d”,&n;fori=1;i<=n;iscanf“%d”,&g;scanf“%d”,&win;f=0;left=1;right=n;whileleft<=right{mid=leftright/2;ifg==win{f=mid;brea;}ifwin<gright=mid-1;ifg<winleft=mid1;}printf“%d\n”,f;return0;}例3、比身高【問題描述】有N個人排成一排，假設(shè)他們的身高均為正整數(shù)，請找出其中符合以下條件的人：排在他前面且比他高的人數(shù)與排在他后面且比他高的人數(shù)相等?！据斎敫袷健康谝恍袨橐粋€正整數(shù)N，1<N<1000，表示有多少個人。下面N行，每行一個正整數(shù)，表示從前往后每個人的身高，假設(shè)每個人的身高≤10000?！据敵龈袷健恳恍幸粋€整數(shù)，表示滿足這個條件的人數(shù)?！据斎霕永?1213【輸出樣例】2【樣例說明】第3、第4個人滿足條件。//esain{scanf“%d”,&n;fori=1;i<=n;iscanf“%d”,&h;fori=1;i<=n;i{t1=t2=0;forj=1;j<i;jifht1;//排在他前面且比他高的人數(shù)forj=i1;j<=n;jifht2;//排在他后面且比他高的人數(shù)ift1==t2ans;}printf“%d\n”,ans;return0;}第5課一維數(shù)組的元素排序?qū)W習(xí)目標(biāo)1掌握選擇排序、冒泡排序和插入排序。2應(yīng)用排序算法解決一些實際問題。一維數(shù)組的元素排序“排序”就是按照某個關(guān)鍵字的大小，將若干對象從小到大或者從大到小進行重新排列。關(guān)鍵字是對象的某一個屬性，它可以是任何基本數(shù)據(jù)類型，甚至結(jié)構(gòu)體等。例如，體育課上我們會按照身高從矮到高站隊，這就是“升序”排序，身高是我們每個人的一個屬性，也就是排序的關(guān)鍵字。再如，將所有單詞按照“字典序”倒過來排序，如oo,yes,most,ey,computer,boo,bad,apple等，就是“降序”排序，關(guān)鍵字的類型就是字符串。排序算法非常多，其中最基本的有選擇排序、冒泡排序和插入排序三種。其本質(zhì)上都是通過數(shù)組中的元素比較和交換來實現(xiàn)的，關(guān)鍵是數(shù)組下標(biāo)的分析。例1、站隊【問題描述】給出n個同學(xué)的身高，請根據(jù)他們的身高升序排列并輸出排序結(jié)果。【輸入格式】第一行1個正整數(shù)n，表示有n個同學(xué)的身高，2<n≤100。第二行包含n個正整數(shù)，之間用一個空格隔開，表示n個同學(xué)的身高。每個同學(xué)的身高都在150~200厘米之間?！据敵龈袷健恳恍衝個正整數(shù)，之間用一個空格隔開，表示n個同學(xué)根據(jù)身高升序排列的結(jié)果。【輸入樣例】7180170176160155150160【輸出樣例】150155160160170176180【問題分析】算法1、選擇排序選擇排序的基本思想是：每一趟從待排序的數(shù)據(jù)中，通過“打擂臺”比較選出最小元素，放在這些數(shù)據(jù)的最前面。這樣，第一趟把n個數(shù)中（第1個到第n個）最小的放在第一個位置，第二趟把剩余的n-1個數(shù)中（第2個到第n個）最小的放在第二個位置，第三趟把剩余的n-2個數(shù)中（第3個到第n個）最小的放在第三個位，……第n-1趟把剩下的2個數(shù)中（第n-1個到第n個）最小的放在第n-1個位置，剩下的最后一個數(shù)（第n個）一定最大，自然落在了第n個位置。//esain{intn,i,j,,temp;//將i~n之間的最小元素放到第i個位置}fori=1;i<n;icout<<h<<endl;return0;}算法2、冒泡排序冒泡排序的基本思想是：從第一個數(shù)開始，依次不斷比較相鄰的兩個元素，如果“逆序”就交換。這樣，一趟排序結(jié)束后，最大的元素就放在了第n個位置了。對于樣例數(shù)據(jù)，第一趟冒泡排序的過程如下：用同樣的方法，第二趟把剩余的前n-1個數(shù)中最大的交換到第n-1個位置，第三趟把剩余的前n-2個數(shù)中最大的交換到第n-2個位置，……經(jīng)過n-1趟，排序結(jié)束。//esain{intn,i,j,temp;}fori=1;i<n;icout<<h<<endl;return0;}對于冒泡排序，我們還可以做些算法“優(yōu)化”。如果一趟排序下來，都沒有任何“逆序”數(shù)對，即沒有發(fā)生“交換”操作，則說明已經(jīng)排好序了。此時，就可以立刻退出循環(huán)。//esain{intn,i,j,temp;flag=false;}ifflagbrea;}fori=1;i<n;icout<<h<<endl;return0;}算法3、插入排序插入排序的基本思想是：把所有待排序元素分成前后兩段，前一段是已經(jīng)排好序的，后一段是待排序的。每一趟都是把后一段的第一個數(shù)“插入”到前一段的某一個位置，保證前一段仍然是有序的。開始時，第1個數(shù)作為前一段肯定是有序的；第一趟，把第2個數(shù)插入進去，保證前2個數(shù)有序；第二趟，把第3個數(shù)插入進去，保證前3個數(shù)有；……第n-1趟，把第n個數(shù)插入進去，保證n個數(shù)都有序。//esain{intn,i,j,,temp;}fori=1;i<n;icout<<h<<endl;return0;}第6課一維數(shù)組的應(yīng)用舉例學(xué)習(xí)目標(biāo)1學(xué)會跟蹤數(shù)組元素調(diào)試程序。2綜合應(yīng)用一維數(shù)組的基本操作解決一些實際問題。例1、學(xué)習(xí)對象【問題描述】n個信息學(xué)選手站在一排，每個選手的位置依次用1~n表示，第i個信息學(xué)選手的編程能力用一個整數(shù)Hi表示。每個信息學(xué)選手都希望找一個編程能力比自己高但又與自己編程能力最接近的選手學(xué)習(xí)，如果有多個符合條件的選手則選擇位置在最前面的選手學(xué)習(xí)。請編程輸出每位選手學(xué)習(xí)對象的位置，如果沒有學(xué)習(xí)對象，則輸出0?！据斎敫袷健康?行一個正整數(shù)n，1≤n≤1000；第2~n1行共n個正整數(shù)，依次表示每位選手的編程能力，1≤Hi≤1000000?！据敵龈袷健縩行，每行輸出一個整數(shù)表示每個選手學(xué)習(xí)對象的位置?！据斎霕永?326112【輸出樣例】310221【問題分析】第i個選手的學(xué)習(xí)對象就是從前往后查找一個選手j，要求Hi<Hj且Hj要盡可能小（打擂臺），如果j可以取多個值，則選取最小的值（保留前面）。//esah,h;intmain{cin>>n;fori=1;i<=n;icin>>h;fori=1;i<=n;i{ans=0;mah=1000001;forj=1;j<=n;jifh<mah{ans=j;mah=h;}cout<<ans<<endl;}return0;}例2、商品排序【問題描述】某商場的倉庫中有n件商品，每件商品的價格在0~1000之間（價格為0的商品為贈品）?，F(xiàn)在商場經(jīng)理要求將這n件商品按價格由低到高排序。請編程輸出n件商品排序后的情況?！据斎敫袷健康谝恍幸粋€正整數(shù)n，表示有n件商品，1≤n≤100000。接下來的n行，每行一個整數(shù)，表示第i件商品的價格。【輸出格式】n行，每行輸出一個整數(shù)。【輸入樣例】518122【輸出樣例】11228【問題分析】本題可以選用學(xué)過的任意一種排序算法實現(xiàn)，但是測試程序發(fā)現(xiàn)會“超時”，因為本題最多有100000件商品，三種排序都需要兩層循環(huán)嵌套。其實，分析數(shù)據(jù)發(fā)現(xiàn)一個重要特征：數(shù)據(jù)雖然很多，但是數(shù)據(jù)范圍比較小。這種情況下，可以使用另外一種排序算法——桶排序。定義一個int型數(shù)組num記錄整數(shù)出現(xiàn)的次數(shù)，初始化都為0，每讀到一個數(shù)，就執(zhí)行num1。輸出時，從0~1000窮舉，每個輸出num次。//esber,num;intmain{cin>>n;fori=1;i<=n;i{cin>>number;num;//記錄整數(shù)number出現(xiàn)的次數(shù)}fori=0;i<1001;iforj=1;j<=num;jcout<<i<<endl;//輸出num次ireturn0;}例3、素數(shù)大酬賓【問題描述】某商場的倉庫中有n種商品，每件商品按1~n依次編號?，F(xiàn)在商場經(jīng)理突發(fā)奇想，決定將編號為素數(shù)（質(zhì)數(shù)）的所有商品拿出來搞優(yōu)惠酬賓活動。請編程幫助倉庫管理員將編號為素數(shù)的商品選出來?！据斎敫袷健恳恍幸粋€正整數(shù)n，表示有n種商品，2≤n≤100000。【輸出格式】一行若干個正整數(shù)，表示若干種商品編號且每個編號均為素數(shù)，請從小到大輸出，每兩個數(shù)之間有一個空格?！据斎霕永?0【輸出樣例】23571