虽然计算机可以在短时间批量处理成千上万条指令,但是不少问题中有许多规律性的重复操作,比如说计算几百个学生的平均分,或者对上万人的名单进行排序。仅使用顺序或者分支结构,对每一步操作都写出对应的语句是不可能的;但可以使用循环语句让计算机反复执行类似的任务。

本章将会介绍循环结构程序设计,同时前面的内容也会进一步的巩固。学完这一章,读者可以初步感受到计算机高效解决问题的能力。

https://www.luogu.com.cn/training/102#problems

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;  
}