数组划分 – 划分存储在数组中的两个数字的最佳方法是什么？

我有两个数组（被除数，除数）：

dividend[] = {1,2,0,9,8,7,5,6,6}; divisor[] = {9,8}; 

我需要结果（被除数/除数）：

 quotient[] = {1,2,3,4,5,6,7}; 

我使用数组减法做了这个：

• 将除数从被除数中减去，直到被除数为0或小于除数，每次递数为1，

但这需要很长时间。 有一个更好的方法吗？

Answer 1

有一个更好的方法吗？

你可以使用长除法 。

Answer 2

做多分。

有一个大小等于除数的临时存储加一，并初始化为零：

 accumulator[] = {0,0,0}; 

现在运行一个循环：

1. 将商的每个数字向左移动一个空格。
2. 将累加器的每个数字向右移动一个空格。
3. 从最重要的一端开始，获取被除数的下一个数字，并将其存储到累加器的最不重要的位置。
4. 计算出accumulator / divisor ，并将商的最低有效位置设置为结果。 将累加器设置为余数。

过去常常在CPU的汇编语言中使用相同的算法而没有除法指令。

Answer 3

除此之外，您是否考虑过使用BigInt类（或您的语言中的等价物），它已经为您做到了这一点？

Answer 4

您可以使用长分部http://en.wikipedia.org/wiki/Long_division

Answer 5

您可以使用长除法算法或更一般的多项式长除法 。

Answer 6

为什么不将它们转换为整数然后使用常规除法？

在伪代码中：

 int dividend_number foreach i in dividend dividend_number *= 10 dividend_number += i int divisor_number foreach i in divisor divisor_number *= 10 divisor_number += i int answer = dividend_number / divisor_number; 

Answer 7

你去！ A是divident。 B是除数。 C是整数引号R是其余的。 每个“巨大”数字都是一个保留大数字的向量。 在huge [0]中，我们保留数字所具有的位数，然后将数字向后记忆。 假设我们的数字是1234，那么核心编码向量将是：

 v[0]=4; //number of digits v[1]=4; v[2]=3; v[3]=2; v[4]=1; 

….

 SHL(H,1) does: H=H*10; SGN(A,B) Compares the A and B numbers SUBSTRACT(A,B) does: A=AB; DIVIDHUGE: makes the division using the mentioned procedures... 

---

 void Shl(Huge H, int Count) /* H <- H*10ACount */ { memmove(&H[Count+1],&H[1],sizeof(int)*H[0]); memset(&H[1],0,sizeof(int)*Count); H[0]+=Count; } int Sgn(Huge H1, Huge H2) { while (H1[0] && !H1[H1[0]]) H1[0]--; while (H2[0] && !H2[H2[0]]) H2[0]--; if (H1[0] < H2[0]) { return -1; } else if (H1[0] > H2[0]) { return +1; } for (int i = H1[0]; i > 0; --i) { if (H1[i] < H2[i]) { return -1; } else if (H1[i] > H2[i]) { return +1; } } return 0; } void Subtract(Huge A, Huge B) /* A <- AB */ { int i, T=0; for (i=B[0]+1;i<=A[0];) B[i++]=0; for (i=1;i<=A[0];i++) A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0; while (!A[A[0]]) A[0]--; } void DivideHuge(Huge A, Huge B, Huge C, Huge R) /* A/B = C rest R */ { int i; R[0]=0;C[0]=A[0]; for (i=A[0];i;i--) { Shl(R,1);R[1]=A[i]; C[i]=0; while (Sgn(B,R)!=1) { C[i]++; Subtract(R,B); } } while (!C[C[0]] && C[0]>1) C[0]--; }