信息學(xué)奧賽NOIP第4單元循環(huán)結(jié)構(gòu)程序的設(shè)計(jì)說(shuō)明

第4單元循環(huán)結(jié)構(gòu)程序設(shè)計(jì)信息學(xué)奧賽（C++）2021/5/91第1課while語(yǔ)句學(xué)習(xí)目標(biāo)1.理解循環(huán)結(jié)構(gòu)的含義。2.熟練掌握while語(yǔ)句的格式和功能。3.初步應(yīng)用while語(yǔ)句解決一些實(shí)際問(wèn)題。2021/5/92循環(huán)結(jié)構(gòu)在程序設(shè)計(jì)中，經(jīng)常需要反復(fù)執(zhí)行某一條語(yǔ)句或一個(gè)語(yǔ)句塊，這種結(jié)構(gòu)稱(chēng)為“循環(huán)結(jié)構(gòu)”或者“重復(fù)結(jié)構(gòu)”。其實(shí)，計(jì)算機(jī)最擅長(zhǎng)的就是重復(fù)做一件事情，所以循環(huán)結(jié)構(gòu)在程序設(shè)計(jì)中應(yīng)用非常廣泛。在C++中，循環(huán)結(jié)構(gòu)有三種實(shí)現(xiàn)語(yǔ)句：while語(yǔ)句、do-while語(yǔ)句和for語(yǔ)句。2021/5/931.while語(yǔ)句的含義其含義為：先計(jì)算表達(dá)式（一般稱(chēng)為循環(huán)條件）的值，當(dāng)表達(dá)式的值為真（循環(huán)條件成立）時(shí)，去執(zhí)行一次循環(huán)體。和if語(yǔ)句不同的是，執(zhí)行完一次循環(huán)體后，while語(yǔ)句又回到開(kāi)始處，繼續(xù)計(jì)算和判斷表達(dá)式的真假，決定是否再次執(zhí)行循環(huán)體。也就是“當(dāng)表達(dá)式成立時(shí)，不斷重復(fù)執(zhí)行循環(huán)體”，所以又稱(chēng)為“當(dāng)型循環(huán)”。while語(yǔ)句的格式如下：while（表達(dá)式）｛

