ý của mình đây
for i := 2 to b do
sum := 1;
for i := 2 to (b div 2) do
Đúng rồi, chỉ cần như thế thôi.
ý của mình đây
for i := 2 to b do
sum := 1;
for i := 2 to (b div 2) do
Đ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.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) 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);
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.
UC.INP | UC.OUT |
3 4 333 5436 | 9 |
type numArray = array[1..32000] of shortint;
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;
for i := na downto 1 do
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: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 đỡ..
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ả
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.
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.
while (a <> b) do
begin
if (a > b) then a := a - b
else b := b - a;
end;
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
....