2022年C++常用算法歸納

1、_ C+ 常用算法歸納 一、基本算法 1、兩數(shù)交換借助第三數(shù) 例：任意讀入 2 個整數(shù),然后按從小到大的次序輸出這兩個數(shù)；【法 1】#include using namespace std; void main int a,b; cinab; ab.couta,b:coutb,a; 【法 2：讓 a 中放較小數(shù)、 b 中放較大數(shù)】#include using namespace std; void main int a,b; cinab; int t; / 中間變量 ab.t=a,a=b,b=t:a=a,b=b; couta,bendl; 精品資料_ 【算法說明： “t=a,a=b,b=t ”

2、,即可借助2、累加 例：求 1+2+3+ +100 的和；#include using namespace std; void main int s,i; s=0; i=1; whilei=100 s=s+i; i=i+1; cout1+2+.+100=s; t,將 a 和 b 的值交換；】【分析：出循環(huán)時,i 為 101 ,其最終一個合法取值（終值）為100 ；此題中 s 被稱為累加器,它以“ s=s+ ” 的形式顯現(xiàn)在循環(huán)中,該式被稱為累加式,累加器在進入循環(huán)前必需獲得合法初值,通常為0；i 是一個特別的累加器,每次遞增1,又稱為計數(shù)器；i 身兼二職：掌握循環(huán)的次數(shù),同時兼做累加式的通項；

3、】3、累乘精品資料_ 例. 求 10.；【分析： 10！=123 10 ,累乘器在進入循環(huán)前必需獲得合適初值；通常為 1；累乘式 格式“ C=C* ” 必需顯現(xiàn)在循環(huán)中；留意,不要讓累乘器溢出；】#include using namespace std; void main long C; int i; C=1; i=1; whilei=10 C=C*i; i+; coutCendl; 【摸索：能否將本程序稍做修改,分別輸出 1.10 ！】二、非數(shù)值運算常用經(jīng)典算法 1、窮舉法 對全部的可能性進行判定,凡是符合條件的做相應(yīng)處理（輸出、儲存等）；例：輸出全部的“ 水仙花” 數(shù),即這樣的三位正整數(shù)

4、：其每一數(shù)位上的數(shù)字的立方之和等于該精品資料_ 數(shù)本身；比如,153=13+53+33；【法一 :一重循環(huán) ,難點 :求出每位數(shù)字】#include using namespace std; void main int sxh; int b,s,g; forsxh=100;sxh=999;sxh+ b=sxh/100; s=sxh/10%10; g=sxh%10; ifb*b*b+s*s*s+g*g*g=sxh coutsxhendl; 【結(jié)論：任意一個正整數(shù)的個位數(shù)字,都可以用“ 該數(shù) %10 ” 求得！】【法二：三重循環(huán)】#include using namespace std; void

5、 main int b,s,g; forb=1;b=9;b+ /時針精品資料_ fors=0;s=9;s+ /分針forg=0;g=9;g+ /秒針ifb*b*b+s*s*s+g*g*g=b*100+s*10+g coutb*100+s*10+gendl; 【發(fā)覺：核心語句 if 被執(zhí)行了 900 次】2、正整數(shù)的各數(shù)位上數(shù)字的獵取例 1：任意讀入一個正整數(shù),依次輸出其低位到高位上的每一位數(shù)字；例 2：任意讀入一個整數(shù),依次輸出其低位到高位上的每一位數(shù)字及其符號位,但如是 0 不輸出符號位；3、迭代法例 1. 猴子吃桃問題；某猴子某天摘了如干只桃子,吃了一半,不過癮,又多吃一只；其次天又吃了一

6、半,不過癮,再多吃一只 到第十天,發(fā)覺只剩 多少只桃子；#include using namespace std; void main int peach,day; peach=1; 精品資料1 只桃子了；問第一天共摘了_ forday=9;day=1;day- peach=peach+1*2; cout 第一天的桃子數(shù) :peach; 【歸納：類似于此題peach 變量的特點：其值不停地被新值替代（自身的原值變化而來）,直到滿意所求終止； 】【問題：能否將上述程序稍作修改,輸出每一天的桃子數(shù)；】#include using namespace std; void main int peach

