自然数、整数、有理数、实数及其算术运算（加、减、乘、除）

一、概念解析

概念解析

1. 自然数（Natural Numbers）
   定义：非负整数（通常指0,1,2,3...，部分定义不包含0），是计数和排序的基础。
   C++表示：int、long long（根据数值范围选择，避免溢出）。

2. 整数（Integers）
   定义：包含正整数、负整数和0（...,-2,-1,0,1,2...），无小数部分。
   C++表示：int（范围±2.1×10⁹）、long long（范围±9.2×10¹⁸），需根据题目数据范围选择。

3. 有理数（Rational Numbers）
   定义：可表示为两个整数之比的数（a/b，b≠0），包括整数、分数、有限小数、无限循环小数。
   C++表示：

   • 浮点数（float/double，但存在精度误差）；
   • 自定义分数结构（存储分子和分母，避免精度损失，信奥赛常用）。

4. 实数（Real Numbers）
   定义：包含有理数和无理数（如π、√2，无限不循环小数）。
   C++表示：float（单精度，约6-7位有效数字）、double（双精度，约15-17位有效数字，信奥赛首选）。

二、算术运算及C++实现

运算	整数运算（int/long long）	有理数/实数运算（double/分数）
加法	a + b（注意溢出）	a + b（double直接运算；分数需通分）
减法	a - b（注意负数溢出）	a - b（同加法逻辑）
乘法	a * b（易溢出，需提前判断）	a * b（double可能损失精度；分数分子乘分子、分母乘分母）
除法	a / b（整数除法自动截断，如5/2=2）	(double)a / b（double；分数需交叉相乘后约分）

三、实战案例

实战案例

案例1：整数运算与溢出避免

问题：计算1到n的和（n≤1e18），避免溢出。

c++

#include <iostream>
using namespace std;

int main() {
    long long n;  // 用long long存储大整数
    cin >> n;
    // 公式：n*(n+1)/2，先除2避免中间结果溢出
    long long sum = n % 2 == 0 ? (n / 2) * (n + 1) : n * ((n + 1) / 2);
    cout << sum << endl;
    return 0;
}

关键点：通过调整运算顺序（先除后乘）避免n*(n+1)超出long long范围。

案例2：分数运算（避免浮点数误差）

问题：计算两个分数的和并化简（如1/2 + 1/3 = 5/6）。

c++

#include <iostream>
#include <algorithm> // 用于gcd
using namespace std;

struct Fraction {
    long long num, den; // 分子、分母
    // 化简分数
    void simplify() {
        long long g = gcd(abs(num), abs(den));
        num /= g;
        den /= g;
        if (den < 0) { // 确保分母为正
            num *= -1;
            den *= -1;
        }
    }
};

Fraction add(Fraction a, Fraction b) {
    Fraction res;
    res.den = a.den * b.den; // 通分：分母相乘
    res.num = a.num * b.den + b.num * a.den; // 分子交叉相加
    res.simplify();
    return res;
}

int main() {
    Fraction a = {1, 2}, b = {1, 3};
    Fraction c = add(a, b);
    cout << c.num << "/" << c.den << endl; // 输出5/6
    return 0;
}

关键点：用结构体存储分数，通过最大公约数（gcd）化简，避免浮点数精度丢失。

案例3：实数运算与精度比较

问题：判断两个实数是否相等（如判断√2×√2是否等于2）。

c++

#include <iostream>
#include <cmath>
using namespace std;

const double EPS = 1e-9; // 精度误差范围

bool equals(double a, double b) {
    return abs(a - b) < EPS; // 差值小于EPS则认为相等
}

int main() {
    double x = sqrt(2) * sqrt(2);
    double y = 2.0;
    if (equals(x, y)) {
        cout << "相等" << endl; // 正确输出“相等”
    } else {
        cout << "不相等" << endl;
    }
    return 0;
}

关键点：浮点数直接用==比较会因精度误差出错，需通过误差范围判断。

四、信奥赛应用场景

信奥赛应用场景

1. 整数场景：

   • 数论问题（质数判断、最大公约数、模运算，如NOIP2017“小凯的疑惑”）；
   • 计数问题（如组合数计算、路径计数，需用long long避免溢出）。

