第一次训练题

第一次训练赛的附加题

 

第一题：POJ 1003 Hangover

求n使得1/2 1/3 ... 1/n>=x.

#include <stdio.h>
#include <math.h>

int main ()
{
    int ans;
    double in,sum=0;
    while (scanf("%lf",&in)&&fabs(in)>1e-5) //本行见注释
    {
        ans=1;
        while (sum<in)
        {
            ans ;
            sum =1.0/ans;
        }
        printf("%d card(s)\n",ans-1);
        sum=0;
    }
    return 1;
}

注释：记得以前好像在哪里看到过说浮点数不会完全等于0，所以使用了fabs函数，不知道是否有必要?

 

第二题：POJ 1004 Financial Management

求12个浮点数的平均值.

#include <stdio.h>

int main ()
{
    int n=12;
    float in,ans=0;
    for (;n>0;n--)
    {
        scanf("%f",&in);
        ans+=in;
    }
    ans/=12;
    printf("$%.2f\0",ans);
    return 1;
}

 

 

第三题：POJ 1005 I Think I Need a Houseboat

题意: 如图,一个海岸线从原点开始以半圆形扩展,每年50平方英里的速度.给你一个点(x,y),求出覆盖到该点的时间.

 

思路:

引用下学长： 求出经过点(x,y)的半圆形的面积,除以50然后向上取整就是最终结果.不过此题的数据不是特别强,所以对结果向下取整再加1也对.

 

是否可以理解为：向上取整不一定等于向下取整加1?

#include <stdio.h>
#include <math.h>
#define PI 3.1416

float area (float x,float y);
int main ()
{
    int ans,T,n=1;
    float x,y;
    scanf("%d",&T);
    while (n<=T)
    {
        scanf("%f%f",&x,&y);
        ans=ceil(area(x,y)/50);
        printf("Property %d: This property will begin eroding in year %d.\n",n,ans);
        n++;
    }
    printf("END OF OUTPUT.");
    return 1;
}


float area (float x,float y)
{
    float r2,s;
    r2=x*x+y*y;
    s=PI*r2/2;
    return s;
}

 

第四题:POJ 1007 DNA Sorting

题意: 给出m个长度都为n的DNA字符串,按照每个字符串的逆序数从小到大排序(如果逆序数相同则按照给出的顺序输出).

思路:

引用学长：这一题主要是考察稳定排序(排序后关键字相同的元素按照原来的顺序排列).可以直接使用比较简单的冒泡排序,选择排序,也可以使用效率较高的快速排序(C语言库函数中的qsort()).

但是qsort()是不稳定的排序,可以通过增加一个下标使之成为稳定排序.

程序中使用了冒泡排序

 

#include <stdio.h>
#include <stdlib.h>

struct DNA
{
    char s[50];
    int sorted;
}dna[100],ls;

int main ()
{
    int temp,i,j,m,n;
    scanf("%d%d",&n,&m);
    getchar();
    for (temp=0;temp<m;temp++)
    {
        dna[temp].sorted=0;
        gets(dna[temp].s);
        for (i=0;i<n-1;i++)
            for (j=i+1;j<n;j++)
                if (dna[temp].s[i]>dna[temp].s[j])
                    dna[temp].sorted++;
    }
    for (i=0;i<m-1;i++)
        for (j=0;j<m-i-1;j++)
            if(dna[j].sorted>dna[j+1].sorted)
            {
                ls=dna[j];
                dna[j]=dna[j+1];
                dna[j+1]=ls;
            }
    for (temp=0;temp<m;temp++)
    {
        puts(dna[temp].s);
    }
    return 1;
}