Giải thích giúp mình thuật toán của bài này cho minh với( khó quá)

theo bạn cách này có nhanh hơn cách bạn phân tích ko bạn
function pp(n:longint):boolean;
var i:longint;
S:longint;
begin
s:=1;
for i:=2 to trunc(sqrt(n)) do
if n mod i = 0 then
begin
inc(s,i);
if i<>n div i then
inc(s,n div i);
if s>n then exit(true);
end;
exit(s>n);
 

tengiday

Happy life
theo bạn cách này có nhanh hơn cách bạn phân tích ko bạn
function pp(n:longint):boolean;
var i:longint;
S:longint;
begin
s:=1;
for i:=2 to trunc(sqrt(n)) do
if n mod i = 0 then
begin
inc(s,i);
if i<>n div i then
inc(s,n div i);
if s>n then exit(true);
end;
exit(s>n);
Đoạn function này chỉ kiểm tra xem 1 số có phải là số phong phú hay không, chứ ko có liệt kê rồi đếm số phong phú. Bạn cần thêm 1 vòng loop nữa để kiểm tra từng số trong đoạn [left, right] nếu muốn dùng function này.

Thuật toán kiểm tra 1 số có phải là số phong phú hay không khác với thuật toán liệt kê rồi đếm số phong phú. Tương tự như với số nguyên tố: kiểm tra 1 số là số nguyên tố sẽ khác với liệt kê số nguyên tố. Nếu đoạn ko lớn thì sẽ ko thấy gì nhiều, nhưng nếu như lớn thì bấy giờ sự khác biệt rất rõ. Tiêu biểu cho 2 dạng này chính là:
- Với từng số n trong đoạn cần tìm, kiểm tra n có phải là nguyên tố hay không bằng cách tìm ước trong khoảng sqrt(n).
- Sàng nguyên tố (dạng Sieve) từ 2 tới n.

Bạn chạy thử chương trình này sẽ thấy: kết quả đầu là dùng kiểu kiểm tra từng số, kết quả sau là dùng kiểu mình đã ghi. Bạn nhớ chạy bằng Free Pascal nhé.
Mã:
var left, right : longint;


function pp(n:longint):boolean;
var i, S : longint;
begin
    s:=1;
    for i:=2 to trunc(sqrt(n)) do
        if n mod i = 0 then
            begin
                s := s + i;
                if i<>n div i then
                    s := s + n div i;
                if s>n then exit(true);
            end;
    exit(s>n);
end;


function countPP2(left, right : longint) : longint;
var i, count : longint;
begin
    count := 0;
    for i := left to right do
        if PP(i) then
            count := count + 1;
    exit(count);
end;


function countPP1(left, right : longint) : longint;
var i, j, count, t : longint;
    sum : array[2..100001] of longint;
begin
    for i := 2 to right do
        sum[i] := 1;
    count := 0;
    t := right div 2 + 1;
    for i := 2 to t do
        begin
            j := i * 2;
            while (j <= right) do
                begin
                    sum[j] := sum[j] + i;
                    j := j + i;
                end;
            if (i >= left) and (sum[i] > i) then
                inc(count);
        end;
    exit(count);
end;


begin
    left := 2;
    right := 100000;


    writeln(countPP2(left, right));
    writeln(countPP1(left, right));
end.
 
bạn xem bài này có thể giúp được gì cho mình không
Cho số X gồm N chữ số, Số Y gồm M chữ số (1<=M<=32000; 1<=N<=32000)).
Yêu cầu: Tính ucln 2 số X và Y.
Dữ liệu vào: Cho trong file văn bản UC.INP có cấu trúc như sau:
Dòng 1: Ghi 2 số nguyên dương N M mỗi số cách nhau một dấu cách.
Dòng 2: Ghi số X
Dòng 3: Ghi số Y
Dữ liệu ra: Ghi ra file UC.OUT, theo cấu trúc như sau:
Dòng 1: Ghi giá trị UCLN.
Ví dụ:
UC.INP
UC.OUT
3 4
333
5436
9
 

tengiday

Happy life
Bài này đơn giản nhất là dùng thuật toán của Euclid với phép trừ. Tuy nhiên phải làm việc với số lớn.
- Bạn dùng array of shortint gồm 32000 phần tử để lưu số. Dùng shortint để tiết kiệm bộ nhớ. Hàng đơn vị được lưu ở vị trí thứ 1 trong mảng.
- Bạn cần viết 1 function trừ 2 số. Chúng ta trừ tay như thế nào thì viết chương trình như vậy nhé.
- Bạn cũng cần 1 hàm để so sánh 2 số dạng mảng.
 
