第4章

循環(huán)結(jié)構(gòu)目錄while語句do…while語句for語句break/continue語句多重循環(huán)算法執(zhí)行效率216:12實際應用中經(jīng)常遇到需要反復執(zhí)行某些固定操作序列的情形，循環(huán)結(jié)構(gòu)正是為此而設置的控制結(jié)構(gòu)，這些需反復執(zhí)行的固定操作序列就定義為循環(huán)體。當程序運行到循環(huán)語句時，若循環(huán)語句的條件判定結(jié)果為真，則選擇執(zhí)行循環(huán)體然后再判斷循環(huán)條件，否則便跳出該循環(huán)轉(zhuǎn)而運行下一條語句。因此，循環(huán)結(jié)構(gòu)的本質(zhì)可歸結(jié)為循環(huán)判斷執(zhí)行的選擇結(jié)構(gòu)。316:121．while語句while語句是C/C++語言的一種基本循環(huán)模式，若條件為真則執(zhí)行循環(huán)體，當條件為假時跳出循環(huán)執(zhí)行后續(xù)語句。while的一般格式為：while(表達式)循環(huán)體while語句的功能是：若表達式為真（非0值為真）則執(zhí)行循環(huán)體；然后再重新判斷表達式，…；如此周而復始，直至表達式為假（0值為假）則跳出該循環(huán)。因此while語句本質(zhì)上相當于循環(huán)判斷執(zhí)行的單分支if語句。while語句的執(zhí)行流程圖如圖4.1所示。while語句中，循環(huán)體可以是一個簡單語句，也可以是一個復合語句（用{}括起的多條語句），甚至是一條空語句；表達式可以是關系表達式、邏輯表達式，甚至是數(shù)值表達式。返回416:12例4.1：求m+(m+1)…+n。輸入：兩個正整數(shù)m和n（m<=n）。輸出：m加到n的和。#include<iostream>usingnamespacestd;intmain(){ intm,n; cin>>m>>n; inti=m,sum=0; while(i<=n) { sum=sum+i; i++; } cout<<sum<<endl; return0;}516:12例4.2：輸入多組整數(shù)，每組數(shù)據(jù)包含兩個整數(shù)a和b，對每組數(shù)據(jù)輸出a+b的結(jié)果。輸入：多組整數(shù)。

輸出：對每組數(shù)據(jù)輸出a+b的結(jié)果。#include<iostream>usingnamespacestd;intmain(){ inta,b;

while(cin>>a>>b) //可以“while(scanf("%d%d",&a,&b)!=EOF)”替代 cout<<a+b<<endl; return0;}616:122．do…while語句do...while語句首先無條件執(zhí)行一次循環(huán)體，然后再判斷循環(huán)條件，若條件為真則再次執(zhí)行循環(huán)體，……，直至循環(huán)條件為假則跳出循環(huán)。do...while語句的一般格式為：do

循環(huán)體while(表達式);do...while語句的循環(huán)體可以是一個簡單語句，也可以是一個復合語句，甚至是一條空語句。do...while語句的執(zhí)行流程圖如圖4.2所示。do...while語句和while語句非常相似，但后者是當型循環(huán)，前者是直到型循環(huán)。do-while語句保證其循環(huán)體至少會執(zhí)行一次；但是在while語句中，若起始時表達式為假則循環(huán)體一次也不會執(zhí)行。不過，若開始時表達式為真，則do...while和while效果完全相同。返回716:12例4.3：輸入正整數(shù)n，求使1+2+…+i>=n成立的最小i。輸入：一個正整數(shù)n。輸出：使1+2+…+i>=n成立的最小i。#include<iostream>usingnamespacestd;intmain(){ intn,i=0,sum=0; cin>>n; do { i++; sum=sum+i; }while(sum<n); cout<<i<<endl; return0;}816:123．for語句for語句是C/C++的第三種循環(huán)控制實現(xiàn)方式。for語句的一般格式為：for([表達式1];[表達式2];[表達式3])循環(huán)體表達式1是for語句執(zhí)行的開始部分，通常用于為循環(huán)控制變量賦初值，僅在for語句運行開始時執(zhí)行一次；表達式2是for語句執(zhí)行的結(jié)束部分，與while的判斷表達式作用一致，用于設置for語句是否執(zhí)行循環(huán)體的判斷條件；表達式3常用于每次執(zhí)行循環(huán)體后改變循環(huán)變量值，以使for語句能趨向于結(jié)束。for語句的執(zhí)行流程圖如圖4.3所示。for語句的循環(huán)體可以是一條簡單語句，也可以是一個復合語句，甚至是一條空語句。for語句中的三個表達式均可省略，但應在其它相應位置有同等效用的功能實現(xiàn)。與while和do…while語句相比，for語句將循環(huán)變量賦初值、循環(huán)條件判斷、循環(huán)變量修改三個操作濃縮體現(xiàn)在一對小括號中，不僅適用于循環(huán)次數(shù)確定的情形，也適用于循環(huán)次數(shù)不確定的情形，使用起來更為方便靈活，因而是一種使用更為廣泛的循環(huán)控制語句。返回916:12例4.4：輸入一個正整數(shù)n，判定它是否為素數(shù)(prime，又稱質(zhì)數(shù))。輸入：一個正整數(shù)n。輸出：若n為質(zhì)數(shù)則輸出“Yes”，否則輸出“No”。#include<cstdio>#include<cmath>intmain(){ intn,i,k,flag=1; scanf("%d",&n); if(n==1)flag=0; k=sqrt(n); for(i=2;i<=k;i++) { if(n%i==0)flag=0; } if(flag==1)printf("Yes\n"); elseprintf("No\n"); return0;}1016:12

