Задать вопрос

hagirangi

Лайки

  • Как ускорить функцию?

    AnnTHony
    @AnnTHony
    Интроверт 
    program addition;

// обычное сложение в столбик
function add(a, b: string): string;
const
  OFFSET = 48;
var
  tmp: integer;
  carry: integer;
  index_a,
  index_b: integer;
  addend_a,
  addend_b: integer;
begin
  result := '';
  
  // индексы последних цифр в каждой строке, т.к. сложение начинается справа налево
  index_a := length(a);
  index_b := length(b);
  
  // значение переноса, то что держим в уме, когда в сумме получаем двузначное число
  // например, 9 + 4 = 13: 3 пишем, а 1 в уме
  carry := 0;
  // продолжаем складывать, пока не пройдем по всем числам каждой строки
  while (index_a <> 0) or (index_b <> 0) do
  begin
    // первое и второе слагаемые
    addend_a := 0;
    addend_b := 0;
    
    // вместо выравнивания строк (дополнения нулями слева), я проверяю чтобы индекс не уходил в минус
    if index_a > 0 then
    begin  
      addend_a := ord(a[index_a]) - OFFSET;
      dec(index_a);
    end;
    
    if index_b > 0 then
    begin  
      addend_b := ord(b[index_b]) - OFFSET;
      dec(index_b);
    end;
    
    // собственно само сложение
    tmp := addend_a + addend_b + carry;
    carry := tmp div 10;
    result := chr((tmp mod 10) + OFFSET) + result;
  end;
  
  if carry > 0 then
    result := chr(carry + OFFSET) + result;
end;

begin
  writeln(add('999999999999999', '8009730000456465480001'));
  // 8009731000456465480000;
end.
    Ответ написан
    3 комментария
    3 комментария

  • Как ускорить функцию?

    @Mercury13
    Программист на «си с крестами» и не только
    Название, конечно, не по прогерскому фэншую, и вспоминается знаменитый стих столетней давности:
    «We slog, slog, slog, slogging over Africa,
    Boots, boots, boots, boots moving up and down again».

    ПЕРВОЕ. Главный тормоз — дополнение строк нулями, которое квадратичное по скорости.
    for i:=length(s1)+1 to m do
         s1:='0'+s1;
      for i:=length(s)+1 to m do
         s:='0'+s;


    Как решить?
    function add1(const large,small:string):string;

function add(const x, y : string) : string;
begin
  if length(x) > length(y)
    then add := add1(x, y)
    else add := add1(y, x);
end;


    Ну и разумеется, сделать, чтобы add1 работала с числами разной длины.

    ВТОРОЕ. У вас, по-видимому, ошибка — 99+1 = 100 не создаст третьего разряда.

    ТРЕТЬЕ. Я не знаю, какой у вас Паскаль, но, вероятно, передача строк по const/var также повысила бы скорость.

    ОФТОП. Если ваша задача не «ввести два числа, сложить и всё», я бы отделил длинное число от его строкового представления, примерно так.
    TLongNum = record
  length : integer;
  data : array [1..1000] of byte;
end;
    Ответ написан
    1 комментарий
    1 комментарий