欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

第2章 循环结构程序设计——算法竞赛入门经典

程序员文章站 2022-06-02 12:12:24
...

前言：循环结构程序设计中最常见的两个问题：算术运算溢出和程序效率低下。

目录

例题2-1：7744问题——如何判断n是否为完全平方数（P20）

例题2-2:3n+1问题——注意不要溢出，int范围2e9+    (P22)

例题2-3:近似计算  (P24)

例题2-4：阶乘之和 （P25）

例题2-5 数据统计 （P27）

1.在Windows下，输入完毕后先按Enter键，再按Ctrl+Z键，最后再按Enter键，即可结束输入。

 2.重定向版 一年前写的

3.fopen版 

例题2-6：数据统计II

习题 2-1：水仙花数

习题 2-2：韩信点兵

习题 2-3：倒三角形

习题 2-4：子序列的和

习题 2-5： 分数化小数

习题 2-6 ：排列

思考题（精度问题）

 

例题2-1：7744问题——如何判断n是否为完全平方数（P20）

（1）用整数m存储sqrt(n)四舍五入(考虑到浮点误差，所以一般要四舍五入)后的整数，判断m*m==n?

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
    int n,m;
    for(int i=1;i<=9;i++){
        for(int j=0;j<=9;j++){
            n=i*1100+j*11;
            m=floor(sqrt(n)+0.5);  //考虑到浮点误差，所以四舍五入。floor(x)返回不超过x的最大整数
            if(n==m*m)
                printf("%d\n",n);
        }
    }
    return 0;
}

（2）枚举平方根x，从而避免平方操作。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
    int n;
    for(int x=30;;x++){
       n=x*x;
       if(n<1000) continue;
       if(n>=10000) break;
 
       if(n/1000==n/100%10&&n%100/10==n%10)  // %、/的优先级一样
           printf("%d\n",n);
    }
    return 0;
}

例题2-2:3n+1问题——注意不要溢出，int范围2e9+    (P22)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;

int main(){
    ll n;
    scanf("%lld",&n);
    ll cnt=0;
    while(n!=1){
        if(n&1) n=3*n+1;
        else n/=2;
        cnt++;
        //cout<<cnt<<" "<<n<<endl;
    }
    printf("%lld\n",cnt);
    return 0;
}

例题2-3:近似计算  (P24)

一年前做的

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-6;

int main(){
    double sum=0,tmp;
    int i=0,t=1;
    do{
        tmp=1.0/(2*i+1);
        sum+=t*tmp;
        t*=-1;
        i++;
    }while(tmp>=eps);
    printf("%.6f\n",sum);
    return 0;
}
//输出：0.785399
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-6;

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<eps) break;
    }
    printf("%.6f\n",sum);
    return 0;
}

例题2-4：阶乘之和 （P25）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
const int mod=1e6;
typedef long long ll;

int main(){
    int n;
    scanf("%d",&n);
    ll sum=0,tmp=1;
    for(int i=1;i<=n;i++){
        tmp*=i;
        tmp%=mod;
        sum+=tmp;
        sum%=mod;

    }
    printf("%lld\n",sum);
   // printf("Time used=%.3f\n",(double)clock()/CLOCKS_PER_SEC); //计时函数以秒为单位
    return 0;
}

从40开始，答案始终不变。因为25！末尾有6个0，所以从第五项开始，后面的所有项都不会影响和的末6位数字。

所以可以在程序前面加个判断，如果n超过25，就将n赋值为25。 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
const int mod=1e6;
typedef long long ll;

int main(){
    int n;
    scanf("%d",&n);
    if(n>25) n=25;
    ll sum=0;
    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;
    }
    printf("%lld\n",sum);
   // printf("Time used=%.3f\n",(double)clock()/CLOCKS_PER_SEC); //计时函数以秒为单位
    return 0;
}

例题2-5 数据统计 （P27）

1.在Windows下，输入完毕后先按Enter键，再按Ctrl+Z键，最后再按Enter键，即可结束输入。

第2章 循环结构程序设计——算法竞赛入门经典

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
const int mod=1e6;
typedef long long ll;

int main(){
    double sum;
    int n,mx,mn,cnt=0;
    while(cin>>n){
        if(cnt==0){
            mx=n,mn=n;
        }else{
            mx=max(mx,n);
            mn=min(mn,n);
        }
        sum+=n;
        cnt++;
    }

    printf("max=%d,min=%d,avr=%.3f\n",mx,mn,sum/cnt);

    return 0;
}

 2.重定向版 一年前写的 

