SDKD上半学期oj部分习题总结

半学期已过，总结上半学期部分Oj中的卡题点。

1、筛选素数

分析：一道要求用筛法解决的素性判断

最初的考量是先将题目要求的范围内全部素数找出并存入数组待用。同样采用筛法思想，但结果显然会Time Limited。

#include<stdio.h>
int main()
{
    int a[50000];
    a[0]=2;
    int len=1,i,j,m,n,f=1;
    for(i=3; i<500000; i+=2)
    {
        for(j=0; j<len; j++)
        {
            if(i%a[j]==0)
            {
                f=0;
                break;
            }
        }
        if(f==1)
            {
                a[len]=i;
                len++;
            }
            f=1;
    }
    while(scanf("%d%d",&m,&n)!=EOF)
    {
            for(j=0;a[j]<=n;j++)
            {
                if(a[j]>=m&&a[j]<=n)
            {
                printf("%d\n",a[j]);
                f=0;
            }

            }
            if(f==1)
            printf("\n");
            printf("\n");

    }


}

接下来AC的代码体现了筛法的优越性，判断素数的同时判断后面数据中的合数，数据越大效果越明显。

#include<stdio.h>
#include <string.h>

int main()
{
    int a[500001];
    int i,j,m,n,f=0;
    memset(a,1,sizeof(a));
    a[1]=0;
    a[0]=0;
    for(i=2; i<500000; i++)
    {
        if(a[i]==0)
            continue;
        for(j=2; i*j<=500000 ; j++)
        {
            a[j*i]=0;
        }
    }
    scanf("%d%d",&m,&n);
    for(j=m; j<=n; j++)
    {
        if(a[j])
        {
            f=1;
            printf("%d\n",j);
        }

    }
    if(f==0)
        printf("\n");
    f=0;
    while(printf("\n")!=0&&scanf("%d%d",&m,&n)!=EOF)
    {

        for(j=m; j<=n; j++)
        {
            if(a[j])
            {
                f=1;
                printf("%d\n",j);
            }

        }
        if(f==0)
            printf("\n");
        f=0;
    }
    return 0;

}

下一步目标：

尝试用费马小定理编写素性判断。

2、Sequence Problem (III) : Array Practice

分析：

在前面两道同类题的基础上修改的题，但其实用函数和二维数组可以少考虑很多步骤。

#include<stdio.h>
int main()
{
    int a[1001]= {0},b[1001]= {0},i,len=0,N,j,n;
    scanf("%d",&N);
    for(j=1; j<=N; j++)
    {
        scanf("%d",&n);
        if(j%2==1)
        {
            for(i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            if(n>len)
                len=n;
        }
        else
        {
            for(i=0; i<n; i++)
            {
                scanf("%d",&b[i]);
            }
            if(n>len)
                len=n;

        }
        if(a[0]==0&&b[0]==0&&j!=1)
        {
            printf("\n");
            n=0;
        }
        else
        {
            if(j>=2)
            {
                for(i=0; i<len-1; i++)
                {
                    printf("%d ",a[i]+b[i]);
                    if(j%2==1)
                        b[i]=0;
                    else
                        a[i]=0;
                }
                if(len!=0)
                {
                    printf("%d\n",a[i]+b[i]);
                    if(j%2==1)
                        b[i]=0;
                    else
                        a[i]=0;
                }
                len=n;
                if(a[0]==0&&b[0]==0)
                {
                    n=0;//新输入的一组为0，且上一组也已归0时，n里存放的值不再具有实际意义，舍去。
                    len=0;
                }
            }
        }

    }

    for(i=0; i<n-1; i++)
    {
        printf("%d ",j%2==1?b[i]:a[i]);
    }
    if(len!=0)
    {
        printf("%d\n",j%2==1?b[i]:a[i]);

    }
    else
    {
        printf("\n");
    }

    return 0;

}

下一步目标：

用二维数组和函数缩减代码行数。

3、汉诺塔

分析：经典递归

#include<stdio.h>
#include<stdlib.h>
void hanuo(int n,int l,int r,int m)
{
    if(n==0);
    else
    {
        hanuo(n-1,l,m,r);
        printf("\n   plate %d : from %d to %d",n,l,r);
        hanuo(n-1,m,r,l);
    }
}
int main()
{
    int n,l,r,m,i=2;
    scanf("%d%d%d%d",&n,&l,&m,&r);
    printf("case 1 :");
    hanuo(n,l,r,m);
    while(printf("\n\n")!=0&&scanf("%d%d%d%d",&n,&l,&m,&r)!=EOF)
    {
        printf("case %d :",i);
        hanuo(n,l,r,m);
        i++;
    }
}

4、百钱买百鸡

分析：

题目要求的时间只支持一重循环，需要通过关系式推导表示另外两个变量。注意小鸡个数不一定能被d整除。
下面贴一下AC的代码。

#include<stdio.h>
#include<stdlib.h>
int main()
{
  int a,b,c,d,m,n,i,j,k,flag=1,side;
  scanf("COCK,HEN,CHICK,MONEY,CHICKS\n");
  while(scanf("%d,%d,%d/%d,%d,%d",&a,&b,&c,&d,&m,&n)!=EOF)
  {

      side=n<m/a?n:m/a;
      for(i=0;i<=side;i++)
      {
          k=d*(m-b*n+b*i-a*i)/(c-b*d);
          j=n-i-k;
          if(d*(m-b*n+b*i-a*i)%(c-b*d)==0&&i>=0&&j>=0&&k>=0&&flag==1)
          {
            flag=0;
            printf("COCKS,HENS,CHICKS\n");
          }
          if(d*(m-b*n+b*i-a*i)%(c-b*d)==0&&i>=0&&j>=0&&k>=0&&flag==0)
            printf("%d,%d,%d\n",i,j,k);
      }
      if(flag==1)
        printf("Cannot buy!\n");
        printf("\n");
        flag=1;
  }
  return 0;
}

虽然AC了，但是题目要求“输入一整张表再判断”，所以又写了一个读入完整表再输出的。

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int e[10000];
    int a,b,c,d,m,n,i,j,k,flag=1,side,hh=0,nn;
    scanf("COCK,HEN,CHICK,MONEY,CHICKS");
    while(scanf("%d,%d,%d/%d,%d,%d",&e[hh],&e[hh+1],&e[hh+2],&e[hh+3],&e[hh+4],&e[hh+5])!=EOF)
    {
        hh+=6;
    }
    for(nn=0; nn<hh; nn+=6)
    {
        a=e[nn];
        b=e[nn+1];
        c=e[nn+2];
        d=e[nn+3];
        m=e[nn+4];
        n=e[nn+5];
        side=n<m/a?n:m/a;
        for(i=0; i<=side; i++)
        {
            k=d*(m-b*n+b*i-a*i)/(c-b*d);
            j=n-i-k;
            if((d*(m-b*n+b*i-a*i)%(c-b*d)==0)&&(i>=0)&&(j>=0)&&(k>=0)&&(flag==1))
            {
                flag=0;
                printf("COCKS,HENS,CHICKS\n");
            }
            if((d*(m-b*n+b*i-a*i)%(c-b*d)==0)&&(i>=0)&&(j>=0)&&(k>=0)&&(flag==0))
                printf("%d,%d,%d\n",i,j,k);
        }
        if(flag==1)
            printf("Cannot buy!\n");
        printf("\n");
        flag=1;
    }
    return 0;
}

