《算法竞赛入门经典》学习ing

第二章：循环结构程序设计

2.1 for循环

First：7744问题 输出所有形如aabb的四位完全平方数 分析：要求：

四位数完全平方数aabb型

方案一：（开方）

程序理念：ab两个变量，（1100a+b11）算出aabb后对其开平方得到c。对c进行取整得到，判断是否与开方值相等。

#include<stdio.h> #include<math.h> int main() { for(int a=1;a<=9;a++) { for(int b=1;b<=9;b++) { double c=sqrt(1100*a+b*11); if(c==floor(c)) printf("%d\n",(11*(a*100+b))); } } }

方案二：枚举法(避免开方） 程序思想：以x为变量进行平方，平方值在1000到9999的范围内逐一进行判断是否为aabb型。

#include<stdio.h> #include<math.h> int main() { for(int x=1;;x++) { int n=x*x; if(n<1000) continue; if(n>9999) break; int hi=n/100; int lo=n0; if(hi/10==hi&&lo/10==lo) //判断是否为aabb型 printf("%d\n",n); } return 0; }

2.2 while循环和do-while循环

1.while语句：while（）当型语句，当括号里的条件符合时，执行循环语句，否则跳出。 使用情况：

循环的循环次数不确定的情况下循环变量并非“递增”式循环

3n+1问题

3n+1问题：一个正整数x，如果是奇数就乘以3再加1，如果是偶数就析出偶数因数2ⁿ，这样经过若干个次数，最终回到1。 分析：

分类奇数，偶数奇数3n+1 偶数n/2输出循环次数 #include<stdio.h> int main() { long long n,count=0; scanf("%lld",&n); while(n>1) { if(n%2==1) n=n*3+1; else n/=2; count++; } printf("%lld\n",count); return 0; }

//注意int； long long；的范围。（乘法溢出）

2.do-while循环语句

（直到型）do{循环体}while{条件}： 达到条件后退出循环

例题2-3 近似计算

计算pi/4=1-1/3+1/5-1/7+······，直到最后一项小于10的-6次方 方案一：利用for语句

#include<stdio.h> #include<math.h> int main() { double sum=0; for(int i=0;;i++) { double term=1.0/(i*2+1); if(i%2==0) sum+=term; else sum-=term; if(term<1e-6) break; } printf("%.6f\n",sum); return 0; }

方案二：利用do-while语句

2.3 循环的代价

例题2-4 阶乘之和

输入n，计算S=1！+2！+3！+······+n！的末六位(不含前导0）。n<10^6,n<=106,n！表示前n个正整数之积。 程序1.0

#include<stdio.h> int main() { int n,s=0; scanf("%d",&n); for(int i=1;i<=n;i++) { int factrail=1; for(int j=1;j<=i;j++) factrail*=j; s+=factrail; } printf("%d",s00000); return 0; }

（漏洞）：乘法溢出 程序2.0

#include<stdio.h> #include<time.h> int main() { int n,s=0; scanf("%d",&n); int MOD=1000000; for(int i=1;i<=n;i++) { int factrail=1; for(int j=1;j<=i;j++) factrail=factrail*j%MOD; s=(s+factrail)%MOD; } printf("%d",s); printf("Time used=%.2f\n,(double)clock()/CLOCKS_PES_SEC"); return 0; }