//
you're reading...
Dùng cho thi học sinh giỏi

Xử lý số nguyên lớn


Đọc thêm về số nguyên lớn


  1. Đề tài về số nguyên lớn
  2. _
  3. _
  4. _

A. Xử lý số nguyên lớn dùng xâu

Các đề mục của phần này ghi theo trong giáo trình Tài liệu giáo khoa chuyên Tin, quyển I.


7.1.Khai báo kiểu số nguyên lớn dùng xâu


Type BigNum = string;


7.2.Hàm so sánh hai số nguyên lớn dùng xâu


function        cmp(a,b : bigNum): integer; 
begin 
      while length(a)<length(b) do a:='0'+a; 
      while length(b) b then exit(1); 
      exit( 1); 
end;

7.3. Hàm cộng hai số nguyên lớn dùng xâu


function add(a,b : bigNum): bigNum;
var sum, carry, i, x, y : integer;
    c : bigNum;
begin
    carry:=0;c:='';
    while length(a)<length(b) do a:='0'+a;
    while length(b)0 then c:='1'+c;
     add:=c;
end;

7.3. Hàm trừ hai số nguyên lớn kiểu xâu


function sub(a,b:bigNum):bigNum;
var c :bigNum; s,borrow,i :integer;
begin
borrow:=0;c:='';
while length(a)<length(b) do a:='0'+a;
while length(b)<length(a) do b:='0'+b;
for i:=length(a) downto 1 do
begin
s:=ord(a[i]) - ord(b[i]) -borrow;
if s1)and(c[1]='0') do delete(c,1,1);
sub:=c;
end;



7.x


_


7.x


_


7.x


_


7.x


_


7.x


_


7.x


_


7.x


_


7.x


_


7.x


_

Type BigNum = string;
Type SignBigNum= record
dau: integer;
giatri:BigNum;
end;
var
a,b: BigNum;
sa,sb: SignBigNum;

function SoSanhSoNguyenLonKhongDau(a,b : bigNum): integer;
begin
while length(a)<length(b) do a:='0'+a;
while length(b) b then exit(1);
exit(-1);
end;

function SoSanhSoNguyenLonCoDau(sa,sb : SignBigNum): integer;
begin
if (sa.dau = sb.dau) and (SoSanhSoNguyenLonKhongDau(sa.giatri,sb.giatri) = 0) then exit(0);
if (sa.dau = -1) and (sb.dau= 1) then exit(-1);
if (sa.dau = -1) and (sb.dau= -1) and (SoSanhSoNguyenLonKhongDau(sa.giatri,sb.giatri) =1) then exit(-1);
if (sa.dau = 1) and (sb.dau= 1) and (SoSanhSoNguyenLonKhongDau(sa.giatri,sb.giatri) = -1) then exit(-1);
if (sa.dau = 1) and (sb.dau= -1) then exit(1);
if (sa.dau = -1) and (sb.dau= -1) and (SoSanhSoNguyenLonKhongDau(sa.giatri,sb.giatri) =-1) then exit(1);
if (sa.dau = 1) and (sb.dau= 1) and (SoSanhSoNguyenLonKhongDau(sa.giatri,sb.giatri) = 1) then exit(1);
end;

function multiply1(a:bigNum;b:longint):bigNum; var i :integer;
carry,s :longint;
c,tmp :bigNum;
begin
c:=”;
carry:=0;
for i:=length(a) downto 1 do
begin
s:=(ord(a[i]) -48) * b + carry;
carry:= s div 10;
c:=chr(s mod 10 + 48)+c;
end;
if carry>0 then str(carry,tmp) else tmp:=”;
multiply1:=tmp+c;
end;

function multiply2(a,b:bigNum):bigNum; var sum,tmp :bigNum;
m,i,j :integer;
begin
m:= -1;
sum:=”;
for i:=length(a) downto 1 do
begin
m:=m+1;
tmp:=”;
for j:=1 to ord(a[i])-48 do tmp:= add(tmp,b);
for j:=1 to m do tmp:=tmp+’0′;
sum:=add(tmp,sum);
end;
multiply2:=sum;
end;

function bigDiv1(a:bigNum;b:longint):bigNum; var s,i,hold:longint;
c:bigNum;
begin
hold:=0;s:=0; c:=”;
for i:=1 to length(a) do
begin
hold:=hold*10 + ord(a[i]) -48;
s:=hold div b;
hold:=hold mod b;
c:=c+chr(s+48);
end;
while (length(c)>1) and(c[1]=’0′) do
delete(c,1,1);
bigDiv1:=c;
end;

function bigMod1(a:bigNum;b:longint):longint; var i,hold:longint;
begin
hold:=0;
for i:=1 to length(a) do
hold:=(ord(a[i]) -48+hold*10) mod b;
bigMod1:=hold;
end;
function bigDiv2(a,b:bigNum):bigNum; var c,hold :bigNum;
kb :array[0..10]of bigNum;
i,k :longint;
begin
kb[0]:=’0′;
for i:=1 to 10 do
kb[i]:=add(kb[i-1],b);
hold:=”;
c:=”;
for i:=1 to length(a) do
begin
hold:=hold+a[i];
k:=1;
while SoSanhSoNguyenLonKhongDau(hold,kb[k]) 1 do
inc(k);
c:=c+chr(k- 1+48);
hold:=sub(hold,kb[k-1]);
end;
while (length(c)>1)and(c[1]=’0′) do delete(c,1,1);
bigDiv2:=c;
end;

function bigMod2(a,b:bigNum):bigNum; var hold :bigNum;
kb :array[0..10]of bigNum;
i,k :longint;
begin
kb[0]:=’0′;
for i:=1 to 10 do
kb[i]:=add(kb[i- 1],b);
hold:=”;
for i:=1 to length(a) do
begin
hold:=hold+a[i];
k:=1;
while SoSanhSoNguyenLonKhongDau(hold,kb[k]) 1 do
inc(k);
hold:=sub(hold,kb[k- 1]);
end;
bigMod2:=hold;
end;

begin
write(‘Nhap sa=’);
readln(sa.dau, sa.giatri);

write(‘Nhap sb=’);
readln(sb.dau, sb.giatri);

case SoSanhSoNguyenLonCoDau(sa,sb) of
1: writeln(sa.dau,sa.giatri, ‘ > ‘,sb.dau,sb.giatri);
0: writeln(sa.dau,sa.giatri, ‘ = ‘,sb.dau,sb.giatri);
-1: writeln(sa.dau,sa.giatri, ‘ < ',sb.dau,sb.giatri);
end;
writeln;
end.


Đọc thêm về số nguyên lớn


  1. Đề tài về số nguyên lớn
  2. _
  3. _
  4. _

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Chín 2016
H B T N S B C
« Th6   Th10 »
 1234
567891011
12131415161718
19202122232425
2627282930  

NCT Computer

Flickr Photos

lost

Lookkk deeeply into my eyes....

Cimitero San Michele

More Photos

Thống kê

  • 115,518 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: