PTA刷题总结-Part 1 基础部分
PTA刷题总结-Part 2 模拟与数学问题
PTA刷题总结-Part 3 数据结构与算法

2 数学问题和基本模拟

2.1 计算闰年

闰年的判别条件是该年年份能被4整除但不能被100整除、或者能被400整除。闰年的2月有29天。

计算闰年真的是个非常常见的题目了，其实只要明白了闰年计算方法，剩下的就是条件语句中的逻辑问题。（题目：7-19 计算天数 (15分)）

#include <stdio.h>


int main() {
    int daysOfM[] = {31,28,31,30,31,30,31,31,30,31,30,31};
    int daysOfMR[] = {31,29,31,30,31,30,31,31,30,31,30,31};
    int yyyy,mm,dd=0;
    int result = 0;
    scanf("%d/%d/%d",&yyyy,&mm,&dd);
    int isRun = 0;
    if ((yyyy%4==0 && yyyy%100!=0)|| yyyy%400==0 ){
        isRun = 1;
    } 
    
    for (int i=1; i<mm;i++) {
        if (i!=2 || i==2 && isRun==0) {
            result += daysOfM[i-1];
        } else {
            result += daysOfMR[i-1];
        }
    }
    result += dd;
    printf("%d\n",result);
    return 0;
}

2.2 最大公约数GCD和最小公倍数LCM

• 最大公约数(Greatest Common Divisor)一般使用辗转相除法
• 最小公倍数( Least Common Multiple )等于a*b/两数最大公约数，但是我们一般写成a/gcd*b，先除后乘，避免a*b的结果太大导致溢出

题目：7-26 最大公约数和最小公倍数 (15分)

#include <stdio.h>

int main() {
    int m,n = 0;
    scanf("%d %d",&m, &n);
    
    int m1 = m;
    int n1 = n;
    while (n1!=0){
        int temp = m1%n1;
        m1 = n1;
        n1 = temp;
    }
    // m1 是最大公倍数
    int lcm = m/m1*n;
    printf("%d %d\n",m1,lcm); 
    
    return 0;
}

题目：7-112 约分最简分式 (15分)

