pat乙级难度少量习题总结

Ranbo_

最近在练习pat乙级模拟题，感觉复试机试难度也就和pat乙级难度差不多了，难度挺低的，我这种初学者都能无压力ac。

一、有花生植株整齐地排列成矩形网格。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说:“你先找出花生最多的植株，去采摘它的花生;然后再找出剩下的植株里花生最多的，去采摘它的花生;依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件：
1. 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2. 从一棵植株跳到前后左右与之相邻的另一棵植株；
3. 采摘一棵植株下的花生；
4. 从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？
注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如花生田里只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为 13, 7, 15, 9。多多在 21 个单位时间内，只能经过(4, 2)、(2, 5)、(5, 4)，最多可以采到 37 个花生。

输入：

包含多组数据，每组数据第一行包括三个整数 M（1≤M≤20）、N（1≤N≤20）和 K（0≤K≤1000），用空格隔开；表示花生田的大小为 M * N，多多采花生的限定时间为 K个单位时间。

紧接着 M 行，每行包括 N 个自然数 P（0≤P≤500），用空格隔开；表示花生田里植株下花生的数目，并且除了0（没有花生），其他所有植株下花生的数目都不相同。

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

typedef struct hs
{
    int num;//花生数量
    int hs_x;
    int hs_y;//所在位置
}HS;

int cmp(const void* a, const void* b)
{
    HS *h1 = (HS*) a;
    HS *h2 = (HS*) b;
    return (h2 -> num - h1 -> num);
}//从大到小排列

HS hs[400];

int main()
{
    int m, n, t;
    while(~scanf("%d %d %d", &m, &n, &t))
    {
        //int field[20][20] = {0};//田里花生的矩阵
        int i, j;
        int ammount = m*n;//田地面积
        int count = 0;
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
            {
                hs[count].hs_x = i;
                hs[count].hs_y = j;
                scanf("%d", &(hs[count].num));
                count++;
            }
        if(ammount < 400)    hs[ammount].num = 0;//最后一个元素置为0
        qsort(hs, ammount, sizeof(hs[0]), cmp);
        int x, y;
        x = -1;            y = hs[0].hs_y; 
        int sum = 0;
        i = 0;
        while(x+1 < t && hs[i].num)//x,y>=t时必须返回，若有花生的地方全部采摘完毕也必须返回
        {
            if(hs[i].hs_x == x && hs[i].hs_y == y)
            {
                sum += hs[i].num;
                i++;
                t--;
                continue;
            }
            
            if(hs[i].hs_x > x)//目标花生在多多右边
            {
                x++;
                t--;
                continue;
            }
            else if(hs[i].hs_x < x)//目标花生在多多左边
            {
                x--;
                t--;
                continue;
            }
            
            if(hs[i].hs_y > y)//目标花生在多多上边
            {
                y++;
                t--;
                continue;
            }
            else if(hs[i].hs_y < y)//目标花生在多多下边
            {
                y--;
                t--;
                continue;
            }
        }
        printf("%d\n", sum);
    }
}

二、对于斐波那契数列Fibonacci(m)，输入一个数n，若Fibonacci(n)少于六位数，则直接输出，否则只输出最后六位数。
//对于多于七位数的数，要注意尾数为0开头的数。

输入：

输入有多组数据。

每组数据一行，包含一个整数n (1≤n≤100000)。

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

int fib[100000] = {1, 2, 3, 5};//动态补充fib数列的内容

int main()
{
    int n;
    int temp = 0;
    int start = 4;//初始时从fib[4]开始没有数据
    int target = -1;
    while(~scanf("%d", &n))
    {
        int i = 4;
        while((!temp) && fib[i])
        {
            if(target > 0)
                break;
            if((fib[i-1] + fib[i-2]) != fib[i])//产生了进位
            {
                target = i;
                temp = 1;
                break;
            }
            i++;
        }//找到第一个大于1000000的fibonacci数（第i个）
        if(n > start)
        {
            for(i = start; i < n; i++)
            {
                fib[i] = fib[i-1] + fib[i-2];
                if(fib[i] >= 1000000)
                {
                    fib[i] = fib[i] % 1000000;//取最后六位
                }
            }
            start = n;
        }
        if(target > 0 && n > target)
        {
            if(fib[n-1] < 10)         //只剩一位
            {printf("00000");}
            else if(fib[n-1] < 100)   //两位
            {printf("0000"); }
            else if(fib[n-1] < 1000)  //三位
            {printf("000");  }
            else if(fib[n-1] < 10000) //四位
            {printf("00");   }
            else if(fib[n-1] < 100000)//五位
            {printf("0");    }
            }
        printf("%d\n", fib[n-1]);
    }
}

