[已解决]高精度求助

额外减小

rt
OpenAI的垃圾ChatGPT请不要回答，谢谢。你的回复都是依托答辩。
好久没写高精度了。今天用c++重新写一遍，但是发现有很多漏洞,效率也很低，有人可以帮忙修正一下吗（在源代码的基础上），谢谢了。这是题目的网站。
注意，我要的不是AC代码模板，我想要在我原本代码的基础上的改进。（也可以说明我的问题在哪，我也会给你最佳）
代码如下。OpenAI的垃圾ChatGPT请不要回答，谢谢。你的回复都是依托答辩。

@zhangjinxuan @Mike_python小 @sfqxx @liuhongrun2022 @元豪

1. #include <iostream>
   
2. #include <typeinfo>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. inline int gjd_cmp(string a,string b)//a>b:return 1   a==b:return 0   a<b:return -1
   
7. {
   
8.         string num1(a),num2(b);
   
9.         while(num1[0]=='0' and num1.length()-1)
   
10.         {
    
11.                 num1.erase(0,1);
    
12.         }
    
13.         while(num2[0]=='0' and num2.length()-1)
    
14.         {
    
15.                 num2.erase(0,1);
    
16.         }
    
17.         if(num1.length()<num2.length())
    
18.         {
    
19.                 return -1;
    
20.         }
    
21.         if(num1.length()>num2.length())
    
22.         {
    
23.                 return 1;
    
24.         }
    
25.         for(int i=0,l=num1.length();i<l;i++)
    
26.         {
    
27.                 if(num1[i]>num2[i])
    
28.                 {
    
29.                         return 1;
    
30.                 }
    
31.                 if(num1[i]<num2[i])
    
32.                 {
    
33.                         return -1;
    
34.                 }
    
35.         }
    
36.         return 0;
    
37. }
    
38. 
    
39. inline string gjd_add(string a,string b)
    
40. {
    
41.         int sum=0;
    
42.         string num1(a),num2(b),ans;
    
43.         if(num1.length()>num2.length())
    
44.         {
    
45.                 num2.insert(0,num1.length()-num2.length(),'0');
    
46.         }
    
47.         else
    
48.         {
    
49.                 num1.insert(0,num2.length()-num1.length(),'0');
    
50.         }
    
51.         for(int i=num1.length()-1;i>=0;i--)
    
52.         {
    
53.                 sum+=num1[i]+num2[i]-2*'0';
    
54.                 ans.insert(0,1,sum%10+'0');
    
55.                 sum/=10;
    
56.         }
    
57.         if(sum)ans.insert(0,1,sum+'0');
    
58.         return ans;
    
59. }
    
60. 
    
61. inline string gjd_sub(string a,string b)
    
62. {
    
63.         int jw=0,op=0;
    
64.         string num1,num2,ans;//num1>num2
    
65.         if(gjd_cmp(a,b)>=0)num1=a,num2=b;
    
66.         else num1=b,num2=a,op=1;
    
67.         for(int i=num1.length()-1;i>=0;i--)
    
68.         {
    
69.                 if(num1[i]<num2[i]+jw)
    
70.                 {
    
71.                         ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
    
72.                         jw=1;
    
73.                 }
    
74.                 else
    
75.                 {
    
76.                         ans.insert(0,1,num1[i]-num2[i]-jw+'0');
    
77.                         jw=0;
    
78.                 }
    
79.         }
    
80.         while((ans[0]=='0')&&(ans.length()-1))
    
81.         {
    
82.                 ans.erase(0,1);
    
83.         }
    
84.         if(op)ans.insert(0,1,'-');
    
85.         return ans;
    
86. }
    
87. 
    
88. inline string gjd_sub1(string a,string b)
    
89. {
    
90.         int jw=0,op=0;
    
91.         string num1,num2,ans;//num1>num2
    
92.         if(gjd_cmp(a,b)>=0)num1=a,num2=b;
    
93.         else num1=b,num2=a,op=1;
    
94.         num2.insert(0,num1.length()-num2.length(),'0');
    
95.         for(int i=num1.length()-1;i>=0;i--)
    
96.         {
    
97.                 if(num1[i]<num2[i]+jw)
    
98.                 {
    
99.                         ans.insert(0,1,num1[i]+10-num2[i]-jw+'0');
    
100.                         jw=1;
     
101.                 }
     
102.                 else
     
103.                 {
     
104.                         ans.insert(0,1,num1[i]-num2[i]-jw+'0');
     
105.                         jw=0;
     
106.                 }
     
107.         }
     
108.         if(op)ans.insert(0,1,'-');
     
109.         return ans;
     
110. }
     
