最大公约数之大数运算
发布时间：2020-12-14 03:41:10 所属栏目：大数据 来源：网络整理
导读：举个例子： 1020 12 1020 % 12 我们这样模拟： str1 - str2= str1 1020 - 120 = 900 ? ?(str2末尾填0，直到str1,str2相差一位) 900 ?- 120 = 780 780 ?- 120 = 660 660 ?- 120 = 540 540 ?- 120 = 420 420 ?- 120 = 300 300 ?- 120 = 180 180 ?- 120 = 60 ?
|
举个例子：>> 1020 12
1020 % 12 我们这样模拟： str1 - str2= str1 1020 - 120 = 900 ? ?(str2末尾填0，直到str1,str2相差一位) 900 ?- 120 = 780 780 ?- 120 = 660 660 ?- 120 = 540 540 ?- 120 = 420 420 ?- 120 = 300 300 ?- 120 = 180 180 ?- 120 = 60 ? ?(注意：此时快速减法已经达到临界点，需要执行str2 = strt = 12) 60 ? - 12 ?= 48 48 ? - 12 ?= 36 36 ? - 12 ?= 24 24 ? - 12 ?= 12 12 ? - 12 ?= 0 ? ? (此时：str1 < strt = 12,break进入main) ----------- r = str1 = 0; 由于str1 = str2 = 12;str2 = r = 0;跳出main()函数while()循环，结果就是12. ?再举个例子： >> 6 5 ?6 % 5 如下模拟： ?str1 - str2 = str1 ?6 ? ?- ?5 ? = 1 ? (此时：str1 < str2 = strt = 12,break进入main) ?5 ? ?- ?1 ? = 4 ?4 ? ?- ?1 ? = 3 ?3 ? ?- ?1 ? = 2 ?2 ? ?- ?1 ? = 1 ?1 ? ?- ?1 ? = 0 ? (此时：str1 < str2 = strt = 1,break进入main) ?---------- r = str1 = 0; 由于str1 = str2 = 1;str2 = r = 0;跳出main()函数while()循环，结果就是1. 思路：如：>>1020 12? 我们用大数减法来模拟大数取余，(直到：str1 < str2)才退出循环，注意用字符串模拟整数时大小的判断。 ?思路：如：>>103 24 字符串按位相减，我们从最末位开始相减，也就是个位，这时牵涉到借位问题。 /*
FileName: 最大公约数之大数运算.cpp
Author: Dojking
Version : V1.0
Date:2014/3/16
Function List:
1.int main() 主函数
2.void swap(); 交换两数
3.void strmod(); 模拟大数取余
4.void strsub(); 模拟大数减法
History:
<author> <time> <version > <desc>
Dojking 2014/3/16 1.0 build
*/
/*************************************************
Function: void swap()
Description: 该函数用于交换两字符串
Calls: 无
Called By:
1.main()
Table Accessed: 无
Table Updated: 无
Input: 无
Output: 无
Return: 无
Others:
思路：交换两字符串时，需要注意，字符串是按位比较的，我们是用字符串来模拟大整数。
所以需要在结合字符串的长度和大小一起来判断。
*************************************************/
/*************************************************
Function: void strmod()
Description: 该函数用于模拟大数取余
Calls: 无
Called By:
1.main()
Table Accessed: 无
Table Updated: 无
Input: 无
Output: 无
Return: 无
Others:
思路：我们用大数减法来模拟大数取余，(直到：str1 < str2)才退出循环，注意用字符串模拟整数时大小的判断。
其中需要注意一个问题：我们这里是用快速减法来模拟取余的，何为快速减法？
比如：1020 - 12 ，我们直接用1020 - 120 相当于一次减了10次12，此时str2 = 120，当str1 < 120时就退出了。
这不是我们想要的结果，所以，我们在快速减法进行到临界点的时候，又将str2 = strt = 12;(strt为我们首先保存的str2值)
*************************************************/
/*************************************************
Function: void strsub()
Description: 该函数用于模拟大数减法
Calls: 无
Called By:
1.strmod()
Table Accessed: 无
Table Updated: 无
Input: 无
Output: 无
Return: 无
Others:
思路：字符串按位相减，我们从最末位开始相减，也就是个位，这时牵涉到借位问题。
str1 str2
比如： 103 - 24
按位相减：个位3-4需要借位，而十位却是0,。我们是这样处理的。
将个位：3+10 - 4 = 9 (已借位)。而十位0被借之后，本来是-1，但是字符串只能储存一位，我们用f来代表-1。
str1 str2
变成：1f3 - 24 个位：9
现在求十位：f - 2又需要借位，f为-1，我们直接这样计算：-1+10-2 = 7
str1 str2
现在变成：073 - 24 个位，十位：97
然后，最前面的0，直接填在后面：970
最后去掉后面无效的0，并逆序，得到结果：79
*************************************************/
/************************************************
举个例子：>> 1020 12
1020 % 12 我们这样模拟：
str1 - str2= str1
1020 - 120 = 900 (str2末尾填0，直到str1,str2相差一位)
900 - 120 = 780
780 - 120 = 660
660 - 120 = 540
540 - 120 = 420
420 - 120 = 300
300 - 120 = 180
180 - 120 = 60 (注意：此时快速减法已经达到临界点，需要执行str2 = strt = 12)
60 - 12 = 48
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0 (此时：str1 < strt = 12,break进入main)
-----------
r = str1 = 0;
由于str1 = str2 = 12;str2 = r = 0;跳出main()函数while()循环，结果就是12.
再举个例子： >> 6 5
6 % 5 如下模拟：
str1 - str2 = str1
6 - 5 = 1 (此时：str1 < str2 = strt = 12,break进入main)
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0 (此时：str1 < str2 = strt = 1,break进入main)
----------
r = str1 = 0;
由于str1 = str2 = 1;str2 = r = 0;跳出main()函数while()循环，结果就是1.
*************************************************/
#include <iostream>
#include <string>
using namespace std;
string r,str1,str2,strt; /*str1：大数1，str2：大数2，r：每步的余数*/
void swap() /*交换str1,str2*/
{
string temp;
temp = str2;
str2 = str1;
str1 = temp;
}
void strsub() /*该函数用大数减法，模拟取余*/
{
int i,j,len;
int len1 = str1.size(); /*得到str1长度*/
int len2 = str2.size();
string str,mod;
while (len1-1 > len2) /*使str1,str2位数相差一位*/
{
str2 += '0'; /*增长str2*/
++len2;
}
for (i = len1-1,j=len2-1; j >= 0; --i,--j) /*模拟减法*/
{
if (str1[i] < str2[j] || str1[i] == 'f') /*需要借位，f表示-1*/
{
if (str1[i-1] != '0') /*高位不为0*/
{
str1[i-1] -= 1; /*向高位借位*/
}
else /*高位为0，借位后变为-1，用f表示-1*/
{
str1[i-1] = 'f'; /* f = -1 */
}
if (str1[i] != 'f') /*本位不为f，执行 '-' 操作*/
str += ((str1[i]-'0')+10-(str2[j]-'0')+'0');
else /*本位为f，直接用-1代替*/
str += ((-1+10)-(str2[j]-'0')+'0');
}
else /*不需要借位，直接 '-' 操作*/
{
str += ((str1[i]-'0')-(str2[j]-'0')+'0');
}
}
if (len1 != len2) /*如果str1,str2长度不等，则需要单独对最高位操作*/
str += str1[0]; /*最高位*/
len = str.size()-1;
while (str[len] == '0' && len != 0) /*去掉相减后高位上的无效0。(len!=0：防止只有一个0的情况)*/
{
--len;
}
while (len >= 0) /*逆序*/
{
mod += str[len];
--len;
}
str1 = mod; /*将中间结果赋值给str1，准备进行下一次strmod()操作*/
// cout<<"str1 = "<<str1<<",str2 = "<<str2<<endl;
}
void strmod() /*此函数作用相当于 str1 %= str2，注意str1,str2都是全局变量*/
{
while (1)
{
if (str1.size() > str2.size() || (str1 >= str2 && str1.size() == str2.size()))/*假设将str1,str2看做数字，当str1<str2时跳出*/
strsub(); /*进行大数减法，模拟取余*/
else if (str1.size() > strt.size() || (str1 > strt && str1.size() == strt.size())) /*防止快速减法带来的错误*/
str2 = strt;
else
break;
}
}
int main()
{
while (1)
{
cin>>str1>>str2; /*输入两个大数*/
if (str1[0] == '0' || str2[0] == '0') /*请不要输入0*/
{
cout<<"input error"<<endl;
break;
}
if (str1 < str2 && str1.size() <= str2.size()) /*如果str1 < str2，则交换*/
{
swap(); /*使str1 > str2*/
}
while (str2[0] != '0') /*大数取余运算*/
{
strt = str2; /*保存str2值，用于strmod()函数临时比较时用*/
strmod(); /*此函数作用相当于 str1 %= str2，注意str1,str2都是全局变量*/
r = str1; /*交换str1,str2两数*/
str1 = str2;
str2 = r;
}
cout<<str1<<endl; /*输出求余结果*/
}
return 0;
}
转载请保留原文地址：http://www.voidcn.com/article/p-ecaaalsx-xw.html （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |