没有合适的资源?快使用搜索试试~ 我知道了~
大整数运算(运行环境VC++2005).pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 135 浏览量
2021-10-08
06:50:49
上传
评论
收藏 28KB PDF 举报
温馨提示
试读
27页
大整数运算(运行环境VC++2005).pdf
资源推荐
资源详情
资源评论
大整数运算
1、伪代码
conv(s1,a);A 字符串转九位的大整数数
conv(s2,b);B 字符串转九位的大整数数
if ( "+" )
add(a,b,c); 加法运算,并统计运算时间
if ( "-" )
sub(a,b,c); 减法运算,并统计运算时间
if ( "*" )
MUL(a,b,c); 乘法运算,并统计运算时间
if ( "/" )
div(a,b,c,d); 除法运算,并统计运算时间
if ( "%")
yu(a,b,c,d); 求余运算,并统计运算时间
if ( "^ " )
eyzhi(a,b,c); 指数运算,并统计运算时间
if ( "^2 " ) (则不输入大整数 B)
MUL(a,a,c); 平方运算,并统计运算时间
2、用户使用说明
本软件使用简单, 界面友好, 用鼠标点击操作, 与市场上买的计算器一样使
用。该软件由 0~9 个数字键和 9 个功能键组成,其中“ C”键为清除键,首先大
数 A,再输入“ +,—, *,/ ”四个运算符进行所需的加减乘除运算,还有, “%,
^”即求余,指数两个运算符,再次输入大数 B,最后按“ =”键输出结果,并显
示时间,而平方运算,只需输入大数 A,再按“ ^2”键,即可得到结果,并显示
时间,如需重新计算,则按“ C”键,进行清零。
3、程序(运行环境 VC++2005)
#pragma once
#include <string>
#include <iostream>
# include <time.h>
#include <cmath>
# include <conio.h>
# include <windows.h>
using namespace std;
const int Bit = 9;
//Bit :大数中的一位可表示的整形数位数
const int MaxBitValue = ( int )pow(10.0,Bit);
//MaxBitValue :进位数
const int BigIntLen = 10000;
//BigIntLen :大数的位数,可表示 BigIntLen*Bit 位整形数
typedef int BigInt[BigIntLen];
//BigInt :大整数标示符, BigInt 等价于 int [BigIntLen]
void conv( char *s,BigInt a){
// 将字符串 s 转为大整数 a
memset(a,0, sizeof ( int )*BigIntLen);
int as=0,e,ten;
for ( int i=( int )strlen(s)-1;i>=0;i-=Bit){
e = 0; ten = 1;
for ( int j=0;j<Bit&&i-j>=0;j++){
e += (s[i-j]- '0' )*ten;
ten *= 10;
}
a[++as]=e;
}
a[0]=as;
}
int cmp( const BigInt a, const BigInt b){
// 大整数比较:若 a>b返回,若 a=b返回,否则返回 -1
int la=a[0],lb=b[0];
if (la>lb) return 1;
if (la<lb) return -1;
for ( int i=la;i>=1;i--){
if (a[i]>b[i]) return 1;
if (a[i]<b[i]) return -1;
}
return 0;
}
void add( const BigInt a, const BigInt b,BigInt c){
// 大整数加法: c=a+b
memset(c,0, sizeof ( int )*BigIntLen);;
int i=0,la=a[0],lb=b[0];
for (i=1;;i++){
if (i>la&&i>lb) break ;
c[i] += a[i] + b[i];
if (c[i]>=MaxBitValue){
c[i+1]++;
c[i]-=MaxBitValue;
}
}
while (c[i]==0&&i>1) i--;
c[0]=i;
}
void sub( const BigInt a, const BigInt b,BigInt c){
// 大整数减法: c=a-b
memset(c,0, sizeof ( int )*BigIntLen);
int i=0,la=a[0],lb=b[0];
for (i=1;;i++){
if (i>la&&i>lb) break ;
if (cmp(a,b)==1)
c[i] += a[i]-b[i];
if (cmp(a,b)==-1)
c[i] +=b[i]-a[i];
if (c[i]<0){
c[i+1]--;
c[i]+=MaxBitValue;
}
}
while (c[i]==0&&i>1) i--;
c[0]=i;
}
void MUL(const BigInt a, const BigInt b,BigInt c){
// 大整数乘法: c=a*b
memset(c,0, sizeof ( int )*BigIntLen);
int i,j,k; __int64 t;
for (i=1;i<=a[0];i++)
for (j=1;j<=b[0];j++){
t = (( __int64 )a[i])*b[j] + c[i+j-1];
c[i+j-1] = ( int )(t%MaxBitValue);
c[i+j] += ( int )(t/MaxBitValue);
}
k=i+j+1;
while (c[k]==0&&k>1) k--;
c[0]=k;
}
void mul( const BigInt A, const int b,BigInt C){
// 大整数与 Int 数乘法: C=A*b;
memset(C,0, sizeof ( int )*BigIntLen);
int i=0; __int64 t;
for (i=1;i<=A[0];i++){
t = C[i] + A[i]*(( __int64 )b);
if (t>=MaxBitValue){
C[i+1] += ( int )(t/MaxBitValue);
t%=MaxBitValue;
}
C[i] = ( int )t;
}
while (C[i]==0&&i>1) i--;
C[0]=i;
}
void leftShift(BigInt a, const int b){
// 大整数左移移位运算
int l=a[0];
for ( int i=l+1;i>1;i--)
a[i] = a[i-1];
a[1] = b;
if (a[l+1]!=0) a[0]++;
}
void div( const BigInt a, const BigInt b,BigInt c,BigInt d){
memset(c,0, sizeof ( int )*BigIntLen);memset(d,0, sizeof (int )*BigIntLen);
if ((b[0]==0||b[0]==1)&&b[1]==0)
return ; // 零除错误,退出
BigInt td,tb;
int t_max,t_mid,t_min,la=a[0],lb=b[0],lc=la,ld=0; // 二分辅助变量
double b_min=b[lb],b_max=b_min+1,d_max=0,d_min=0;
if (lb>1){
b_min = b_min*MaxBitValue + b[lb-1];
b_max = b_min + 1;
}
for ( int i=la;i>=1;i--){
leftShift(d,a[i]);
if (cmp(b,d)==1) continue ;
ld = d[0]; d_min = d[ld];
while (d_min<b_min)
d_min = d_min*MaxBitValue + d[ld-1];
d_max = d_min+1;
t_max = ( int )(d_max/b_min) + 1,t_min = ( int )(d_min/b_max)-1;
while ( true ){ // 二分查找一位商
t_mid = (t_max + t_min)/2;
mul(b,t_mid,tb);
if (cmp(tb,d)==1){
t_max = t_mid-1;
continue ;
}
sub(d,tb,td);
if (cmp(td,b)>=0){
t_min = t_mid+1;
continue ;
}
break ;
}
memcpy(d,td, sizeof ( int )*BigIntLen);
c[i] = t_mid;
}
while (c[lc]==0&&lc>1) lc--;
c[0]=lc;
}
void yu( const BigInt a, const BigInt b,BigInt c,BigInt d){
memset(c,0, sizeof ( int )*BigIntLen);memset(d,0, sizeof (int )*BigIntLen);
if ((b[0]==0||b[0]==1)&&b[1]==0)
return ; // 零除错误,退出
BigInt td,tb,h;
int t_max,t_mid,t_min,la=a[0],lb=b[0],lc=la,ld=0,o; // 二分辅助变量
double b_min=b[lb],b_max=b_min+1,d_max=0,d_min=0;
if (lb>1){
b_min = b_min*MaxBitValue + b[lb-1];
b_max = b_min + 1;
}
for ( int i=la;i>=1;i--){
leftShift(d,a[i]);
if (cmp(b,d)==1) continue ;
剩余26页未读,继续阅读
资源评论
maodi_lzc
- 粉丝: 1
- 资源: 4万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功