На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Друзья, соблюдайте, пожалуйста, правила форума и данного раздела:
Данный раздел не предназначен для вопросов и обсуждений, он содержит FAQ-заготовки для разных языков программирования. Любой желающий может разместить здесь свою статью. Вопросы же задавайте в тематических разделах!
• Если ваша статья может быть перенесена в FAQ соответствующего раздела, при условии, что она будет оформлена в соответствии с Требованиями к оформлению статей.
• Чтобы остальным было проще понять, указывайте в описании темы (подзаголовке) название языка в [квадратных скобках]!
Модераторы: Модераторы
  
> Длинная арифметика , [Pascal] продолжение
    Недавно решал задачи про длинную арифметику. Написал еще 2 процедуры - это длинное вычитание и деление длинного на короткое. Вот:


    ExpandedWrap disabled
      procedure longsub(a,b:tlong; var c:tlong);
      var k,i,p:longint;
      begin
        fillchar(c,sizeof(c),0);
        if a[0]>b[0] then k := a[0] else k := b[0];
        p := 0;
        for i := 1 to k do
          begin
            c[i]:=a[i]-b[i]-p;
            if c[i]<0 then
              begin
                p := 1;
                inc(c[i],osn);
              end
            else p:=0;
          end;
        for i := k downto 1 do
          if c[i]<>0 then break;
        c[0]:=i;
      end;




    ExpandedWrap disabled
      procedure longdiv(a:tlong; b:longint; var c:tlong);
      var
        p:longint;
        i,j,ost:integer;
      begin
        fillchar(c,sizeof(c),0);p:=0;
        i := 1;
        j := a[0];
        while i<j do
          begin
            swap(a[i],a[j]);
            inc(i);
            dec(j);
          end;
        ost:=0;
        for i := 1 to a[0] do
          begin
            c[i]:=(Longint(ost)*osn+a[i])div b;
            ost :=(Longint(ost)*osn+a[i])mod b;
          end;
        if c[1]=0 then
          begin
            c[0]:=a[0]-1;
            for i := 1 to c[0] do c[i]:=c[i+1];
            c[c[0]+1]:=0;
          end
        else c[0]:=a[0];
        i := 1;
        j := c[0];
        while i<j do
          begin
            swap(c[i],c[j]);
            inc(i);
            dec(j);
          end;
      end;



    Прошу приобщить все это к основной статье.
    Сообщение отредактировано: Jin X -
      А обьяснить принцип? Как ты пришёл к этим процедурам? Это всё желательно показать, т.к. готовых процедур и модулей в интернете полно, а вот нормального описания мало.
        ну хорошо. начнем с вычитания.


        Цитата Arsuit @
        if a[0]>b[0] then k := a[0] else k := b[0];
        в этой строчке мы в переменную k записываем max(a[0],b[0]) - для границы цикла.

        Затем мы запускаем цикл от 1 до k.
        Переменная p служит для того, чтобы мы знали, занимали ли мы из соседнего разряда, или нет. (Если занимали, то p=1, иначе p=0 (все помнят вычитание столбиком?)).

        Цитата Arsuit @
        c[i]:=a[i]-b[i]-p;
        Текущему разряду ответа присваиваем разность текущих разрядов вычитаемого и ... ну как его... то, что вычитают. Не помнь я как оно называется. Скажите пожалуйста, кто помнит. Ну так вот. Текущему разряду разности присваиваем разности вичитаемого, то, что вычитают и, если мы из этого разряда занимали, то вычитаем еще и единицу. Затем мы проверяем, если разность получилась отрицательной (if c[i]<0) то занимаем из соседнего разряда, а к текущему разряду ответа прибавляем основание (т. к. он стал отрицатльным).

        и наконец вот эти
        Цитата Arsuit @
        for i := k downto 1 do
        if c[i]<>0 then break;
        c[0]:=i;
        строки определяют кол-во цивр в ответе.
        Ну вот с вычитанием мы вроде немного разобрались. Теперь деление. (Чтобы понять все, что здесь написано, вы должны помнить, как делятся числа столбиком :) )


        Цитата Arsuit @
        i := 1;
        j := a[0];
        while i<j do
        begin
        swap(a[i],a[j]);
        inc(i);
        dec(j);
        end;

        начнем с этих строк. Они переворачивают делимое. (если кто помнит, в длинной арифметике все числа записаны задом на перед - так с ними удобнее работать, в данном же случае (в случае деления) с длинным числом как раз таки удобнее работать, если оно записано в нормальном виде).

        В переменной ost хранится остаток от деления разряда делимого на делитель. На каждом шаге цикла от 1 до a[0] мы к текущему остатку приписываем цифру из текущего разряда делимого (Longint(ost)*osn+a[i]), и делим все это на делитель (div b) и записываем в разряд частного. А в переменную, хранящую остаток мы записываем остаток от деления (Longint(ost)*osn+a[i]) на делитель.
        Все. число поделено.


        if c[1]=0 then
        begin
        c[0]:=a[0]-1;
        for i := 1 to c[0] do c[i]:=c[i+1];
        c[c[0]+1]:=0;
        end
        else c[0]:=a[0];
        если a[1]<b то получится так, что c[1] будет равно 0. Ведущие нули нам не нужны, так что если это так, то сдвигаем все число на разряд влево. А заодно и опредиляем кол-во цифр в ответе.
        В конце алгоритма мы переворачиваем число обратно.

        Заметим, что этот алгоритм деления можно несколько усовершенствовать. Можно не переворачивать число, и начать деление с конца. Но выигрыш во времени от этого будет не значительный, а запутаться можно. Так что решайте сами, что вам важнее.

        Добавлено
        ну вот. заценивайте статейку.
          ну так это будут приобщать к общей статье?
            Будут, когда ты это оформишь как следует. В таком виде ничего присоединяться не будет.
              Хорошо, я уже работаю над этим.
                Посмотрел я на свою бывшую статью и ужаснулся... Решил все полностью переписать. Вот гляньте, что я пока написал. Оформлю я все пото, когда допишу все до конца. пока прошу просто посмотреть, почитать, дополнить.

                Длинная арифметика

                Что нужно знать, чтобы понять весь изложенный здесь материал:
                1. Что такое одномерные массивы
                2. Что такое системы счисления, остатки.
                3. Уметь складывать, вычитать, умножать, делить числа столбиком.


                Начальные сведения.

                Когда вы пишите программы на каком либо языке программирования, бывает такое, что стандартных типов данных не хватает, для решения той или иной задачи. Такое бывает, например, если программа использует какой-либо комбинаторный алгоритм, или просто калькулятор длинных чисел.… Здесь уже стандартных типов данных (longint, int64 для паскаля/дельфи и long long для СИ) не хватит. Есть, конечно, типы с плавающей точкой (double, extended), но и их иногда может не хватить…

                Именно для таких случаев существует замечательный способ, который называется длинной арифметикой. Длинная арифметика подразумевает собой хранение длинного числа поразрядно, в одномерном массиве. При том способ хранения может быть разный. Некоторые хранят в одном элементе по одной цифре, другие же хранят в одном элементе несколько цифр в целях экономии памяти, т. к. процессор выполняет арифметические операции с различными числами за одно и то же время (это относится к сравнительно коротким числам, которые хранятся в стандартных типах). Я предпочитаю хранить несколько цифр (при этом я считаю, что оптимальное число цифр – 4), и ниже будут примеры, реализующие именно этот способ. Но выбирать, чем пользоваться, все же вам. Однако стоит отметить, что в этом способе ЗНАЧИТЕЛЬНО усложняется процедура чтения длинного числа. Кроме всего прочего, число в массиве записывается «задом на перед» - так удобнее. То есть если у меня есть число 123456789012345, и я храню в элементе по 4 цифры, то оно у меня будет выглядеть так:
                2345’8901’4567’123.

                В паскале длинные числа стоит описывать так:
                ExpandedWrap disabled
                  const
                    osn=10000; //основание. Так как в элементе массива мы храним 4 цифры, то можно сказать, что оно записано в osn-ичной системе счисления.
                    max=100; //кол-во элементов массива
                  type
                    TLong=array[0..max] of integer; // собственно сам массив с длинным числом.


                Для удобства в нулевом элементе храним кол-во занятых элементов массива (как в стандартном типе string).


                Чтение/вывод

                Дальнейшее знакомство с длинными числами наверное стоит начать с процедур чтения/вывода длинного числа. Именно с этого как правило приходится начинать писать длинную арифметику (если конечно эти процедуры вообще нужны).

                Чтение.
                Для тех, кто хранит в одном элементе массива одну цифру тут все совсем просто. Читаем посимвольно число, преобразуем символы в цифры, записываем в массив. Затем массив переворачиваем (ведь мы храним число «задом на перед», вы не забыли?). Пример:
                ExpandedWrap disabled
                  Procedure Long_read(var a:tlong);
                  var
                    c:char;
                    i,j:integer;
                    a:array[1..100] of byte;
                  begin
                    fillchar(a,sizeof(a),0);
                    repeat
                      read(c);
                    until c in ['0'..'9'];//пропускаем не цифры
                    i := 1;
                    while c in ['0'..'9'] do//пока цифры
                      begin
                        inc(i);
                        a[i]:=ord(c)-ord('0'); //преобразуем символ в цифру
                        read(c); //читаем еще символ.
                      end;
                    a[0]:=i;
                    j := i;
                    i := 1;
                    while i<j do //переворачиваем.
                      begin
                        swap(a[i],a[j]);
                        inc(i);
                        dec(j);
                      end;
                  end;


                Процедура Swap меняет значения переменных.
                Если же вы все таки надумали хранить в одном элементе несколько цифр, то алгоритм чтения будет другой. Мы читаем из входного файла по одной цифре начиная с начала массива, и по ходу дела перемещаем все вправо.

                ExpandedWrap disabled
                  procedure longread(var a:tlong);
                  var
                    c:char;
                    i:longint;
                  begin
                    fillchar(a,sizeof(a),0); //заполняем массив нулями.
                    repeat
                      read(c);
                    until c in ['0'..'9'];  //пропускаем не символы.
                    while c in ['0'..'9'] do
                      begin
                        for i := a[0] downto 1 do  //цикл смещения.
                          begin
                            a[i+1]:=a[i+1]+(Longint(a[i])*10) div osn; //добавляем одну цифру из текущего разряда в следующий.
                            a[i] := (Longint(a[i])*10) mod osn; //убираем одну цифру из текущего.
                          end;
                        a[1]:=a[1]+ord(c)-ord('0'); // в конец первого разряда записываем полчтенную цифру.
                        if a[a[0]+1]>0 then inc(a[0]); // если мы заняли еще один элемент массива, то увеличиваем нулевой элемент
                        read(c);  //читаем очередной символ.
                      end;
                  end;



                P.S. извиняюсь, что так долго пишу - я школу заканчиваю, экзамены, выпускные, поступление на носу...
                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0298 ]   [ 15 queries used ]   [ Generated: 9.12.24, 14:36 GMT ]