5、求一元二次方程

分析：输出繁琐，且有双精度变量的精确度问题

在不考虑精度问题时，示例“-5 2 -0.2”结果：
two imaginary roots : 0.2+1.49012e-009i, 0.2-1.49012e-009i
代码如下：

#include <stdio.h>
#include <math.h>
int main()
{
    double a,b,c,delta,x1,x2,x3;
    int i=1;
    while(scanf("%lf",&a)&&a!=0)
    {
        scanf("%lf%lf",&b,&c);
        delta=b*b-4*a*c;
        if(a<0)
        {
            a=-a;
            b=-b;
            c=-c;
        }
        printf("Case %d :\n",i);
        if(a==1)
            printf("x^2 ");
        else
            printf("%gx^2 ",a);
        if(b==1)
            printf("+ x ");
        else if(b==-1)
            printf("- x ");
        else if(b==0);
        else
            printf("%c %gx ",b>0?'+':'-',fabs(b));
        if(c!=0)
            printf("%c %g ",c>0?'+':'-',fabs(c));
        printf("= 0\n");
        if(delta>0)
        {
            x1=(-b-sqrt(delta))/(2*a);
            x2=(-b+sqrt(delta))/(2*a);
            printf("two real roots : %g, %g\n",x1,x2);
        }
        else if(delta==0)
        {
            x1=-b/(2*a);
            printf("only one real root : ");
            printf("%g\n",x1);
        }
        else
        {
            x1=(-b)/(2*a);
            x3=sqrt(fabs(delta))/(2*a);
            printf("two imaginary roots : ");
            if(x1!=0)
            {
                printf("%g",x1);
                if(x3==1)
                    printf("+i");
                else if(x3==0);
                else
                    printf("+%gi",x3);
            }
            else
            {
                if(x3==1)
                    printf("i");
                else if(x3==0);
                else
                    printf("%gi",x3);

            }
            printf(", ");
            if(x1!=0)
                printf("%g",x1);

            if(x3!=1)
                printf("-%gi\n",x3);
            else if(x3==0);
            else
                printf("-i\n");
        }
        printf("\n");
        i++;
    }
    return 0;
}

为何会出现这样的问题呢？我们不妨单独求一下该示例的Δ

#include<stdio.h>
int main()
{
    double a=-5,b=2,c=-0.2;
    printf("%g",b*b-4*a*c);
}

结果如下：

结果不是0！
查阅资料后在网站http://www.mamicode.com/info-detail-857022.html中找到了答案：
The difference between 1 and the smallest value greater than 1
for double objects is: 2.22045e-016
该数值是双精度数的1和大于1的差。由此确认是精度问题。
同时，发现如果把Δ的计算拆分为两数bb和4a*c相减，可以得到正确结果。
代码如下：