#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int INF=1e9;

int main(){
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif // LOCAL
    double sum;
    int n,mx,mn,cnt=0;
    while(cin>>n){
        if(cnt==0){
            mx=n,mn=n;
        }else{
            mx=max(mx,n);
            mn=min(mn,n);
        }
        sum+=n;
        cnt++;
    }

    printf("max=%d,min=%d,avr=%.3f\n",mx,mn,sum/cnt);

    return 0;
}

第2章 循环结构程序设计——算法竞赛入门经典

注意：in.txt、out.txt这两个文件和程序要在同一文件目录中。输入输出都在文本中进行。 

如果比赛要求标准输入输出，只需在提交之前删除#define LOCAL即可。

3.fopen版 

没实现TT

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int INF=1e9;

int main(){
    FILE *fin,*fout;
    fin=fopen("in.txt","rb");
    fout=fopen("out.txt","rw");
    double sum;
    int n,mx,mn,cnt=0;
    while(fscanf(fin,"%d",&n)==1){
        if(cnt==0){
            mx=n,mn=n;
        }else{
            mx=max(mx,n);
            mn=min(mn,n);
        }
        sum+=n;
        cnt++;
    }

    fprintf(fout,"max=%d,min=%d,avr=%.3f\n",mx,mn,sum/cnt);
    fclose(fin);
    fclose(fout);

    return 0;
}

 

例题2-6：数据统计II

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long ll;

int main(){
    double sum;
    int n,mx,mn,a,kase=0;
    while(~scanf("%d",&n)){
        if(n==0) break;
        sum=0;
        for(int i=0;i<n;i++){
             scanf("%d",&a);
             if(i==0){
                mx=a,mn=a;
            }else{
                mx=max(mx,a);
                mn=min(mn,a);
            }
            sum+=a;
        }
        printf("Case %d: %d %d %.3f\n",++kase,mx,mn,sum/n);
    }

    return 0;
}

习题 2-1：水仙花数

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long ll;

int main(){
    int a,b,c;
    for(int i=100;i<=999;i++){
        a=i/100;
        b=i%100/10;
        c=i%10;
        if(i==a*a*a+b*b*b+c*c*c) printf("%d\n",i);
    }
    return 0;
}

第2章 循环结构程序设计——算法竞赛入门经典

 

习题 2-2：韩信点兵

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long ll;

int main(){
    int a,b,c,kase=0;
    while(cin>>a>>b>>c){
        bool flag=false;
        for(int i=10;i<=100;i++){
            if(i%3==a&&i%5==b&&i%7==c){
                printf("Case %d: %d\n",++kase,i);
                flag=true;
                break;
            }
        }
        if(!flag) printf("Case %d: NO answer\n",++kase);
    }
    return 0;
}

习题 2-3：倒三角形

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long ll;

int main(){
    int n;
    scanf("%d",&n);
    for(int i=n;i>0;i--){
        for(int j=0;j<n-i;j++){
            printf(" ");
        }
        for(int j=0;j<2*i-1;j++)
            printf("#");
        printf("\n");
    }
    return 0;
}

习题 2-4：子序列的和

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long ll;

int main(){
    ll n,m;
    double sum=0;
    while(~scanf("%lld%lld",&n,&m)){
        if(n==0&&m==0)
            break;
        //以下两种方式都可以防止算术运算溢出
        /*for(ll i=n;i<=m;i++){    
            sum+=1.0/(i*i);
        }*/
        for(int i=n;i<=m;i++){
            sum+=1.0/i/i;
        }
        printf("%.5f\n",sum);
    }
    return 0;
}

习题 2-5： 分数化小数

#include<iostream>
#include<cstdio>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long ll;

int main(){
    int a,b,c,kase=0;
    while(cin>>a>>b>>c){
        if(a==0&&b==0&&c==0) break;
        double res=1.0*a/b;
        printf("Case %d: %.*f\n",++kase,c,res);   //注意*的用法
    }
    return 0;
}

习题 2-6 ：排列

不太动脑筋想到的是九重循环。不写了。

思考题（精度问题）

相关标签： 算法竞赛入门经典

上一篇： ajax+php控制所有后台函数调用_PHP

下一篇： Codeforces Round #491 (Div. 2)---B

推荐阅读