代码收藏家 【C++&Python】高精度+关于东方博宜OJ四题答案+题目
高精度介绍
高精度加法
高精度加法是一种用于处理大整数加法的算法。由于普通整数类型（如int或long）在计算机中存储的范围有限，当处理超出这些范围的大整数时，就需要采用高精度加法。以下是高精度加法的基本步骤和原理：
-
存储大整数：
- 通常使用字符串来表示大整数，因为字符串可以容纳非常大的整数值而不会丢失精度。
-
逆向存储并转换为整型数组：
- 将字符串表示的大整数逆向存储到一个整型数组中，这样便于处理进位。
-
逐位相加并处理进位：
- 从低位到高位，逐位将两个大整数对应位置的数字相加，如果和大于等于10，则需要向前一位进位。
-
处理最高位的进位：
- 在所有位都相加完毕后，检查最高位是否有进位，如果有，则需要将进位加到结果中。
-
去除前导零并输出结果：
- 最后，去除结果中的前导零，并将结果以字符串或整型数组的形式输出。
高精度加法在密码学、计算几何学、金融、大数据处理、游戏开发、社交网络分析等多个领域都有广泛的应用。
以下是一个简单的C++代码示例，用于实现高精度加法：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string add(string num1, string num2) {
string sum = "";
int carry = 0;
// 从个位开始逐位相加
for (int i = num1.size() - 1, j = num2.size() - 1; i >= 0 || j >= 0 || carry; i--, j--) {
int digit1 = i >= 0 ? num1[i] - '0' : 0;
int digit2 = j >= 0 ? num2[j] - '0' : 0;
int tempSum = digit1 + digit2 + carry;
// 计算当前位的值，并更新进位
sum += to_string(tempSum % 10);
carry = tempSum / 10;
}
// 翻转结果字符串
reverse(sum.begin(), sum.end());
return sum;
}
int main() {
string num1 = "12345678901234567890";
string num2 = "98765432109876543210";
string result = add(num1, num2);
cout << num1 << " + " << num2 << " = " << result << endl;
return 0;
}这段代码定义了一个add函数，它接受两个大整数字符串作为输入，并返回它们的和。在主函数中，我们定义了两个大整数num1和num2，并调用add函数计算它们的和，最后输出结果。
请注意，高精度加法的实现可能会因编程语言和数据结构的不同而有所差异。以上示例仅供参考，具体实现可能需要根据实际情况进行调整。
高精度减法
高精度减法是一种在计算机科学中处理大数运算的技术，它通过模拟手工算术运算的过程，实现了对大整数的精确计算。以下是关于高精度减法的一些关键信息和实现步骤：
定义与特点
实现步骤
-
输入与预处理：
- 输入两个大数，通常以字符串形式表示。
- 确保被减数大于等于减数，如果小于，则交换两者，并在最终结果前添加负号。
- 将字符串形式的数字转换为整数数组，以便逐位进行减法运算。如果两个字符串长度不同，需要在位数少的字符串前面补0，以确保它们具有相同的长度。
-
逐位减法运算：
- 从低位到高位逐位进行减法运算。在每一位上进行减法时，需要考虑借位的情况。
- 如果当前位的被减数小于减数，则需要从高位借位（即高位减一，当前位加10）。
- 将每一位的运算结果存储到相应的数组中。
-
处理结果：
- 去掉结果数组中的前导零。
- 如果最高位有借位（即被减数小于减数），则在最终结果前添加负号。
- 将结果数组转换回字符串形式并输出。
示例代码
下面是一个使用C++实现高精度减法的示例代码：
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool cmp(vector<int>&A, vector<int>&B) {
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1; i >= 0; i--)
if (A[i] != B[i]) return A[i] > B[i];
return true; // A和B相等，也返回true
}
vector<int> sub(vector<int>&A, vector<int>&B) {
vector<int> C;
int t = 0; // A[i]-B[i]-上一位的借位（有借位为1，否则为0）
for (int i = 0; i < A.size(); i++) {
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10); // 将两种情况合并起来写
if (t < 0) t = 1; // 小于0，有借位
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去掉前导0
return C;
}
int main() {
string a, b;
cin >> a >> b;
vector<int> A, B;
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
if (cmp(A, B)) { // A>=B
auto C = sub(A, B);
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
} else { // A<B
auto C = sub(B, A);
printf("-");
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
}
return 0;
}这段代码首先定义了一个比较函数cmp来判断两个大数的大小，然后定义了减法函数sub来执行高精度减法运算，最后在main函数中读取输入、调用相关函数并输出结果。
注意事项
高精度乘法
高精度乘法是一种用于计算机无法用普通数据类型（如C++中的long long int）表示的大整数进行乘法运算的方法。以下是对高精度乘法的详细解释：
-
定义：
- 高精度乘法是指对超出标准数据类型表示范围的大整数进行乘法运算的方法。
- 由于计算机的存储字节有限，无法完整表示一个很大整数的精确值，因此需要采用高精度算法。
-
实现原理：
- 高精度乘法主要通过按位模拟乘法来实现，即模拟手工进行多位数乘法的过程。
- 在实现过程中，通常会将大整数以字符串或数组的形式存储，并逐位进行乘法运算。
- 运算过程需要考虑进位问题，并对结果进行适当的调整，以确保结果的准确性。
-
应用场景：
- 高精度乘法在需要处理大整数运算的场合有着广泛的应用，如密码学、金融计算、科学计算等领域。
- 它还可以用于解决一些实际问题，如计算大数的阶乘、高精度浮点运算等。
-
复杂度分析：
- 对于两个大整数m和n，如果m的长度为lm，n的长度为ln，则朴素算法的复杂度为O(lm * ln)。
- 通过优化算法，可以在一定程度上降低计算复杂度，提高计算效率。
-
代码实现：
- 高精度乘法可以使用多种编程语言来实现，如C、C++、Pascal、Java等。
- 实现过程中需要处理大整数的存储、运算和结果输出等问题。
请注意，高精度乘法涉及大量的计算和数据处理，因此在实现过程中需要注意算法的效率和稳定性。同时，对于金融、科学计算等领域的应用，还需要考虑算法的精度和可靠性。如果您需要在特定领域应用高精度乘法，建议咨询相关领域的专家或查阅相关文献资料。
Python代码
高精度乘法通常涉及处理非常大的整数或浮点数，这些数字可能超出了标准数据类型（如C/C++中的int或double）的范围。为了实现高精度乘法，我们需要使用字符串或特殊的库来处理这些大数字。
以下是一个使用Python实现高精度乘法的简单示例。Python本身支持任意精度的整数，因此我们可以直接使用内置的int类型进行高精度计算。不过，为了演示如何手动处理大数字乘法，我们将使用字符串来表示数字，并编写一个函数来模拟乘法运算。
def multiply_strings(num1, num2):
# 初始化结果列表，用于存储每一位的乘积和进位
result = * (len(num1) + len(num2))
# 反转数字字符串，使得低位在前，高位在后
num1 = num1[::-1]
num2 = num2[::-1]
# 遍历num1和num2的每一位数字
for i in range(len(num1)):
for j in range(len(num2)):
# 计算当前位的乘积，并加上之前的进位
product = int(num1[i]) * int(num2[j]) + result[i + j]
# 更新当前位的结果和进位
result[i + j] = product % 10
result[i + j + 1] += product // 10
# 反转结果列表，并去除前导零
while len(result) > 1 and result[-1] == 0:
result.pop()
result = result[::-1]
# 将结果列表转换为字符串并返回
return ''.join(map(str, result))
# 测试高精度乘法函数
num1 = "12345678901234567890"
num2 = "98765432109876543210"
print(multiply_strings(num1, num2))这个代码实现了一个简单的高精度乘法算法，它使用了字符串来表示大数字，并通过模拟手工乘法的过程来计算结果。注意，这个实现并没有考虑负数或小数的情况，只适用于正整数的乘法。如果需要处理负数或小数，可以在此基础上进行扩展。
另外，如果你使用的是Python，并且不需要手动实现高精度乘法算法，你可以直接利用Python的内置int类型来进行高精度计算。Python的int类型支持任意精度的整数运算，因此你可以直接将大数字作为字符串读入，然后使用int()函数将其转换为整数进行计算。例如：
num1 = "12345678901234567890"
num2 = "98765432109876543210"
result = int(num1) * int(num2)
print(result)C++代码
当然，下面是一个实现高精度乘法的C++代码示例。这段代码使用了字符串来处理大整数的输入和输出，并通过模拟手工乘法的过程来实现高精度乘法计算。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 辅助函数：将字符串表示的数字倒序存储为整型数组
vector<int> stringToVector(const string &num) {
vector<int> result(num.size());
transform(num.rbegin(), num.rend(), result.begin(), [](char c) { return c - '0'; });
return result;
}
// 辅助函数：将整型数组表示的数字转换为字符串
string vectorToString(const vector<int> &num) {
string result;
for (int digit : num) {
result.push_back(digit + '0');
}
// 移除前导零
while (result.size() > 1 && result.back() == '0') {
result.pop_back();
}
reverse(result.begin(), result.end());
return result;
}
// 高精度乘法函数
string multiply(const string &num1, const string &num2) {
vector<int> n1 = stringToVector(num1);
vector<int> n2 = stringToVector(num2);
vector<int> result(n1.size() + n2.size(), 0);
for (size_t i = 0; i < n1.size(); ++i) {
for (size_t j = 0; j < n2.size(); ++j) {
result[i + j] += n1[i] * n2[j];
result[i + j + 1] += result[i + j] / 10;
result[i + j] %= 10;
}
}
return vectorToString(result);
}
int main() {
string num1, num2;
cout << "请输入第一个大整数: ";
cin >> num1;
cout << "请输入第二个大整数: ";
cin >> num2;
string result = multiply(num1, num2);
cout << "乘积是: " << result << endl;
return 0;
}代码解释
-
stringToVector函数： - 将字符串表示的数字转换为整型数组，并倒序存储以便于后续计算。
-
vectorToString函数： - 将整型数组表示的数字转换为字符串，同时移除前导零。
-
multiply函数： - 实现高精度乘法，使用两个循环模拟手工乘法的过程。
result数组用于存储中间结果和最终结果，其大小为n1.size() + n2.size()。- 内部循环计算乘积，并处理进位。
-
main函数： - 读取用户输入的两个大整数，调用
multiply函数计算乘积，并输出结果。
这段代码能够处理非常大的整数乘法，但需要注意的是，对于极大的数字（如几万位以上的数字），可能会遇到性能问题或内存限制。在实际应用中，可以使用更高效的大整数库，如 GMP（GNU Multiple Precision Arithmetic Library）来处理超大整数的运算。
高精度除法
高精度除法是一种用于计算两个大整数相除的算法。它可以处理超出计算机正常字长限制的数字，从而实现高精度的除法运算。高精度除法遵循长除法原理，具体实现过程如下：
-
初始化：
- 将被除数（分子）和除数（分母）表示为一个由个位数字组成的数组。
- 将商（结果）数组和余数设置为0。
-
计算过程：
- 将余数数组与一位除数相乘，得到一个临时数组。
- 将临时数组与被除数数组进行比较。
- 如果临时数组小于或等于被除数数组，则将临时数组除以除数，得到商的这一位。
- 否则，减小商的这一位。
- 将商的这一位乘以除数，得到一个新的余数数组。
- 将新的余数数组与被除数数组相减，得到新的被除数数组。
- 重复上述步骤，直到被除数数组为0或达到所需的精度。
-
比较和减法：
- 比较临时数组和被除数数组至关重要，因为它决定了商的每一位的计算。
-
乘法：
- 将商的每一位乘以除数以获得新的余数。
-
减法：
- 将新的余数从被除数中减去以获得新的被除数。
-
输出结果：
- 采用倒序的方式输出，因为数据保存是倒序结构。
高精度除法广泛应用于密码学、科学计算、加密货币和其他需要高精度算术运算的领域。
在实现高精度除法时，需要注意以下几点：
高精度除法的实现代码可能因具体需求而有所不同，但基本原理和步骤是相似的。如果需要具体的代码实现，可以参考相关的编程教程或示例代码。
请注意，高精度除法涉及复杂的数学运算和数据处理，因此在实现时需要特别注意边界条件和错误处理。如果您在金融、医疗、法律等存在风险的领域使用高精度除法，请务必进行充分的测试和验证，并咨询相关领域的专家。
python代码
高精度除法通常涉及处理非常大的数字或需要非常精确的结果，这在许多编程语言中都可以实现。下面是一个使用Python实现高精度除法的示例代码。Python由于其内置的decimal模块，非常适合这种任务。
首先，你需要确保你的Python环境中安装了decimal模块（Python标准库中自带，无需额外安装）。这个模块提供了对任意精度十进制浮点数的支持。
以下是一个简单的示例，展示如何使用decimal模块来进行高精度除法：
from decimal import Decimal, getcontext
# 设置精度（例如：50位小数）
getcontext().prec = 50
# 定义两个高精度数字
num1 = Decimal('1234567890123456789012345678901234567890')
num2 = Decimal('98765432109876543210')
# 进行高精度除法
result = num1 / num2
# 打印结果
print("高精度除法结果：", result)在这个例子中，我们首先将decimal模块的精度设置为50位小数（你可以根据需要调整这个值）。然后，我们定义了两个高精度的十进制数num1和num2，并使用/运算符进行除法运算。最后，我们打印出除法的结果。
这个代码将输出一个非常精确的结果，包含多达50位的小数（如果结果的小数部分有那么多位的话）。
请注意，Decimal类型的数字在创建时应该使用字符串形式，以避免在创建时就丢失精度。例如，Decimal('0.1')比Decimal(0.1)更准确，因为后者在Python的浮点数表示中可能已经丢失了精度。
C++代码
高精度除法在C++中涉及到处理大整数或大浮点数的除法运算，这在标准数据类型（如int、long、double等）无法处理的情况下尤为重要。为了实现这一点，通常需要自己编写代码来处理字符串形式的数字，或者利用现有的高精度数学库。
下面是一个简单的高精度除法示例，它使用字符串来表示大整数，并进行模拟的手工除法：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
// 辅助函数：将字符串表示的数字转换为整数
int strToInt(const std::string& str) {
return std::stoi(str);
}
// 辅助函数：将整数转换为字符串
std::string intToStr(int num) {
return std::to_string(num);
}
// 高精度除法函数
std::string highPrecisionDivision(const std::string& numeratorStr, const std::string& denominatorStr) {
int numerator = strToInt(numeratorStr);
int denominator = strToInt(denominatorStr);
// 如果分母为0，则无法除法
if (denominator == 0) {
throw std::runtime_error("Denominator cannot be zero.");
}
// 结果存储为字符串
std::string result = "";
int temp = numerator;
// 模拟手工除法过程
while (temp >= denominator) {
result += intToStr(temp / denominator);
temp = temp % denominator * 10;
// 如果余数后补0后仍小于分母，则需要在结果中补0
if (temp < denominator) {
result += "0";
}
}
// 去除结果前导的0
size_t pos = result.find_first_not_of('0');
if (pos == std::string::npos) {
return "0";
} else {
return result.substr(pos);
}
}
int main() {
std::string numerator, denominator;
// 输入被除数和除数
std::cout << "Enter the numerator: ";
std::cin >> numerator;
std::cout << "Enter the denominator: ";
std::cin >> denominator;
try {
std::string result = highPrecisionDivision(numerator, denominator);
std::cout << "Result: " << result << std::endl;
} catch (const std::exception& e) {
std::cerr << e.what() << std::endl;
}
return 0;
}注意事项
-
局限性：上述代码仅适用于处理较小的整数，并且假设输入能够被
std::stoi正确转换为int。对于非常大的数字（超过int或long long的范围），这个方法将不适用。 -
扩展性：要处理真正的高精度（如几百位甚至更多位的数字），你需要实现一个完整的大整数类，该类能够存储和操作任意大小的数字。这通常涉及到字符串处理或数组/向量来存储每一位数字。
-
使用库：对于实际应用，考虑使用现有的高精度数学库，如GMP（GNU Multiple Precision Arithmetic Library）或Boost.Multiprecision，这些库提供了高效且健壮的高精度计算功能。
如果你需要处理超过标准数据类型限制的大数字，建议深入学习这些库的使用或实现自己的大整数类。
AC/OJ/洛谷代码（高精度）示例：
1268.高精度加法(oj.czos.cn里的题)：
题目：
答案（无注释）：
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[250],b[250],c[500];
int len1,len2;
int main(){
cin>>s1>>s2;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
len1=s1.length();
len2=s2.length();
for(int i=0;i<len1;i++)
{
a[i]=s1[len1-1-i]-'0';
}
for(int i=0;i<len2;i++)
{
b[i]=s2[len2-1-i]-'0';
}
int len=len1>len2?len1:len2;
for(int i=0;i<len;i++)
{
c[i]=a[i]+b[i];
}
for(int i=0;i<len;i++)
{
if(c[i]>=10)
{
c[i+1]=c[i+1]+c[i]/10;
c[i]%=10;
}
}
if(c[len]!=0) len++;
for(int i=len-1;i>=0;i--)
{
cout<<c[i];
}
return 0;
} 1269.高精度减法(oj.czos.cn里的题)：
题目：
提示：
- 注意退位。
- 注意负数及负号。
答案（无注释）：
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[250],b[250],c[250];
int len1,len2;
int main(){
cin>>s1>>s2;
if(s1==s2)
{
cout<<"0";
return 0;
}
len1=s1.size();
len2=s2.size();
char op='+';
if(len2>len1||len2==len1&&s2>s1)
{
op='-';
swap(s1,s2);
}
for(int i=0;i<s1.size();i++)
{
a[i]=s1[s1.size()-i-1]-'0';
}
for(int i=0;i<s2.size();i++)
{
b[i]=s2[s2.size()-i-1]-'0';
}
for(int i=0;i<s1.size();i++)
{
if(a[i]<b[i])
{
a[i]=10+a[i];
a[i+1]--;
}
c[i]=a[i]-b[i];
}
int sp=0;
for(int i=s1.size()-1;i>=0;i--)
if(c[i]!='0')
{
sp=i;
}
if(op=='-') cout<<op;
if(c[s1.size()-1]==0)
for(int i=s1.size()-2;i>=sp;i--)
cout<<c[i];
else
{
for(int i=s1.size()-1;i>=sp;i--)
cout<<c[i];
}
return 0;
} 1287.高精度乘(oj.czos.cn里的题)：
题目：
答案（无注释）：
#include<bits/stdc++.h>
using namespace std;
int a[1005],b[1005],c[1005];
int f=0;
int main(){
string s,s1;
cin>>s>>s1;
if(s=="0"||s1=="0")
{
cout<<"0";
return 0;
}
int len=1004;
for(int i=s.size()-1,j=0;i>=0;i--,j++)
a[j]=s[i]-'0';
for(int i=s1.size()-1,j=0;i>=0;i--,j++)
b[j]=s1[i]-'0';
for(int i=0;i<len;i++)
{
for(int j=0;j<=i;++j)
c[i]+=a[j]*b[i-j];
if(c[i]>=10)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
for(int i=len-1;i>=0;i--)
{
if(c[i]!=0&&f==0) f++;
if(f==1) cout<<c[i];
}
return 0;
}1271.高精度整数除法(oj.czos.cn里的题)：
题目：
答案（无注释）：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,n;
cin>>a>>b>>n;
cout<<a/b<<".";
int c=a%b;
for(int i=1;i<=n;i++){
c*=10;
cout<<c/b;
c%=b;
}
return 0;
}作者：programming expert
