鱼C论坛

 找回密码
 立即注册
查看: 1172|回复: 4

[技术交流] 舍罕王问题瞧一瞧

[复制链接]
发表于 2020-10-29 15:13:27 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

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

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

  27. //初始化大整数结构体,为数组分配内存
  28. int InitNumeric(LPNUMERIC pNum,int size)
  29. {
  30.         int nRet = 0;
  31.         do
  32.         {
  33.                 if(IS_INITED(pNum))
  34.                 {
  35.                         break;
  36.                 }

  37.                 pNum->_num = (int *)malloc(size * sizeof(int));
  38.                 if(pNum->_num == 0)
  39.                 {
  40.                         break;
  41.                 }

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

  43.                 pNum->_len = 0;
  44.                 pNum->_initFlag = 0;
  45.                 pNum->_size = size;

  46.                 nRet = 1;
  47.         }while(0);

  48.         return nRet;
  49. }

  50. //当分配的内存不足以存储大整数时,为之重新分配内存
  51. //建议为防止内存频繁地被重新分配,可以在初始化时分配大一点
  52. int ReinitNumeric(LPNUMERIC pNum,int size)
  53. {
  54.         int nRet = 0;
  55.        
  56.         do
  57.         {
  58.                 if(!IS_INITED(pNum))
  59.                 {
  60.                         break;
  61.                 }
  62.                
  63.                 if(size <= pNum->_size)
  64.                 {
  65.                         break;
  66.                 }
  67.                
  68.                 pNum->_num = (int *)realloc(pNum->_num,size*sizeof(int));

  69.                 if(pNum->_num == 0)
  70.                 {
  71.                         break;
  72.                 }

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

  75.                 nRet = 1;
  76.         }while(0);
  77.        
  78.         return nRet;
  79. }

  80. //释放内存
  81. void UninitNumeric(LPNUMERIC pNum)
  82. {
  83.         if(IS_INITED(pNum))
  84.         {
  85.                 free(pNum->_num);
  86.                 pNum->_num = 0;
  87.         }
  88. }

  89. //给结构体一个初始整数值,这个值必须小于 1000000000
  90. int SetNumber(LPNUMERIC pNum,int number)
  91. {
  92.         int nRet = 0;
  93.        
  94.         do
  95.         {
  96.                 if(number >= BASE)
  97.                 {
  98.                         break;
  99.                 }

  100.                 if(!IS_INITED(pNum) && InitNumeric(pNum,1)==0)
  101.                 {
  102.                         break;
  103.                 }
  104.                
  105.                 pNum->_num[0] = number;
  106.                 pNum->_len = 1;

  107.                 nRet = 1;
  108.         }while(0);

  109.         return nRet;
  110. }

  111. //当需要给结构体一个大于999999999的初始值时,
  112. //可以用字符串形式给它赋值,实例如下:
  113. /*
  114.         NUMERIC num;
  115.         SetNumeric(&num,"1234567890987654321");
  116. */
  117. int SetNumeric(LPNUMERIC pNum,char * number)
  118. {
  119.         int i = 0;
  120.         int nRet = 0;
  121.         char cByte = 0;
  122.         int value = 0;
  123.         int power = 0;
  124.         int index =0;
  125.         int nLen = strlen(number);
  126.         int size = nLen / NUM_LEN + (nLen % NUM_LEN == 0 ? 0 : 1);

  127.         do
  128.         {
  129.                 if(nLen == 0)
  130.                 {
  131.                         break;
  132.                 }
  133.                
  134.                 if(!IS_INITED(pNum) && InitNumeric(pNum,size) == 0)
  135.                 {
  136.                         break;
  137.                 }

  138.                 if(size > pNum->_size && ReinitNumeric(pNum,size) == 0)
  139.                 {
  140.                         break;
  141.                 }
  142.                
  143.                 for(i=0 ; i<nLen ; i++)
  144.                 {
  145.                         if(number[i]<'0' || number[i]>'9')
  146.                         {
  147.                                 break;
  148.                         }
  149.                 }
  150.                 if(i < nLen--)
  151.                 {
  152.                         break;
  153.                 }


  154.                 for(i=nLen ; i>=0 ; i--)
  155.                 {
  156.                         if((nLen - i) % NUM_LEN == 0)
  157.                         {
  158.                                 if(nLen - i != 0)
  159.                                 {
  160.                                         pNum->_num[index++] = value;
  161.                                 }

  162.                                 value = 0;
  163.                                 power = 1;
  164.                         }
  165.                         cByte = number[i] - 0x30;
  166.                         value += power * cByte;
  167.                         power *= 10;
  168.                 }

  169.                 if(value != 0)
  170.                 {
  171.                         pNum->_num[index++] = value;
  172.                 }

  173.                 pNum->_len = index;               
  174.                 nRet = 1;
  175.         }while(0);

  176.         return nRet;
  177. }

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

  189. */
  190. int Number2String(LPNUMERIC pNum,char * number)
  191. {
  192.         int i = 0;
  193.         int nRet = 0;
  194.         char buffer[16] = {0};
  195.        
  196.         do
  197.         {
  198.                 if(!IS_INITED(pNum))
  199.                 {
  200.                         break;
  201.                 }

  202.                 if(number == 0)
  203.                 {
  204.                         nRet = pNum->_len * NUM_LEN + 1;
  205.                         break;
  206.                 }

  207.                 number[0] = 0;
  208.                
  209.                 for(i=pNum->_len-1 ; i>=0 ; i--)
  210.                 {
  211.                         if(i == pNum->_len-1)
  212.                         {
  213.                                 sprintf(buffer,"%d",pNum->_num[i]);
  214.                         }
  215.                         else
  216.                         {
  217.                                 sprintf(buffer,"%09d",pNum->_num[i]);
  218.                         }
  219.                         strcat(number,buffer);
  220.                 }

  221.                 nRet = strlen(number);
  222.         }while(0);

  223.         return nRet;
  224. }

  225. //大整数与一个 int 相加
  226. int AddNumber(LPNUMERIC pNum,int number)
  227. {
  228.         int i;
  229.         int nRet = 0;
  230.         int carry = 0;
  231.         unsigned int value = 0;
  232.        
  233.         do
  234.         {
  235.                 if(!IS_INITED(pNum))
  236.                 {
  237.                         break;
  238.                 }
  239.                
  240.                 if(pNum->_size == pNum->_len && ReinitNumeric(pNum,pNum->_size + 1) == 0)
  241.                 {
  242.                         break;
  243.                 }
  244.                                
  245.                 for(i=0 ; i<pNum->_len ; i++)
  246.                 {
  247.                         value = pNum->_num[i] + number + carry;
  248.                         pNum->_num[i] = value % BASE;
  249.                         carry = value / BASE;
  250.                 }
  251.                
  252.                 if(carry != 0)
  253.                 {
  254.                         pNum->_num[i++] = carry;
  255.                 }
  256.                 pNum->_len = i;
  257.                
  258.                 nRet = 1;
  259.         }while(0);
  260.        
  261.         return nRet;       
  262. }

  263. //大整数加另外一个大整数
  264. int AddNumeric(LPNUMERIC pNum,LPNUMERIC pAdd)
  265. {
  266.         int i;
  267.         int nRet = 0;
  268.         int carry = 0;
  269.         int size = 0;
  270.         unsigned int value = 0;
  271.        
  272.         do
  273.         {
  274.                 if(!IS_INITED(pNum) || !IS_INITED(pAdd))
  275.                 {
  276.                         break;
  277.                 }
  278.                
  279.                 if(pNum->_size < pAdd->_len)
  280.                 {
  281.                         size = pAdd->_len + 1;
  282.                 }
  283.                 else if(pNum->_size == pNum->_len)
  284.                 {
  285.                         size = pNum->_size + 1;
  286.                 }

  287.                 if(size != 0 && ReinitNumeric(pNum,size) == 0)
  288.                 {
  289.                         break;
  290.                 }
  291.                
  292.                 size = pNum->_len > pAdd->_len ? pNum->_len : pAdd->_len;

  293.                 for(i=0 ; i<size ; i++)
  294.                 {
  295.                         value = carry;

  296.                         if(i < pNum->_len)
  297.                         {
  298.                                 value += pNum->_num[i];
  299.                         }

  300.                         if(i < pAdd->_len)
  301.                         {
  302.                                 value += pAdd->_num[i];
  303.                         }

  304.                         pNum->_num[i] = value % BASE;
  305.                         carry = value / BASE;
  306.                 }
  307.                
  308.                 if(carry != 0)
  309.                 {
  310.                         pNum->_num[i++] = carry;
  311.                 }
  312.                 pNum->_len = i;
  313.                
  314.                 nRet = 1;
  315.         }while(0);
  316.        
  317.         return nRet;       
  318. }

  319. //大整数与一个 int 相乘
  320. int MulNumber(LPNUMERIC pNum,int number)
  321. {
  322.         int i;
  323.         int nRet = 0;
  324.         int carry = 0;
  325.         int * plong = 0;

  326.         do
  327.         {
  328.                 if(!IS_INITED(pNum))
  329.                 {
  330.                         break;
  331.                 }

  332.                 if(pNum->_size == pNum->_len && ReinitNumeric(pNum,pNum->_size + 1) == 0)
  333.                 {
  334.                         break;
  335.                 }

  336.                 plong = pNum->_num;

  337.                 _asm
  338.                 {
  339.                         MOV ESI,plong
  340.                 }
  341.                
  342.                 for(i=0 ; i<pNum->_len ; i++)
  343.                 {
  344.                         _asm
  345.                         {
  346.                                 MOV        EAX,[ESI]
  347.                                 MUL number
  348.                                 ADD EAX,carry
  349.                                 ADC EDX,0
  350.                                 MOV EBX,BASE
  351.                                 DIV EBX
  352.                                 MOV [ESI],EDX
  353.                                 MOV carry,EAX
  354.                                 ADD        ESI,4
  355.                         }
  356.                 }

  357.                 if(carry != 0)
  358.                 {
  359.                         pNum->_num[i++] = carry;
  360.                 }

  361.                 pNum->_len = i;

  362.                 nRet = 1;
  363.         }while(0);

  364.         return nRet;
  365. }

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

  372.         do
  373.         {
  374.                 if(!IS_INITED(pNum))
  375.                 {
  376.                         break;
  377.                 }
  378.                
  379.                 plong += (pNum->_len - 1);

  380.                 _asm
  381.                 {
  382.                         MOV ECX,carry
  383.                         MOV ESI,plong
  384.                         XOR EDX,EDX
  385.                 _DivLoop:
  386.                         MOV EAX,EDX
  387.                         MOV EBX,BASE
  388.                         MUL EBX
  389.                         ADD EAX,[ESI]
  390.                         ADC EDX,0
  391.                         MOV EBX,number
  392.                         DIV EBX
  393.                         MOV [ESI],EAX
  394.                         SUB ESI,4
  395.                         TEST EAX,EAX
  396.                         JNZ _NotZero
  397.                         DEC carry
  398.                 _NotZero:
  399.                         LOOP _DivLoop
  400.                 }

  401.                 pNum->_len = carry;

  402.                 nRet = 1;
  403.         }while(0);

  404.         return nRet;
  405. }

  406. //测试:计算一个数的阶乘
  407. void Factorial(int n)
  408. {
  409.         int len = 0;
  410.         char * buffer = 0;
  411.         NUMERIC num;
  412.         InitNumeric(&num,1000);
  413.         SetNumber(&num,n);

  414.         while(n > 2)
  415.         {
  416.                 if(MulNumber(&num,--n) == 0)
  417.                 {
  418.                         break;
  419.                 }
  420.         }

  421.         len = Number2String(&num,0);
  422.         buffer = (char *)malloc(len);
  423.         Number2String(&num,buffer);
  424.         printf("%s\n",buffer);
  425.         UninitNumeric(&num);
  426.         free(buffer);
  427. }

  428. //测试:计算舍罕王应给的小麦
  429. void test()
  430. {
  431.         int i = 0;
  432.         char buffer[64] = {0};
  433.         NUMERIC num,num1;

  434.         SetNumber(&num,1);
  435.         SetNumber(&num1,1);

  436.         for(i=1 ; i<64; i++)
  437.         {
  438.                 MulNumber(&num1,2);
  439.                 AddNumeric(&num,&num1);
  440.         }

  441.         Number2String(&num,buffer);
  442.         printf("舍罕王应该给依达尔 %s 粒麦子!\n",buffer);
  443.         SetNumeric(&num1,buffer);
  444.         DivNumber(&num1,25000);
  445.         Number2String(&num1,buffer);

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

  450. int main()
  451. {
  452.         test();
  453.         return 0;
  454. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-10-29 15:16:55 | 显示全部楼层
舍罕王问题测试结果如图:

未命名.JPG
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-10-29 15:26:17 | 显示全部楼层
本帖最后由 jackz007 于 2020-10-29 15:34 编辑

        518 行源代码,是不是过于复杂,这道题只是用到了 64 位整型数的最大值,但是绝对没有超出,所以,全程使用 64 位无符号长整型数完全可以解决问题。
        我的代码运算的结果和你是完全一样的。
  1. #include <stdio.h>
  2. int main(void)
  3. {
  4.         unsigned long long d , result                       ;
  5.         int i , k                                           ;
  6.         for(result = 0 , i = 0 ; i < 64 ; i ++) {
  7.                 for(d = 1 , k = 0 ; k < i ; k ++) d = d * 2 ;
  8.                 result += d                                 ;
  9.         }
  10.         printf("\n")                                        ;
  11.         printf("舍罕王需要付给达依尔的麦子数量为:\n")       ;
  12.         printf("        %20I64u 粒\n" , result)             ;
  13.         printf("        %20I64u kg\n" , result / 25000)     ;
  14.         printf("\n")                                        ;
  15. }
复制代码

        下面是编译、运行实况:
  1. D:\00.Excise\C>g++ -o sh sh.c

  2. D:\00.Excise\C>sh

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


  6. D:\00.Excise\C>
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-10-29 16:16:22 | 显示全部楼层
占个楼
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-10-29 16:19:27 | 显示全部楼层
jackz007 发表于 2020-10-29 15:26
518 行源代码,是不是过于复杂,这道题只是用到了 64 位整型数的最大值,但是绝对没有超出,所以, ...

是有点复杂,不过,程序不局限于算这个啊,还可以算别的
,比如说10000的阶乘。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-16 10:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表