111. 
     
112. inline string gjd_mul(string a,string b)
     
113. {
     
114.         long long la=a.length(),lb=b.length();
     
115.         long long ia[la+50]={0},ib[lb+50]={0},ic[la+lb+100]={0};
     
116.        
     
117.         string ans;
     
118.         //num1.length()>num2.length()
     
119.         for(int i=la-1;i>-1;i--)
     
120.         {
     
121.                 ia[i]=a[la-i-1]-'0';
     
122.         }
     
123.         for(int i=lb-1;i>-1;i--)
     
124.         {
     
125.                 ib[i]=b[lb-i-1]-'0';
     
126.         }
     
127.         int sum=0,w=0;
     
128.         for(int i=0;i<la;i++)
     
129.         {
     
130.                 for(int j=0;j<lb;j++)
     
131.                 {
     
132.                         ic[i+j]+=ia[i]*ib[j];
     
133.                 }
     
134.         }
     
135.         for(int i=0;i<la+lb;i++)
     
136.         {
     
137.                 ic[i+1]+=ic[i]/10;
     
138.                 ans.insert(0,1,ic[i]%10+'0');
     
139.         }
     
140.         while((ans[0]=='0')&&(ans.length()-1))
     
141.         {
     
142.                 ans.erase(0,1);
     
143.         }
     
144.         return ans;
     
145. }
     
146. 
     
147. inline string gjd_div(string a,string b)
     
148. {
     
149.         string ans,tmp(a);
     
150.         if(gjd_cmp(a,b)==-1)return "0";
     
151.         if(gjd_cmp(a,b)==0)return "1";
     
152.         //a>b
     
153.         for(int i=b.length();i<=a.length();i++)
     
154.         {
     
155.                 if(gjd_cmp(tmp.substr(0,i),b)==-1)
     
156.                 {
     
157.                         ans.push_back('0');
     
158.                 }
     
159.                 else
     
160.                 {
     
161.                         for(int j=9;j>0;j--)
     
162.                         {
     
163.                                
     
164.                                 if(gjd_cmp(tmp.substr(0,i),gjd_mul(b,(string)""+(char)(j+'0')))!=-1)
     
165.                                 {
     
166.                                         tmp=gjd_sub1(tmp.substr(0,i),gjd_mul(b,(string)""+(char)(j+'0')))+tmp.substr(i,tmp.length());
     
167.                                         ans.push_back('0'+j);
     
168.                                         break;
     
169.                                 }
     
170.                         }
     
171.                 }
     
172.         }
     
173.         if(ans[0]=='0' and ans.length()-1) ans.erase(0,1);
     
174.         return ans;
     
175. }
     
176. 
     
177. inline string gjd_mod(string a,string b)
     
178. {
     
179.         return gjd_sub(a,gjd_mul(b,gjd_div(a,b)));
     
180. }
     
181. 
     
182. int main()
     
183. {
     
184.         string a,b;
     
185.         cin>>a>>b;
     
186.         string div=gjd_div(a,b);
     
187.         cout<<gjd_add(a,b)<<endl<<gjd_sub(a,b)<<endl<<gjd_mul(a,b)<<endl<<div<<endl<<gjd_sub(a,gjd_mul(b,div))<<endl;
     
188.        
     
189. }

复制代码

彩虹
https://www.luogu.com.cn/record/116845653

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-7-22 21:01:45

zhangjinxuan 发表于 2023-7-22 10:26
把加减乘除都实现啦

我给你悄悄说一声，我只会加减，不会乘除

kkksc003是这样说的：  

可以将a[ i ]*b[ j ]的贡献全都在中间产物的第 i+j-1 位上，可以把所有贡献算出来，最后一口气处理所有进位问题,代码很长，展示部分

1. for (int i = 1;i <= lena;i++)
   