2. 有理数场景：

   • 分数应用题（如比例计算、概率问题，需用分数结构保证精度）；
   • 高精度计算（如大分数加减乘除，避免浮点数误差）。

3. 实数场景：

   • 几何问题（距离计算、角度求解，如计算两点间距离sqrt((x1-x2)^2 + (y1-y2)^2)）；
   • 二分法（如求方程近似解，需控制double精度）。

五、避坑指南

避坑指南

1. 整数溢出：

   • 陷阱：int存储1e10会溢出（1e10 > 2e9），导致结果错误。
   • 解决：优先用long long；运算前预判范围（如a * b是否超过LLONG_MAX）。

2. 浮点数精度：

   • 陷阱：0.1 + 0.2 != 0.3（二进制存储误差）；double精度有限，无法精确表示所有小数。
   • 解决：用EPS（如1e-9）判断相等；高精度场景改用分数结构。

3. 整数除法截断：

   • 陷阱：5 / 2 = 2（向下取整），负数除法更复杂（如-5 / 2 = -3在部分编译器中）。
   • 解决：需向上取整时用(a + b - 1) / b（仅正整数）；负数除法单独处理。

4. 类型转换错误：

   • 陷阱：int a = 1e9; double b = a * 2;（a*2先溢出int，再转double）。
   • 解决：运算前强制转换类型，如(double)a * 2。

重要

• 类型选择：根据数据范围选整数类型（int/long long）；精度敏感用分数结构，非敏感用double。
• 运算原则：整数运算防溢出，浮点数运算防精度，分数运算必化简。
• 核心思想：信奥赛中“正确性”优先于“简洁性”，需根据题目场景选择合适的数类型及运算方式，避免因类型或精度问题丢分。

进制与进制转换：二进制、八进制、十进制、十六进制

一、概念解析

进制的基本概念

1. 进制的基本概念
   进制（进位制）是一种计数方式，指逢特定数值进位。例如十进制逢10进1，二进制逢2进1。
   关键术语：

   • 基数：每个数位上允许的最大数字加1（如二进制基数为2，十六进制基数为16）。
   • 数位：数字中每个位置（如十进制"123"中，1在百位，2在十位）。

2. 常见进制

   进制	基数	数字范围	表示方法（C++）	示例
   二进制	2	0,1	前缀0b（C++11起）	0b1010（对应十进制10）
   八进制	8	0-7	前缀0	012（对应十进制10）
   十进制	10	0-9	无前缀	10（对应十进制10）
   十六进制	16	0-9,A-F（或a-f）	前缀0x	0xA（对应十进制10）

二、进制转换原理及C++实现

进制转换原理及C++实现

1. 其他进制转十进制（按权展开）

• 原理：将每个数位的数值乘以基数的位权（从右往左，位权从0开始），再求和。
  例：二进制1010转十进制：1×2³ + 0×2² + 1×2¹ + 0×2⁰ = 8 + 0 + 2 + 0 = 10。

• C++实现（字符串表示的任意进制转十进制）：

c++

#include <iostream>
#include <string>
using namespace std;

// 其他进制转十进制（base范围2-16）
long long toDecimal(const string &s, int base) {
    long long res = 0;
    for (char c : s) {
        int val;
        if (c >= '0' && c <= '9') val = c - '0';
        else if (c >= 'A' && c <= 'F') val = 10 + c - 'A';
        else if (c >= 'a' && c <= 'f') val = 10 + c - 'a';
        else return -1; // 非法字符
        res = res * base + val;
    }
    return res;
}

int main() {
    cout << toDecimal("1010", 2) << endl;   // 输出10（二进制转十进制）
    cout << toDecimal("A", 16) << endl;     // 输出10（十六进制转十进制）
    return 0;
}

2. 十进制转其他进制（除基取余法）

• 原理：将十进制数反复除以目标基数，取余数作为新进制的数位（从低位到高位）。
  例：十进制10转二进制：10÷2=5余0 → 5÷2=2余1 → 2÷2=1余0 → 1÷2=0余1，倒序得1010。

• C++实现（十进制转任意进制字符串）：

c++

#include <iostream>
#include <string>
#include <algorithm> // 用于reverse
using namespace std;