循環(huán)體｝2021/5/942.while語(yǔ)句的應(yīng)用舉例【問(wèn)題分析】設(shè)sum存放答案，初始化為0。再設(shè)i為循環(huán)控制變量，初始化為1。當(dāng)循環(huán)條件（i<=100）成立時(shí)，反復(fù)執(zhí)行以下循環(huán)體：（1）將i累加到和sum中；（2）將i取值為下一個(gè)數(shù)，即i++。最后，輸出ans的值。例1、求1+2+3+…+100的值。2021/5/95//p4-1-1#include<iostream>usingnamespacestd;intmain(){inti=1,sum=0;while(i<=100)sum+=i++;cout<<sum<<endl;return0;}2021/5/96例2、閱讀程序，寫(xiě)出程序的運(yùn)行結(jié)果。//p4-1-2#include<iostream>usingnamespacestd;intmain(){inti=100,x=0,y=0;while(i>0){i--;x=i%8;if(x==1)y++;}cout<<y<<endl;return0;}2021/5/97【問(wèn)題分析】一般采用列表觀察、找規(guī)律的方法，閱讀和理解程序。對(duì)于本題而言，循環(huán)條件為“i>0”，用到i、x和y這3個(gè)變量，列表如表4.1-1。通過(guò)找規(guī)律發(fā)現(xiàn)，每次i是8*x+1時(shí)，y的值會(huì)加1，也就是97、89、81、…、9、1，一共99/8+1=13。所以，程序最后輸出y的值為13。2021/5/98例3、統(tǒng)計(jì)正數(shù)【問(wèn)題描述】輸入若干整數(shù)，以0結(jié)尾，統(tǒng)計(jì)其中有多少個(gè)正整數(shù)?！据斎敫袷健恳恍腥舾烧麛?shù)，最后一個(gè)為0?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示輸入的數(shù)據(jù)中正整數(shù)的個(gè)數(shù)?！緲永斎搿?6-320【樣例輸出】32021/5/99【問(wèn)題分析】對(duì)于本題來(lái)說(shuō)，首先要輸入一個(gè)整數(shù)，當(dāng)它不為0時(shí)，需要反復(fù)執(zhí)行：（1）判斷該數(shù)是否為正數(shù)，如果是，則答案累加1；（2）輸入下一個(gè)數(shù)，再返回去判斷是否為0。//p4-1-3#include<iostream>usingnamespacestd;intmain(){intx,s=0;cin>>x;while(x!=0){//也可以簡(jiǎn)寫(xiě)成while(x)if(x>0)s++;cin>>x;}cout<<s<<endl;return0;}2021/5/910例4、投資收益【問(wèn)題描述】小華在去年賺了一大筆錢(qián)。他想把這些錢(qián)用于投資，并對(duì)自己能得到多少收益感到好奇。已知投資的年利率為r（0~20之間的整數(shù)），小華現(xiàn)有m元錢(qián)。他想知道投資多少年后，他的錢(qián)將會(huì)超過(guò)y元?！据斎敫袷健恳恍腥齻€(gè)整數(shù)r、m和y，相鄰兩個(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。m為100~1000000之間的整數(shù)?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，即要投資的年數(shù)。保證答案的范圍在1~400之間?！緲永斎搿?50006077【樣例輸出】4【樣例說(shuō)明】第一年后：1.05*5000=5250；第二年后：1.05*5250=5512.5；第三年后：1.05*5512.5=5788.125；第四年后：1.05*5788.125=6077.53125。2021/5/911【問(wèn)題分析】小華手里有m元錢(qián)，目標(biāo)是超過(guò)y元錢(qián)，k表示答案（初始化為0）。所以，當(dāng)條件“m<=y”成立時(shí)，要反復(fù)執(zhí)行：（1）修改m的值，即m=m*（1+r%）；（2）修改k的值，即k++。循環(huán)結(jié)束后，k的值即為所求的答案。//p4-1-4#include<iostream>usingnamespacestd;intmain(){doubler,m,y;intk=0;cin>>r>>m>>y;while(m<=y){m=m*(1+r/100);k=k+1;}cout<<k<<endl;return0;}2021/5/912實(shí)踐鞏固2021/5/913第2課do-while語(yǔ)句學(xué)習(xí)目標(biāo)1.熟練掌握do-while語(yǔ)句的格式和功能。2.體會(huì)do-while語(yǔ)句與while語(yǔ)句的區(qū)別。3.熟練運(yùn)用do-while語(yǔ)句解決一些實(shí)際問(wèn)題。2021/5/914do-while語(yǔ)句do-while語(yǔ)句是C++中用于解決至少執(zhí)行一次重復(fù)操作（循環(huán)體）的循環(huán)語(yǔ)句。2021/5/9151.do-while語(yǔ)句的含義do-while語(yǔ)句的格式如下：do{