2.     for(int j =1;j<= lenb;j++)
   
3.         c[i+j-1] += a[i]*b[i]//计算贡献
   
4. 
   

复制代码

@额外减小 不知道是否有帮助

跳转到最佳答案楼层

额外减小

注：好像主要是高精度减法函数的问题，大部分点都是line 2挂掉了

Mike_python小

你好！我可以帮助你改进你的高精度计算代码。我已经仔细阅读了你的代码，并发现了几个问题和改进的地方。下面是我对每个函数的建议：

1. gjd_cmp 函数：
   - 在比较字符串长度之前，确保 num1 和 num2 的长度大于 0。
   - 在最后用以比较大小的循环中，应该添加一个条件来处理当字符串长度相等时的情况。

2. gjd_add 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。

3. gjd_sub 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。
   - 可以简化代码逻辑，减少重复的判断语句。

4. gjd_sub1 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。
   - 可以简化代码逻辑，减少重复的判断语句。

5. gjd_mul 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。

6. gjd_div 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。
   - 可以使用 string 类型的构造函数简化代码。

7. gjd_mod 函数：
   - 使用引用传递来避免不必要的拷贝操作。
   - 在函数内部声明变量时，使用更具描述性的名称。

除了上述建议，你还可以考虑以下改进：

- 考虑使用 std::vector 或自定义的类来表示大整数，这样可以更方便地进行运算和处理。
- 优化乘法运算，可以使用 Karatsuba 算法或其他快速的大整数乘法算法。

希望以上建议对你有帮助！如果你有任何疑问，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

isdkz

首先，我非常高兴您在这里寻求帮助。我看到了你的代码，你已经非常接近解决问题了，但有几个地方可能需要改进，我会为你详细说明。

1. 函数gjd_cmp:
   在此函数中，你一直在删除数字前的0，这种方式相对效率较低。因为string的erase操作时间复杂度为O(n)。所以在数字长度非常长的情况下，这会浪费很多时间。我们可以直接找到第一个非零的位置，然后从那里开始比较，这样可以提高效率。

2. 函数gjd_sub和gjd_sub1:
   这两个函数几乎相同，只是在处理输入长度时有所不同。这可能会导致代码冗余。我们可以合并这两个函数，将处理长度的部分做成条件判断。

3. 函数gjd_mul:
   这个函数的效率可以进一步提高。在你的实现中，你遍历每一位，然后一位一位地进行乘法和加法，这实际上是一个O(n^2)的算法。有一种更好的方法叫做Karatsuba算法，该算法可以将复杂度降低到O(n^1.585)，这将大大提高效率。

4. 函数gjd_div:
   这个函数中，每一位都调用了乘法和比较函数，这可能会导致效率低下。实际上，你可以使用二分法找到每一位的值，这将大大提高效率。

以上就是我对你代码的一些改进建议。请注意，编写高精度计算的代码时，需要特别关注性能和效率。希望我的建议能够对你有所帮助，如果你还有其他问题，欢迎随时提问。

歌者文明清理员

币

Threebody1

币

Threebody1

币

额外减小

歌者文明清理员 发表于 2023-7-22 00:47
币

还不睡觉啊。

歌者文明清理员

额外减小 发表于 2023-7-22 00:50
还不睡觉啊。

是

额外减小

歌者文明清理员 发表于 2023-7-22 00:51
是

那你快看看我的代码罢。

歌者文明清理员

额外减小 发表于 2023-7-22 00:51
那你快看看我的代码罢。

我只看见了“回帖奖励”几个字

我不会C/C++

额外减小

歌者文明清理员 发表于 2023-7-22 00:54
我只看见了“回帖奖励”几个字

我不会C/C++

好吧

sfqxx

币

额外减小

sfqxx 发表于 2023-7-22 00:56
币

回答问题

sfqxx

额外减小 发表于 2023-7-22 00:57
回答问题

中了再说

isdkz

币

sfqxx

这种题你不用 python 可惜了

sfqxx

中奖绝缘体

额外减小

sfqxx 发表于 2023-7-22 01:05
这种题你不用 python 可惜了

我不想，python没法训练我的算法能力

sfqxx

额外减小 发表于 2023-7-22 01:12
我不想，python没法训练我的算法能力

。。。