虽然计算机可以在短时间批量处理成千上万条指令，但是不少问题中有许多规律性的重复操作，比如说计算几百个学生的平均分，或者对上万人的名单进行排序。仅使用顺序或者分支结构，对每一步操作都写出对应的语句是不可能的；但可以使用循环语句让计算机反复执行类似的任务。
本章将会介绍循环结构程序设计，同时前面的内容也会进一步的巩固。学完这一章，读者可以初步感受到计算机高效解决问题的能力。
P5718 【深基4.例2】找最小值
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main(void)
{
int n; cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cout<<a[0];
return 0;
}
P5719 【深基4.例3】分类平均
#include<bits/stdc++.h>
using namespace std;
int sum1,sum2,cnt1,cnt2;
int main(void)
{
int n,k; cin>>n>>k;
for(int i=1;i<=n;i++)
{
if(i%k==0) sum1+=i,cnt1++;
else sum2+=i,cnt2++;
}
printf("%.1lf %.1lf",1.0*sum1/cnt1,1.0*sum2/cnt2);
return 0;
}
P5720 【深基4.例4】一尺之棰
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n,cnt=1; cin>>n;
while(n!=1) n/=2,cnt++;
cout<<cnt;
}
P5721 【深基4.例6】数字直角三角形
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n,cnt=1; cin>>n;
for(int i=n;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
printf("%02d",cnt++);
}
puts("");
}
return 0;
}
P1009 [NOIP1998 普及组] 阶乘之和
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>A,ans;
vector<int> add(vector<int> A,vector<int> B)
{
int t=0;
vector<int>C;
for(int i=0;i<A.size()||i<B.size();i++)
{
if(i<A.size()) t+=A[i];
if(i<B.size()) t+=B[i];
C.push_back(t%10);
t=t/10;
}
if(t) C.push_back(1);
return C;
}
vector<int> mul(vector<int> A,int b)
{
vector<int>C;
int t=0;
for(int i=0;i<A.size()||t;i++)
{
if(i<A.size()) t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
return C;
}
int main(void)
{
cin>>n;
ans.push_back(0);
A.push_back(1);
for(int i=1;i<=n;i++)
{
A=mul(A,i);
ans=add(ans,A);
}
for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
return 0;
}
P1980 [NOIP2013 普及组] 计数问题
#include<bits/stdc++.h>
using namespace std;
int n,x,cnt;
int main(void)
{
cin>>n>>x;
for(int i=1;i<=n;i++)
{
int k=i;
while(k)
{
if(k%10==x) cnt++;
k/=10;
}
}
cout<<cnt;
return 0;
}
P1035 [NOIP2002 普及组] 级数求和
#include<bits/stdc++.h>
using namespace std;
int n;
int main(void)
{
double sum=0;
cin>>n;
for(int i=1;i<=10000000;i++)
{
sum+=1.0/i;
if(sum>n)
{
cout<<i;
break;
}
}
return 0;
}
P2669 [NOIP2015 普及组] 金币
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n; cin>>n;
int sum=0,k=1,cnt=0;
while(cnt+1<=n)
{
for(int i=1;i<=k&&(cnt+1)<=n;i++) sum+=k,cnt++;
k++;
}
cout<<sum;
return 0;
}
P5722 【深基4.例11】数列求和
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n; cin>>n;
int sum=0;
for(int i=1;i<=n;i++) sum+=i;
cout<<sum;
return 0;
}
P5723 【深基4.例13】质数口袋
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int st[N],prime[N],cnt;
int n;
void solve(int n)
{
int sum=0;
for(int i=2;i<=N;i++)
{
if(!st[i])
{
prime[cnt++]=i;
if( (sum+i) > n ) return;
else sum+=i;
}
for(int j=0;prime[j]<=N/i;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main(void)
{
cin>>n;
solve(n);
for(int i=0;i<cnt-1;i++) cout<<prime[i]<<endl;
cout<<cnt-1<<endl;
return 0;
}
P1217 [USACO1.5]回文质数 Prime Palindromes
- 先线性筛筛出所有的质数，然后枚举质数判断即可。
注意: 打表到1e7即可，首先1e9一定不可以。故最大到99999999，因为[1e7-99999999],这些数是8位的数是偶数位的数一定可以被11整除。
故一定一个都没有，所以只需枚举到1e7即可。
性质:偶数位的回文数一定被11整除，这里除了11是质数外，其他所有的偶数位的回文数一定不是质数
能被11整除的数的性质：奇数位的数字之和 减 偶数位的数字之和能被11整除。
这里以4位的回文数为例:
设abcd
a = d
b = c
a + c = d + c
b + d = c + d
故： a+c = b+d
故一定可以被11整除。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int M=1e7+10;
int prime[N],cnt,l,r;
bool st[M];
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
st[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int check(int x)
{
if(x<l||x>r) return 0;
string s=to_string(x);
for(int i=0;i<s.size()/2;i++)
if(s[i]!=s[s.size()-1-i]) return 0;
return 1;
}
int main(void)
{
init(1e7);
cin>>l>>r;
for(int i=0;i<cnt;i++)
if(check(prime[i])) cout<<prime[i]<<endl;
return 0;
}
P1423 小玉在游泳
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
double n; cin>>n;
double sum=0,step=2;
int cnt=0;
while(sum<n) sum+=step,step*=0.98,cnt++;
cout<<cnt;
return 0;
}
P1307 [NOIP2011 普及组] 数字反转
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
string s; cin>>s;
if(s[0]=='-') cout<<s[0],s=s.substr(1);
reverse(s.begin(),s.end());
while(s.size()>1&&s[0]=='0') s=s.substr(1);
cout<<s;
return 0;
}
P1720 月落乌啼算钱（斐波那契数列）
#include<bits/stdc++.h>
using namespace std;
int n;
double solve(int n)
{
double sum1=1,sum2=1;
for(int i=1;i<=n;i++) sum1*=(1+sqrt(5))/2;
for(int i=1;i<=n;i++) sum2*=(1-sqrt(5))/2;
return (sum1-sum2)/sqrt(5);
}
int main(void)
{
cin>>n;
printf("%.2lf",solve(n));
return 0;
}
P5724 【深基4.习5】求极差 / 最大跨度值
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cout<<a[n-1]-a[0];
return 0;
}
P1420 最长连号
#include<bits/stdc++.h>
using namespace std;
int n,x,s[100010];
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
int ans=1;
for(int i=0;i<n;i++)
{
int temp=1;
for(int j=i+1;j<n;j++)
{
if((s[j]-s[j-1])==1) temp++;
else break;
}
ans=max(ans,temp);
}
cout<<ans;
return 0;
}
P1075 [NOIP2012 普及组] 质因数分解
#include<bits/stdc++.h>
using namespace std;
int check(int x)
{
for(int i=2;i<=x/i;i++) if(x%i==0) return 0;
return 1;
}
int main(void)
{
int n; cin>>n;
for(int i=2;i<=n/i;i++)
{
if(n%i==0&&check(i)&&check(n/i))
{
cout<<n/i;
return 0;
}
}
return 0;
}
P5725 【深基4.习8】求三角形
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n; cin>>n;
int k=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) printf("%02d",k++);
puts("");
}
k=1;
puts("");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n-i;j++) cout<<" ";
for(int j=1;j<=i;j++) printf("%02d",k++);
puts("");
}
return 0;
}
P5726 【深基4.习9】打分
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n,sum;
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
sort(a,a+n);
sum-=a[0],sum-=a[n-1];
printf("%.2lf",1.0*sum/(n-2));
return 0;
}
P4956 [COCI2017-2018#6] Davor
#include<bits/stdc++.h>
using namespace std;
int n;
int main(void)
{
cin>>n;
for(int i=100;i>=0;i--)
{
for(int j=1;j<=100000;j++)
{
int sum=7*i+7*6/2*j;
sum=sum*52;
if(sum==n)
{
cout<<i<<endl;
cout<<j<<endl;
return 0;
}
}
}
return 0;
}
P1089 [NOIP2004 提高组] 津津的储蓄计划
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int s1=0,s2=0;
for(int i=1;i<=12;i++)
{
int x; cin>>x;
s2+=300,s2-=x;
if(s2<0)
{
printf("-%d\n",i);
return 0;
}
s1=s1+s2/100*100;
s2=s2%100;
}
cout<<s1*1.2+s2;
return 0;
}
