Деление массива - Каков наилучший способ разделить два числа, хранящиеся в массиве?

Question

У меня есть два массива (делитель, делитель):

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

Кроме того, вы рассматривали возможность использования класса BigInt (или эквивалентной вещи на вашем языке), который уже сделает это для вас?

Answer 2

Делать длинное деление.

Временное хранилище имеет размер, равный делителю плюс один, и инициализируется нулем:

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

Теперь запустите цикл:

1. Сдвиг каждой цифры частного на одну позицию влево.
2. Смещение каждой цифры аккумулятора на одну позицию вправо.
3. Возьмите следующую цифру дивиденда, начиная снаиболее значимый конец, и сохраните его в наименее значимом месте накопителя.
4. Найдите accumulator / divisor и задайте наименее значимое место частного для результата.Установите остаток аккумулятора.

Используется для многократного использования этого же алгоритма на языке ассемблера для процессоров, у которых не было инструкций деления.

Answer 3

Вы можете использовать длинное деление http://en.wikipedia.org/wiki/Long_division

Answer 4

Вы можете использовать Длинный алгоритм деления или более общий Полиномиальное длинное деление .

Answer 5

Есть ли лучший способ сделать это?

Вы можете использовать длинное деление .

Answer 6

Вот, пожалуйста! А делитель. B является делителем. C - целое число R это остальное. Каждое «огромное» число - это вектор, сохраняющий большое число. В огромном [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=A-B;
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 <- A-B */
        { 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]--;
            }

Answer 7

Почему бы не преобразовать их в целые числа, а затем использовать обычное деление?

в псевдокоде:

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;