7、,day; peach=1; forday=9;day=1;day- peach=peach+1*2; cout 第day 天的桃子數(shù) :peachendl; 4、排序（1）冒泡排序法（起泡法）【算法要領(lǐng)： n 個數(shù)據(jù)最多處理n-1 趟,每一趟從頭到尾（或從尾到頭）兩兩相鄰的元素進行比較,升序排序時,如前者大后者小,就交換兩數(shù) ,每一趟比前一趟少比較一次；】例：任意讀入 10 個整數(shù),升序排列后輸出；精品資料_ #include using namespace std; void main const int N=10; int aN,i,j; fori=0;iai; /外循環(huán)處理 N-1 趟

8、,掌握趟數(shù) forj=1;j=N-1;j+ fori=0;iai+1 int t; t=ai;ai=ai+1;ai+1=t; fori=0;iN;i+ coutai ; （2）挑選法排序挑選法排序是相對好懂得的排序算法；假設(shè)要對含有驟是：n 個數(shù)的序列進行升序排列,算法步從數(shù)組存放的n 個數(shù)中找出最小數(shù)的下標（算法見下面的“ 求最值”）,然后將最小數(shù)與第1個數(shù)交換位置；精品資料_ 除第 1 個數(shù)以外,再從其余n-1 個數(shù)中找出最小數(shù)（即n 個數(shù)中的次小數(shù)）的下標,將此數(shù)與第 2 個數(shù)交換位置；重復步驟 n-1 趟,即可完成所求；例：任意讀入10 個數(shù),然后進行升序排列； 【主函數(shù)讀入、調(diào)用、輸

9、出；子函數(shù)排序；】#include using namespace std; void PXint *p,int n /【法 1：挑選法】int i,j,k,t; fori=0;i=n-2;i+ k=i; forj=i+1;j=n-1;j+ if*p+j*p+k k=j; ifk.=i t=*p+i;*p+i=*p+k;*p+k=t; void main int a10,i; fori=0;iai; PXa,10;/ 為增大子函數(shù)敏捷性,將元素個數(shù)傳過去 fori=0;i10;i+ 精品資料_ coutaiendl; /【法 2：以下冒泡法】#include #include using na

10、mespace std; void PXint *p,int n int i,j; int t; forj=1;j=n-1;j+ fori=0;i*p+i+1 t=*p+i;*p+i=*p+i+1; *p+i+1=t; void main int a10,i; fori=0;iai; PXa,10; fori=0;i10;i+ coutsetw4ai; 精品資料_ 5、查找：次序查找（線性查找）例：任意讀入10 個數(shù),查找其中有無9 這個數(shù)；#include using namespace std; void main const int N=10; int aN,i; fori=0;iai;

11、 fori=0;iN;i+/正常出口出來,i 為 N ifai=9break; ifiN cout 有endl; else cout 無endl; 【小技巧：定義一個規(guī)律量】#include using namespace std; void main const int N=10; 精品資料_ int aN,i; bool flag=false; /先假設(shè)無 fori=0;iai; fori=0;iN;i+/正常出口出來,i 為 N ifai=9flag=true;break; ifflag.=false cout 有endl; else cout 無endl; 【用 while 改寫】#i

12、nclude using namespace std; void main const int N=10; int aN,i; fori=0;iai; i=0; whilei=N-1&ai.=9i+; ifi=N-1 cout 有endl; 精品資料_ else cout 無endl; 6、判定素數(shù)（質(zhì)數(shù)）數(shù)學定義：“ 凡是只能被 1 和自身整除的大于 1 的整數(shù),就稱為質(zhì)數(shù),即素數(shù)；”【換句話,即“ 不能被 2 自身 -1整除”】例 1.任意讀入一個大于 1 的整數(shù),判定其是否為素數(shù)；【法一 : 緊扣數(shù)學定義】#include using namespace std; void main i

13、nt x; do cout1:n; cinx; whilex=1; int k; fork=2;k=x-1;k+ /窮舉的思維 ifx%k=0break; ifx=k /判定難點 coutx 是素數(shù) n; 精品資料_ else coutx 不是素數(shù) n; 【用一個小技巧：借助一個“ 規(guī)律型” 變量： “ 是素數(shù)時為 true ,否就為 false ”】#include using namespace std; void main int x; do cout1:n; cinx; whilex=1; int k; bool flag; flag=true; /第一假設(shè) x 是素數(shù)！fork=2;

