「PAT乙级真题解析」Basic Level 1103 缘分数 (问题分析+完整步骤+伪代码描述+提交通过代码)

题设给定两个关系式`a^3 - (a-1)^3 = c^2`和`b^2 + (b-1)^2 = c`, 要求指定区间内满足两个等式的a和b。 即, 要求指定区间内满足等式`a^3 - (a-1)^3 = (b^2 + (b-1)^2)^2`的a和b。 等式可以化简为: `3*a^2 - 3*a = 4*b^4 - 8*b^3 + 8*b^2 - 4*b`

#算法#数据结构#pat考试#需求分析#c语言

Table of Contents

乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT (Basic Level) Practice 1103 缘分数

问题分析

  • 题设给定两个关系式a^3 - (a-1)^3 = c^2b^2 + (b-1)^2 = c, 要求指定区间内满足两个等式的a和b。
  • 即, 要求指定区间内满足等式a^3 - (a-1)^3 = (b^2 + (b-1)^2)^2的a和b。
  • 等式可以化简为: 3*a^2 - 3*a = 4*b^4 - 8*b^3 + 8*b^2 - 4*b

性能优化

可以考虑将每一个值x的 3*x^2 - 3*x4*x^4 - 8*x^3 + 8*x^2 - 4*x存储起来, 避免重复计算防止超时

完整描述步骤

  1. 获取输入: 取值区间左端点, 取值区间右端点
  2. 初始化计数器:
    • solution个数 = 0
  3. a的取值 从 取值区间左端点 到 取值区间右端点:
    • b的取值从 1 到 a - 1:
      • 如果满足 3*a^2 - 3*a = 4*b^4 - 8*b^3 + 8*b^2 - 4*b:
        • 输出"{a} {b}"
        • solution个数++
  4. 如果 solution个数 == 0:
    • 输出"No Solution"

伪代码描述

  1. get input: min_number, max_number
  2. init counter:
    • solution_amount = 0;
  3. for a in range(min_number, max_number + 1):
    • for b in range(1, a):
      • if 3a^2 - 3a == 4b^4 - 8b^3 + 8b^2 - 4b:
        • print("{a} {b}");
        • solution_amount++;
  4. if solution_amount == 0:
    • print("No Solution");

注意事项

  1. 题设使用了"另一个整数c"的表述, 说明a和c不能相同。
    • 比如a=1, b=1, c=1的情况不能认为是满足条件的缘份数(测试点4)
    • 输入样例: 1 1

完整提交代码

/*
# 问题分析
题设给定两个关系式`a^3 - (a-1)^3 = c^2`和`b^2 + (b-1)^2 = c`, 要求指定区间内满足两个等式的a和b。
即, 要求指定区间内满足等式`a^3 - (a-1)^3 = (b^2 + (b-1)^2)^2`的a和b。
等式可以化简为: `3*a^2 - 3*a = 4*b^4 - 8*b^3 + 8*b^2 - 4*b`
 
## 性能优化
可以考虑将每一个值x的 `3*x^2 - 3*x`和`4*x^4 - 8*x^3 + 8*x^2 - 4*x`存储起来, 避免重复计算防止超时
 
# 完整描述步骤
1. 获取输入: 取值区间左端点, 取值区间右端点
2. 初始化计数器:
    - solution个数 = 0
3. a的取值 从 取值区间左端点 到 取值区间右端点:
    - b的取值从 1 到 a - 1:
        - 如果满足 `3*a^2 - 3*a = 4*b^4 - 8*b^3 + 8*b^2 - 4*b`:
            - 输出"{a} {b}"
            - solution个数++
4. 如果 solution个数 == 0:
    - 输出"No Solution"
 
# 伪代码描述
1. get input: min_number, max_number
2. init counter:
    - solution_amount = 0;
3. for a in range(min_number, max_number + 1):
    - for b in range(1, a):
        - if 3*a^2 - 3*a == 4*b^4 - 8*b^3 + 8*b^2 - 4*b:
            - print("{a} {b}");
            - solution_amount++;
4. if solution_amount == 0:
    - print("No Solution");
 
# 注意事项
1. 题设使用了"另一个整数c"的表述, 说明a和c不能相同。
    - 比如a=1, b=1, c=1的情况不能认为是满足条件的缘份数(测试点4)
    - 输入样例: 1 1
*/
 
# include<stdio.h>
# include<math.h>
 
int meet_condition(int a, int b){
    int left = 3 * a * a - 3 * a;
    int right = 4 * b * b * b * b - 8 * b * b * b + 8 * b * b - 4 * b;
    if (left == right){
        return 1;
    }
 
    return 0;
}
 
int main(){
    int min_number, max_number;
    scanf("%d %d", &min_number, &max_number);
    
    int solution_amount = 0;
    for (int a = min_number; a <= max_number; a++){
        for (int b = 1; b < a; b++){
            if (a == 1 && b == 1){
                continue;
            }
            if (meet_condition(a, b) == 1){
                printf("%d %d\n", a, b);
                solution_amount++;
            }
        }
    }
    
    if (solution_amount == 0){
        printf("No Solution");
    }
    
    return 0;
}
「PAT乙级真题解析」Basic Level 1103 缘分数 (问题分析+完整步骤+伪代码描述+提交通过代码) | 生活糖果