循環(huán)體}while（表達(dá)式）;其含義為：先執(zhí)行一次循環(huán)體，然后判斷表達(dá)式是否成立，如果成立，則返回繼續(xù)執(zhí)行循環(huán)體，直到表達(dá)式不成立，才退出循環(huán)。一般稱(chēng)之為“直到型循環(huán)”。2021/5/916例1、用do-while語(yǔ)句實(shí)現(xiàn)輸出一行10個(gè)“@”。//p4-2-1#include<cstdio>usingnamespacestd;intmain(){inti=1;do{printf(“@”);i++;}while(i<=10);return0;}2021/5/917例2、統(tǒng)計(jì)正數(shù)【問(wèn)題描述】用do-while語(yǔ)句實(shí)現(xiàn)：輸入若干整數(shù)，以0結(jié)尾，統(tǒng)計(jì)其中有多少個(gè)正整數(shù)?！据斎敫袷健恳恍腥舾烧麛?shù)，最后一個(gè)為0?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示輸入的數(shù)據(jù)中正整數(shù)的個(gè)數(shù)?！緲永斎搿?6-320【樣例輸出】32021/5/918//p4-2-2#include<iostream>usingnamespacestd;intmain(){intx,s=0;do{cin>>x;if(x>0)s++;}while(x!=0);cout<<s<<endl;return0;}2021/5/919例3、投資收益【問(wèn)題描述】小華在去年賺了一大筆錢(qián)！他想把這些錢(qián)用于投資，并對(duì)自己能得到多少收益感到好奇。已知投資的年利率為r（0~20之間的整數(shù)），小華現(xiàn)有m元錢(qián)。他想知道投資多少年后，他的錢(qián)將會(huì)超過(guò)y元。要求用do-while語(yǔ)句實(shí)現(xiàn)?！据斎敫袷健恳恍腥齻€(gè)整數(shù)r、m和y，相鄰兩個(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。m為100~1000000之間的整數(shù)?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，即要投資的年數(shù)。保證答案的范圍在1~400之間。2021/5/920【樣例輸入】550006077【樣例輸出】4//p4-2-3#include<iostream>usingnamespacestd;intmain(){doubler,m,y;intk=0;cin>>r>>m>>y;do{m=m*(1+r/100);k=k+1;}while(m<=y)cout<<k<<endl;return0;}2021/5/921例4、數(shù)字和【問(wèn)題描述】輸入一個(gè)正整數(shù)，輸出它的各位數(shù)字之和?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)，int范圍以?xún)?nèi)?！据敵龈袷健恳恍幸粋€(gè)正整數(shù)，表示答案?！緲永斎搿?58【樣例輸出】152021/5/922【問(wèn)題分析】求一個(gè)正整數(shù)的各位數(shù)字之和，需要“分解”出它的每一位數(shù)字，每次進(jìn)行累加。定義累加器s，初始化為0。對(duì)于正整數(shù)n，分解的過(guò)程就是從低位到高位，不斷求余累加（s+=n%10）和整除（n=n/10），直到n等于0。2021/5/923//p4-2-4#include<cstdio>usingnamespacestd;intmain(){intn,s=0;scanf(“%d”,&n);do{s+=n%10;n/=10;}while(n!=0);printf(“%d\n”,s);return0;}2021/5/924實(shí)踐鞏固2021/5/925第3課for語(yǔ)句學(xué)習(xí)目標(biāo)1.熟練掌握f(shuō)or語(yǔ)句的格式、功能和應(yīng)用場(chǎng)合。2.學(xué)會(huì)用for語(yǔ)句改寫(xiě)while和do-while語(yǔ)句。3.熟練應(yīng)用for語(yǔ)句解決一些實(shí)際問(wèn)題。2021/5/926for語(yǔ)句如果重復(fù)執(zhí)行的操作（循環(huán)體）次數(shù)是固定的、已知的，則一般使用for語(yǔ)句。for語(yǔ)句的格式如下：for(表達(dá)式1;表達(dá)式2;表達(dá)式3){