noi chung mình cũng đã biết cách lưu trữ từng chữ số vào mảng rồi.nhưng chỉ biết được chừng đó thôi.ko biết cách để áp dụng những thuật mà bạn nói..mong bạn giải thích cụ thể cho mình bằng chương trình được ko ak..thanh ban
 

tengiday

Happy life
Mình đang dọn nhà nên mấy hôm nay hơi bận tí. Mình chưa test kỹ lắm, nên bạn kiểm tra lại xem sao nhé.
Đầu tiên, chúng ta cần 1 type của shortint để chứa số trước:
Mã:
type numArray = array[1..32000] of shortint;
Mỗi array phải khởi tạo là 0. Để cho thuận tiện, mỗi một array số, mình đều đi kèm với 1 biến để lưu số chữ số có nghĩa của nó.

Sau đó là procedure so sánh 2 số. Procedure này trả ra 1 nếu a > b; 0 nếu a = b; và -1 nếu a < b.
Mã:
function compare(a: numArray; na: integer; b: numArray; nb: integer) : shortint;
var i : integer;
begin
    if (na < nb) then exit(-1);
    if (na > nb) then exit(1);
    for i := na downto 1 do
        begin
            if (a[i] > b[i]) then exit(1);
            if (a[i] < b[i]) then exit(-1);
        end;
    exit(0);
end;
Tiếp theo là procedure tìm hiệu của 2 số; kết quả sẽ được lưu lại ở số a nhé. Vì tính chất của thuật toán nên mình assume rằng a >= b trong procedure này.
Mã:
procedure differences(var a: numArray; var na: integer; b: numArray; nb: integer);
var i, index : integer;
    nho : shortint;
begin
    nho := 0;
    index := 1;
    for i := 1 to na do
        begin
            if (a[i] >= b[i] + nho) then
                begin
                    a[i] := a[i] - b[i] - nho;
                    nho := 0;
                end
            else
                begin
                    a[i] := a[i] + 10 - b[i] - nho;
                    nho := 1;
                end;
            if (a[i] > 0) then
                index := i;
        end;
    na := index;
end;
Có đủ 2 procedures này rồi thì cuối cùng, chúng ta có thể viết được hàm tìm UCLN như sau:
Mã:
procedure greatestCommonDivisor(var a: numArray; var na: integer; var b: numArray; var nb: integer);
var t : shortint;
begin
    t := compare(a, na, b, nb);
    while (t <> 0) do
        begin
            if (t > 0) then
                differences(a, na, b, nb);
            if (t < 0) then
                differences(b, nb, a, na);
            t := compare(a, na, b, nb);
        end;
end;
Kết quả sẽ được lưu ở 1 trong 2 biến: a và b, đi kèm với số chữ số trong a và b. Để truy xuất kết quả, bạn cần dùng
Mã:
for i := na downto 1 do

PS: Thuật toán này là đơn giản nhất, cho nên nó sẽ chạy không nhanh ở một vài test. Nếu muốn có tốc độ thì phải dùng thuật toán Euclid với mod/div, và phải viết procedure chia 2 số lớn. Để chia 2 số lớn với tốc độ nhanh thì bạn có thể tham khảo cách computer chia 2 số như thế nào.
 
Sửa lần cuối:
cảm ơn bạn rất nhiều.cho mình hỏi thêm ở thủ tục trừ hai số có phải bạn mới chỉ xét 1 trườngng hợp a>=b thôi pải ko ak.
nếu có thời gian rảnh mong bạn có thể post chương trình cho mình với dk ko ak..mình cũng muốn học hỏi thêm kiến thức..mong bạn giúp đỡ..
 

tengiday

Happy life
cảm ơn bạn rất nhiều.cho mình hỏi thêm ở thủ tục trừ hai số có phải bạn mới chỉ xét 1 trườngng hợp a>=b thôi pải ko ak.
nếu có thời gian rảnh mong bạn có thể post chương trình cho mình với dk ko ak..mình cũng muốn học hỏi thêm kiến thức..mong bạn giúp đỡ..
Vì tính chất của thuật toán, lúc nào mình cũng lấy số lớn trừ cho số nhỏ cả, cho nên mình chỉ làm mỗi trường hợp a >= b (thật tế là a > b) thôi. Bạn xem trong hàm greatestCommonDivisor của mình sẽ thấy rõ điều này. Code mình viết cho bạn chỉ còn mỗi nhập xuất và xử lý mấy trường hợp đặc biệt như b = 0, và khởi tạo cho mảng thôi. Bạn có thể test thế này:
Mã:
a[1] := 8; a[2] := 1; na := 2;    // Số 18
b[1] := 2; b[2] := 1; nb := 2;    // Số 12
greatestCommonDivisor(a, na, b, nb);     // UCLN của 18 và 12
for i := na downto 1 do write(a[i]);         // Ghi kết quả
 
