C程序设计C程序设计 (59).pdf
C C程序设计程序设计Programming in CProgramming in C函数之间实现批量数据传递函数之间实现批量数据传递1、大数类型的接口设计2、大数类型的实现C C程序设计程序设计程序设计程序设计3 36.3.2 6.3.2 数组参数的传递机制数组参数的传递机制【大数运算和高精度运算】计算整数3333333333333333333333333333333333+-2222222222222222222222222222222222加、减、乘、除四则运算。4 46.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析C语言现有的数据类型0184467440737095516158unsigned long long intunsigned _int64无符号长长整型9223372036854775807-92233720368547758088long long int_int64长长整型042949672954unsigned long无符号长整型-2147483648+21474836474long长整型042949672954unsigned int无符号整型-2147483648+21474836474int整型数值范围内存长度类型标识符类型5 56.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析显然，这是一个大数计算问题。大数计算的运算对象和结果精度一般是少则数十位，多则几万位。在C语言内置数据类型中，精度最多只有二十多位，数值位数的长度是有限的。因此，大数计算不能直接用C语言的内置数据类型实现出来。所以，编写程序时，需要首先设计出能够表示“大数”的数据类型，再设计算法求解。6 66.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（1）由于需要表示无限位的整数，所以用整型数组来存放大数，定义为“大数类型”。例如：intint A A N N;/大数类型/大数类型需要特别规定：A0存放大数最高位下标的偏移值（相对于A2）A1存放大数的符号，为1表示正数，为-1表示负数A2存放个位，A3存放十位，A4存放百位，AA0+2存放最高位。7 76.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（2）从“用户”角度来讲，如果输入输出3333333333333333333333333333333333、2222222222222222222222222222222222的数据是直观的和方便的。但scanf、printf不支持像这样的大整数输入输出。为此，可以考虑使用字符数组。按字符数组的方式调用scanf、printf函数（%s格式），并设计字符数组形式的“大数”转换为“大数类型”的函数str2big。8 86.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（3）设计“大数类型”相关的转换函数/将字符数组“大整数”s转换为“大数类型”A/将字符数组“大整数”s转换为“大数类型”Avoidvoid str2bigstr2big(charchar s s,intint A A););/将C语言整型n转换为“大数类型”A/将C语言整型n转换为“大数类型”Avoidvoid int2bigint2big(intint n n,intint A A););9 96.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（4）设计“大数类型”的输入输出函数voidvoid printprint(intint A A););/向控制台输出“大数类型”/向控制台输出“大数类型”voidvoid scanscan(intint A A););/从控制台输入“大数类型”/从控制台输入“大数类型”10106.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（5）设计“大数类型”的实用函数voidvoid assignassign(intint A A,intint B B););/“大数类型”赋值 A=B/“大数类型”赋值 A=Bvoidvoid zerojustifyzerojustify(intint A A););/调整大数A中高位无意义的0/调整大数A中高位无意义的0intint comparecompare(intint A A,intint B B););/“大数类型”比较 AB返回-1,A=B返回0,AB返回-1,A=B返回0,AA：R=-(B-A)逐位相减15156.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析逐位相减算法：算法从低位开始减，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减被减数，如果减不了，就要借位后再去减，同时置借位为1，否则置借位为0。16166.3.2 6.3.2 数组参数的传递机制数组参数的传递机制12345678671234345798减数被减数减数被减数-初始化借位为0，各对应位相减后再减上借位数1、借位为1初始化借位为0，各对应位相减后再减上借位数1、借位为19 92、借位为12、借位为16 63、借位为03、借位为00 04、借位为04、借位为02 2由低位向高位相加计算，直至所有运算结束由低位向高位相加计算，直至所有运算结束17176.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（9）MulMul(intint A A,intint B B,intint R R)函数实现算法：初始令row=A，R=0，由B的个位开始。执行r=r+row B次，即R=row*B的某位row=row*10处理B的高位重复执行18186.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（10）DivDiv(intint A A,intint B B,intint R R)函数实现算法：基本思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。先分别调整A和B的符号初始令row=A，tmp=0，R=0，按A逐位执行：19196.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例题分析（10）DivDiv(intint A A,intint B B,intint R R)函数实现算法：row=row*10，row位长为A某位值若row不小于B逐位相减 row-B，R对应位为相减数（即除法结果）重复执行重复执行20206.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.601#include#include 2#include#include 3#define max(a,b)(a)(b)?(a):(b)#define max(a,b)(a)(b)?(a):(b)4#define N 102#define N 102/大数类型最大位数+2/大数类型最大位数+25 voidvoid AddAdd(intint A A,intint B B,intint R R););/大数加法函数/大数加法函数6 voidvoid SubSub(intint A A,intint B B,intint R R););/大数减法函数/大数减法函数7 voidvoid MulMul(intint A A,intint B B,intint R R););/大数乘法函数/大数乘法函数8 voidvoid DivDiv(intint A A,intint B B,intint R R););/大数除法函数/大数除法函数9/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数10 voidvoid str2bigstr2big(charchar s s,intint A A)/nnnnnn=A/nnnnnn=A11 /字符串形式的“大数”转换为大数类型/字符串形式的“大数”转换为大数类型12 intint i i;13 forfor(i i=0 0;i i 0 0;i i-)-)21216.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.601#include#include 2#include#include 3#define max(a,b)(a)(b)?(a):(b)#define max(a,b)(a)(b)?(a):(b)4#define N 102#define N 102/大数类型最大位数+2/大数类型最大位数+25 voidvoid AddAdd(intint A A,intint B B,intint R R););/大数加法函数/大数加法函数6 voidvoid SubSub(intint A A,intint B B,intint R R););/大数减法函数/大数减法函数7 voidvoid MulMul(intint A A,intint B B,intint R R););/大数乘法函数/大数乘法函数8 voidvoid DivDiv(intint A A,intint B B,intint R R););/大数除法函数/大数除法函数9/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数10 voidvoid str2bigstr2big(charchar s s,intint A A)/nnnnnn=A/nnnnnn=A11 /字符串形式的“大数”转换为大数类型/字符串形式的“大数”转换为大数类型12 intint i i;13 forfor(i i=0 0;i i 0 0;i i-)-)22226.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.601#include#include 2#include#include 3#define max(a,b)(a)(b)?(a):(b)#define max(a,b)(a)(b)?(a):(b)4#define N 102#define N 102/大数类型最大位数+2/大数类型最大位数+25 voidvoid AddAdd(intint A A,intint B B,intint R R););/大数加法函数/大数加法函数6 voidvoid SubSub(intint A A,intint B B,intint R R););/大数减法函数/大数减法函数7 voidvoid MulMul(intint A A,intint B B,intint R R););/大数乘法函数/大数乘法函数8 voidvoid DivDiv(intint A A,intint B B,intint R R););/大数除法函数/大数除法函数9/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数10 voidvoid str2bigstr2big(charchar s s,intint A A)/nnnnnn=A/nnnnnn=A11 /字符串形式的“大数”转换为大数类型/字符串形式的“大数”转换为大数类型12 intint i i;13 forfor(i i=0 0;i i 0 0;i i-)-)23236.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.6016 A A 0 0+;+;/记录最高位索引/记录最高位索引17 A A A A 0 0+2 2=s s i i-0;-0;/字符转换为数值/字符转换为数值18 19 ifif(s s 0 0=-)=-)A A 1 1=-=-1 1;/符号为负/符号为负20 elseelse /否则为正数/否则为正数21 A A 0 0+;+;22 A A A A 0 0+2 2=s s 0 0-0;-0;23 A A 1 1=1 1;/符号为正/符号为正24 25 26 voidvoid int2bigint2big(intint n n,intint A A)27 /整型转换为大数类型/整型转换为大数类型28 intint i i,t t;29 forfor(i i=0 0;i i N N;i i+)+)A A i i=0 0;/初始化/初始化30 A A 0 0=-=-1 1;/初始时为NaN/初始时为NaN24246.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.6016 A A 0 0+;+;/记录最高位索引/记录最高位索引17 A A A A 0 0+2 2=s s i i-0;-0;/字符转换为数值/字符转换为数值18 19 ifif(s s 0 0=-)=-)A A 1 1=-=-1 1;/符号为负/符号为负20 elseelse /否则为正数/否则为正数21 A A 0 0+;+;22 A A A A 0 0+2 2=s s 0 0-0;-0;23 A A 1 1=1 1;/符号为正/符号为正24 25 26 voidvoid int2bigint2big(intint n n,intint A A)27 /整型转换为大数类型/整型转换为大数类型28 intint i i,t t;29 forfor(i i=0 0;i i=0 0?1 1:-:-1 1;/由n确定符号/由n确定符号32 t t=n n=0 0?n?n:-:-n n;33 whilewhile(t t 0 0)/将n每1位设置到大数中/将n每1位设置到大数中34 A A 0 0+;+;35 A A A A 0 0+2 2 =t t%1010;36 t t=t t/1010;37 38 ifif(n n=0 0)A A 0 0=0 0;/n为0，则大数也为0/n为0，则大数也为039 40 voidvoid printprint(intint A A)41 /输出大数/输出大数42 intint i i;43 ifif(A A 1 1=-=-1 1)printfprintf(-);(-);/输出负号/输出负号44 forfor(i i=A A 0 0;i i=0 0;i i-)-)45 printfprintf(%d,(%d,A A i i+2 2););26266.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.6031 A A 1 1=n n=0 0?1 1:-:-1 1;/由n确定符号/由n确定符号32 t t=n n=0 0?n?n:-:-n n;33 whilewhile(t t 0 0)/将n每1位设置到大数中/将n每1位设置到大数中34 A A 0 0+;+;35 A A A A 0 0+2 2 =t t%1010;36 t t=t t/1010;37 38 ifif(n n=0 0)A A 0 0=0 0;/n为0，则大数也为0/n为0，则大数也为039 40 voidvoid printprint(intint A A)41 /输出大数/输出大数42 intint i i;43 ifif(A A 1 1=-=-1 1)printfprintf(-);(-);/输出负号/输出负号44 forfor(i i=A A 0 0;i i=0 0;i i-)-)45 printfprintf(%d,(%d,A A i i+2 2););27276.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.6046 printfprintf(nn););47 48 voidvoid scanscan(intint A A)49 /输入大数（字符串形式大整数）/输入大数（字符串形式大整数）50 charchar s s N N-2 2;51 scanfscanf(%s,(%s,s s););/输入大整数-nnnnnn/输入大整数-nnnnnn52 str2bigstr2big(s s,A A););53 54 voidvoid assignassign(intint A A,intint B B)55 /大数赋值A=B/大数赋值A=B56 intint i i;57 forfor(i i=0 0;i i 0 0&A A A A 0 0+2 2 =0 0)62 A A 0 0-;-;/大数高位中的0无意义/大数高位中的0无意义63 ifif(A A 0 0=0 0&A A 2 2=0 0)64 A A 1 1=1 1;/避免出现-0/避免出现-065 66 intint comparecompare(intint A A,intint B B)67 /比较A和B-1(AB)0(A=B)1(AB)0(A=B)1(AB)68 intint i i;69 ifif(A A 1 1=-=-1 1&B B 1 1=1 1)returnreturn 1 1;/A-B+/A-B-/A+B-71 ifif(B B 0 0 A A 0 0)returnreturn A A 1 1;/同号不同位数/同号不同位数72 ifif(A A 0 0 B B 0 0)returnreturn-1 1*A A 1 1;/同号不同位数/同号不同位数73 forfor(i i=A A 0 0;i i=0 0;i i-)-)/同号同位数/同号同位数74 ifif(A A i i+2 2 B B i i+2 2 )returnreturn-1 1*A A 1 1;75 ifif(B B i i+2 2 A A i i+2 2 )returnreturn A A 1 1;29296.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.6076 77 returnreturn 0 0;/相等/相等78 79 voidvoid digitshiftdigitshift(intint A A,intint n n)80 /计算A*10n/计算A*10n81 intint i i;82 ifif(A A 0 0=0 0&A A 2 2=0 0)returnreturn;/为0/为083 forfor(i i=A A 0 0;i i=0 0;i i-)-)84 A A i i+n n+2 2 =A A i i+2 2;/大数向左移动n位/大数向左移动n位85 forfor(i i=0 0;i i n n;i i+)+)86 A A i i+2 2 =0 0;/低n位为0/低n位为087 A A 0 0=A A 0 0+n n;/大数位长增加n/大数位长增加n88 89 voidvoid AddAdd(intint A A,intint B B,intint R R)90 /大数加法R=A+B/大数加法R=A+B30306.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.6091 intint i i,c c=0 0;/c为进位/c为进位92 int2bigint2big(0 0,R R););/R=0/R=093 ifif(A A 1 1=B B 1 1)R R 1 1=A A 1 1;/A、B同号/A、B同号94 elseelse 95 ifif(A A 1 1=-=-1 1)/A-则R=B-A/A-则R=B-A96 A A 1 1=1 1;97 SubSub(B B,A A,R R););98 A A 1 1=-=-1 1;99 100 elseelse /B-则R=A-B/B-则R=A-B101 B B 1 1=1 1;102 SubSub(A A,B B,R R););103 B B 1 1=-=-1 1;104 105 returnreturn;31316.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.60106 107 R R 0 0=maxmax(A A 0 0,B B 0 0)+)+1 1;/和的位长/和的位长108 forfor(i i=0 0;i i=R R 0 0;i i+)+)/逐位相加，考虑进位/逐位相加，考虑进位109 R R i i+2 2 =(=(c c+A A i i+2 2 +B B i i+2 2)%)%1010;110 c c=(=(c c+A A i i+2 2 +B B i i+2 2)/)/1010;111 112 zerojustifyzerojustify(R R););113 114 voidvoid SubSub(intint A A,intint B B,intint R R)115 /大数减法R=A-B/大数减法R=A-B116 intint i i,v v,b b=0 0;/b为借位/b为借位117 int2bigint2big(0 0,R R););/R=0/R=0118 ifif(A A 1 1=-=-1 1|B B 1 1=-=-1 1)/R=A-B,R=-A-B做加法/R=A-B,R=-A-B做加法119 B B 1 1=-=-1 1*B B 1 1;120 AddAdd(A A,B B,R R););32326.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.60106 107 R R 0 0=maxmax(A A 0 0,B B 0 0)+)+1 1;/和的位长/和的位长108 forfor(i i=0 0;i i=A则R=-(B-A)/BA则R=-(B-A)125 SubSub(B B,A A,R R););126 R R 1 1=-=-1 1;127 returnreturn;128 129 R R 0 0=maxmax(A A 0 0,B B 0 0););/减的位长/减的位长130 forfor(i i=0 0;i i=0 0)b b=0 0;133 ifif(v v 0 0)/处理借位/处理借位134 v v=v v+1010;135 b b=1 1;34346.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.60136 137 R R i i+2 2=v v%1010;138 139 zerojustifyzerojustify(R R););140 141 voidvoid MulMul(intint A A,intint B B,intint R R)142 /大数乘法R=AxB/大数乘法R=AxB143 intint tmptmp N N,rowrow N N;144 intint i i,j j;145 int2bigint2big(0 0,R R););/R=0/R=0146 assignassign(rowrow,A A););/row=A/row=A147 forfor(i i=0 0;i i=B B 0 0;i i+)+)/B逐位乘A/B逐位乘A148 forfor(j j=1 1;j j=B B i i+2 2;j j+)+)/多次相加/多次相加149 AddAdd(R R,rowrow,tmptmp););/R=R+row*B/R=R+row*B150 assignassign(R R,tmptmp););35356.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.60136 137 R R i i+2 2=v v%1010;138 139 zerojustifyzerojustify(R R););140 141 voidvoid MulMul(intint A A,intint B B,intint R R)142 /大数乘法R=AxB/大数乘法R=AxB143 intint tmptmp N N,rowrow N N;144 intint i i,j j;145 int2bigint2big(0 0,R R););/R=0/R=0146 assignassign(rowrow,A A););/row=A/row=A147 forfor(i i=0 0;i i=B B 0 0;i i+)+)/B逐位乘A/B逐位乘A148 forfor(j j=1 1;j j=0 0;i i-)-)171 digitshiftdigitshift(rowrow,1 1););/row=row*10/row=row*10172 rowrow 2 2 =A A i i+2 2;173 R R i i+2 2 =0 0;174 whilewhile(comparecompare(rowrow,B B)!=)!=1 1)/rowB/rowB175 R R i i+2 2+;+;/结果为相减次数/结果为相减次数176 SubSub(rowrow,B B,tmptmp););/逐位相减 row-B/逐位相减 row-B177 assignassign(rowrow,tmptmp););178 179 180 zerojustifyzerojustify(R R););39396.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.60181 A A 1 1=asignasign;/A符号还原/A符号还原182 B B 1 1=bsignbsign;/B符号还原/B符号还原183 184 intint mainmain()()185 /调用大数运算函数计算结果/调用大数运算函数计算结果186 intint c c,A A N N,B B N N,R R N N,Z Z N N;187 printfprintf(a=);(a=);188 scanscan(A A););/输入大数A/输入大数A189 printfprintf(b=);(b=);190 scanscan(B B););/输入大数B/输入大数B191 AddAdd(A A,B B,R R););/计算大数加法R=A+B/计算大数加法R=A+B192 printfprintf(a+b=);(a+b=);193 printprint(R R););194 c c=comparecompare(A A,B B););/大数比较/大数比较195 printfprintf(a%s b(a%s bnn,c c=0 0?=:(=:(c c :);40406.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.60196 SubSub(A A,B B,R R););/计算大数减法R=A-B/计算大数减法R=A-B197 printfprintf(a-b=);(a-b=);198 printprint(R R););199 MulMul(A A,B B,R R););/计算大数乘法R=AxB/计算大数乘法R=AxB200 printfprintf(a*b=);(a*b=);201 printprint(R R););202 int2bigint2big(0 0,Z Z););203 ifif(comparecompare(Z Z,B B)=)=0 0)printfprintf(a/b=NaN(a/b=NaNnn););/不能除0/不能除0204 elseelse 205 DivDiv(A A,B B,R R););/计算大数除法R=A/B/计算大数除法R=A/B206 printfprintf(a/b=);(a/b=);207 printprint(R R););208 209 returnreturn 0 0;210 41416.3.2 6.3.2 数组参数的传递机制数组参数的传递机制例6.601#include#include 2#include#include 3#define max(a,b)(a)(b)?(a):(b)#define max(a,b)(a)(b)?(a):(b)4#define N 102/大数类型最大位数+2#define N 102/大数类型最大位数+25 void Add(int A,int B,int R);/大数加法函数void Add(int A,int B,int R);/大数加法函数6 void Sub(int A,int B,int R);/大数减法函数void Sub(int A,int B,int R);/大数减法函数7 void Mul(int A,int B,int R);/大数乘法函数void Mul(int A,int B,int R);/大数乘法函数8 void Div(int A,int B,int R);/大数除法函数void Div(int A,int B,int R);/大数除法函数9/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数/使用整型数组表示大数类型：其中A0=位数 A1=符号 A2.大数10 void str2big(char s,int A)/nnnnnn=Avoid str2big(char s,int A)/nnnnnn=A11 /字符串形式的“大数”转换为大数类型/字符串形式的“大数”转换为大数类型12 int i;int i;13 for(i=0;iN;i+)Ai=0;/初始化for(i=0;i0;i-)for(i=strlen(s)-1;i0;i-)a+b=5555555555555555555555555555555555a ba-b=1111111111111111111111111111111111a*b=7407407407407407407407407407407405925925925925925925925925925925926a/b=133333333333333333333333333333333332222222222222222222222222222222222结束结束