循環(huán)體}2021/5/927例1、用for語(yǔ)句實(shí)現(xiàn)：輸出一行10個(gè)“@”。//p4-3-1a#include<cstdio>usingnamespacestd;intmain(){for(inti=1;i<=10;i++)printf(“@”);printf(“\n”);return0;}2021/5/928for語(yǔ)句寫(xiě)法靈活，上述程序也可以寫(xiě)成：//p4-3-1b#include<cstdio>usingnamespacestd;intmain(){inti=1;for(;i<=10;i++)printf(“@”);printf(“\n”);return0;}2021/5/929還可以寫(xiě)成：//p4-3-1c#include<cstdio>usingnamespacestd;intmain(){inti=1;for(;i<=10;){printf(“@\n”);i++;}printf(“@\n”);return0;}2021/5/930例2、斐波那契數(shù)列【問(wèn)題描述】斐波那契數(shù)列是指這樣的數(shù)列：第一個(gè)數(shù)和第二個(gè)數(shù)都為1，接下來(lái)每個(gè)數(shù)都等于前面兩個(gè)數(shù)之和。編程輸入一個(gè)正整數(shù)k，輸出斐波那契數(shù)列第k個(gè)數(shù)?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)k，1≤k≤46?！据敵龈袷健恳恍幸粋€(gè)正整數(shù)，表示斐波那契數(shù)列第k個(gè)數(shù)的大小?！緲永斎搿?9【樣例輸出】4181【問(wèn)題分析】2021/5/931//p4-3-2#include<iostream>usingnamespacestd;intmain(){intk;cin>>k;intk1=1,k2=1,k3=1;for(inti=3;i<=k;i++){k3=k1+k2;k1=k2;//迭代法k2=k3;}cout<<k3<<endl;return0;}2021/5/932例3、求平均年齡【問(wèn)題描述】給出一個(gè)班級(jí)里每名學(xué)生的年齡（正整數(shù)），求所有學(xué)生的平均年齡，保留到小數(shù)點(diǎn)后兩位?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，表示學(xué)生的人數(shù)，1≤n≤100。后面n行，每行一個(gè)正整數(shù)，表示學(xué)生的年齡，15≤年齡≤25?！据敵龈袷健恳恍幸粋€(gè)浮點(diǎn)數(shù)，保留到小數(shù)點(diǎn)后兩位?！緲永斎搿?1817【樣例輸出】17.502021/5/933//p4-3-3#include<cstdio>usingnamespacestd;intmain(){intn;floats;scanf(“%d”,&n);for(inti=1;i<=n;i++){intx;scanf("%d",&x);s+=x;}printf(“%.2f\n”,s/n);return0;}2021/5/934例4、整數(shù)的個(gè)數(shù)【問(wèn)題描述】給定k個(gè)正整數(shù)，每個(gè)數(shù)都是大于或等于1，且小于或等于10。編程統(tǒng)計(jì)其中1、5和10出現(xiàn)的次數(shù)?！据斎敫袷健康谝恍幸粋€(gè)正整數(shù)k；第二行包含k個(gè)正整數(shù)，每?jī)蓚€(gè)正整數(shù)之間用一個(gè)空格隔開(kāi)?！据敵龈袷健康谝恍袨?出現(xiàn)的次數(shù)，第二行為5出現(xiàn)的次數(shù)，第三行為10出現(xiàn)的次數(shù)?！緲永斎搿?158105【樣例輸出】1212021/5/935//p4-3-4#include<cstdio>usingnamespacestd;intmain(){intn;ints1=0,s2=0,s3=0;scanf("%d",&n);for(inti=1;i<=n;i++){intx;scanf(“%d”,&x);if(x==1)s1++;if(x==5)s2++;if(x==10)s3++;}printf(“%d\n%d\n%d\n”,s1,s2,s3);return0;}2021/5/936實(shí)踐鞏固2021/5/937第4課循環(huán)嵌套學(xué)習(xí)目標(biāo)1.理解循環(huán)嵌套的含義。2.熟練應(yīng)用循環(huán)語(yǔ)句及其嵌套解決一些實(shí)際問(wèn)題。2021/5/938循環(huán)結(jié)構(gòu)的嵌套循環(huán)結(jié)構(gòu)與分支結(jié)構(gòu)的嵌套類(lèi)似，也可以在一個(gè)循環(huán)語(yǔ)句的循環(huán)體里出現(xiàn)另一個(gè)循環(huán)語(yǔ)句，不管是while語(yǔ)句、do-while語(yǔ)句還是for語(yǔ)句。這樣的循環(huán)結(jié)構(gòu)稱(chēng)為“循環(huán)嵌套”。2021/5/939例1、輸出矩形【問(wèn)題描述】輸入n和m，輸出一個(gè)n行m列的“*”矩形圖案?！据斎敫袷健恳恍袃蓚€(gè)正整數(shù)n和m，中間用一個(gè)空格隔開(kāi)，1≤n、m≤100?！据敵龈袷健枯敵鲆粋€(gè)n行m列的“*”矩形圖案?！緲永斎搿?4【樣例輸出】************2021/5/940//p4-4-1#include<cstdio>usingnamespacestd;intmain(){intn,m;scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){for(intj=1;j<=m;j++)printf(“*”);printf(“\n”);}return0;}【問(wèn)題分析】要輸出n行，所以可以編寫(xiě)一個(gè)外層循環(huán)，窮舉行。然后，在循環(huán)體里，還要輸出m個(gè)“*”，所以再嵌套一個(gè)內(nèi)層循環(huán)，窮舉每一行的“*”個(gè)數(shù)。2021/5/941例2、數(shù)字三角形【問(wèn)題描述】輸入一個(gè)正整數(shù)n，輸出n行的數(shù)字三角形。其中，第1行為數(shù)字1，第2行為數(shù)字23，第3行為數(shù)字456，第4行為數(shù)字7890，第5行為數(shù)字12345，…【輸入格式】一行一個(gè)正整數(shù)n，1≤n≤100?！据敵龈袷健縩行的數(shù)字三角形?！緲永斎搿?【樣例輸出】12345678902021/5/942//p4-4-2#include<cstdio>usingnamespacestd;intmain(){intn,t=1;scanf("%d",&n);for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){printf(“%d”,t%10);t++;}printf(“\n”);}return0;}2021/5/943例3、與7無(wú)關(guān)的數(shù)【問(wèn)題描述】一個(gè)正整數(shù)，如果它能被7整除，或者它的某一位上的數(shù)字為7，則稱(chēng)其為“與7相關(guān)”的數(shù)?，F(xiàn)在，請(qǐng)編程求出所有小于或等于n的“與7無(wú)關(guān)”的正整數(shù)個(gè)數(shù)?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，n≤10^6?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示答案?！緲永斎搿?1【樣例輸出】172021/5/944//p4-4-3#include<iostream>usingnamespacestd;intmain(){intn,ans=0;cin>>n;for(inti=1;i<=n;i++){intflag1=1,flag2=1;if(i%7==0)flag1=0;intx=i;while(x&&flag2){if(x%10==7)flag2=0;x=x/10;}if(flag1&&flag2)ans++;}cout<<ans<<endl;return0;}2021/5/945實(shí)踐鞏固2021/5/946第5課break和continue語(yǔ)句學(xué)習(xí)目標(biāo)1.理解break語(yǔ)句和continue語(yǔ)句的作用。2.學(xué)會(huì)使用break語(yǔ)句和continue語(yǔ)句。2021/5/947break和continue語(yǔ)句在循環(huán)結(jié)構(gòu)中，有時(shí)需要提前跳出循環(huán)體，或者忽略本次循環(huán)的后續(xù)語(yǔ)句而去執(zhí)行下一次循環(huán)。為此，C++提供了break語(yǔ)句和continue語(yǔ)句。2021/5/9481.break語(yǔ)句

