论坛 › C\C++交流 › 舍罕王问题瞧一瞧

xieglt 发表于 2020-10-29 15:13:27

舍罕王问题瞧一瞧

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***********************************************************************************
用整形数组解决大数高精度计算问题
32位系统下 unsigned int 最大存储的数为：4294967296，因此可以考虑用数组来存储大数
为了防止最高位为1导致负数的问题，数组中每个元素最大只存储 999999999
为了解决溢出问题，在做乘法和除法的时候用到了内嵌汇编，某些编译器可能不支持
***********************************************************************************/
#define BASE        (1000000000)
#define        NUM_LEN        (9)
#define IS_INITED(p)        ((p->_num != 0) && (p->_initFlag == 0))

//定义一个结构体来存储大整数
typedef struct tagNumeric
{
        //存储大数的数组
        int * _num;
        //为数组分配的内存大小，以 int 为单位，计算字节数则为：_size * sizeof(int)
        int _size;
        //大数的长度，即数组中的有用长度
        int _len;
        //结构体初始化标记
        //鉴于某些编译器初始化变量，某些编译器不初始化变量
        //因此，认为 _initFlag == 0 && _num != 0 时，结构体被初始化
        int _initFlag;
}NUMERIC,*LPNUMERIC;

//初始化大整数结构体，为数组分配内存
int InitNumeric(LPNUMERIC pNum,int size)
{
        int nRet = 0;
        do
        {
                if(IS_INITED(pNum))
                {
                        break;
                }

                pNum->_num = (int *)malloc(size * sizeof(int));
                if(pNum->_num == 0)
                {
                        break;
                }

                memset(pNum->_num,0,size*sizeof(int));

                pNum->_len = 0;
                pNum->_initFlag = 0;
                pNum->_size = size;

                nRet = 1;
        }while(0);

        return nRet;
}

//当分配的内存不足以存储大整数时，为之重新分配内存
//建议为防止内存频繁地被重新分配，可以在初始化时分配大一点
int ReinitNumeric(LPNUMERIC pNum,int size)
{
        int nRet = 0;
       
        do
        {
                if(!IS_INITED(pNum))
                {
                        break;
                }
               
                if(size <= pNum->_size)
                {
                        break;
                }
               
                pNum->_num = (int *)realloc(pNum->_num,size*sizeof(int));

                if(pNum->_num == 0)
                {
                        break;
                }

                memset(pNum->_num + pNum->_size,0,(size - pNum->_size)*sizeof(int));
                pNum->_size = size;

                nRet = 1;
        }while(0);
       
        return nRet;
}

//释放内存
void UninitNumeric(LPNUMERIC pNum)
{
        if(IS_INITED(pNum))
        {
                free(pNum->_num);
                pNum->_num = 0;
        }
}

//给结构体一个初始整数值，这个值必须小于 1000000000
int SetNumber(LPNUMERIC pNum,int number)
{
        int nRet = 0;
       
        do
        {
                if(number >= BASE)
                {
                        break;
                }

                if(!IS_INITED(pNum) && InitNumeric(pNum,1)==0)
                {
                        break;
                }
               
                pNum->_num = number;
                pNum->_len = 1;

                nRet = 1;
        }while(0);

        return nRet;
}

//当需要给结构体一个大于999999999的初始值时，
//可以用字符串形式给它赋值，实例如下:
/*
        NUMERIC num;
        SetNumeric(&num,"1234567890987654321");
*/
int SetNumeric(LPNUMERIC pNum,char * number)
{
        int i = 0;
        int nRet = 0;
        char cByte = 0;
        int value = 0;
        int power = 0;
        int index =0;
        int nLen = strlen(number);
        int size = nLen / NUM_LEN + (nLen % NUM_LEN == 0 ? 0 : 1);

        do
        {
                if(nLen == 0)
                {
                        break;
                }
               
                if(!IS_INITED(pNum) && InitNumeric(pNum,size) == 0)
                {
                        break;
                }

                if(size > pNum->_size && ReinitNumeric(pNum,size) == 0)
                {
                        break;
                }
               
                for(i=0 ; i<nLen ; i++)
                {
                        if(number<'0' || number>'9')
                        {
                                break;
                        }
                }
                if(i < nLen--)
                {
                        break;
                }


                for(i=nLen ; i>=0 ; i--)
                {
                        if((nLen - i) % NUM_LEN == 0)
                        {
                                if(nLen - i != 0)
                                {
                                        pNum->_num = value;
                                }

                                value = 0;
                                power = 1;
                        }
                        cByte = number - 0x30;
                        value += power * cByte;
                        power *= 10;
                }

                if(value != 0)
                {
                        pNum->_num = value;
                }

                pNum->_len = index;               
                nRet = 1;
        }while(0);

        return nRet;
}

