（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第4讲 高精度数

学科竞赛编程 C++ NOIP NOI IOI 1 1 PART ONE 高精度数的定义 32位计算机有符号整数（int）的取值范围是 32 31 30 … … 5 4 3 2 1 ± 1 1 … … 1 0 0 1 0 -231 0 +231-1 ～ ～ 1 PART ONE 高精度数的定义 32位计算机无符号整数（unsigned int）的取值范围是 32 31 30 … … 5 4 3 2 1 1 1 1 … … 1 0 0 1 0 0 232-1 ～ 32位无整形：0~4294967295 1 PART ONE 高精度数的定义 长整型（long long） 有符号数范围 -263~263 -1 无符号数范围 0~264 -1 1000位整数 如何存储？ 高精度数 或 大数 1 PART ONE 高精度数的存储 分类 整型数组 字符数组 存储方式 按字符串输入，并通过循环语句，将字符转化为数字 直接输入，以字符方式存储 获取位数 计算每个数组的元素位数再相加 strlen( )函数 输出 采用循环语句打印数组元素 字符串输出，方便 运算 直接计算 转换为数字后计算 思想：高精度数每一位数字存储在一个数组中 1 PART ONE 问题分析 高精度数的存储 小任务：请用字符数组方法输入两个大数 9753186420321 123456789 （回车） char s1[100] char s2[100] ‘9’ ‘7’ ‘5’ ‘3’ ‘1’ ‘8’ ‘6’ ‘4’ ‘2’ ‘0’ ‘3’ ‘2’ ‘1’ \0 ‘1’ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’ \0 亲自出码 char s1[100],s2[100]; cin>>s1>>s2; cout<<s1<<“ ”<<s2; //或者get(s1); get(s2); 1 PART ONE 方法一：前面元素从低位开始存储 高精度数的存储 int n1[100] int n2[100] 9 7 5 3 1 8 6 4 2 0 3 2 1 0 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 缺点：不利于大数运算时的位置对齐 9753186420321 + 123456789 1 PART ONE 高精度数的存储 int s1[100] int s2[100] 1 2 3 0 2 4 6 8 1 3 5 7 9 0 0 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 方法二：前面元素存储大数低位，后面元素存储大数高位 方法三：第一个元素存储大数长度 int s1[100] int s2[100] 13 1 2 3 0 2 4 6 8 1 3 5 7 9 0 0 9 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 优点：大数计算对齐 缺点：不利于求大数长度；数组输入要采用循环语句 1 PART ONE 高精度数的存储 字符数组 整型数组方法一 整型数组方法三 整型数组方法二 缺点：计算麻烦，需采用循环语句先将字符转化为数字； 即-48 缺点： 不利于求大数长度； 输入繁琐； 缺点： 输入繁琐； 考虑时间成本，及缺点是否好解决的难易程度，因此大数存储多采用字符数组。 1 PART ONE 两个高精度数 位数相同 且没有进位 1 两个高精度数 位数不同 且没有进位 2 两个高精度数 位数相同 且有进位 3 两个高精度数 位数不同 且有进位 4 高精度数的加法 1 PART ONE 高精度数的加法 1、两个高精度数位数相同且没有进位 小任务：输入两个高精度数，输出这两个数的和 输入：2222222222 3333333333 输出：5555555555 问题分析 char a1[100] char b1[100] ‘3’ ‘3’ ‘3’ ‘3’ ‘3’ ‘3’ ‘3’ ‘3’ ‘3’ ‘3’ \0 第一步：以字符串形式输入数组 ‘2’ ‘2’ ‘2’ ‘2’ ‘2’ ‘2’ ‘2’ ‘2’ ‘2’ ‘2’ \0 1 PART ONE 高精度数的加法 点击添加文本 int a[100] int b[100] 3 3 3 3 3 3 3 3 3 3 \0 第二步：以for循环遍历，将字符数组存储到整型数组 2 2 2 2 2 2 2 2 2 2 \0 点击添加文本 cout sum a[1]+b[1] a[2]+b[2] … a[i]+b[i] 第三步：以for循环遍历，将对应数组元素相加，无进位， 并顺位输出 [0] [1] …………….[i]………… 1