专栏首页xiaoxi666的专栏【模板小程序】十进制大数除法(输出商和余数)

【模板小程序】十进制大数除法(输出商和余数)

完善内容:增加了余数的输出。

大数除法,应该算是四则运算里面最难的一种了。不同于一般的模拟,除法操作步数模仿手工除法,而是利用减法操作实现的。

其基本思想是反复做除法,看从被除数里面最多能减去多少个除数,商就是多少。

逐个减显然太慢,要判断一次最多能减少多少个整的10的n次方。

以7546除23为例。

先减去23的100倍,就是2300,可以减3次,余下646。   此时商就是300;

然后646减去23的10倍,就是230,可以减2次,余下186。此时商就是320;

然后186减去23,可以减8次,此时商就是328.

根据这个思想,不难写出下面的代码。

还是那句话,可能算法效率不是很高。但是常规解题思路一般就是这样了。

如果以后有能力,有时间了。  我会试着去优化。

ps:大数系列学习资源来自 <c程序设计竞赛实训教程>一书和一些大牛的博客。

注意:程序不保留小数(只有商,没有余数),看了很多程序都是没有小数。

  1 /*
  2 本程序说明:
  3 
  4 大数除法 http://blog.csdn.net/hitwhylz/article/details/9700935
  5 
  6 */
  7 
  8 #include<stdio.h>
  9 #include<string.h>
 10 #include<stdlib.h>
 11 #define MaxLen 200
 12 //函数SubStract功能:
 13 //用长度为len1的大整数p1减去长度为len2的大整数p2
 14 // 结果存在p1中,返回值代表结果的长度
 15 //不够减 返回-1 正好够 返回0
 16 int SubStract( int *p1, int *p2, int len1, int len2 )
 17 {
 18     int i;
 19     if( len1 < len2 )
 20         return -1;
 21     if( len1 == len2 )
 22     {                        //判断p1 > p2
 23         for( i=len1-1; i>=0; i-- )
 24         {
 25             if( p1[i] > p2[i] )   //若大,则满足条件,可做减法
 26                 break;
 27             else if( p1[i] < p2[i] ) //否则返回-1
 28                 return -1;
 29         }
 30     }
 31     for( i=0; i<=len1-1; i++ )  //从低位开始做减法
 32     {
 33         p1[i] -= p2[i];
 34         if( p1[i] < 0 )          //若p1<0,则需要借位
 35         {
 36             p1[i] += 10;         //借1当10
 37             p1[i+1]--;           //高位减1
 38         }
 39     }
 40     for( i=len1-1; i>=0; i-- )       //查找结果的最高位
 41         if( p1[i] )                  //最高位第一个不为0
 42             return (i+1);       //得到位数并返回
 43     return 0;                  //两数相等的时候返回0
 44 }
 45 int main()
 46 {
 47     int n, k, i, j;             //n:测试数据组数
 48     int len1, len2;             //大数位数
 49     int nTimes;                 //两大数相差位数
 50     int nTemp;                  //Subtract函数返回值
 51     int num_a[MaxLen];          //被除数
 52     int num_b[MaxLen];          //除数
 53     int num_c[MaxLen];          //商
 54     char str1[MaxLen + 1];      //读入的第一个大数
 55     char str2[MaxLen + 1];      //读入的第二个大数
 56 
 57     scanf("%d",&n);
 58     while ( n-->0 )
 59     {
 60         scanf("%s", str1);        //以字符串形式读入大数
 61         scanf("%s", str2);
 62 
 63         for ( i=0; i<MaxLen; i++ )   //初始化清零操作
 64         {
 65             num_a[i] = 0;
 66             num_b[i] = 0;
 67             num_c[i] = 0;
 68         }
 69 
 70         len1 = strlen(str1);  //获得大数的位数
 71         len2 = strlen(str2);
 72 
 73         for( j=0, i=len1-1; i>=0; j++, i-- )
 74             num_a[j] = str1[i] - '0';  //将字符串转换成对应的整数,颠倒存储
 75         for( j=0, i=len2-1; i>=0; j++, i-- )
 76             num_b[j] = str2[i] - '0';
 77 
 78         if( len1 < len2 )   //如果被除数小于除数,结果为0
 79         {
 80             printf("0\n");
 81             continue;   //利用continue直接跳出本次循环。 进入下一组测试
 82         }
 83         nTimes = len1 - len2;    //相差位数
 84         for ( i=len1-1; i>=0; i-- )    //将除数扩大,使得除数和被除数位数相等
 85         {
 86             if ( i>=nTimes )
 87                 num_b[i] = num_b[i-nTimes];
 88             else                     //低位置0
 89                 num_b[i] = 0;
 90         }
 91         len2 = len1;
 92         for( j=0; j<=nTimes; j++ )      //重复调用,同时记录减成功的次数,即为商
 93         {
 94             while((nTemp = SubStract(num_a,num_b + j,len1,len2 - j)) >= 0)
 95             {
 96                 len1 = nTemp;      //结果长度
 97                 num_c[nTimes-j]++;//每成功减一次,将商的相应位加1
 98             }
 99         }
100 
101         //输出商
102         for( i=MaxLen-1; num_c[i]==0 && i>=0; i-- );//跳过高位0
103         if( i>=0 )
104             for( ; i>=0; i-- )
105                 printf("%d", num_c[i]);
106         else
107             printf("0");
108         printf("\n");
109 
110 
111         //此时的num_a存的就是余数(其实就是取模)
112         for( i=MaxLen-1; num_a[i]==0 && i>=0; i-- );//跳过高位0
113         if( i>=0 )
114             for( ; i>=0; i-- )
115                 printf("%d", num_a[i]);
116         else
117             printf("0");
118         printf("\n");
119 
120     }
121     return 0;
122 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【模板小程序】求第n个质数

    xiaoxi666
  • Kolakoski序列产生器

    xiaoxi666
  • 【模板小程序】求M~N范围内的质数个数

    xiaoxi666
  • cf1102F. Elongated Matrix(状压dp)

    然后枚举一个起点,\(f[sta][i]\)表示走过了\(sta\)这个集合内的元素,当前在\(i\)点的\(k\)的最大值

    attack
  • 爱彼迎19年社招java面试题 求DAG图中每个点的祖先个数

    例如上图, 则H的祖先个数是3个(包括它自己哈),分别是和. 而N的祖先个数是4()。

    ACM算法日常
  • 编程小技巧

    1.判断一个自然数是否是某个数的平方?(其实就是判断这个数一定是奇数相加的) 由于 (n+1)^2 =n^2 + 2n + 1, = ... = 1 +...

    猿人谷
  • LintCode 搜索插入位置题目分析代码

    给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

    desperate633
  • 【HDU 5855】Less Time, More profit(网络流、最小割、最大权闭合子图)

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Othe...

    饶文津
  • LintCode 搜索插入位置题目分析代码

    给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

    desperate633
  • 八大经典排序算法总结

    终于到了排序部分了。这部分也是最难总结的,毕竟不同的排序算法思想多少会有差别,有些甚至完全不一样。今天不知道要码多少字。好吧,先为我的手指默哀三分钟~

    指点

扫码关注云+社区

领取腾讯云代金券