在循環(huán)體中遇到break語(yǔ)句，就會(huì)立刻跳出循環(huán)體，執(zhí)行循環(huán)結(jié)構(gòu)后面的語(yǔ)句。例1、與7無(wú)關(guān)的數(shù)?！締?wèn)題描述】一個(gè)正整數(shù)，如果它能被7整除，或者它的某一位上的數(shù)字為7，則稱(chēng)其為“與7相關(guān)”的數(shù)?，F(xiàn)在，請(qǐng)編程求出所有小于或等于n的“與7無(wú)關(guān)”的正整數(shù)個(gè)數(shù)。【輸入格式】一行一個(gè)正整數(shù)n，n≤10^6?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示答案?！緲永斎搿?1【樣例輸出】172021/5/949【問(wèn)題分析】

判斷x中是否有數(shù)字7的時(shí)候，一旦出現(xiàn)“x%10==7”，則說(shuō)明x是與7相關(guān)的數(shù)，就可以用break語(yǔ)句立刻退出當(dāng)前的while循環(huán)，這樣可以提高程序的效率。

2021/5/950//p4-5-1#include<iostream>usingnamespacestd;intmain(){intn,ans=0;cin>>n;for(inti=1;i<=n;i++){intflag1=1,flag2=1;if(i%7==0)flag1=0;intx=i;while(x){if(x%10==7){flag2=0;break;}x=x/10;}if(flag1&&flag2)ans++;}cout<<ans<<endl;return0;}2021/5/9512.continue語(yǔ)句在循環(huán)體中遇到continue語(yǔ)句，就會(huì)忽略本次循環(huán)的后續(xù)語(yǔ)句而去執(zhí)行下一次循環(huán)。例2、與7無(wú)關(guān)的數(shù)?！締?wèn)題描述】一個(gè)正整數(shù)，如果它能被7整除，或者它的某一位上的數(shù)字為7，則稱(chēng)其為“與7相關(guān)”的數(shù)。請(qǐng)編程求出所有小于或等于n的“與7無(wú)關(guān)”的正整數(shù)個(gè)數(shù)?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，n≤10^6?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示答案。2021/5/952【問(wèn)題分析】當(dāng)i是7的倍數(shù)，即“i%7==0”時(shí)，說(shuō)明i已經(jīng)是與7相關(guān)的數(shù)了，此時(shí)，就不再需要判斷i的某一位是否是7了。所以，可以用continue忽略本次循環(huán)的后續(xù)語(yǔ)句，而去執(zhí)行下一次循環(huán)，判斷下一個(gè)數(shù)了。這樣做同樣可以提高程序的效率?！緲永斎搿?1【樣例輸出】172021/5/953//p4-5-2#include<iostream>usingnamespacestd;intmain(){intn,ans=0;cin>>n;for(inti=1;i<=n;i++){intflag=1;if(i%7==0)continue;intx=i;while(x){if(x%10==7){flag=0;break;}x=x/10;}if(flag)ans++;}cout<<ans<<endl;return0;}2021/5/9543.break語(yǔ)句和continue語(yǔ)句的應(yīng)用舉例例3、素?cái)?shù)的判定【問(wèn)題描述】輸入一個(gè)正整數(shù)，判斷其是否為素?cái)?shù)。如果是，則輸出“prime”；否則，輸出“notprime”?！据斎敫袷健恳恍幸粋€(gè)正整數(shù)n，2≤n≤10^7?！据敵龈袷健恳恍幸粋€(gè)字符串?！緲永斎搿?【樣例輸出】notprime2021/5/955//p4-5-3#include<iostream>#include<cmath>usingnamespacestd;intmain(){intx;cin>>x;for(inti=2;i<=sqrt(x);i++){//或者i*i<=xif(x%i==0){cout<<“not“;break;}}cout<<“prime”<<endl;return0;}2021/5/956例4、素?cái)?shù)的統(tǒng)計(jì)【問(wèn)題描述】輸入兩個(gè)正整數(shù)m和n，判斷m和n之間（含m和n）一共有多少個(gè)素?cái)?shù)?！据斎敫袷健恳恍袃蓚€(gè)正整數(shù)m和n，2≤m≤n≤10^4?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示素?cái)?shù)的個(gè)數(shù)?！緲永斎搿?10【樣例輸出】22021/5/957//p4-5-4#include<iostream>＃include<cmath>usingnamespacestd;intmain(){intm,n,i,j,ans=0;cin>>m>>n;for(i=m;i<=n;i++){for(j=2;j<sqrt(i);j++)if(i%j==0)break;if(j<sqrt(i))co