輸入：一個整數(shù)n。

輸出：1-2/3+3/5-4/7+5/9-6/11+...的前n項和。#include<cstdio>intmain(){ intn,i; doubleitem,num,deno,sum=0,flag=-1; scanf("%d",&n); for(i=1;i<=n;i++) { num=i; deno=2*i-1; flag=-flag; item=flag*num/deno; sum=sum+item; } printf("%.3lf",sum); return0;}1116:124．break/continue語句break語句和continue語句均用于改變循環(huán)執(zhí)行的狀態(tài)，但兩者的含義和執(zhí)行效用不同。break語句用于強制中斷所屬循環(huán)（若為for語句則表達式3也將不再運行）；continue語句用于跳過本次循環(huán)中還未運行的余下語句轉(zhuǎn)而開始下一輪循環(huán)判斷（若為for語句則執(zhí)行表達式3后再開始下一輪循環(huán)判斷）。返回1216:12例4.6：輸入一個正整數(shù)n，判定它是否為素數(shù)(prime，又稱質(zhì)數(shù))。輸入：一個正整數(shù)n。

輸出：若n為質(zhì)數(shù)則輸出“Yes”，否則輸出“No”。#include<iostream>#include<cmath>usingnamespacestd;intmain(){ intn,i;

cin>>n; intk=sqrt(n); for(i=2;i<=k;i++) if(n%i==0)break; if(n==1||i<=k)cout<<"No\n"; elsecout<<"Yes\n"; return0;}1316:12例4.7：輸出a到b之間的不能被3整除的整數(shù)。輸入：兩個正整數(shù)a、b。輸出：a到b之間的不能被3整除的整數(shù)。#include<iostream>usingnamespacestd;intmain(){ inta,b,i; cin>>a>>b; for(i=a;i<=b;i++){ if(i%3==0)continue; cout<<i<<""; }return0;}1416:125．多重循環(huán)循環(huán)語句的循環(huán)體內(nèi)又包含了另一循環(huán)語句，則稱為多重循環(huán)或循環(huán)的嵌套。例4.8：公雞五文一只，母雞三文一只，小雞一文三只，m文錢買m只雞，三種雞各買多少只？

輸入：m。輸出：公雞、母雞和小雞的只數(shù)(若有多個解則僅輸出字典序最小的解)。#include<iostream>usingnamespacestd;intmain(){ intm,x,y,z; cin>>m; for(x=0;x<=m/5;x++) for(y=0;y<=m/3;y++){ z=m-x-y; if(5*3*x+3*3*y+z==3*m){ cout<<x<<""<<y<<""<<z<<endl; return0; } }return0;}返回1516:12例4.9：求a到b之間存在多少個素數(shù)。輸入：兩個正整數(shù)a、b。輸出：a到b之間的全部素數(shù)的個數(shù)。#include<iostream>#include<cmath>usingnamespacestd;intmain(){ inta,b,i,j,k,ans=0; cin>>a>>b; for(i=a;i<=b;i++){

