1. Duyệt xuôi và duyệt ngƣợc
Giai đoạn duyệt xuôi: từ điểm xuất phát, dựa trên những nhận xét hợp l{ nào đó sẽ lần
lượt tìm ra những điểm trung gian cần phải qua trước khi tới đích trên hành trình ngắn nhất.
Trong giai đoạn tìm kiếm theo chiều thuận này, người ta lưu lại vết của hành trình vào một
mảng trace mà trace*i+=j có { nghĩa điểm j là điểm cần phải qua ngay trước điểm i trong
hành trình ngắn nhất.
Giai đoạn duyệt ngược: Với mảng trace, từ trace[kt]=i1 biết được trước khi đến điểm
đích kt phải qua điểm i1. Tương tự, từ trace[i1]=i2 biết được trước khi đến điểm i1 phải qua
điểm i2…, cuối cùng, từ trace[ik]=xp biết được trước khi đến điểm ik phải qua điểm xuất phát
xp. Suy ra hành trình ngắn nhất là xp
ik…i2i1
kt.
Ví dụ 1. Phân tích số thành tổng hai lập phương
Phân tích một số nguyên dương N thành tổng hai lập phương của hai số nguyên
dương. Có bao nhiêu cách khác nhau?
Input: Số N nhập từ bàn phím
Output: Đưa kết quả ra màn hình, mỗi cách trên một dòng
Phân tích.
Bình thường có thể xét mọi cặp số nguyên dương i và j có giá trị tăng dần để chọn ra
những cặp (i,j) mà i3
+j3
=N.
Tuy nhiên nhận thấy nếu i tăng thì j giảm nên ta có thể dùng phương pháp duyệt đồng
thời ngược và xuôi (i: tăng dần, j: giảm dần) như sau: Ban đầu chọn j có giá trị cao nhất, còn i
=1. Kiểm tra k=i3
+j3
, nếu k=N thì cặp (i,j) này là một kết quả, tiếp tục tăng i và giảm j, nếu
k>N thì giảm j, nếu k<N thì tăng i. Công việc này được lặp cho đến khi i>j. Cách duyệt này
hiệu quả hơn cách bình thường.
Văn bản chương trình.
uses Crt;
var i,j,count,N,k : Integer;
BEGIN
write('Nhập N = '); Readln(N);
count:= 0;
i := 1;
Blog Thuật toán
3
j := 1;
while (j*j*j+1<N) do Inc(j);
repeat
k :=i*i*i+j*j*j;
if k=N then begin
Inc(count);
Write(i:4,j:4); Inc(i) ; Dec(j);
end;
if k < N then Inc(i);
if k > N then Dec(j);
until i >j;
writeln('Co ',count,' Cach phan tich ' );
readln
END.