三、有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入：

由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。

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

int main()
{
    //c0记录可以产子的牛，c1,c2记录养了1，2天的牛
    long long int c0[55] = {1, 1, 1, 2, 3}, c1[55] = {0, 1, 1, 1, 2}, c2[55] = {0, 0, 1, 1, 1};
    long long int sum[55] = {1, 2, 3, 4, 6};
    int n;
    int start = 5;
    while(~scanf("%d", &n))
    {
        if(n > start)
        {
            for(int i = start; i < n; i++)
            {
                c0[i] = c2[i-1] + c0[i-1];
                c2[i] = c1[i-1];
                c1[i] = c0[i-1];
                sum[i] = c0[i] + c1[i] + c2[i];
            }
            start = n;
        }
        printf("%ld\n", sum[n-1]);
    }
}

四、对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<50),判定该表达式的值是否为素数

输入：

输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。

输出：

对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。

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

int is_prime(int n)
{
    if(n == 2)
        return 1;
    int m = sqrt(n);
    for(int i = 2; i <= m; i++)
    {
        if(n % i == 0)
            return 0;
    }
    return 1;
}

int main()
{
    int x, y;
    int temp;
    while(1)
    {
        scanf("%d %d", &x, &y);
        if(x == 0 && y == 0)
            break;
        int target;
        temp = 1;
        for(int i = x; i <= y; i++)
        {
            target = i*i + i + 41;
            if(is_prime(target))
                continue;
            else
            {
                temp = 0;
                break;
            }
        }
        if(temp)
            printf("OK\n");
        else
            printf("Sorry\n");
    }
}

五、计算机中采用浮点数表示所有实数，但这意味着精度丢失。请实现一套分数的计算器。分子分母在[1, 30]之间。

输入示例：

1/3 2/3 +
1/5 1/4 -
1/2 1/3 *
2/3 4/3 /

输出：

1/1
-1/20
1/6
1/2

无非就是化简分式的问题。可以用辗转相除法，但是因为要求范围较小，我用的是直接找分子分母是否有公约数。

//30以内的质数只有2，3，5，7，11，13，17，19，23，29
#include <stdio.h>
#include <stdlib.h>

int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

int is_relative(int a, int b)
{
    for(int i = 0; i < 10; i++)
    {
        if(a % prime[i] == 0 && b % prime[i] == 0)
                return prime[i];//不互质,有因数prime[i]
    }
    return 1;//互质
}

int main()
{
    int a1, b1, a2, b2;
    char sign;
    int temp1, temp2;
    while(~scanf("%d/%d %d/%d %c", &a1, &b1, &a2, &b2, &sign))
    {
        int x;
        if(sign == '+')
        {
            temp2 = b1 * b2;
            temp1 = a1*b2 + a2*b1;
        }
        else if(sign == '-')
        {
            temp2 = b1 * b2;
            temp1 = a1*b2 - a2*b1;
        }
        else if(sign == '*')
        {
            temp2 = b1 * b2;
            temp1 = a1 * a2;
        }
        else
        {
            temp2 = a2 * b1;
            temp1 = a1 * b2;
        }
        if(temp1 == temp2)
            temp1 = temp2 = 1;
        while((x = is_relative(temp1, temp2)) != 1)
        {
            temp1 = temp1/x;
            temp2 = temp2/x;
        }
        
        printf("%d/%d\n", temp1, temp2);
    }
}

六、因式分解。把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × ... × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ ... ≤ an。其中a1、a2、...、an均为素数。先给出一个整数a，请输出分解后的因子。

输入：

输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。

输出：

对应每组数据，以“a = a1 * a2 * a3...”的形式输出因式分解后的结果。

//和上一个题思路一样，这个题实现起来更方便，唯一要注意的是*不能输出多了，且最后不能有空格。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 1000000

int is_composite(int n);

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        printf("%d = ", n);
        int x = is_composite(n);
        int temp = 0;
        if(x != 0)
        {
            printf("%d", x);
            n = n/x;
            temp = 1;
        }
        else
            printf("%d", n);
        while((x = is_composite(n)))
        {
            printf(" * %d", x);
            n = n/x;
        }
        if(temp)
            printf(" * %d", n);
        printf("\n");
    }
}

int is_composite(int n)
{
    if(n == 2)
        return 0;
    int s = sqrt(n);
    for(int i = 2; i <= s; i++)
    {
        if(n % i == 0)
            return i;//有因数i
    }
    return 0;
}

还有很多模拟题，不过大都是斐波那契数列的变形或者是其他我之前记录过的类似的题目，这里就没写了。反正时间还很久，继续学习，争取今年复试上机拿个满分~