BẠN COPY TEXT GIÚP MÌNH VỚI AK. MÌNH TEXT MÀ VẪN CÓ SAI BẠN AK. SAI CHỖ NÀO BẠN CHỈNH SỬA CHO MÌNH HIỂU VỚI NHÉ ( MÌNH TEXT BẰNG TURBO PASCAL ..
const fi='UC.inp';
fo='UC.out';
MAX=32001;
type mmc=array[1..MAX] of byte;
var f:text;
a,B:mmc;n,D,M:INTEGER;
NA,NB: INTEGER;
procedure doc;
var
x:char; I,J,so,code:integer;
begin
assign(f,fi);reset(f);
readln(f,n,m);
for i:=1 to MAX do begin a:=0;b:=0;end;
j:=n;
for i:=1 to n do
begin
read(f,x);
val(x,so,code);
a[j]:=a[j]+so;
j:=j-1;
end;
readln(f);
j:=m;
for i:=1 to m do
begin
read(f,x);
val(x,so,code);
b[j]:=b[j]+so;
j:=j-1;
end;
if m>n then d:=m else d:=n;
close(f);
end;


function compare(a: mmc; na: integer; b: mmc; nb: integer) : longint;
var i : integer;
begin
if (na < nb) then exit;
if (na > nb) then exit;
for i := na downto 1 do
begin
if (a > b) then exit ;
if (a < b) then exit;
end;
exit;
end;
procedure differences(var a: mmc; var na: integer; b: mmc; nb: integer);
var i, index : integer;
nho : longint;
begin
nho := 0;
index := 1;
for i := 1 to na do
begin
if (a >= b + nho) then
begin
a := a - b - nho;
nho := 0;
end
else
begin
a := a + 10 - b - nho;
nho := 1;
end;
if (a > 0) then
index := i;
end;
na := index;
end;
procedure greatestCommonDivisor(var a: mmc; var na: integer; var b: mmc; var nb: integer);
var t : shortint;
begin
t := compare(a, na, b, nb);
while (t <> 0) do
begin
if (t > 0) then
differences(a, na, b, nb);
if (t < 0) then
differences(b, nb, a, na);
t := compare(a, na, b, nb);
end;
end;
procedure xuat;
var i,dem:integer;
begin
assign(f,fo);rewrite(f);
differences(a, na, b, nb);
greatestCommonDivisor(a, na, b, nb);
for i := na downto 1 do write(a);
close(f);
end;
BEGIN
doc;
XUAT;
END.
 

tengiday

Happy life
Về tổng thể là đúng rồi đấy, chỉ có một chỗ cần chỉnh lại. Trong ví dụ của mình, na là số chữ số của a, nb là số chữ số của b. Như vậy, bạn xem trong "procedure xuat", số chữ số của a là biến nào, và tương tự cho số chữ số của b?
Ngoài ra, ko biết có phải lúc paste ra bị thiếu ký tự, mấy cái exit trả ra kết quả bạn nên chỉnh cho chính xác 1, -1, 0 nhé. Function compare chỉ ra 3 giá trị là -1, 0, 1 cho nên ko cần tới longint đâu bạn; chỉ cần shortint là đủ.
 
bạn thử xem giúp mình. mình chỉnh sửa lại rồi mà nó lại bào lỗi tràn stack tai thủ tục trừ 2 mảng vậy ak

const fi='UC.inp';
fo='UC.out';
MAX=32001;
type mmc=array[1..MAX] of byte;
var f:text;
a,B:mmc;n,D,M:INTEGER;
NA,NB: INTEGER;
procedure doc;
var
x:char; I,J,so,code:integer;
begin
assign(f,fi);reset(f);
readln(f,n,m);
for i:=1 to MAX do begin a:=0;b:=0;end;
j:=n;
for i:=1 to n do
begin
read(f,x);
val(x,so,code);
a[j]:=a[j]+so;
j:=j-1;
end;
readln(f);
j:=m;
for i:=1 to m do
begin
read(f,x);
val(x,so,code);
b[j]:=b[j]+so;
j:=j-1;
end;
close(f);
end;
function compare(a: mmc; n: integer; b: mmc; m: integer) : integer;
var i : integer;
begin
if (n < m) then exit; compare:=1;
if (n > m) then exit;compare:=-1;
exit;
compare := 0;
for i := n downto 1 do
begin
if (a > b) then exit; compare := 1 ;
if (a < b) then exit; compare:= -1
end;
exit;
compare:= 0;
end;
procedure differences(var a: mmc; var n: integer; b: mmc; m: integer);
var i, index : integer;
nho : longint;
begin
nho := 0;
index := 1;
for i := 1 to n do
begin
if (a >= b + nho) then
begin
a := a - b - nho;
nho := 0;
end
else
begin
a := a + 10 - b - nho;
nho := 1;
end;
if (a > 0) then
index := i;
end;
na := index;
end;
procedure greatestCommonDivisor(var a: mmc; var n: integer; var b: mmc; var m: integer);
var t : shortint;
begin
t := compare(a, n, b, m);
while (t <> 0) do
begin
if (t > 0) then
differences(a, n, b, m);
if (t < 0) then
differences(b, m, a, n);
t := compare(a, n, b, m);
end;
end;
procedure xuat;
var i,dem:integer;
begin
assign(f,fo);rewrite(f);
differences(a, n, b, m);
greatestCommonDivisor(a, n, b, m);
for i := n downto 1 do write(a);
close(f);
end;
BEGIN
doc;
XUAT;
END.
 

tengiday

Happy life
Bạn thử đoạn code này xem sao:
Mã:
const   MAX = 32001;
        fi = 'UC.INP';
        fo = 'UC.OUT';
type numArray = array[1..MAX] of shortint;
var a, b : numArray;
    n, m : integer;
    f : text;


procedure doc;
var x : char;
    i, so, code : integer;
begin
    assign(f, fi); reset(f);
    readln(f, n, m);
    for i:=1 to MAX do begin a[i]:=0; b[i]:=0; end;
    for i:=n downto 1 do
        begin
            read(f, x);
            val(x, so, code);
            a[i] := so;
        end;
    readln(f);
    for i:=m downto 1 do
        begin
            read(f, x);
            val(x, so, code);
            b[i] := so;
        end;
    close(f);
end;


function compare(a: numArray; na: integer; b: numArray; nb: integer) : shortint;
var i : integer;
begin
    if (na < nb) then exit(-1);
    if (na > nb) then exit(1);
    for i := na downto 1 do
        begin
            if (a[i] > b[i]) then exit(1);
            if (a[i] < b[i]) then exit(-1);
        end;
    exit(0);
end;


procedure differences(var a: numArray; var na: integer; b: numArray; nb: integer);
var i, index : integer;
    nho : shortint;
begin
    nho := 0;
    index := 1;
    for i := 1 to na do
        begin
            if (a[i] >= b[i] + nho) then
                begin
                    a[i] := a[i] - b[i] - nho;
                    nho := 0;
                end
            else
                begin
                    a[i] := a[i] + 10 - b[i] - nho;
                    nho := 1;
                end;
            if (a[i] > 0) then
                index := i;
        end;
    na := index;
end;


procedure greatestCommonDivisor(var a: numArray; var na: integer; var b: numArray; var nb: integer);
var t : shortint;
begin
    t := compare(a, na, b, nb);
    while (t <> 0) do
        begin
            if (t > 0) then
                differences(a, na, b, nb);
            if (t < 0) then
                differences(b, nb, a, na);
            t := compare(a, na, b, nb);
        end;
end;


procedure xuat;
var i : integer;
begin
    assign(f,fo); rewrite(f);
    for i := n downto 1 do write(a[i]);
    close(f);
end;


begin
    doc;
    greatestCommonDivisor(a, n, b, m);
    xuat;
end.
Mình gắn phần của mình và phần của bạn viết vào với nhau.
 
mình cũng đã text thử cả hai bài của mình và của bạn lên hai môi truong turbo va free nhưng vân ko dk ban ak mong bạn xem lại giúp mình với.cho mình hỏi cái này nữa ở chỗ này
t := compare(a, na, b, nb);//với cái này t sẽ nhận 1 , -1 , 0 mục đích làm j hở bạn
{ nhờ bạn giải thích đoạn code này mình với}
while (t <> 0) do
begin
if (t > 0) then
differences(a, na, b, nb);
if (t < 0) then
differences(b, nb, a, na);
t := compare(a, na, b, nb);
end;
 

tengiday

Happy life
1) Mình chạy bằng chương trình Pascal online, ko có cài đặt vào máy. Bạn thử thế này ở Begin, End. của chương trình chính, comment out cái 'doc', 'xuat' đi:
Mã:
begin
    a[1] := 8; a[2] := 0; a[3] := 1; n := 3;     // số 108
    b[1] := 2; b[2] := 7; m := 2;     // số 72
    greatestCommonDivisor(a, n, b, m);
    for i := n downto 1 do write(a[i]);     // in ra số 36
    writeln();
