Bài toán mã đi tuần

#1

Đọc trên mạng thì em thấy có thuật toán mã đi tuần, xem code thì em thấy khá dài, em biến tấu một chút theo ý mình thì em thấy nó chạy hình như không bao giờ dừng, em nghĩ mãi mà không biết đã sai chỗ nào ạ!!!

program gin;
uses crt;
const 
	h : array[1..8] of Integer = (2, 1, -1, -2, -2, -1,  1,  2);
	c : array[1..8] of Integer = (1, 2,  2,  1, -1, -2, -2, -1);
var 
	t, i, j, cot, hang : Integer;
	a : array[1..100, 1..100] of Integer;
	kt : array[-2..11, -2..11] of Boolean;
procedure print;
var 
	i : Integer;
begin 
	for i := 1 to 8 do
	begin 
		for j := 1 to 8 do write(a[i, j],' ');
		writeln;
	end;
	halt;
end;
procedure try(i, j : Integer);
var
	g : Integer;
begin
	a[i, j] := t;
	// writeln(t);
	if t = 64 then print
	else 
	for g := 1 to 8 do if kt[i + h[g], j+ c[g]] then 
	begin 
		kt[i, j] := false;
		inc(t);
		try(i + h[g], j + c[g]);
		kt[i, j] := true;
		dec(t);
	end;
end;

begin 
	write('Nhap toa do : ');
	read(hang, cot);
	t := 1;
	for i:= low(kt) to high(kt) do 
	for j := low(kt[i]) to high(kt[i]) do 
	kt[i, j] := false;
	for i:=1 to 8 do 
	for j:=1 to 8 do 
	kt[i, j] := true;
	try(hang, cot);
end.
#2

Biến tấu làm gì…
Hàm low, high là cái gì thế, lần đầu mình thấy luôn :v
Bạn debug thử bằng cách thêm writeln(i, ' ', j) để xem bạn đã duyệt qua các trạng thái nào.
Mà để mảng 5x5 debug cho dễ, 8x8 hơi khó quan sát.

UPD: Đã nhìn thấy lỗi. Phải gán kt[i+h[g], j+c[g]] = false, nếu không chỉ sau 2 trạng thái nó sẽ quay về trạng thái cũ.
VD: Từ i, j -> i+1, j+2 -> i, j -> … -> lặp vô hạn
Mục đích của quay lui là quay cái trạng thái đích (là i+h[g], j+c[g]) kia. Còn trạng thái của i, j phải được gán ở đầu hàm, tức là

procedure try(i, j)
begin
    kt[i, j] := false;
    {code}
    for g:=1 to 8 do
        if kt[i+h[g], j+c[g]] = true then
        begin
            kt[i+h[g], j+c[g]] := false;
            try(i+h[g], j+c[g]);
            kt[i+h[g], j+c[g]] := true;
        end;
end;

Kia là mã giả thôi. Mà nói thật là chả ai đi code ngược đời như bạn, bình thường ô đã duyệt được gán là true, chưa duyệt là false; thế mà bạn gán ngược lại :v

1 Like
#3

Biến tấu cho hiểu rõ chứ anh

https://www.freepascal.org/docs-html/rtl/system/low.html
https://www.freepascal.org/docs-html/rtl/system/high.html

Tại em quen tay rồi, từ trước giờ cứ cái nào đã duyệt qua thì false

#4

Đậu, đừng có mà chưa hiểu code đã biến tấu rồi :v Nhiều code đúng sau khi biến tấu đã trở thành code không thể debug nổi :v

Hàm low và high dùng làm gì, đừng nghịch dại. Tốt nhất là bỏ đi plz. Các chỉ số của hàm kt không chạy quá 0…n được đâu.
-> Nói luôn: thêm điều kiện i+h[g] và j+c[g] nằm trong khoảng duyệt được (tức là từ 0…n-1 hoặc 1…n), điều này rất quan trọng.

Đừng quen dại -_- sau này nhiều bài toán khác phải xác định rõ ràng trạng thái true và false, không phải cứ gán bừa là được. Quen tay kiểu này có ngày debug code đến vỡ mồm :v

2 Likes
#5

Là sao anh, nói rõ được không ạ

Em làm một số trường hợp đúng còn một số trường hợp nó như này

Nhap toa do : 4 5 
64 45 32 27 22 7 24 27 
53 36 29 44 31 26 21 6 
46 63 52 33 28 23 8 25 
37 54 35 30 43 10 5 20 
62 47 58 51 34 19 14 9 
55 38 61 42 17 2 11 4 
48 59 40 57 50 13 18 15 
39 56 49 60 41 16 3 12

Không tìm thấy số 1 mà có lận 2 số 27 luôn!!

#6

Rõ ràng là i+h[g], j+c[g] là trạng thái sau của i, j còn gì. Mà trạng thái sau bắt buộc phải truy cập được chứ.
i, j truy cập được <-> 1 <= i, j <= 8
-> i+h[g], j+c[g] truy cập được <-> 1 <= i+h[g], j+c[g] <= 8

2 số 27 là do có 1 số 27 khác đè vào số 1. Mà trường hợp như vậy xảy ra là do code sai!

UPD: Không thấy số 1 là do ô hang, cot không gán kt[hang, cot] đã duyệt. Ô hang, cot là ô đầu tiên và bắt buộc phải duyệt từ đầu, nên phải gán kt[hang, cot] = true, tức là đã duyệt.

1 Like
#7

Khi em làm vậy thì nó lại lặp vô hạn như ban đầu

#8

Gán bằng true nếu như bạn coi true là đã duyệt…
Mình tạm coi true là đã duyệt.
Mã giả:

procedure try(i, j)
begin
    a[i, j] := t;
    for g:=1 to 8 do
        if (1 <= i+h[g] <= 8) and (1 <= j+c[g] <=8) and (kt[i+h[g], j+c[g]] = true) then
        begin
            kt[i+h[g], j+c[g]] := true;
            inc(t);
            try(i+h[g], j+c[g]);
            kt[i+h[g], j+c[g]] := false;
            dec(t);
        end;

{code...}

begin
    readln(hang, cot);
    for i:=1 to 8 do
        for j:=1 to 8 do kt[i, j] := false;
    
    t := 1;
    kt[hang, cot] := true;
    try(hang, cot);
end.
1 Like
#9

Mình cũng hay code kiểu TRUE là chưa duyệt vìIf kt[i] then... có vẻ thuận tay hơn :v
Chủ thread dính vô hạn có lẽ do để mã chạy quá khỏi bàn cờ đấy

1 Like
#10

Dính vô hạn vì 2 nguyên nhân:

  • Chạy quá khỏi bàn cờ
  • Chạy vào 2 ô kề nhau suốt, như i, j và i + 2, j + 1.
1 Like
#11

Thớt nên đặt tên hằng số để tránh những vấn đề ntn và cho người khác dễ đọc code.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?