//将大整数转化成字符串，以便于输出。
//当 number 指针传 0 时，函数将返回转化成字符串所需要的内存空间
//实例如下:
/*
        int len =0;
        char * buffer;
        NUMERIC num;
        SetNumeric(&num,"12345678909876543121");
        len = Number2String(&num,0);
        buffer = (char *)malloc(len);
        Number2String(&num,buffer);

*/
int Number2String(LPNUMERIC pNum,char * number)
{
        int i = 0;
        int nRet = 0;
        char buffer = {0};
       
        do
        {
                if(!IS_INITED(pNum))
                {
                        break;
                }

                if(number == 0)
                {
                        nRet = pNum->_len * NUM_LEN + 1;
                        break;
                }

                number = 0;
               
                for(i=pNum->_len-1 ; i>=0 ; i--)
                {
                        if(i == pNum->_len-1)
                        {
                                sprintf(buffer,"%d",pNum->_num);
                        }
                        else
                        {
                                sprintf(buffer,"%09d",pNum->_num);
                        }
                        strcat(number,buffer);
                }

                nRet = strlen(number);
        }while(0);

        return nRet;
}

//大整数与一个 int 相加
int AddNumber(LPNUMERIC pNum,int number)
{
        int i;
        int nRet = 0;
        int carry = 0;
        unsigned int value = 0;
       
        do
        {
                if(!IS_INITED(pNum))
                {
                        break;
                }
               
                if(pNum->_size == pNum->_len && ReinitNumeric(pNum,pNum->_size + 1) == 0)
                {
                        break;
                }
                               
                for(i=0 ; i<pNum->_len ; i++)
                {
                        value = pNum->_num + number + carry;
                        pNum->_num = value % BASE;
                        carry = value / BASE;
                }
               
                if(carry != 0)
                {
                        pNum->_num = carry;
                }
                pNum->_len = i;
               
                nRet = 1;
        }while(0);
       
        return nRet;       
}

//大整数加另外一个大整数
int AddNumeric(LPNUMERIC pNum,LPNUMERIC pAdd)
{
        int i;
        int nRet = 0;
        int carry = 0;
        int size = 0;
        unsigned int value = 0;
       
        do
        {
                if(!IS_INITED(pNum) || !IS_INITED(pAdd))
                {
                        break;
                }
               
                if(pNum->_size < pAdd->_len)
                {
                        size = pAdd->_len + 1;
                }
                else if(pNum->_size == pNum->_len)
                {
                        size = pNum->_size + 1;
                }

                if(size != 0 && ReinitNumeric(pNum,size) == 0)
                {
                        break;
                }
               
                size = pNum->_len > pAdd->_len ? pNum->_len : pAdd->_len;

                for(i=0 ; i<size ; i++)
                {
                        value = carry;

                        if(i < pNum->_len)
                        {
                                value += pNum->_num;
                        }

                        if(i < pAdd->_len)
                        {
                                value += pAdd->_num;
                        }

                        pNum->_num = value % BASE;
                        carry = value / BASE;
                }
               
                if(carry != 0)
                {
                        pNum->_num = carry;
                }
                pNum->_len = i;
               
                nRet = 1;
        }while(0);
       
        return nRet;       
}

//大整数与一个 int 相乘
int MulNumber(LPNUMERIC pNum,int number)
{
        int i;
        int nRet = 0;
        int carry = 0;
        int * plong = 0;

        do
        {
                if(!IS_INITED(pNum))
                {
                        break;
                }

                if(pNum->_size == pNum->_len && ReinitNumeric(pNum,pNum->_size + 1) == 0)
                {
                        break;
                }

                plong = pNum->_num;

                _asm
                {
                        MOV ESI,plong
                }
               
                for(i=0 ; i<pNum->_len ; i++)
                {
                        _asm
                        {
                                MOV        EAX,
                                MUL number
                                ADD EAX,carry
                                ADC EDX,0
                                MOV EBX,BASE
                                DIV EBX
                                MOV ,EDX
                                MOV carry,EAX
                                ADD        ESI,4
                        }
                }

                if(carry != 0)
                {
                        pNum->_num = carry;
                }

                pNum->_len = i;

                nRet = 1;
        }while(0);

        return nRet;
}

