Понеділок, 18.12.2017, 02:21
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Меню сайту
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Розбір задач
Додавання двох «довгих» чисел в системі числення з основою N майже не відрізняється від додавання в десятковій системі. «Перевертаємо» числа (для зручності), додаємо, корегуємо. 
Задача А
Const c:string='0123456789ABCDEF';
Var sa,sb:string;
    a,b,s:array[0..500] of longint;
    i,j,n,la,lb:longint;
Begin Readln(n);
      Readln(sa); la:=length(sa);
      Readln(sb); lb:=length(sb);
      For i:=1 to la do a[la-i+1]:=pos(sa[i],c)-1;
      For i:=1 to lb do b[lb-i+1]:=pos(sb[i],c)-1;
      For i:=1 to la do s[i]:=a[i]+b[i];
      For i:=1 to la do Begin s[i+1]:=s[i+1]+s[i] div n; s[i]:=s[i] mod n End;
      If s[la+1]>0 Then inc(la);
      For i:=la downto 1 do Write(c[s[i]+1]); Writeln;
End.

Віднімання – аналогічно: «перевертаємо» числа (для зручності), віднімаємо, корегуємо.
Задача В
Var sa,sb:string;
    a,b,s:array[0..500] of longint;
    i,j,n,la,lb:longint;
Begin Readln(n);
      Readln(sa); la:=length(sa);
      Readln(sb); lb:=length(sb);
      For i:=1 to la do a[la-i+1]:=pos(sa[i],c)-1;
      For i:=1 to lb do b[lb-i+1]:=pos(sb[i],c)-1;
      For i:=1 to la do s[i]:=a[i]-b[i];
      For i:=1 to la do if s[i]<0 Then Begin inc(s[i],n); dec(s[i+1]) End;
      for la:=la downto 1 do if s[la]>0 Then Break;
      For i:=la downto 1 do Write(c[s[i]+1]); Writeln;
End.

Добуток – так само: «перевертаємо» числа, множимо, корегуємо.
Задача С
Const c:string='0123456789ABCDEF';
Var sa,sb:string;
    a,b,s:array[0..500] of longint;
    i,j,n,la,lb:longint;
Begin Readln(n);
      Readln(sa); la:=length(sa);
      Readln(sb); lb:=length(sb);
      For i:=1 to la do a[la-i+1]:=pos(sa[i],c)-1;
      For i:=1 to lb do b[lb-i+1]:=pos(sb[i],c)-1;
      For i:=1 to la do For j:=1 to lb do s[i+j-1]:=s[i+j-1]+a[i]*b[j];
      For i:=1 to la+lb do Begin s[i+1]:=s[i+1]+s[i] div n; s[i]:=s[i] mod n End;
      inc(la,lb); If s[la]=0 Then dec(la);
      For i:=la downto 1 do Write(c[s[i]+1]); Writeln;
End.

Кульмінація – ділення двох «довгих» ввібрало ідеї попередніх алгоритмів. Основні етапи: вводимо рядки, перевертаємо дільник, готуємо добутки дільника на можливі цифри результату, виконуємо ділення шляхом підбору кожної цифри результату.
Задача D
Const c:string='0123456789ABCDEF';
Type arr=array[0..500] of longint;
Var sa,sb:ANSIstring;
    a,o,r:arr; b:array[0..16] of arr;
    i,j,k,n,la,lb,po,ki:longint;
Function bilshe(k:integer):boolean; var i:integer;
Begin if b[k][0]<ki-po+1 Then bilshe:=false Else
       if b[k][0]>ki-po+1 Then bilshe:=true Else Begin
        For i:=po to ki do if b[k][b[k][0]+po-i]<>o[i] Then Break;
        if b[k][b[k][0]+po-i]>o[i] Then bilshe:=true else bilshe:=false
       End;
End;
Begin Readln(n);
      Readln(sa); la:=length(sa);
      Readln(sb); lb:=length(sb);
      For i:=1 to la do a[i]:=pos(sa[i],c)-1;
      For i:=1 to lb do b[1][lb-i+1]:=pos(sb[i],c)-1; b[1][0]:=lb;
      For j:=2 to n do Begin b[j][0]:=lb;
       For i:=1 to lb do b[j][i]:=b[1][i]*j;
       For i:=1 to lb do Begin inc(b[j][i+1],b[j][i] div n); b[j][i]:=b[j][i] mod n End;
       While b[j][b[j][0]+1]>0 do Begin inc(b[j][0]);
        inc(b[j][b[j][0]+1],b[j][b[j][0]+1] div n); b[j][b[j][0]]:=b[j][b[j][0]] mod n End;
      End; b[0][0]:=1;
      po:=1;
      For i:=1 to la do Begin ki:=i; o[ki]:=a[i];
       For k:=1 to n do if bilshe(k) Then Break; dec(k); r[i]:=k;
       For j:=1 to b[k][0] do Begin o[ki+1-j]:=o[ki+1-j]-b[k][j];
        if o[ki+1-j]<0 Then Begin inc(o[ki+1-j],n); dec(o[ki-j]) End;
        for po:=po to ki+1 do if o[po]>0 Then Break;
       End;
      End;
      For i:=1 to la do if r[i]>0 Then Break;
      For i:=i to la do Write(c[r[i]+1]); Writeln;
End.
Copyright MyCorp © 2017
Пошук
Календар
«  Грудень 2017  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728293031
Архів записів
Друзі сайту
Обдаровані діти

Хмельницькі олімпіади

НМЦ ІКТ і ДН

Портал ХОІППО

Безкоштовний конструктор сайтів - uCoz