Шустрый
Профиль
Группа: Участник
Сообщений: 142
Регистрация: 2.12.2007
Где: Москва
Репутация: нет
Всего: 0
|
У нас было такое же задание но на Делфе, думал тоже на С переделать но уж больно много там писать... Вот код на делфе может поможет... | Код |
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Edit1: TEdit;
Edit2: TEdit;
Button1: TButton;
Edit3: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Button2: TButton;
Edit4: TEdit;
Label4: TLabel;
Label5: TLabel;
Button3: TButton;
Button4: TButton;
Button10: TButton;
Edit11: TEdit;
Label12: TLabel;
GroupBox4: TGroupBox;
Button5: TButton;
Button6: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button10Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Edit4Change(Sender: TObject);
procedure Button5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
function ChrToNum(Ch: Char): Byte;
function NumToChr(N: Byte): Char;
function Sum(A, B: String): String;
function Sub(A, B: String): String;
function Mul(A, B: String): String;
function ShortDiv(A: String; B: Char; var Ost: Char): String;
function PowerMod(a, k, m: String): String;
function PowerModMul(a, k, m: String): String;
function SysToSys(A: String; NewSystem: Byte): String;
function Pow(A : String; k : String): String;
var
Form1: TForm1;
NumSystem : Integer;
implementation
{$R *.dfm}
//Преобразовываем символ в цифру
function ChrToNum(Ch: Char): Byte;
begin
Result := 0;
if (Ord(Ch) >= 48) and (Ord(Ch) < 58) then
Result := Ord(Ch)-48
else
if (Ord(Ch) >= 65) and (Ord(Ch) <= 90) then
Result := Ord(Ch)-55
else
if (Ord(Ch) >= 97) and (Ord(Ch) <= 122) then
Result := Ord(Ch)-87;
if Result >= NumSystem then Result := 0;
end;
//Преобразовываем цифру в символ
function NumToChr(N: Byte): Char;
begin
N := N mod NumSystem;
Result := '0';
if N < 10 then Result := Chr(48+N) else Result := Chr(55+N);
end;
//Выполняем суммирование чисел, представленных строками
function Sum(A, B: String): String;
var
s : String;
i : Integer;
la, lb, k, j : Integer;
begin
//Если оба числа неотрицательны, то используем
//стандартный алгоритм
if ((A[1]<>'-') and (B[1]<>'-')) then
begin
i := 0;
la := Length(A);
lb := Length(B);
Result := '';
k := 0;
while (i < la) or (i < lb) do
begin
j := ChrToNum(A[la-i]) + ChrToNum(B[lb-i]) + k;
Result := NumToChr((j mod NumSystem)) + Result;
k := j div NumSystem;
Inc(i);
end;
if k > 0 then Result := NumToChr(k) + Result;
end;
//Если оба числа отрицательны, то складываем их модули, а
//затем приписываем результату знак
if ((A[1]='-') and (B[1]='-')) then
begin
Delete(A,1,1);
Delete(B,1,1);
i := 0;
la := Length(A);
lb := Length(B);
Result := '';
k := 0;
while (i < la) or (i < lb) do
begin
j := ChrToNum(A[la-i]) + ChrToNum(B[lb-i]) + k;
Result := NumToChr((j mod NumSystem)) + Result;
k := j div NumSystem;
Inc(i);
end;
if k > 0 then Result := NumToChr(k) + Result;
Result := '-' + Result;
end;
//Если одно из чисел отрицательно, то используем функцию
//нахождения разности
if (A[1]='-') and (B[1]<>'-') then
begin
Delete(A,1,1);
Result:=Sub(B,A);
end;
if (A[1]<>'-') and (B[1]='-') then
begin
Delete(B,1,1);
Result:=Sub(A,B);
end;
end;
//Выполняем вычитание
function Sub(A, B: String): String;
var
s,AB,NS,Res,U,V : String;
i: Integer;
la, lb, k, j,r: Integer;
begin
//Если оба числа отрицательны, то меняем местами уменьшаемое
//и вычитаемое
U:=A;
V:=B;
if (U[1]='-') and (V[1]='-') then
begin
Delete(V,1,1);
AB:=V;
Delete(U,1,1);
V:=U;
U:=AB;
end;
//Если оба числа неотрицательны, то
//используем стандартный алгоритм
if (U[1]<>'-') and (V[1]<>'-') then
begin
i := 0;
la := Length(U);
lb := Length(V);
Result := '';
k := 0;
while (i < lb) do
begin
j := ChrToNum(U[la-i]) - ChrToNum(V[lb-i]) + k;
if j >= 0 then
begin
Result := NumToChr(j) + Result;
k := 0;
end
else
begin
Result := NumToChr(NumSystem+j) + Result;
k := -1;
end;
Inc(i);
end;
while i<la do
begin
j:= ChrToNum(U[la-i]) + k;
if j<0 then
begin
Result := NumToChr(NumSystem+j) + Result;
k := -1;
end
else
begin
Result := NumToChr(j) + Result;
k := 0;
end;
Inc(i);
end;
end;
//Если числа имеют разные знаки, то используем функцию суммирования
if (U[1]='-') and (V[1]<>'-') then
begin
Delete(U,1,1);
Result := '-' + Sum(U,V);
end;
if (U[1]<>'-') and (V[1]='-') then
begin
Delete(V,1,1);
Result := Sum(U,V);
end;
while (Result[1]='0') and (Result<>'0') do Delete(Result,1,1);
if Sum(Result,B)<>A then
begin
i := 0;
Res:=Result;
NS:=Pow(IntToStr(NumSystem),IntToStr(length(Res)));
la := Length(NS);
lb := Length(Res);
Result := '';
k := 0;
while (i < lb) do
begin
j := ChrToNum(NS[la-i]) - ChrToNum(Res[lb-i]) + k;
if j >= 0 then
begin
Result := NumToChr(j) + Result;
k := 0;
end
else
begin
Result := NumToChr(NumSystem+j) + Result;
k := -1;
end;
Inc(i);
end;
while i<la do
begin
j:= ChrToNum(NS[la-i]) + k;
if j<0 then
begin
Result := NumToChr(NumSystem+j) + Result;
k := -1;
end
else
begin
Result := NumToChr(j) + Result;
k := 0;
end;
Inc(i);
end;
while (Result[1]='0') and (Result<>'0') do Delete(Result,1,1);
Result:='-'+Result;
end;
end;
//Выполняем умножение
function Mul(A, B: String): String;
var
C: String;
la, lb, lc, i, j, k, t: Integer;
begin
Result:='';
//Проверяем числа на знаки
if (A[1]='-') and (B[1]='-') then
begin
Delete(A,1,1);
Delete(B,1,1);
end;
if (A[1]='-') and (B[1]<>'-') then
begin
Delete(A,1,1);
Result:= '-' + Result;
end;
if (A[1]<>'-') and (B[1]='-') then
begin
Delete(B,1,1);
Result:= '-' + Result;
end;
la := Length(A);
lb := Length(B);
lc := la + lb;
C := '';
for i := 1 to lc do C := C + '0';
for j := 0 to la-1 do
if A[la-j] <> '0' then
begin
k := 0;
for i := 0 to lb-1 do
begin
t := ChrToNum(B[lb-i])*ChrToNum(A[la-j]) + ChrToNum(C[lc-i-j]) + k;
C[lc-i-j] := NumToChr(t mod NumSystem);
k := t div NumSystem;
end;
C[lc-j-lb] := NumToChr(k);
end;
while (C[1]='0') and (C<>'0') do delete(C,1,1);
Result:=Result+C;
end;
//Выполняем деление на число, которое меньше 10
function ShortDiv(A: String; B: Char; var Ost: Char): String;
var
s : String;
r, j, v: Integer;
begin
r := 0;
Result := '';
v := ChrToNum(B);
for j := 1 to Length(A) do
begin
Result := Result + NumToChr((r*NumSystem + ChrToNum(A[j])) div v);
r := (r*NumSystem + ChrToNum(A[j])) mod v;
end;
Ost := NumToChr(r);
while (Result[1]='0') and (Result<>'0') do delete(Result,1,1);
end;
//Выполняем деление на число, которое больше 9
function Divide(A: String; B: String; var Ost: String): String;
var
Scale, m, n, vJ, uJ, qGuess, i, r, carry, borrow, temp1, temp2, temp : Integer;
U, V, Ut, Vt, q : String;
os : Char;
Aa, Ba, uShift : array[0..50] of Byte;
begin
Result:='';
//Проверяем числа на знаки
if (A[1]='-') and (B[1]='-') then
begin
Delete(A,1,1);
Delete(B,1,1);
end;
if (A[1]='-') and (B[1]<>'-') then
begin
Delete(A,1,1);
Result:= '-' + Result;
end;
if (A[1]<>'-') and (B[1]='-') then
begin
Delete(B,1,1);
Result:= '-' + Result;
end;
if length(B)=1 then
begin
Result:=Result+ShortDiv(A,B[1],os);
Ost:=os;
end
else
begin
Scale := NumSystem div (ChrToNum(B[1])+1);
Ut:=Mul(A,IntToStr(Scale));
Vt:=Mul(B,IntToStr(Scale));
n:=length(Vt);
m:=length(Ut)-length(Vt);
if m<0 then Result:='0';
for i:=1 to m+n do U := U + Ut[m+n-i+1];
for i:=1 to n do V:=V+Vt[n-i+1];
for i:=0 to m+n-1 do Aa[i]:=ChrToNum(U[i+1]);
for i:=0 to n-1 do Ba[i]:=ChrToNum(V[i+1]);
vJ:=m;
uJ:=n+vJ;
i:=0;
while (vJ>=0) do
begin
qGuess := (Aa[uJ]*NumSystem + Aa[uJ-1]) div Ba[n-1];
r := (Aa[uJ]*NumSystem + Aa[uJ-1]) mod Ba[n-1];
while (r < NumSystem) do
begin
temp2:= Ba[n-2]*qGuess;
temp1:= r*NumSystem+Aa[uJ-2];
if (temp2 > temp1) or (qGuess=NumSystem) then
begin
qGuess := qGuess - 1;
r := r + Ba[n-1];
end
else break;
end;
carry:=0;
borrow:=0;
for i:=vJ to m+n-1 do uShift[i-vJ]:=Aa[i];
i:=0;
while (i<n) do
begin
temp1 := Ba[i]*qGuess + carry;
carry := temp1 div NumSystem;
temp1 := temp1 - carry*NumSystem;
temp2:=uShift[i] - temp1 + borrow;
if temp2<0 then
begin
uShift[i]:=temp2 + NumSystem;
borrow := -1;
end
else
begin
uShift[i]:=temp2;
borrow:=0;
end;
i:=i+1;
end;
temp2 := uShift[i] - carry + borrow;
if temp2<0 then
begin
uShift[i]:=temp2 + NumSystem;
borrow := -1;
end
else
begin
uShift[i]:=temp2;
borrow:=0;
end;
if borrow=0 then q:=q+NumToChr(qGuess)
else
begin
q:= q+NumToChr(qGuess-1);
carry:=0;
i:=0;
while (i<n) do
begin
temp:=uShift[i] + Ba[i] + carry;
if temp>=NumSystem then
begin
uShift[i]:=temp - NumSystem;
carry := 1;
end
else
begin
uShift[i]:=temp;
carry:=0;
end;
i:=i+1;
end;
uShift[i]:= uShift[i] + carry - NumSystem;
end;
for i:=vJ to m+n-1 do Aa[i]:=uShift[i-vJ];
i:=m+n-1;
while (i>0) and (Aa[i]=0) do i:=i-1;
m:=i+1-n;
vJ:=vJ-1;
uJ:=uJ-1;
end;
Result:=Result+q;
Ost:=Sub(A,Mul(Result,B));
end;
if Result<>'0' then while (Result[1]='0') do Delete(Result,1,1);
if Result[1]='-' then while (Result[2]='0') do Delete(Result,2,1);
end;
function Pow(A : String; k : String): String;
var
N, Y, Z, N1,Ost : String;
Ostatok : Char;
begin
N := k;
Y := '1';
Z := A;
repeat
N1 := N;
N := ShortDiv(N, '2', Ostatok);
ShortDiv(N1, '2', Ostatok);
if Ostatok <> '0' then Y := Mul(Y, Z);
Z := Mul(Z,Z);
until(N = '0');
Result := Y;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
Edit3.Text := Sum(Edit1.Text, Edit2.Text);
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Edit3.Text := Sub(Edit1.Text, Edit2.Text);
end;
procedure TForm1.Button4Click(Sender: TObject);
var
O1 : String;
begin
Edit3.Text := Divide(Edit1.Text,Edit2.Text,O1);
Edit11.Text := O1;
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
Edit3.Text := Mul(Edit1.Text, Edit2.Text);
end;
//Находим остаток от деления числа в высокой степени на
//задонное число
//1) С помощью бинарного метода
function PowerMod(a, k, m: String): String;
var
N, Y, Z, N1,Ost : String;
Ostatok : Char;
begin
N := k;
Y := '1';
Z := a;
repeat
N1 := N;
N := ShortDiv(N, '2', Ostatok);
ShortDiv(N1, '2', Ostatok);
if Ostatok <> '0' then Y := Mul(Y, Z);
Z := Mul(Z,Z);
until(N = '0');
Divide(Y,m,Ost);
Result := Ost;
end;
//2) С помощью последовательного умножения
function PowerModMul(a, k, m: String): String;
var
i : Integer;
N, Y, Z, N1, Ost : String;
Ostatok : Char;
begin
Y:=Pow(a,k);
if length(m)=1 then ShortDiv(Y, m[1], Ostatok)
else
begin
Divide(Y,m,Ost);
Ostatok := Ost[1];
end;
Result := Ostatok;
end;
//Перевод числа из десятичной системы счисления в
//другую
function SysToSys(A: String; NewSystem: Byte): String;
var
Ost : Char;
Ost1 : String;
sys : Integer;
begin
while A<>'0' do
begin
A := Divide(A,IntToStr(NewSystem),Ost1);
Result := Ost1 + Result;
end;
end;
//3) Упрощенный вариант нахождения остатка
function BinPowerMod(a, k, m: String): String;
var
dk,Ost1 : String;
i : Integer;
Ost : Char;
begin
dk := SysToSys(k,2);
Divide(a,m,Ost1);
for i:=2 to length(dk) do
begin
if dk[i]='0' then Divide(Mul(Ost1,Ost1),m,Ost1)
else
begin
Divide(Mul(Ost1,Ost1),m,Ost1);
Divide(Mul(Ost1,a),m,Ost1);
end;
end;
Result:=Ost1;
end;
procedure TForm1.Button10Click(Sender: TObject);
begin
Edit3.Text := Pow(Edit1.Text, Edit2.Text);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
NumSystem:=StrToInt(Edit4.Text);
end;
procedure TForm1.Edit4Change(Sender: TObject);
begin
NumSystem:=StrToInt(Edit4.Text);
end;
procedure TForm1.Button5Click(Sender: TObject);
begin
Edit3.Text := SysToSys(Edit1.Text,StrToInt(Edit2.Text));
end;
end.
|
--------------------
Мой блог |
[C|C++] Арифметика с большими числами, аналог BigInteger в Java 
Загрузка ...
