Dùng Excel tạo bộ Test cho các bài toán tin (2 người xem)

[chibi]

Khi làm các bài tập tin trong sách (THCS và THPT) thường các bộ test với số lượng ít và đơn giản. Để đánh giá tốt thuật toán của các bài giải chúng ta cần có những bộ test lớn.
Tôi mong muốn các bạn giúp các thày cô giáo có được những bộ test đa dạng cho các bài toán tin.
Đây là ví dụ thứ nhất cho chủ đề này.
Ví dụ 1: Cho bảng A kích thường m x n (m dòng, n cột), mỗi ô trong bảng có kí hiệu là A(i,j) (hàng i cột j) chứa 1 số nguyên dương. Từ ô A(i,j) có thể đi được tới A(i-1,j+1) hoặc A(i,j+1) hoặc A(i+1,j+1).

Tìm đường đi từ cột 1 đến cột n sao cho tổng giá trị trong các ô đi qua là lớn nhất.
Thuật giải: Ta gọi A(i,j) là giá trị trong các ô A(i,j). B(i,j) là tổng lớn nhất của các ô đi qua từ cột 1 đến ô A(i,j), như vậy ta có công thức:

B(i,1)=A(i,1)
B(i,j)= Max{B(i-1,j-1), B(i,j-1), B(i+1,j-1)} + A(i,j)

Và kết quả cuối cùng là Max{B(i,n)}.
Bộ test trong file đính kèm.

 

[tigertiger]

Tìm đường đi từ cột 1 đến cột n sao cho tổng giá trị trong các ô đi qua là lớn nhất.

oh, lời giải phải chỉ ra đường đi cơ mà, chibi ơi

chưa download file về nhưng nếu theo bạn thì KQ chỉ ra tổng thôi và vị trí ô cuối thôi nhỉ, k chỉ ra vị trí

bài này trong tin học thường dùng thuật toán "thử sai quay luu" - không biết đúng ý tác giả ko

 

[chibi]

Không phải là dùng Excel để giải các bài toán tin mà là dùng Excel để tạo ra các bộ dữ liệu test cho các bài toán tin.