На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Алгоритм деления двух длинных чисел, Помогите, пожалуйста
    Здравствуйте, очень нужна помощь знающих людей. У меня задание - написать программу деления 2 длинных чисел на Visual Studio Net(на языке C). Не могу понять, как выполнить деление. ПРочитал кучу инфы, но вопрос остается открытым. Я так понял, чтобы осуществить деление надо, чтобы 2 числа находились в массивах а дальше?
    Буду очень признателен, если у кого-то есть готовый программный код иолил советы... Спасибо!
      Ну ты напиши на листочке 2 числа и подели. и по аналогии делай...
        Совет:
        1.Юзать длинную математику
        2.Описание алгоритма дано во 2 книге Д Кнута-Целочисленные вычисления
        3.Если это очередная контрольная то исходных текстов не ждите тут -разбиритесь сами (вдруг препод смросит :
        -а какого типа должны быть переменные хранящие длинные числа
        4 У меня есть деления но я писал на VB(школьное деление)


        Обозначим делитель B=(b0, b1, …, bn-1 ), делимое A=(a0, a1, …, an+m-1), числа имеют длины n и n+m
        соответственно.
        Общий цикл остается почти таким же: алгоритм состоит из последовательно выполняемых шагов,
        где шаг представляет собой деление (n+1)-разрядной части A на n-разрядный делитель
        B(исключение может составлять первый шаг, но это укладывается в общую схему, которая будет
        обсуждаться ниже).
        При этом i-й шаг состоит из двух действий:
        1. Угадать i-ю цифру частного q[i]
        2. Не создавая временных чисел, вычесть “сдвинутое” произведения B*q[i] из A.
        При этом сдвиг B относительно A на каждом шаге уменьшается.
        Рассмотрим действия, совершаемые при делении A=68971
        на B=513. Здесь n=5, m=2
        1. i = (индекс старшего коэффициента A) = 4
        a. Угадываем q[0] = 1
        b. Вычитаем сдвинутое B*1 = 513 из A
        (на бумаге мы при этом пишем только
        значимую для следующего шага часть A)
        2. i = 3
        a. Угадываем q[1] = 3
        b. Вычитаем сдвинутое B*3 = 1539 из A
        3. i = 2
        a. Угадываем q[3] = 4
        b. Вычитаем сдвинутое B*4 = 2052 из A
        4. i < m = 2, процесс закончен. То, что осталось от A после вычитаний является остатком
        деления.
        Вроде бы, все очевидно, за исключением одного “творческого” шага – угадывания.
        6 8 9 7 1
        5 1 3
        5 1 3
        1 7 6 7
        1 5 3 9
        2 2 8 1
        2 0 5 2
        2 2 9
        1 3 4
        горизонтальные линии проводятся
        между шагами
        Как заставить компьютер генерировать правильное частное q ? Или, хотя бы, достаточно близкое к
        нему число ?
        Довольно интересный способ состоит в высказывании догадки qGuess по первым цифрам
        делителя и делимого. Понятно, что этих нескольких цифр недостаточно для гарантированно
        правильного результата, однако неплохое приближение все же получится.
        Пусть очередной шаг представляет собой деление некоторого U = (u0, u1, …, un) на B=(b0, b1, …, bn-
        1). Если bn-1 ≥ BASE/2, то можно доказать следующие факты1.
        1. Если положить qGuess = (un*BASE + un-1) / bn-1 , то qGuess-2 ≤ q ≤ qGuess.
        Иначе говоря, вычисленная таким способом “догадка” будет не меньше искомого частного,
        но может быть больше на 1 или 2.
        2. Если же дополнительно выполняется неравенство
        qGuess*bn-2 > BASE*r + un-2 , где r – остаток при нахождении qGuess и qGuess ≠ BASE, (2)
        то qGuess-1 ≤ q ≤ qGuess, причем вероятность события qGuess = q+1 приблизительно равна
        2/BASE.
        Таким образом, если bn-1 ≥ BASE/2, то можно вычислить qGuess = (un*BASE + un-1) / bn-1 и
        уменьшать на единицу до тех пор, пока не станут выполняться условия (2). Получившееся
        значение будет либо правильным частным q, либо, с вероятностью 2/BASE, на единицу большим
        числом.
        Что делать, если bn-1 слишком мало, чтобы пользоваться таким способом ?
        Например, можно домножить делитель и делимое на одно и то же число scale = BASE / ( bn-1 +1 ).
        При этом несколько изменится способ вычисления остатка, а частное останется прежним. Такое
        домножение иногда называют нормализацией числа.
        На тот случай, если qGuess получилось все же на единицу большим q, будем использовать в
        пункте (b) вычитание, аналогичное функции Sub, которое вместо отрицательного числа даст
        дополнение до следующей степени основания.
        Если такое произошло, то последний перенос будет равен borrow = -1. Это сигнал, что необходимо
        прибавить одно B назад. Заметим, что в конце сложения будет лишний перенос carry=1, о котором
        нужно забыть (он компенсирует borrow=-1).
        Например, делим A=505 на B=50. Угаданное частное qGuess=11.
        505-550 = 955(=1000-45). Последний перенос borrow=-1, рельное частное q=qGuess-1=10.
        Необходимо прибавить одно B: 955+50 = 5.
        При сложении произошел перенос carry=1 из старшего разряда. Должно было получится 1005, но
        об этом переносе “забыли”, так как он компенсировал borrow=-1.

        ExpandedWrap disabled
          // Q = A/B, R=A%B
          void Div(const BigInt &A, BigInt &B, BigInt &Q, BigInt &R) {
          // Вырожденный случай 1. Делитель больше делимого.
          if ( A.Size < B.Size ) {
          Q.zero();
          R=A;
          return;
          }
          // Вырожденный случай 2. Делитель – число базового типа.
          if ( B.Size == 1) {
          SDiv ( A, B.Coef[0], Q, R.Coef[0]);
          R.Size = 1;
          return;
          }
          1 Доказательства не очень сложны, и если они интересны – они присутствуют в книге Д. Кнута [3].
          // Создать временный массив U, равный A
          // Максимальный размер U на цифру больше A, с учетом
          // возможного удлинения A при нормализации
          BigInt U(A.Size+1); U = A; U.Coef[A.Size]=0;
          // Указатели для быстрого доступа
          short *b=B.Coef, *u=U.Coef, *q=Q.Coef;
          long n=B.Size, m=U.Size-B.Size;
          long uJ, vJ, i;
          long temp1, temp2, temp;
          short scale; // коэффициент нормализации
          short qGuess, r; // догадка для частного и соответствующий остаток
          short borrow, carry; // переносы
          // Нормализация
          scale = BASE / ( b[n-1] + 1 );
          if (scale > 1) {
          SMul (U, scale, U);
          SMul (B, scale, B);
          }
          // Главный цикл шагов деления. Каждая итерация дает очередную цифру частного.
          // vJ - текущий сдвиг B относительно U, используемый при вычитании,
          // по совместительству - индекс очередной цифры частного.
          // uJ – индекс текущей цифры U
          for (vJ = m, uJ=n+vJ; vJ>=0; --vJ, --uJ) {
          qGuess = (u[uJ]*BASE + u[uJ-1]) / b[n-1];
          r = (u[uJ]*BASE + u[uJ-1]) % b[n-1];
          // Пока не будут выполнены условия (2) уменьшать частное.
          while ( r < BASE) {
          temp2 = b[n-2]*qGuess;
          temp1 = r*BASE + u[uJ-2];
          if ( (temp2 > temp1) || (qGuess==BASE) ) {
          // условия не выполнены, уменьшить qGuess
          // и досчитать новый остаток
          --qGuess;
          r += b[n-1];
          } else break;
          }
          // Теперь qGuess - правильное частное или на единицу больше q
          // Вычесть делитель B, умноженный на qGuess из делимого U,
          // начиная с позиции vJ+i
          carry = 0; borrow = 0;
          short *uShift = u + vJ;
          // цикл по цифрам B
          for (i=0; i<n;i++) {
          // получить в temp цифру произведения B*qGuess
          temp1 = b[i]*qGuess + carry;
          carry = temp1 / BASE;
          temp1 -= carry*BASE;
          // Сразу же вычесть из U
          temp2 = uShift[i] - temp1 + borrow;
          if (temp2 < 0) {
          uShift[i] = temp2 + BASE;
          borrow = -1;
          } else {
          uShift[i] = temp2;
          borrow = 0;
          }
          }
          // возможно, умноженое на qGuess число B удлинилось.
          // Если это так, то после умножения остался
          // неиспользованный перенос carry. Вычесть и его тоже.
          temp2 = uShift[i] - carry + borrow;
          if (temp2 < 0) {
          uShift[i] = temp2 + BASE;
          borrow = -1;
          } else {
          uShift[i] = temp2;
          borrow = 0;
          }
          // Прошло ли вычитание нормально ?
          if (borrow == 0) { // Да, частное угадано правильно
          q[vJ] = qGuess;
          } else { // Нет, последний перенос при вычитании borrow = -1,
          // значит, qGuess на единицу больше истинного частного
          q[vJ] = qGuess-1;
          // добавить одно, вычтенное сверх необходимого B к U
          carry = 0;
          for (i=0; i<n; i++) {
          temp = uShift[i] + b[i] + carry;
          if (temp >= BASE) {
          uShift[i] = temp - BASE;
          carry = 1;
          } else {
          uShift[i] = temp;
          carry = 0;
          }
          }
          uShift[i] = uShift[i] + carry - BASE;
          }
          // Обновим размер U, который после вычитания мог уменьшиться
          i = U.Size-1;
          while ( (i>0) && (u[i]==0) ) i--;
          U.Size = i+1;
          }
          // Деление завершено !
          // Размер частного равен m+1, но, возможно, первая цифра - ноль.
          while ( (m>0) && (q[m]==0) ) m--;
          Q.Size = m+1;
          // Если происходило домножение на нормализующий множитель –
          // разделить на него. То, что осталось от U – остаток.
          if (scale > 1) {
          short junk; // почему-то остаток junk всегда будет равен нулю…
          SDiv ( B, scale, B, junk);
          SDiv ( U, scale, R, junk);
          } else R=U;
          }






        При делении числа длины n на число длины m производится Θ(n-m) проходов цикла, каждый из
        которых делает несколько операций стоимостью Θ (m). Таким образом, общая оценка будет
        квадратичной, как и у умножения: Θ (nm).
        Сообщение отредактировано: Dethlord -
        Подпись выключена.
          в двоичную систему переводишь и делишь столбиком
          1. выравниваешь делимое и делитель по старшему биту
          2. вычитаешь из делимого делитель
          3. если возникает перенос, т.е. делимое меньше, то оставлем его без изменений, -> п.5
          4. результат пишешь в делимое, в частное + 1
          5. сдвигаешь в право делитель, влево частное на 1 бит
          6. делитель не изменился? -> п.2
          7. теперь в делимом остаток, ставим запятую, если надо делим дальше до нужной точности
            Dethlord спасибо, но не понял, что за код приведен, там не описаны используемые в нем функции.
            tDCKWL хороший алгоритм, но чтобы мне его реализовать потребуется очень много времени, а его мало. Не мог бы написать на С? Буду оч. признателен.
              я си не знаю тока асм
                Ну тогда может подскажешь... смотри у меня 2 массива, в первом - делимое, во втором - делитель. В каждой ячейке массива по одной цифре. Как реализовать твой метод? Мы же не можем получить полнео число, чтобы потом его перевести в двоичную систему(оно же длинное)...
                  делай как на бумажке делишь. длину разряда выбирай произвольно, не важно, бит, байт, слово и т.п.
                    Я написал подробную схему в чем проблемма то?
                    Подпись выключена.
                      Мы этому товарищу уже замучились объяснять как же надо делить
                      Деление двух длинных чисел
                      Благодарности отослать мылом, пиво, цветы и поклонниц - в аттаче.
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script Execution time: 0,1184 ]   [ 16 queries used ]   [ Generated: 26.02.20, 13:55 GMT ]