#include <stdio.h>
int gcd(int a,int b){
    while (b!=0){
        int temp = a%b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    int up = 0;
    int down = 0;
    scanf("%d/%d", &up,&down);
    int g = gcd(up,down);
    up = up/g;
    down = down/g;
    printf("%d/%d", up, down);
    return 0;
}

2.3 取出整数的各位数字

常见的题目类型有从右向左取（从个位开始）和从左向右取（从最高位开始）的。

无所谓顺序的，比如求各位数字的和（题目：7-28 求整数的位数及各位数字之和 (15分)），就可以直接从右向左取。不断地对10求余，取出来，然后对原数除以10，去掉末位。一直到原数最后只剩下一位。
注意，下面代码中之所以使用do{...}while()而不使用while(){}，是为了保证输入数字0的时候，也能计算出来有1位。

#include <stdio.h>

int main() {
    int m=0;
    scanf("%d",&m);
    
    int count = 0;
    int sum = 0;
    do{
        int digit = m %10;
        m = m/10;
        count++;
        sum+=digit;
    }while (m >0);
    printf("%d %d\n", count, sum);
    return 0;
}

题目：7-100 逆序的三位数 (10分)

#include <stdio.h>

int main() {
    int x = 0;
    scanf("%d", &x);
    int r = 0;
    do {
        int digit  = x%10;
        r = r*10+digit;
        x /= 10;
    } while(x>0);
    
    printf("%d\n", r);
    return 0;
}

但是有的题目要求你从高位开始输出，不得不从左向右取，目前看有两种方法

• 先找到最高位，比如42345的最高位是是42345/10000=4，然后次高位用2345/1000=2，以此类推。
• 如果题目已经告诉你输入的整数位数范围，可以使用定长的字符数组
  题目：7-37 输出整数各位数字 (15分)

#include <stdio.h>
long count(long m); 
int main() {
    long m = 0;
    scanf("%ld",&m);
    long c =  count(m);
    while (c != 0){
        int digit =  m / c;
        printf("%d",digit);
        if (c >= 9){
            printf(" ");
        }
        m = m % c;
        c = c/10;
        
    }

    return 0;
}

long count(long m){
    long c = 1;
    while(m>9) {
        m = m/10;
        c = c*10;
    }
    return c;
}

题目：7-30 念数字 (15分)

#include <stdio.h>
#include <string.h>
int main() {
    char str[1000] = {'\0'};
    scanf("%s", str);
    int len = strlen(str);
    for (int i=0; i< len; i++) {
        switch(str[i]){
            case '-':printf("fu");break;
            case '0':printf("ling");break;
            case '1':printf("yi");break;
            case '2':printf("er");break;
            case '3':printf("san");break;
            case '4':printf("si");break;
            case '5':printf("wu");break;
            case '6':printf("liu");break;
            case '7':printf("qi");break;
            case '8':printf("ba");break;
            case '9':printf("jiu");break;
            default:break;
        }
        if (i<len-1) {
            printf(" ");
        }
    }
    
    return 0;
}

2.4 素数

素数就是我们说的质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。1不是素数，2是素数。

题目：7-33 统计素数并求和 (20分)

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

int isPrime(int k);
int main() {
    int m,n = 0;
    scanf("%d %d",&m,&n);
    int count = 0;
    int sum = 0;
    for (int i=m; i<=n;i++){
        if (isPrime(i)){
            count++;
            sum+=i;
        }
    }
    
    printf("%d %d\n", count,sum);

    return 0;
}

int isPrime(int k){
    int isP = 1;
    if (k < 2){
        isP = 0;
        return isP;
    } else {
        for(int i=2; i<sqrt(k);i++){
            if (k % i==0){
                isP = 0;
                break;
            }
        }
    }
    return isP;
}

这道题中如果最小值已知是从1开始计算的话，可以考虑使用素数表的方法去实现isPrime(),而不是sqrt(k) ,如下，构造了一个小于m的素数表。

#include <stdio.h>
int prime[20000] = {2};

int isPrime(int x, int prime[], int count){
    int r = 1;
    for (int i=0;i<count;i++){
        if (x % prime[i] == 0){
            r = 0;
            break;
        }
    }
    return r;
}
int main() {
    int m=0;
    scanf("%d", &m);
    int count = 1;
    for (int i=3;i<m;i++){
        if (isPrime(i, prime,count)){
            prime[count++] = i;
        }   
    }
    return 0;
}

但是经过实际题目检验，发现当N非常大，接近于10^5 时，使用prime数组方式判断是否是素数的方法面临超时风险，而使用sqrt不会
题目：素数对猜想 (20分)

#include <stdio.h>
#include <math.h>
int r = 0; 
int isPrime(int k){
    int r = 1;
    for (int i=2;i<=sqrt(k);i++){
        if (k % i==0){
            r = 0;
        }
    }
    return r;
}
int main(){
    int n = 0;
    scanf("%d", &n);
    int count = 1;
    int pre = 2;
    for (int i=3;i<=n;i++){
        if (isPrime(i)){
            if (i-pre==2){
                r++;
            }
            count ++;
            pre = i;
        }
    }
    
    

    printf("%d", r);
    return(0);
}

2.5 使用数组进行循环模拟

题目：猴子选大王
典型的约瑟夫环问题，这里可以使用数组进行模拟。

#include <stdio.h>
int a[1001];// 1表示淘汰 
int main(){
    int n = 0,s=0,count=0;
    int i = 0; // 数组下标 
    scanf("%d", &n);
    while(s != n-1){ // 淘汰猴子的数量达到n-1时退出
        i++;
        if (i>n){
            i = 1;
        }
        if(a[i] == 0){ // 只判断剩下的猴子 
            count++;
            if (count %3==0){
                a[i] = 1;
                s++; // 每次淘汰一只猴子，直到s==n-1，剩下最后一只 
            } 
        } 
        
    }
    for (int j=1;j<=n;j++){
        if (a[j]==0){
            printf("%d",j);
        }
    }
    return(0);
}

其他解法单独写了一章，可见PTA例题精析-约瑟夫问题 Josephus Problem

题目：7-39 天梯赛座位分配 (20分)
三维数组，纵向循环

#include <stdio.h>
int teamNum[101];
int a[101][11][11]; // i,j,k
int main(){
    int n = 0,maxTeamNum = 0;
    scanf("%d", &n);
    for (int i=1;i<=n;i++){
        scanf("%d", &teamNum[i]);
        if (teamNum[i] >maxTeamNum){
            maxTeamNum = teamNum[i];
        }
    }
    int num = 0,lastI = 0;
    while (maxTeamNum>0){
        for (int k=1;k<=10;k++){
            for (int i=1;i<=n;i++){
                int j=1;
                while (a[i][j][10]>0 && j<=teamNum[i]){
                    j++;
                }
                if (j<=teamNum[i]){
                    if (lastI == i){
                        num +=2;
                    } else {
                        num++;
                    }
                    a[i][j][k] = num;
                    lastI = i;
                }
            }
        }
        maxTeamNum--;
    }

    // output
    for (int i=1;i<=n;i++){
        printf("#%d\n", i);
        for (int j=1;j<=teamNum[i];j++){
            printf("%d", a[i][j][1]);
            for (int k=2;k<=10;k++){
                printf(" %d", a[i][j][k]);
            }
            printf("\n");
        }
    }
    return 0;
}