end.
Như thế nó chạy đúng ko bạn?

2) Đoạn 'while do' đó là thuật toán tìm UCLN của 2 số a và b. Lẽ ra nó là vầy:
Mã:
while (a <> b) do
   begin
      if (a > b) then a := a - b
      else b := b - a;
   end;
Nhưng khi làm việc với số lớn nên phải thay đổi cho phù hợp.
 
uk thank bạn nhiều.mình đang thử text lại. ak mình cũng đang tìm hiểu về giải thuật quay lui mình có bài quay lui này
nhờ bạn giải thích thuật toán cho mình hiểu về thuật toán với ak
bài toán atm
Một máy ATM hiện có n < = 20 tờ tiền có giá t1, t2.t3...tn. Hãy đưa ra mộtcách trả với số tiền ñúng bằng s
.Dữ liệu vào từ file “ATM.INP” có dạng:
- Dòng đầu là 2 số
n và s
- Dòng thứ 2 gồm ' số t1, t2...tn.
Kết quả ra file “ATM.OUT” có dạng: Nếu có thể trả đúng thì đưa ra cách trả,nếu không ghi -1.
ATM.INP
10 390
200 10 20 20 50 50 50 50 100 100
ATM.OUT
20 20 50 50 50 100 100
bài giải
const MAX =20;
fi ='ATM.INP';
fo ='ATM.OUT';
type vector =array[1..MAX]of longint;
var t :array[1..MAX]of longint;
x,xs : vector;
n,s,sum :longint;
ok :boolean;
procedure input;
var f :text;
i :longint;
begin
assign(f,fi); reset(f);
readln(f,n, s);
for i:=1 to n do read(f,t);
close(f);
end;
procedure check(x:ector);
var i :longint;
f :text;
begin
if sum = s then begin
xs:=x;
ok:=true;
end;
end;
procedure printResult;
var i :longint;
f :text;
begin
assign(f,fo); rewrite(f);
if ok then begin
for i:=1 to n do
71
if xs=1 then write(f,t,' ');
end
else write(f,'-1');
close(f);
end;
procedure backTrack(i:longint);
var j :longint;
begin
for j:=0 to 1 do begin
x:=j;
sum:=sum + x*t;
if (i=n) then check(x)
else if sum<=s then backTrack(i+1);
if ok then exit; {nếu ñã tìm ñược nghiệm thì không duyệt nữa}
sum:=sum - x*t;
end;
end;
BEGIN
input;
ok:=false;
sum:=0;
backTrack(1);
PrintResult;
END.
mong bạn giúp đỡ....

 

tengiday

Happy life
Nói thật ngắn gọn thì thuật toán này duyệt hết những tổ hợp "tiền" rồi tìm ra một tổ hợp mà tổng của nó bằng s. Cách duyệt của nó là dùng đệ quy quay lui.
- Mảng x dùng để đánh dấu tờ tiền nào mình đã dùng. x = 1 tức là tờ tiền t đang dùng.
- Cách chương trình điền vào mảng x sẽ như thế này, và dựa vào đó sẽ biết được tờ tiền nào đang đc dùng.
Mã:
0 0 0 0 0 0 0 0 0 0   Ko chọn tờ nào
0 0 0 0 0 0 0 0 0 1   Chọn tờ cuối
0 0 0 0 0 0 0 0 1 0   Chọn tờ áp cuối
0 0 0 0 0 0 0 0 1 1   Chọn 2 tờ cuối
0 0 0 0 0 0 0 1 0 0   Chọn tờ thứ 3 từ cuối
0 0 0 0 0 0 0 1 1 0   Chọn 2 tờ áp cuối
....
 

Bài viết đang hot

Thống kê

Chủ đề
102,777
Bài viết
470,596
Thành viên
340,591
Thành viên mới nhất
Quang Nguyễn NĐ
Top