Перевести число в q-ичную систему

[DenSeven]

Натуральное число в p-ичной системе счисления задано своими цифрами, хранящимися в в массиве К(n). Проверить корректность такого представления и перевести число в q-ичную систему ( возможно, число слишком велико, чтобы получить его внутреннее представление; кроме того, p меньше или равно 10 и q меньше или равно10 )

[Serge_Bliznykov]

Проверить корректность такого представления

это легко.
если циферки от нуля до P-1 - то число корректно.

перевести число в q-ичную систему ( возможно, число слишком велико, чтобы получить его внутреннее представление

а это не так просто.
Если P и Q не являются одним и тем же числом в разной степени (2, 4, 8, например, или 3 и 9), тогда единственный способ, который я вижу - это использование длинной арифметики.

[newerow1989]

Перевод чисел из одной системы счисления в другую можно посмотреть здесь.

[Serge_Bliznykov]

Сообщение от newerow1989

Перевод чисел из одной системы счисления в другую можно посмотреть здесь.

Угу. Но только если числа укладываются в представление int64

[Dekay]

( возможно, число слишком велико, чтобы получить его внутреннее представление; кроме того, p меньше или равно 10 и q меньше или равно10 )

[evg_m]

p:=10; q:=2;
K=(1,0,2,4);

i:=n;
while i>0 do begin
  j:=0;
  t:=1;
  while j<n do begin
    t:=t *p +K[j];
    К[j]:=t div q;
    t:=t mod q;
  end;
  R[i]:=t;
  i:=i-1;
end;

НАПИСАНО В БЛОКНОТЕ!! p>=q !!!

p и q любые чтобы имелась возможность выполнения операций
p mod q; 1=p^0 < q <p^1 =p

p<q ??? находим x=1,2, ...n.... такое что p^(x-1) <q <=p^x . и переводим наше числО(К) в систему p1 =p^x (x-граммы) К1
теперь имеем q<=p1 (т.е. предыдущий случай)

[evg_m]

procedure Recode(p: integer; K: TMarr; q: integer; var R: TMArr);
var
  n, nr: integer;
  i, j, t: integer;
  x: integer;
  rx: extended;
begin
  n:=length(K);
  rx:=ln(q)/ln(p);
  nr:=trunc(n/rx)+1;
  x:=trunc(rx)+1;
  SetLength(R,nr);

  i:=nr-1;
  t:=1;
  while i>=0 do begin
    t:=0;
    j:=0;
    while j<n do begin
      t:=t *p +K[j];
      if (n-1-j) mod x =0 then begin
        K[j]:=t div q;
        t:=t mod q;
      end
      else begin
        K[j]:=0;
      end;
      j:=j+1;
    end;
    R[i]:=t;
    i:=i-1;
  end;

end;

[Serge_Bliznykov]

evg_m, супер, работает!

[evg_m]

evg_m, супер, работает!

а на p=2; q:=4; т.е. когда q=p^x;
не уверен в правильности расчетов

  rx:=ln(q)/ln(p);
  nr:=trunc(n/rx)+1;
  x:=trunc(rx)+1;

для этого случая

[Serge_Bliznykov]

а на p=2; q:=4; т.е. когда q=p^x;

я проверил. работает!
например, 110(2) -> 12(4)