k=sqrt(i); for(j=2;j<=k;j++)

if(i%j==0)break; if(j>k)ans++; } cout<<ans<<endl;return0;}1616:12例4.10：公雞五文錢一只，母雞三文錢一只，小雞一文錢三只，用m文錢買m只雞，公雞、母雞、小雞各買多少只？輸入：一個正整數(shù)m。輸出：若有解只輸出一個解，即公雞數(shù)量最少的那個解；若無解輸出“Noanswer”。#include<iostream> //解法1usingnamespacestd;intmain(){ intm,i,j,k,noAnswer=1; cin>>m; for(i=0;i<=m/5;i++){ for(j=0;j<=m/3;j++){ k=m-i-j; if(i*15+j*9+k==m*3){ //找到一個解

cout<<i<<""<<j<<""<<k<<endl; //輸出解 noAnswer=0; //無解標志置0 break; //結(jié)束內(nèi)層循環(huán)，即j控制的循環(huán) } } if(noAnswer==0)break; //若已找到解，結(jié)束由i控制的循環(huán)

} if(noAnswer==1)cout<<"Noanswer"<<endl; return0;}1716:12#include<iostream> //解法2usingnamespacestd;intmain(){ intm,i,j,k,noAnswer=1; cin>>m; for(i=0;i<=m/5;i++){ for(j=0;j<=m/3;j++){ k=m-i-j; if(i*15+j*9+k==m*3) { //找到一個解

cout<<i<<""<<j<<""<<k<<endl; //輸出解 noAnswer=0; //無解標志置0 gotoloop; //使用goto語句直接跳轉(zhuǎn)到整個循環(huán)之后的語句 } } } loop:if(noAnswer==1)cout<<"Noanswer"<<endl; return0;}1816:126．算法執(zhí)行效率算法是對特定問題的解決方法的求解步驟描述，程序是依據(jù)算法思想采用某種編程語言書寫的具體代碼。一個算法具有有窮性、確定性、可行性、輸入、輸出5大特性。（1）有窮性：一個算法應在有限步驟之內(nèi)結(jié)束；（2）確定性：算法的每一步驟應清晰準確無歧義；（3）可行性：算法中的任何步驟均可分解為基本的可執(zhí)行操作；（4）輸入：一個算法有0個或多個輸入，以從外界獲取所需的必要信息；（5）輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工處理后的結(jié)果。一個好的算法應達到以下目標：（1）正確性：分為語法正確和邏輯正確兩個層面；（2）可讀性：便于人閱讀、有助于閱讀者對算法的理解；（3）健壯性：對任意非法輸入應該有合適的處理策略；（4）高效性：花費較少的時間代價和空間代價。返回1916:12

2016:12時間復雜度與執(zhí)行時間

時間復雜度計算所得數(shù)值限時1秒1000000游刃有余10000000勉勉強強100000000僅限循環(huán)體非常簡單的情況2116:12如何測量程序的運行時間？#include<time.h>#include<iostream>//#include<bits/stdc++.h>usingnamespacestd;intmain(){ inti,k=0; intn=1e8; clock_tstart,end; start=clock(); for(i=0;i<n;i++) k++; end=clock(); cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;}2216:12

#include<iostream>usingnamespacestd;intmain(){ intm,n; cin>>m>>n; intresult=1; while(n!=0){ if(n%2==1)result=result*m%1007; n=n/2; //等價于n>>=1; m=m*m%1007; } cout<<result<<endl;

return0;}2316:12例4.12：輸入一個正整數(shù)，輸出其位數(shù)（用while語句實現(xiàn)）。

輸入：一個正整數(shù)。

輸出：正整數(shù)的位數(shù)。#include<iostream>usingnamespacestd;intmain(){ intn,num=0; cin>>n; while(n>0) { n=n/10; num++; } cout<<num<<endl; return0;}2416:12例4.13：給定一個整數(shù)，請將該數(shù)各個數(shù)位上的數(shù)字反轉(zhuǎn)得到一個新數(shù)。新數(shù)也應滿足整數(shù)的常見形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應為零。

輸入：一個十進制整數(shù)。（-690）

輸出：對應的反轉(zhuǎn)數(shù)。（-96）#include<iostream>usingnamespacestd;intmain(){ intx,y=0; cin>>x; while(x!=0) { y=y*10+x%10; x=x/10; } cout<<y; return0;}2516:12例4.14：小明買了許多圣誕禮物準備用于班級活動，回家后感覺太累了，便讓機器人小靈幫忙數(shù)一下禮物一共有多少份。但是小靈不喜歡數(shù)字4，因此每次數(shù)到4時便跳過該數(shù)。例，若小靈數(shù)到639時，下一份禮物小靈就會數(shù)650。輸入：一個整數(shù)num，表示小靈給出的禮物的份數(shù)，1<num<1000，且一定不含整數(shù)4。

輸出：一個整數(shù)為禮物的實際份數(shù)。#include<iostream>usingnamespacestd;intmain(){ intnum,w=1,sum=0; cin>>num; while(num>0) { intb=num%10; if(b>4)b--; sum=sum+b*w; w=w*9; num=num/10; } cout<<sum<<endl; return0;}2616:12例4.15：分解質(zhì)因數(shù)。

輸入：一個正整數(shù)n。（36）

輸出：n的質(zhì)因數(shù)的乘積形式。（2*2*3*3）#include<iostream>usingnamespacestd;intmain(){ intn,i=2; cin>>n; while(n!=1) { while(n%i==0) { cout<<i; n=n/i; if(n!=1)cout<<"*"; } i++; } return0;}2716:12例4.16：輸入n和a，求a+aa+aaa+…aa…a(n個a)，如當n=3，a=2時，2+22+222=246。

輸入：包含兩個整數(shù)，n和a,含義如上述，n和a都是小于10的非負整數(shù)。

輸出：輸出前n項和，單獨占一行。#include<iostream>usingnamespacestd;intmain(){ intn,a,sum=0; cin>>n>>a; intitem=0; for(inti=1;i<=n;i++) { item=item*10+a; sum=sum+item; } cout<<sum<<endl; return0;}2816:12例4.17：媽媽給了小明m元零花錢，為了鼓勵小明節(jié)約，說如果小明每天只消費1元，每花k元就可以得到1元額外獎勵，如果聽媽媽的話小明最多可以花多少天？

輸入：輸入2個整數(shù)m、k（1<k<m<1000）。

輸出：輸出一個整數(shù)，表示m元可以消費的天數(shù)。#include<iostream>usingnamespacestd;intmain(){ intm,k; cin>>m>>k; intsum=0; while(m>=k) { sum=sum+(m–m%k); m=m/k+m%k; } sum=sum+m; cout<<sum<<endl;

return0;}2916:12例4.18：輸入一個正整數(shù)n。輸出n!的最高位上的數(shù)字。

輸入：輸入一個正整數(shù)n(n<=1000)。

輸出：輸出n!的最高位上的數(shù)字。#include<iostream>#include<cmath>usingnamespacestd;intmain(){ intn,i; doubles=0;

cin>>n; for(i=1;i<=n;i++) s=s+log10(i); s=s-int(s); s=pow(10,s);

cout<<int(s)<<endl;

return0;}3016:12例4.19：有一輛智能小車，最初(時間為0)的位置為(0,0)，我們想知道它最后的位置。小車以每小時10公里的速度向北移動(北為y軸正向，東為x軸正向)。小車會收到一系列依照時間戳記排序的命令，1表示“向左轉(zhuǎn)”，2表示“向右轉(zhuǎn)”，3表示“停止”。每個命令的前面有一個時間戳記，所以知道該命令是何時發(fā)出的。最后一個命令一定是“停止”。另外假設，這輛小車非常靈活，它可以在瞬間轉(zhuǎn)彎例，小車在時間為5時收到一個“向左轉(zhuǎn)”的命令1，在時間10收到一個“向右轉(zhuǎn)”的命令2，在時間15收到一個“停止”的命令3。那么在最后時間15時，小車的位置將在（-50,100）。程序只要求輸出小車最后的位置，第一個整數(shù)是x坐標，第二個整數(shù)是y坐標。輸入：輸入包含多個命令，每個命令由整數(shù)time和command組成，表示在時刻time發(fā)出命令command。command的取值范圍1-3，含義如上所述。輸出：輸出占一行，包含兩個整數(shù)，表示小車的最終位置。兩個整數(shù)之間由空格隔開。3116:12#include<iostream>usingnamespacestd;intmain(){ intx=0,y=0; intcommand; //存儲命令號 intpreTime=0,curTim