//大整数与一个 int 相除
int DivNumber(LPNUMERIC pNum,int number)
{
        int nRet = 0;
        int carry = pNum->_len;
        int * plong = pNum->_num;

        do
        {
                if(!IS_INITED(pNum))
                {
                        break;
                }
               
                plong += (pNum->_len - 1);

                _asm
                {
                        MOV ECX,carry
                        MOV ESI,plong
                        XOR EDX,EDX
                _DivLoop:
                        MOV EAX,EDX
                        MOV EBX,BASE
                        MUL EBX
                        ADD EAX,
                        ADC EDX,0
                        MOV EBX,number
                        DIV EBX
                        MOV ,EAX
                        SUB ESI,4
                        TEST EAX,EAX
                        JNZ _NotZero
                        DEC carry
                _NotZero:
                        LOOP _DivLoop
                }

                pNum->_len = carry;

                nRet = 1;
        }while(0);

        return nRet;
}

//测试：计算一个数的阶乘
void Factorial(int n)
{
        int len = 0;
        char * buffer = 0;
        NUMERIC num;
        InitNumeric(&num,1000);
        SetNumber(&num,n);

        while(n > 2)
        {
                if(MulNumber(&num,--n) == 0)
                {
                        break;
                }
        }

        len = Number2String(&num,0);
        buffer = (char *)malloc(len);
        Number2String(&num,buffer);
        printf("%s\n",buffer);
        UninitNumeric(&num);
        free(buffer);
}

//测试：计算舍罕王应给的小麦
void test()
{
        int i = 0;
        char buffer = {0};
        NUMERIC num,num1;

        SetNumber(&num,1);
        SetNumber(&num1,1);

        for(i=1 ; i<64; i++)
        {
                MulNumber(&num1,2);
                AddNumeric(&num,&num1);
        }

        Number2String(&num,buffer);
        printf("舍罕王应该给依达尔 %s 粒麦子！\n",buffer);
        SetNumeric(&num1,buffer);
        DivNumber(&num1,25000);
        Number2String(&num1,buffer);

        printf("如果每 25000 粒麦子为 1 公斤，那么应该给 %s 公斤麦子！\n",buffer);
        UninitNumeric(&num);
        UninitNumeric(&num1);
}

int main()
{
        test();
        return 0;
}

xieglt 发表于 2020-10-29 15:16:55

舍罕王问题测试结果如图:

jackz007 发表于 2020-10-29 15:26:17

本帖最后由 jackz007 于 2020-10-29 15:34 编辑

      518 行源代码，是不是过于复杂，这道题只是用到了 64 位整型数的最大值，但是绝对没有超出，所以，全程使用 64 位无符号长整型数完全可以解决问题。
      我的代码运算的结果和你是完全一样的。
#include <stdio.h>
int main(void)
{
      unsigned long long d , result                     ;
      int i , k                                           ;
      for(result = 0 , i = 0 ; i < 64 ; i ++) {
                for(d = 1 , k = 0 ; k < i ; k ++) d = d * 2 ;
                result += d                                 ;
      }
      printf("\n")                                        ;
      printf("舍罕王需要付给达依尔的麦子数量为:\n")       ;
      printf("      %20I64u 粒\n" , result)             ;
      printf("      %20I64u kg\n" , result / 25000)   ;
      printf("\n")                                        ;
}
      下面是编译、运行实况：
D:\00.Excise\C>g++ -o sh sh.c

D:\00.Excise\C>sh

舍罕王需要付给达依尔的麦子数量为:
      18446744073709551615 粒
             737869762948382 kg


D:\00.Excise\C>

小甲鱼的铁粉 发表于 2020-10-29 16:16:22

占个楼{:10_254:}

xieglt 发表于 2020-10-29 16:19:27

jackz007 发表于 2020-10-29 15:26
518 行源代码，是不是过于复杂，这道题只是用到了 64 位整型数的最大值，但是绝对没有超出，所以， ...

是有点复杂，不过，程序不局限于算这个啊，还可以算别的
，比如说10000的阶乘。

查看完整版本: 舍罕王问题瞧一瞧