[北大OJ](1001)求幂算法

题目描述:

img

题目样本:

img

思路:

  • 常见的int,double,long已经满足不了那么高精度的数值
  • 我们可以用字符串存入字符数组中,再进行计算
  • 例如1.23和1.23相乘
  • 从字符串的输入,从小数点位置判断出小数点后的位数,这里是2位
  • 在字符串中去掉小数点,这里是123
  • 然后取数依次相乘,产生的进位相加,根据位置再错位相加,这里是
  • 123
  • 0246
  • 00369
  • 得到字符串是15129
  • 然后两个乘数的小数点位数和是4,所以结果的小数点也移动4位
  • 则结果是1.5129
  • 乘法运算就完成了,因为是字符串,所以位数可以特别长
  • 特别注意:首位相乘产生的进位要单独存放,因为每一位数在[0,9]之间
  • 最大计算值为81,,只有一个进位

然后看下代码:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
void rmpoint(char[], int*);
void chen(char[], char[]);
void addpoint(char[], char[], int);
int main()
{
    char n1[7], n2[410], n3[410];
    int a, p, i;
    /*输入基数和指数*/
    while (scanf("%s %d", n1, &a) != EOF)
    {
        rmpoint(n1, &p);/*将基数和指数存入字符串*/
        strcpy(n2, n1);
        for (i = 0; i < a - 1; i++)
        {
            chen(n1, n2);
        }
        p = p * a;
        if (p != 0)
        {
            addpoint(n2, n3, p);
        }
        printf("%s\n", n3);
    }
    return 0;
}
void rmpoint(char a[], int* c)
{
    int i, j, p, c1;
    c1 = 0;
    //char b[205];
    p = strlen(a);
    for (i = 0, j = 0; i < p; i++)
    {
        if (a[i] == '.')
        {
            c1 = p - 1 - i;
            continue;
        }
        a[j] = a[i];
        j++;
    }

    *c = c1;
    a[j] = 0;
}
void chen(char a[], char b[])
{
    int c[410] = { 0 };
    int i, j, sum, k, k1;
    k = 409;
    k1 = 409;
    for (i = strlen(a) - 1; i >= 0; i--)
    {
        for (j = strlen(b) - 1; j >= 0; j--, k--)
        {
            sum = (a[i] - '0') * (b[j] - '0') + c[k];
            c[k - 1] = c[k - 1] + sum / 10;
            c[k] = sum % 10;
        }
        k = --k1;
    }
    for (i = 0; i < 410; i++)
    {
        if (c[i] != 0)
        {
            break;
        }
    }
    for (j = i, i = 0; j < 410; i++, j++)
    {
        b[i] = c[j] + '0';
    }
    b[i] = 0;
}
void addpoint(char a[], char b[], int p)
{
    int i, j, p1, p2, j1, min;
    p2 = 0;
    p1 = strlen(a);
    if (p1 >= p)
    {
        p = p1 - p;
        for (i = p1 - 1; i >= 0; i--)
        {
            if (a[i] != '0')
            {
                break;
            }
            p2++;
        }
        if (p1 - p2 < p)
        {
            min = p;
        }
        else
        {
            min = p1 - p2;
        }
        for (i = 0, j = 0; i < min; i++, j++)
        {
            if (p == i)
            {
                b[j] = '.';
                i--;
                p--;
                continue;
            }
            b[j] = a[i];
        }
        b[j] = 0;
    }
    else
    {
        b[0] = '.';
        p = p - p1;
        for (i = p1 - 1,j1 = 0; p1 >= 0; i--)
        {
            if (a[i] != '0')
            {
                break;
            }
            j1++;
        }
        for (i = 1, j = 0; j < p; j++, i++)
        {
            b[i] = '0';
        }

        for (j = 0; j < p1 - j1; i++, j++)
        {
            b[i] = a[j];
        }
        b[i] = 0;
    }
}

我们根据上述思路进行一个程序的剖析

首先,基数为字符串,存入数组内,然后指数为数值,存放在一个变量内,用户从键盘输入

img

n1数组用于输入字符串,a变量用于输入指数,其他的变量我们不管

