学步园

大整数除以小整数求余数

// 大整数除以小整数，求余数的方法
inline int div(int a[], int n, int m){//m=7 for example
  int ys = 0;
  for(int i = 0; i<n; i++){
   ys*=10, ys+=a[i]; 
   ys%=m;
  }
  return ys;
}

验证

void testDiv(){
  int b[5] = {7, 9, 8, 0, 1};
  assert(div(b, 5, 1)==0);
  assert(div(b, 5, 2)==1);
  assert(div(b, 5, 3)==1);
  assert(div(b, 5, 7)==1);
}

大整数十进制除法

{int as[], int e, int k} 表示一个小数。 e表示第一个小数位下标。k表示最后一位（包括小数）的下标。

很多for循环。典型的线性扫描。

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAXN 100
using namespace std;
char* xj(char *buf){
  return buf;
}
void divide(int a, int b){
  int as[MAXN], cs[MAXN]; 
  int d=a/b;
  memset(as, 0 ,sizeof(as));
  memset(cs, 0 ,sizeof(cs));
  
  // 装入 a=》as
  int i=MAXN-1, j=0;
  while(a>0){
    as[j++]=a%10; a/=10; 
  }
  j--;
  for(; i>=0&&j>=0; i--,j--){
    as[i]=as[j];
    as[j]=0;
  }
  
  // as/b =》 cs， 注意cs.e = as.e, cs前面有多余的0。
  int e1= i, e2;
  long long int c=0, t;
  for(i=MAXN-1; i>=0; i--){
    c*=10;
    t = c+as[i];
    cs[i]=t/b;
    c=t%b;
    if(i<=e1+1&&c==0) break;
  }
  if(i<0) i=0;
  int k = i;
  
  // cs =》 buf
  char buf[MAXN+2];  
  for(i=MAXN-1; i>e1+1; i--) // 跳过多余0
    if(cs[i]!=0) break;
  for(j=0; i>e1; i--,j++){   // 记录整数部分
    buf[j]='0'+cs[i];
  }
  if(i>=k) buf[j++]='.';  // 是否有小数部分
  e2=j;
  for(i=e1; i>=k && j<MAXN+1; i--,j++){ // 小数部分
    //cout<<i<<":"<<cs[i]<<endl;
    buf[j]='0'+cs[i]; 
  }
  buf[j]=0;

  // print buf
  cout<<d;
  if(e2<j) {
    cout<<".";
    cout<<(buf+e2);
  }
  cout<<endl;
}

int main(){
  int a=2, b=3;
  cout<<"input a b"<<endl;
  while(~scanf("%d%d", &a, &b)){
    cout<<a<<"/"<<b<<":"<<endl;
    divide(a, b);
  }
  return 0;
}