关于高精度除法

最新推荐文章于 2025-03-31 09:18:28 发布

「已注销」

最新推荐文章于 2025-03-31 09:18:28 发布

阅读量717

点赞数 1

分类专栏：高精度算法文章标签：高精度算法

本文链接：https://blog.csdn.net/Julytree/article/details/66970512

版权

高精度算法专栏收录该内容

1 篇文章

订阅专栏

输入m,n输出其商的整数部分。
思路1：用减法模拟除法，即用n去减m，一直减到不能再减为止。
结果：这种算法只利用了高精度减法，所以代码实现难度较低。但m远远大于n时（eg：9999÷3），运算时间过长。因此不可取。
思路2：模拟除法竖式
这种解法比较容易想到，也符合认知规律，重点在于解决2个问题：
1.如何进行某一位置的除法；
2.如何把上一次的余数加入这次的计算。
关于问题1，我们发现，此时的除法，除数与被除数位数相差不多（商不会超过9），因此可用减法来模拟。
while ( 比较得被除数>除数)
{减一次；商++；
}
关于问题2，我的解决方法是用 head和tail作为指针，划出被除数的范围。

模拟竖式

在某种意义上，把被除数m [ ] 当成了一个队列，队头为0时，队头向后推。除到不能再除时，队尾的后移一位。
为了表示方便，我们最好不要像平时做高精度一样，把个位记为m[1],十位记为m[2]……而是按照数字输入的顺序，最高位的为m[1]，次高位为m[2]……
伪代码：
int head=1,tail 1=n[0] ; ans[0]=1
while (tail<=m[0])
{
while (比较被除数与n前者大)
{在head到tail的范围内减一次；更新head值；
ans [ans[0]]++
}
ans [0]++;tail++
}
输出ans
但这样做出来后，只能得5分，原因是：因为得数的前与后都有可能出现0，只需在循环外或输出前判断一下即可。如果输入的被除数小于除数，直接得0。

#include<iostream>
#include<cstring>
#include<cstdio>
char n1[101],m1[101];
int m[101],n[101],ans[101],head,tail;
using namespace std;

bool start(int a[],int b[])//-----------------------start
{
 if(a[0]>b[0]) return 1;
 if(a[0]<b[0]) return 0;
 if(a[0]==b[0])
  for(int i=1;i<=a[0];i++)
  {
    if(a[i]>b[i]) return 1;
    if(a[i]<b[i]) return 0;
  } 
 return 1;  
}
void in(char a1[],int a[])
{ 
 gets(a1);
 a[0]=strlen(a1);
 for(int i=0;i<a[0];i++)
 a[i+1]=a1[i]-48;       
}
void out(int ans[])//------------------------------------out
{
 int h=1;
 while(ans[h]==0) h++;  
 for(int i=h;i<=ans[0];i++)
  cout<<ans[i];     
}
bool cmp(int a[],int b[])//--------------------------------cmp
{
    if(tail-head+1>b[0]) return 1;
    if(tail-head+1<b[0]) return 0;
    if(tail-head+1==b[0])
    for(int i=0;i<b[0];i++)
    {
     if(a[head+i]>b[i+1]) return 1;
     if(a[head+i]<b[i+1]) return 0;     
    }
 return 1;      
}
void jian(int a[],int b[])//---------------------- 减一次 
{
 int i=0;
 while(i<b[0])
  {
   if(a[tail-i]<b[b[0]-i])
    {a[tail-i]+=10; a[tail-i-1]--;} 
   a[tail-i]-=b[b[0]-i]; 
   i++;
  }
   while(a[head]==0) head++;    
}
void work(int a[],int b[])//----------------------------work
{
 head=1; tail=b[0]; ans[0]=1;
while(tail<=a[0])//--------------------------从后往前 
 {
  while(cmp(a,b)==1)//----------------------减多次 
   {
    jian(a,b);
    ans[ans[0]]++;
   }
  ans[0]++;
  tail++;   
 }
 if(ans[ans[0]]==0) ans[0]--;
}
int main()//---------------------------------------main
{
 in(m1,m);
 in(n1,n);
 if (start(m,n)==0)
  {
   cout<<0;
   return 0;    
  }
 work(m,n);
 out(ans);
 return 0;  
}