14、k=x-1;k+ / 窮舉的思維 ifx%k=0 flag=false; break; ifflag=true coutx 是素數(shù) n; else coutx 不是素數(shù) n; 精品資料_ 【用 while 改寫】#include using namespace std; void main int x,k; cinx; k=2; whilex%k.=0k+; ifk=x coutx 是素數(shù) n; else coutx 不是素數(shù) n; 【變形一：用 sqrt 函數(shù),求平方根】#include #include using namespace std; void main int x,k; cin

15、x; bool flag=true; 精品資料_ fork=2;k=sqrtx;k+ ifx%k=0flag=false;break; ifflag=true coutx 是素數(shù) n; else coutx 不是素數(shù) n; 7、插入、刪除三、數(shù)值運算經(jīng)典算法：1、輾轉(zhuǎn)相除法求兩正整數(shù)的最大公約數(shù) 例：任意讀入 2 個正整數(shù),輸出其最大公約數(shù)；#include using namespace std; void main int x,y,r; do cout0 、y0:n; cinxy; while.x0&y0; r=x%y; 精品資料_ whiler.=0 x=y;y=r;r=x%y; cou

16、tyendl; 【改寫：用 do while 】#include using namespace std; void main int x,y,r; do cout0 、y0:n; cinxy; while.x0&y0; do r=x%y; x=y; y=r; whiler.=0; coutxendl; 2級數(shù)運算（綻開式的求解）精品資料_ 例 1、求 1+1/2.+1/3.+ +1/n.+ ,直到某項的值小于 10-6為止；【法一：直接法（略） 】【法二：間接法（遞推法）前項 /項次 =后項】#include using namespace std; void main float s,t;

17、 int i; / 表示項次 s=0; t=1; i=1; whilet=1e-6 s=s+t; i+; t=t/i; coutsendl; 例 2、讀入 0 x1 ,運算 x+x2+x3+ xn+ 直到某項的值小于 10-6為止；【法一：直接法：直接利用項次描述通項；】#include #include using namespace std; void main 精品資料_ float x,s,t; int i;/ 能用整數(shù),不用實數(shù) do cout0 xx; whilex=1|x=1e-6 s=s+ t; i+; t =powx,i; coutsendl; 3、間接法求通項 例 1、讀入

18、 0 x1 ,運算 x+x2+x3+ xn+ 直到某項的值小于 10-6為止；【法二：遞推法（間接法）求通項：利用前項求后項；】【分析：此題中如前一項值為 t,就后一項的值為 t*x 】#include 精品資料_ using namespace std; void main float x,s; do cout0 xx; whilex=1|x=1e-6 s=s+t; t=t*x; coutsendl; 例 2、求斐比利斯數(shù)列的前 20 項； 1、1、2、3、5、8、13 （制定前兩項,第三項開頭總是前兩項之和； ）【分析：此題只能有間接法（遞推法）#include using namespa

19、ce std; void main int f1,f2,f3; f1=f2=1; ,利用前 2 項求后 1 項；】精品資料_ coutf1 f2 ; int i; fori=3;i=20;i+ f3=f1+f2; f1=f2; f2=f3; coutf3 ; 例 3、編程輸出形如上圖的等腰三角形（行數(shù)敏捷讀入）；* * * * #include using namespace std; void main int h; cout=1h; int i=1,j;/ 用二重循環(huán)完成（循環(huán)的嵌套）whilei=h/ 外循環(huán)掌握行數(shù)精品資料_ forj=1;j=h-i;j+/ 第一個循環(huán)輸出每行的空格

20、cout ; forj=1;j=2*i-1;j+ / 其次個循環(huán)輸出每行的星號cout*; coutendl; i+; 4、矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置的算法要領(lǐng)是：n m 矩陣的相應(yīng)列；將一個 m 行 n 列矩陣（即 m n 矩陣） 的每一行轉(zhuǎn)置成另一個例、將以下23 矩陣轉(zhuǎn)置后輸出；1 4 即將1 2 3 轉(zhuǎn)置成4 5 6 2 5 3 6 #include #include using namespace std; void main int a23,b32,i,j,k=1; fori=0;i2;i+ 精品資料_ forj=0;j3;j+ aij=k+; /將 a 轉(zhuǎn)置到 b 中,窮舉 fori=0;i2;i+/ 以 a 為基準 forj=0;j3;j+ bji=aij; fori=0;i3;i+ forj=0;j2;j+ coutsetw3bij; coutendl; 5、楊輝三角形 楊輝三角形的每一行是 x+yn的綻開式各項的系數(shù)；例如第一行是