Nhập x,n. Tính 4 chữ số tận cùng của x^n ????????? Ai pro cho tôi xin code pascal bài trên bằng pp đệ quy ( thuật toán chia để trị) .?

Propram VD;

Uses crt;

Var a : real;

x, b, i : integer;

n : Byte;

Begin

Clrscr;

Write(`Nhap (x;n) = ´); Read(x;n);

Writeln;

a:=1;

If n>1 then For i:=1 to n do a:=a*x;

If a<10000 then write(`4 chu so cuoi la ´,a)

Else

begin

b:=a - 10000*(Trunc(a/10000));

Write(`4 chu so cuoi la ´,b);

end;

Readln

End.

Hàm Trunc(x) là lấy phần nguyên của số thực x

Vd: Trunc(3,45)

Kết quả = 3

Lấy a là kq của biểu thức x^n chia cho 10000 để dịch chuyển dấu phẩy thập phân sang trái 4 chữ số rồi lấy phần nguyên nhân cho 10000 để hoàn lại, sau đó lấy số ban đầu trừ lại là ra 4 chữ số cuối là b.

b

4 chữ số tận cùng nên chỉ cần lấy số <10000.

Cách giải:

c = 10000

y = x mod c

i=0

r = 1

while ( i < n) 

    r = r * y

    r = r mod c

end_while

print( r)

cách giải này sẽ không bị tràn số khi tính x^n

k

c

bổ sung là x<=1000, n<=10^12 :V