第二章

• 筆記
• aabb
• 階乘之和
• 水仙花數(shù)
• 韓信點(diǎn)兵
• 倒三角形
• 子序列的和
• 分?jǐn)?shù)化小數(shù)
• 排列
• 擴(kuò)展

筆記

1、函數(shù) double floor(double x) 向下取整，返回不超過x的最大整數(shù)；函數(shù) double ceil(double x) 向上取整，返回不小于x的最小整數(shù)。若給定的數(shù)為整數(shù)，則返回該整數(shù)。按理說返回的是整數(shù)，函數(shù)類型應(yīng)該是int ，但據(jù)codeblocks提示，函數(shù)類型為double 。頭文件 math.h
2、為減少浮點(diǎn)數(shù)運(yùn)算帶來的誤差，一般改成四舍五入，即floor(x+0.5)。
【floor(x)等于1的區(qū)間是[1,2)，而floor(x+0.5)等于1的區(qū)間為[0.5，1.5) 】
3、int 的取值范圍為-2147483648~2147483647【>10⁹，<10¹⁰】
?long long 的最大值：-9223372036854775808~9223372036854775807【>10¹⁸，<10¹⁹】
4、要計(jì)算只包含加法、減法和乘法的整數(shù)表達(dá)式除以正整數(shù)n的余數(shù)，可以在每步計(jì)算后對n取余，結(jié)果不變。
5、25！末尾有6個(gè)0

aabb

輸出所有形如aabb的4位完全平方數(shù)（即前兩位數(shù)字相等，后兩位數(shù)字也相等）。
【若一個(gè)數(shù)能表示成某個(gè)整數(shù)的平方的形式，則稱這個(gè)數(shù)為完全平方數(shù)】

//解法一： #include<bits/stdc++.h> using namespace std; int main() {for(int a=1;a<=9;a++)for(int b=0;b<=9;b++){int n=a*1100+b*11; //構(gòu)造aabb數(shù)int m=floor(sqrt(n)+0.5);　//減少浮點(diǎn)運(yùn)算帶來的誤差if(m*m==n) cout<<n<<endl;}return 0; }

也可以使用枚舉法，避免開平方操作

//解法二：枚舉 #include<bits/stdc++.h> using namespace std; int main() {int n;for(int x=1;n<=9999;x++){n=x*x;if(n<1000)continue;int a=n/100;int b=n%100;if(a/10==a%10&&b/10==b%10)printf("%d\n",n);}return 0; }

階乘之和

輸入n，計(jì)算s=1！+ 2！+ 3！+…+n！的末6位（不含前導(dǎo)0）。n<=10⁶，n！表示前n個(gè)正整數(shù)之積。
樣例輸入：
10
樣例輸出：
37913

#include<bits/stdc++.h> using namespace std; const int mod=1000000; int main() {int n,sum=0;cin>>n;for(int i=1;i<=n;i++){int factorial=1; for(int j=1;j<=i;j++){factorial=(factorial*j)%mod;}sum=(sum+factorial)%mod;}cout<<sum; }

25！的末尾有6個(gè)0，所以從第5項(xiàng)開始，后面的所有項(xiàng)都不會影響和的末6位數(shù)字，因此可以在程序中加一句 if（n>25）n=25；這樣就不存在溢出問題了。【在該程序中，當(dāng)n=25時(shí)，sum=940313】

水仙花數(shù)

輸出100~999中的所有水仙花數(shù)。若三位數(shù)ABC滿足ABC=A³+B³+C³，則稱其為水仙花數(shù)。例如：153=1³+5³+3³

#include<bits/stdc++.h> using namespace std; int main() {for(int i=00;i<=999;i++){int sum=0;for(int j=i;j!=0;j/=10){sum+=(j%10)*(j%10)*(j%10);//使用pow函數(shù)會出錯(cuò)}if(i==sum)cout<<i<<endl;} }

韓信點(diǎn)兵

題意：有n個(gè)士兵（10<=n<=100），3人一排余a人，5人一排余b人，7人一排余c人。問n等于多少？
輸入a，b，c的值；
輸出n的值。

樣例輸入：
2 1 6
2 1 3
樣例輸出：
41
No answer

//解法一：枚舉 #include<bits/stdc++.h> using namespace std; int main() {int a,b,c;while(cin>>a>>b>>c){int i=10;for(i=10; i<=100; i++){if(i%3==a&&i%5==b&&i%7==c){cout<<i<<endl;break;}}if(i==101)cout<<"NO answer"<<endl;} }

中國剩余定理：

在《孫子算經(jīng)》中有這樣一個(gè)問題：“今有物不知其數(shù)，三三數(shù)之剩二（除以3余2），五五數(shù)之剩三（除以5余3），七七數(shù)之剩二（除以7余2），問物幾何？”這個(gè)問題稱為“孫子問題”，該問題的一般解法國際上稱為“中國剩余定理”。具體解法分三步：

（1）找出三個(gè)數(shù)：從3和5的公倍數(shù)中找出除7余1的最小數(shù)15，從3和7的公倍數(shù)中找出除5余1 的最小數(shù)21，最后從5和7的公倍數(shù)中找出除3余1的最小數(shù)70。
（2）用15乘以2（2為最終結(jié)果除以7的余數(shù)），用21乘以3（3為最終結(jié)果除以5的余數(shù)），同理，用70乘以2（2為最終結(jié)果除以3的余數(shù)），然后把三個(gè)乘積相加15?2+21?3+70?2得到和233。
（3）用233除以3，5，7三個(gè)數(shù)的最小公倍數(shù)105，得到余數(shù)23，即233%105=23。這個(gè)余數(shù)23就是符合條件的最小數(shù)。

//解法2：剩余定理 //特征數(shù)：15 21 70 #include<bits/stdc++.h> using namespace std; int main() {int a,b,c,num;while(cin>>a>>b>>c) {num=(15*c+21*b+70*a)%105;if(num<=100&&num>=10)cout<<num<<endl;elsecout<<"No answer"<<endl;} }

倒三角形

題意：輸入n，輸出一個(gè)n層的倒三角形。

樣例輸入：
5
樣例輸出：

######################### #include<bits/stdc++.h> using namespace std; int main() {int n;cin>>n;for(int i=1;i<=n;i++){for(int k=1;k<=i-1;k++)//空格{cout<<" ";}for(int j=1;j<=2*n-1-2*(i-1);j++)//#號{cout<<"#";}cout<<endl;} }

子序列的和

題意：輸入兩個(gè)正整數(shù)n<m<10⁶，輸出1/n²+1/(n+1)²+…1/m²，保留5位小數(shù)。輸入包含多組數(shù)據(jù)，結(jié)束標(biāo)記為n=m=0。

樣例輸入：
2 4
65536 655360
樣例輸出：
Case 1：0.42361
Case 2：0.00001

#include<bits/stdc++.h> using namespace std; int main() {int n,m;int counter=0;while(cin>>n>>m&&(n+m)){counter++;double sum=0;for(int i=n;i<=m;i++){sum+=1.0/i/i; //此處使用sum+=1.0/(i*i)會溢出}printf("Case %d:%.5f\n",counter,sum);} }

分?jǐn)?shù)化小數(shù)

輸入正整數(shù)a,b,c，輸出a/b的小數(shù)形式，精確到小數(shù)點(diǎn)后c位。a，b<=10⁶，c<=100。輸入包含多組數(shù)據(jù)，結(jié)束標(biāo)記為a=b=c=0。
樣例輸入：
1 6 4
0 0 0
樣例輸出：
Case 1： 0.1667
因?yàn)閏<100，所以不能用double來存儲輸出結(jié)果

#include<bits/stdc++.h> using namespace std; void Div(int a, int b, int c) {int k, i;printf("%d.",a/b);//輸出整數(shù)部分跟小數(shù)點(diǎn)k = a;for(i = 0; i < c-1; i++){k = (k%b)*10;cout<<k/b;}k = (k%b)*10;if((k%b)*10/b >= 5)//四舍五入 cout<<k/b + 1<<endl;elsecout<<k/b<<endl; }int main() {int a, b, c;while(cin>>a>>b>>c&&(a||b||c)){Div(a, b, c);} }

排列

用1，2，3，…，9組成一個(gè)3位數(shù)abc，def，ghi，每個(gè)數(shù)字恰好使用一次，要求abc：def：ghi=1：2：3。按照“abc def ghi”的格式輸出所有解，每行一個(gè)解。

#include<bits/stdc++.h> using namespace std; int main() {int a[10];for(int i=123; i<=329; i++)//abc最小為123，最大為987/3==329{int sum=0;memset(a,0,sizeof(a));int j=2*i,k=3*i;//使用的數(shù)對應(yīng)位置為1，否則為0a[i/100]=a[(i%100)/10]=a[i%10]=1;a[j/100]=a[(j%100)/10]=a[j%10]=1;a[k/100]=a[(k%100)/10]=a[k%10]=1;for(int m=1; m<=9; m++)sum+=a[m];if(sum==9)//都使用過了一次cout<<i<<" "<<j<<" "<<k<<endl;}return 0; }

擴(kuò)展

1：中國剩余定理：POJ 1006–Biorhythms
2：求一個(gè)數(shù)的階乘末尾有多少個(gè)連續(xù)的零。【題解：點(diǎn)這里查看解析】
代碼：

#include<bits/stdc++.h> using namespace std; int main() {int n;cin>>n;int count = 0;while{n = n/5;if (n == 0) {break;} else {count += n;}}cout<<count<<endl; }

參考資料：
【1】博客：https://www.cnblogs.com/chichu-chen/p/10126864.html
【2】博客：中國剩余定理

總結(jié)

以上是生活随笔為你收集整理的第二章 循环结构程序设计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。