#include<stdio.h>
int main()
{
    double a=-5,b=2,c=-0.2,dee,ltt;
    dee=b*b;
    ltt=4*a*c;
    printf("%g",dee-ltt);
}

结果：

于是我提交了第二次的代码，试图通过拆分Δ跳过精度问题，但是答案仍然有错误。第二次代码：

#include <stdio.h>
#include <math.h>
int main()
{
    double a,b,c,x1,x2,x3,dee,ltt;
    int i=1;
    while(scanf("%lf",&a)&&a!=0)
    {
        scanf("%lf%lf",&b,&c);

        dee=b*b;
        ltt=4*a*c;	//拆分，跳过精度判断
        if(a<0)
        {
            a=-a;
            b=-b;
            c=-c;
        }
        printf("Case %d :\n",i);
        if(a==1)
            printf("x^2 ");
        else
            printf("%gx^2 ",a);
        if(b==1)
            printf("+ x ");
        else if(b==-1)
            printf("- x ");
        else if(b==0);
        else
            printf("%c %gx ",b>0?'+':'-',fabs(b));
        if(c!=0)
            printf("%c %g ",c>0?'+':'-',fabs(c));
        printf("= 0\n");
        if(dee-ltt>0)
        {
            x1=(-b-sqrt(dee-ltt))/(2*a);
            x2=(-b+sqrt(dee-ltt))/(2*a);
            printf("two real roots : %g, %g\n",x1,x2);
        }
        else if(dee-ltt==0&&dee-ltt==-0)
        {
            x1=-b/(2*a);
            printf("only one real root : ");
            printf("%g\n",x1);
        }
        else
        {
            x1=(-b)/(2*a);
            x3=sqrt(fabs(dee-ltt))/(2*a);
            printf("two imaginary roots : ");
            if(x1!=0)
            {
                printf("%g",x1);
                if(x3==1)
                    printf("+i");
                else if(x3==0);
                else
                    printf("+%gi",x3);
            }
            else
            {
                if(x3==1)
                    printf("i");
                else if(x3==0);
                else
                    printf("%gi",x3);

            }
            printf(", ");
            if(x1!=0)
                printf("%g",x1);

            if(x3!=1)
                printf("-%gi\n",x3);
            else if(x3==0);
            else
                printf("-i\n");
        }
        printf("\n");
        i++;
    }
    return 0;
}

假设Δ判断已经不存在问题，考虑输出的值仍存在精度问题，将绝对值小于1e-6的计算值全部视为0，结果AC。
最后AC的答案：

#include <stdio.h>
#include <math.h>
int main()
{
    double a,b,c,x1,x2,x3,dee,ltt;
    int i=1;
    while(scanf("%lf",&a)&&a!=0)
    {
        scanf("%lf%lf",&b,&c);

        dee=b*b;
        ltt=4*a*c;	//拆分，跳过精度判断
        if(a<0)
        {
            a=-a;
            b=-b;
            c=-c;
        }
        printf("Case %d :\n",i);
        if(a==1)
            printf("x^2 ");
        else
            printf("%gx^2 ",a);
        if(b==1)
            printf("+ x ");
        else if(b==-1)
            printf("- x ");
        else if(b==0);
        else
            printf("%c %gx ",b>0?'+':'-',fabs(b));
        if(c!=0)
            printf("%c %g ",c>0?'+':'-',fabs(c));
        printf("= 0\n");
        if(dee-ltt>0)
        {
            x1=(-b-sqrt(dee-ltt))/(2*a);
            x2=(-b+sqrt(dee-ltt))/(2*a);
            if(fabs(x1)<1e-6)	//x1精度
                x1=0;
            if(fabs(x2)<1e-6)	//x2精度
                x2=0;
            printf("two real roots : %g, %g\n",x1,x2);
        }
        else if(dee-ltt==0&&dee-ltt==-0)
        {
            x1=-b/(2*a);
            if(fabs(x1)<1e-6)	//x精度
                x1=0;
            printf("only one real root : ");
            printf("%g\n",x1);
        }
        else
        {
            x1=(-b)/(2*a);
            x3=sqrt(fabs(dee-ltt))/(2*a);
            if(fabs(x1)<1e-6)
                x1=0;	//实部精度
            if(fabs(x3)<1e-6)
                x3=0;	//虚部精度
            printf("two imaginary roots : ");
            if(x1!=0)
            {
                printf("%g",x1);
                if(x3==1)
                    printf("+i");
                else if(x3==0);
                else
                    printf("+%gi",x3);
            }
            else
            {
                if(x3==1)
                    printf("i");
                else if(x3==0);
                else
                    printf("%gi",x3);

            }
            printf(", ");
            if(x1!=0)
                printf("%g",x1);

            if(x3!=1)
                printf("-%gi\n",x3);
            else if(x3==0);
            else
                printf("-i\n");
        }
        printf("\n");
        i++;
    }
    return 0;
}

萌新初次尝试写博文，如有错漏，欢迎各位大佬指点。