然后进入到repoint函数内,此函数的功能是:从小数点的位置判断出小数点后的后的位数,如何实现?看代码

img

n1数组作为形参被传入进a数组中,p变量的地址作为形参传入指针C中(因为程序需要在函数内计算小数点前有几位,则需要改变p变量的值,在此之前,p变量并未初始化,则通过传址调用让p在函数内改变其值)

定义了变量i,j,p,c1,他们的功能如下:

  • p存放字符串的长度(不包括空字符)
  • i控制字符数组下标,通过循环找到存放‘.’(小数点)字符的数组下标
  • j用来控制去除小数点
  • c1存放小数点后的位置

模拟输入

我们假设输入的数值为样本数值的:95.123

进入程序后,n1存储的字符串为95.123,p存储的为0,在这一步程序将记录小数点后的位数,和去除小数点

进入循环后:

img

第一次循环(strlen函数返回字符串长度,不包括空字符,所以95.123为6)

  • i=0,a[i]=9,判断为假,则j=0,a[j]=a[i]=9,j自增为1

第二次循环

  • i=1,a[i]=5,判断为假,则j=1,a[j]=a[i]=5,j自增为2

第三次循环

  • i=2,a[i]=. ,判断为真,进入if语句,c1=6-1-2=3,然后之间进入下一段循环,这时j依旧为2

第四次循环

  • i=3,a[i]=1,判断为假,则j=2,a[j]=a[i]=1,j自增为3

第五次循环

  • i=4,a[i]=2,判断为假,则j=3,a[j]=a[i]=2,j自增为4

第六次循环

  • i=5,a[i]=3,判断为假,则j=4,a[j]=a[i]=3,j自增为5

到这里循环结束,进入下面的语句

  • *c=c1,这时将临时变量c1的值为3,存入形参指针c内,指针c指向的是实参p的地址,到这一步p的地址内已经存入了3这个数值
  • a[j]=0,这时a[j]对应的地址为a[5],则a[5]=0,注意,这时是将a数组下标为5的地址赋空,而不是等于0!!!

函数结束,形参a数组为实参n1数组,在函数内,n1数组被转换成了95123。

这时程序将n1字符串利用strcpy函数拷贝进n2,进入下一个循环

img

这段循环的作用是,完成指数的目的,依次对两数进行相乘,我们这边假设存入a地址为12

进入chen函数

img

这时我们需要定义一个临时数组c,存放每次相乘后的结果。k和k1是控制c数组的下标,形参a、b两数组均为95123

进入第一个循环,循环从字符串最后一位开始

第一个循环控制第一个数组a,第二个循环控制第二个数组b,像冒泡算法一样,依次取出a数组中的数去遍历b数组,在第二个循环中进行相乘运算。

我们先来看看字符数组中对应的ASCII码

img附录1

img附录2

第一趟的第一次循环(i均为4)

  • i=4,a[i]=3,进入循环,j=4,b[j]=3,c[k]=0,进入运算后,sum=9
  • k=409,k数组在这之前全部赋空,则程序会默认把所有数值都赋为0
  • c[k-1]=0+0.9,但这时c数组的类型为int,所以不算小数,表明无进位
  • c[k]=9%10,得到的值为0余9,则c[k]也等于9
  • 总结一下c数组:c[409]=9,k[408]=0
  • 此时c数组的值为00

第二次循环

  • i=4,a[i]=3,进入循环,j=3,b[j]=2,进入运算后,sum=6
  • k=408,c[k-1]=0+0.6,c[407]=0
  • c[k]=6%10,c[k]=6
  • 总结一下c数组:c[409]=9,k[408]=6,c[407]=0
  • 此时c数组的值为069

第三次循环

  • i=4,a[i]=3,进入循环,j=2,b[j]=1,进入循环后,sum=3
  • k=407,c[k-1]=0+0.1,c[406]=0
  • c[k]=3%10,c[k]=3
  • 总结一下c数组:c[409]=9,k[408]=6,c[407]=3,c[406]=0
  • 此时c数组的值为0369