// 十进制转其他进制（base范围2-16）
string fromDecimal(long long num, int base) {
    if (num == 0) return "0";
    string res;
    while (num > 0) {
        int rem = num % base;
        if (rem < 10) res += (char)('0' + rem);
        else res += (char)('A' + rem - 10);
        num /= base;
    }
    reverse(res.begin(), res.end()); // 反转得到正确顺序
    return res;
}

int main() {
    cout << fromDecimal(10, 2) << endl;   // 输出1010（十进制转二进制）
    cout << fromDecimal(255, 16) << endl; // 输出FF（十进制转十六进制）
    return 0;
}

3. 二进制与十六进制/八进制快速转换

• 二进制转十六进制：每4位二进制对应1位十六进制（如1010 1111 → AF）。
• 二进制转八进制：每3位二进制对应1位八进制（如10 101 → 25）。
• 反向转换同理，直接按位扩展即可。

三、实战案例

实战案例

案例1：二进制加法（模拟手工运算）

问题：实现两个二进制字符串的加法（如"1010" + "1101" = "10111"）。

c++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string addBinary(string a, string b) {
    string res;
    int i = a.size() - 1, j = b.size() - 1;
    int carry = 0; // 进位
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        carry = sum / 2; // 计算新进位
        res += (sum % 2) + '0'; // 当前位结果
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    cout << addBinary("1010", "1101") << endl; // 输出10111
    return 0;
}

案例2：十六进制与十进制互转（处理输入输出）

问题：读取十六进制数，输出其十进制值；读取十进制数，输出其十六进制值（大写）。

c++

#include <iostream>
#include <iomanip> // 用于setbase
using namespace std;

int main() {
    // 十六进制转十进制
    int hexNum;
    cin >> hex >> hexNum; // 用hex指示输入为十六进制
    cout << dec << hexNum << endl; // 用dec指示输出为十进制

    // 十进制转十六进制
    int decNum;
    cin >> dec >> decNum; // 用dec指示输入为十进制（默认）
    cout << hex << uppercase << decNum << endl; // uppercase使字母大写
    return 0;
}

四、信奥赛应用场景

信奥赛应用场景

1. 位运算优化：
   二进制是位运算（&、|、^、<<、>>）的基础，可高效解决状态压缩、掩码问题。例如：

   • 用二进制表示集合（1010表示包含第1和第3个元素）；
   • 用n & (n-1)判断n是否为2的幂（如NOIP2011“数字反转”优化）。

2. 数据压缩与存储：
   十六进制常用于表示二进制数据（如颜色值0xFF0088），八进制可简化文件权限表示（如0755）。

3. 进制转换题：
   直接考察进制转换逻辑，如“将N进制数转为M进制数”（需通过十进制中转）。

4. 密码学与哈希：
   哈希值、UUID等常以十六进制表示（如MD5值e10adc3949ba59abbe56e057f20f883e）。

五、避坑指南

避坑指南

1. 输入输出格式错误：

   • 陷阱：用cin读取十六进制时忘记加hex前缀，导致数据解析错误（如输入A会被当作0）。
   • 解决：明确指定格式：cin >> hex >> x（输入）、cout << hex << x（输出）。

2. 前导零混淆：

   • 陷阱：C++中012表示八进制（值为10），而非十进制12，易导致逻辑错误。
   • 解决：避免在代码中写带前导零的数字；处理输入字符串时需先判断进制前缀。

3. 溢出问题：

   • 陷阱：转换大进制数（如64位二进制）时，用int存储会溢出。
   • 解决：优先用long long或unsigned long long；超大数据需用字符串模拟运算。

4. 字符大小写问题：

   • 陷阱：十六进制中a和A均表示10，但比较字符串时会被视为不同。
   • 解决：转换前统一转为大写或小写（如用toupper()/tolower()函数）。

重要

• 核心逻辑：进制转换的本质是“按权展开”（其他转十进制）和“除基取余”（十进制转其他），二进制与十六进制/八进制可快速互转。
• C++工具：利用hex/oct/dec控制输入输出格式，复杂转换需手动实现字符串处理。
• 信奥重点：进制是位运算的基础，需熟练掌握二进制操作及跨进制转换，尤其注意格式和溢出问题，避免因细节丢分。