第四次循环(重点)

  • 注意,在这循环内已经有进位,注意c数组的变化
  • i=4,a[i]=3,进入循环,j=1,b[j]=5,进入循环后,sum=15
  • k=406,c[k-1]=0+1.5,c[405]=1
  • c[k]=15&10,得到的结果为5(15/10=1余5)
  • 总结一下:c[409]=9,k[408]=6,c[407]=3,c[406]=5,c[405]=1
  • 此时c数组的值为:15369

第五次循环(重点)

  • i=4,a[i]=3,进入循环,j=0,b[j]=9,进入循环后
  • sum = (a[i] - '0') * (b[j] - '0') + c[k];
  • sum=3*9+1=28
  • k=405,c[k-1]=0+28/10=2.8,为整数类型,则c[k-1]=2
  • c[k]=sum%10,c[k]=8
  • 总结一下:c[409]=9,k[408]=6,c[407]=3,c[406]=5,c[405]=8,c[404]=2

第六次循环

  • j=5,不满足循环条件,退出循环
  • k=--k1,k1自减后等于408
  • 这是c数组尾端开始的值为:285369

第一趟的模拟已经结束,我们怎么理解这一趟循环呢?可以在纸上手算一下3*95123,依次计算。是不是得出来的值是285369

那么这一循环的作用就是依次拿出字符串内的一个数去像另外一个数组做遍历,依次相乘,然后进位相加,我们可以推导出后面五趟的结果

第二趟

img

i为3,对应的a[i]=2,*b[4]=*3这时k为408,对应的c[k]为6,对应的c[k-1]为3,

  • 第一次循环,sum=12,c[407]=3+1=4,c[408]=2,数组为:285429

i为3,对应的a[i]=2,b[j]=2,这时k为407,对应的c[k]为4,对应的c[k-1]为5,

  • 第二次循环,sum=8,c[406]=5+0=5,c[407]=8,数组为:285829

i为3,对应的a[i]=2,b[j]=1,这时k为406,对应的c[k]为5,对应的c[k-1]为8

  • 第三次循环,sum=7,c[405]=0+8=8,c[406]=7,数组为:287829

i为3,对应的a[i]=2,b[j]=5,这时k为405,对应的c[k]为8,对应的c[k-1]为2

  • 第四次循环,sum=18,c[404]=2+1=3,c[405]=8,数组为:387829

i为3,对应的a[i]=2,b[j]=9,这时k为404,对应的c[k]为3,对应的c[k-1]为0

  • 第五次循环,sum=21,c[403]=0+2=2,c[404]=1,数组为:2187829

第六次循环

  • j=5,不满足循环条件,退出循环
  • k=--k1,k1自减后等于407
  • 这是c数组尾端开始的值为:0.....0....02187829

第二趟结果出来后,手算下23*95123,得到的结果为2187829,在这时已经能大致明白里面的奥秘,我们根据前边的思路做一个总结

  • 我们第一次进入chen函数的是95123*95123
  • 00000285369
  • 00001902460
  • 00009512300
  • 00475615000
  • 08561070000
  • 最后下来得到:9048385129

那么我们第一个循环的作用就明白了,字符串相乘,数组都在0-9之间,遍历后,前一位为进位,后一位为相乘结果,通过取模和除法得到进位和余位的值,进位相加,完成两数相乘的功能,因为从尾端开始,我们可以这样理解

  • 95123*3
  • 95123*20
  • 95123*100
  • 95123*5000
  • 95123*90000

每取到一个数,结果的下标都要前进一位,这儿可以对应程序中的k=--k1,因为从尾部开始,是个位,十位等逐个相乘,对于此程序来说,K是控制余位,而k-1则是控制进位,而i和j则是控制两个字符串的相乘

这个循环弄懂了,我们进入下一个循环

img

这个循环的作用就是遍历数组直到i下标中的值不为0停止,这时i的下标已经到了c数组中存放的两数相乘的结果,对应上述的就是9048385129,到达9的下标为c[400]

img

这时让j=i=400,i=0,重置两个下标的位置,让形参b也就是第二个字符串,对应的实参为n2

我们直接加一段输出函数输出循环的运作过程

img

我们可以看到,在第一次进入循环后,对应附录一,此循环功能是把每一次计算出来的结果传入n2数组中,n1始终为输入的基数

  • 第一个循环的作用是找到计算结果的第一个字符,达到了抑制前导0
  • 第二个循环的作用是将结果传入第二个数组中,进行下一步的循环

在上述过程完成十二次以后,结束了调用chen函数,进行下一步,此时n2数组内的值应该为95123的12次方。值为:

img

接下来按照之前的思路,是添加小数点了,这时需要计算小数点后有几位,在这一步之前,变量p在rmpoint函数后已经记录了小数点,在模拟当中,字符串为95.123,小数点后为3位

img

就要进入函数,addpoint函数,我们来看一下这段函数的代码并且讲解它的第一个循环:

img

形参a对应实参n2,形参b对应实参n3,形参p对应实参p,n2为计算的结果,n3为一个空数组,用于存放添加小数点后的结果,p为小数点后的总和,这里3*12是36

首先程序定义了6个变量,i和j毫无疑问是控制循环和下标的,p1到这里被赋值了字符串的位数,p2被赋空,进入第一个判断,如果这个字符串的长度大于数组后的位数,则进入第一个if语块,这儿肯定是大于的

img

首先p等于小数点的总位数减去小数点后的位数,这儿是总长度(不包括空字符)和小数点后的长度

img

相减后p=24,这时进入循环,从a数组的尾字符开始遍历,寻找不为0的字符,然后跳出循环,这儿起到:不打印不重要的尾随0

那么这时p2作为计数变量,计算循环走了多少次,实际上就是计算尾随0有多少位

这里p2的值为0

img

然后进入下一个if块,判断的表达式是p1-p2<p,这段语句就是判断总长度减去尾随0的长度是否要小于小数点前的位数

如果小于,则:min存放小数点前的位数,这里min=24

如果不小于,则:min存放总长度减去尾随0的长度,这里min=60

然后进入for循环,这个循环的作用就是添加小数点,从头开始遍历整个数组,然后将实参n2中的结果依次存入n3当中,知道循环走到p的位置,在这儿让实参n3[24]存入小数点字符,因为这时n2中并无小数点字符,则要把全部结果传入n3中,i必须自减调到之前的字符来

p自减完全是不执行此判断,这儿p可以变为任何数,只要不让i再次等于它就行

最后依次传入最后的字符,就完成了这一步骤

如果字符串的长度要小于或等于字符串后的位数(这个else块语句的作用就是不打印前导0)

img

如果结果要小于字符串的位置,就代表无整数部分,进入else语块

首先肯定是将实参n3数组的第一位存入小数点字符,然后进入第一个循环,

p=p-p1就是将字符串后的位数减去字符串总长度,得到结果相差多少字符(与实际结果相差多少个10的p次方)

第一个循环的作用是从字符串尾端开始,找到存放数组不为字符0的数组位置

j1作为计数数组,主要功能就是记录尾随0有多少位

第二个循环的作用就是让从下标1开始往n3数组中添加0字符,达到相差倍数的作用

i已经走过上列的循环,现在i下标所指向的数在0后面,第三个循环是从0后面逐渐向n3数组存入结果,最后将字符串结尾赋空

这儿最好赋为空字符,好理解一点!

img

用0.123示范输出结果:

img

总结

此算法第一步是去除小数点,让用两个数组,控制出小数点的下标

第二步是依次相乘,进位相加,这个和手算一样的步骤,在纸上模拟并能写出对应的程序,将结果存放到一个数组中

第三步是添加小数点,这儿要判断,首先题目的要求是:

  • 不输出前导0
  • 不输出尾随0

这儿对应的情况是基数无整数部分,如0.123

和基数有整数部分:如12.0,则不添加小数点

和基数有整数和小数部分:如95.123,对应位置添加小数点然后从小数点的位置依次复制进新的数组

其中无整数部分比较难,需要去判断相差几位然后补0,最后在依次复制进新的数组内,最后补空字符

此算法来自:北大OJ评论区

此思路来自:CDNS大佬————air_shark

感谢上述两位大佬我才能如此顺利的练习此算法!

本文链接:

https://nullcode.fun/85.html
1 + 4 =
快来做第一个评论的人吧~