Hỏi & đáp lập trình

[canh en buon]

Cuối cùng cũng thi xong:hug: (mặc dù hy sinh gần 1 nữa::( )
Thôi kệ rớt thì hè này cày tiếp...

Thích thì chiều

Đề bài: Hãy tìm đường đi qua 1 ma trận sao cho tổng các số trên đường đi là nhỏ nhất.

Ví dụ: ma trận MxN
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
Tổng các số đã đi qua là 6

Buồn quá, bài post lên mấy ngày mà không ai giải ra.
Chắc tại diễn đàn dành cho gamer nên không ai quan tâm lắm đến lập trình
(bài này mình post bên www.ddth.com thì nhận được rất nhiều cách giải.

Nhưng cũng an ủi là bạn @Gaique9x đã gửi mail bài giải cho mình.

Sử dụng giải thuật tham lam
Ý tưởng: con đường ngắn nhất trong các con đường ngắn nhất là con đường ngắn nhất
...

Bạn @Gaique9x có ý tưởng rất độc đáo, nhưng rất tiếc cách giải của bạn không cho ra đáp án tối ưu.


Trong bài này có 1 cách giải rất hay (sử dung qui hoặch động):

Đầu tiên ta qui hoặch lại cái ma trận theo qui tắc:
+ Giữ nguyên cột đầu tiên (cột 1).
+ Các cột tiếp theo (cột n), tại mổi phần tử ta cộng thêm 1 phần tử kề nó bé nhất trong cột trước đó (cột n-1)
Ví dụ:
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
cột đầu tiên giữ nguyên

5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
phần tử đầu tiên của cột 2 có 2 phần tử kề nó.

5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
ta chọn phận tử 5 là phần tử nhỏ nhất trong các phần tử kề nó

5 7 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
Cộng nó vào

5 7 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
phần tử thứ 2 trong cột 2 ta có 3 phần tử kề nó, ta tiếp tục làm tương tự như trên

5 7 9 2 9 0
6 3 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0

Cứ thế ta qui hoặch xong cột 2.
5 7 9 2 9 0
6 3 2 9 7 1
1 5 2 1 2 5
8 4 8 0 1 0


Tiếp theo cột 3 ta làm tương tự cột 2
5 7 9 2 9 0
6 3 2 9 7 1
1 5 2 1 2 5
8 4 8 0 1 0

5 7 9 2 9 0
6 3 2 9 7 1
1 5 2 1 2 5
8 4 8 0 1 0

5 7 12 2 9 0
6 3 2 9 7 1
1 5 2 1 2 5
8 4 8 0 1 0

5 7 12 2 9 0
6 3 05 9 7 1
1 5 05 1 2 5
8 4 12 0 1 0

Các cột còn lại tương tự, cuối cùng ta có:
5 7 12 07 16 13
6 3 05 14 13 8
1 5 05 06 07 11
8 4 12 05 06 6

Trong cột cuối cùng ta chọn phần tử nhỏ nhất, đó chính là giá trị của đường đi ngắn nhất
5 7 12 07 16 13
6 3 05 14 13 8
1 5 05 06 07 11
8 4 12 05 06 6

ánh xạ vào bảng cũ ta có
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0

Cuối cùng ta chỉ việc truy hồi lại các phần tử kề nó bé nhất là ta đã tìm xong đường đi ngắn nhất.

5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0

kề nó có 2 phần tử
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
???--> lấy phần tử bé nhất

5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0

tương tự ta có
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0

Nếu cải tiến giải thuật này 1 chút cho phép ta mở rộng bài toán ra, bằng cách cho các phần tử có thể đi nhiều hơn N bước (nhưng không được đi lùi)
Ví dụ:
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 7 0 1 1 0
4 2 7 0 0 0

 

[bachkhoapro1204]

Sao ngộ quá hen

Tôi nhớ cái đề lúc đầu là:

Thích thì chiều

Đề bài: Hãy tìm đường đi qua 1 ma trận sao cho tổng các số trên đường đi là nhỏ nhất.

Ví dụ: ma trận MxN
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
Tổng các số đã đi qua là 7

Nhưng sao bây giờ lại:

Thích thì chiều

Đề bài: Hãy tìm đường đi qua 1 ma trận sao cho tổng các số trên đường đi là nhỏ nhất.

Ví dụ: ma trận MxN
5 2 9 2 9 0
6 2 2 9 7 1
1 4 2 1 2 5
8 3 8 0 1 0
Tổng các số đã đi qua là 6

Vậy cái nào là đáp án đúng

 

[bachkhoapro1204]

Bác có thể giải thích kỹ thêm về mấy cái giải thuật đó không (nào là tham lam, nào là qui hoặch động...)

Tôi thấy chúng cũng hay hay, mà học kỳ sau tôi cũng đụng chúng rồi (do đó biết trước vẫn tốt hơn)

Thank

 

[tomorrowneverdies]

Hix, mấy bạn học cao quá mình không dám so...
Gọi b[i,j]( hay b[j] gì cũng được, tùy ngôn ngữ) là đường đi ngắn nhất khi tới ô [i,j], ta có công thức truy hồi: b[i,j]=a[i,j]+max(b[i-1,j-1],b[i,j-1],b[i+1,j-1]).
Tham lam là thuật toán tìm cách tối ưu nhất tại bước mình đang xét, còn qui hoạch động là giải và kết hợp các bài toán con theo quan điểm: tất cả các bài toán con tối ưu thì bài toán lớn cũng tối ưu.
Thôi không dám chen vào '.'.

 

[canh en buon]

Sao ngộ quá hen

Tôi nhớ cái đề lúc đầu là:

Bạn "vạch lá tìm sâu" @bachkhoapro1204 để ý kỹ quá.
Cái đề đầu do tính nhẫm nên bị lộn, xin lổi nhe.
Còn đáp án nào đúng thì chắc bạn đã biết rồi.

Hix, mấy bạn học cao quá mình không dám so...
Gọi b[i,j]( hay b[j] gì cũng được, tùy ngôn ngữ) là đường đi ngắn nhất khi tới ô [i,j], ta có công thức truy hồi: b[i,j]=a[i,j]+max(b[i-1,j-1],b[i,j-1],b[i+1,j-1]).
Tham lam là thuật toán tìm cách tối ưu nhất tại bước mình đang xét, còn qui hoạch động là giải và kết hợp các bài toán con theo quan điểm: tất cả các bài toán con tối ưu thì bài toán lớn cũng tối ưu.
Thôi không dám chen vào '.'.

Bạn @tomorrowneverdies chắc có ý nói mình nhiều chuyện quá.:p

Thực ra nếu dùng công thức truy hồi thì rất dễ, những bạn nào pro về thuật toán nhìn vào là hiểu liền, nhưng còn mấy bác dân thường thì chỉ biết cắn lưỡi nhìn mà không hiểu

Còn về thuật toán mình chỉ có bổ sung 1 tí về qui hoặch động

Thực ra qui hoặch động là 1 biến dạng của giải thuật chia để trị, nhưng có 1 số cải tiến:
+ Chia để trị là chia bài toán lớn thành các bài toán con độc lập nhau (giải từ trên xuống), còn qui hoặch động là kết hợp các bài toán con thành bài toán lớn (giải từ dưới lên).
+ Do đó qui hoặch động sẽ cho ra lời giải tối ưu vì tận dụng lại kết quả các bài toán con, nhưng sẽ tốn bộ nhớ để lưu trữ kết quả trung gian
+ Ngoài ra qui hoặch động chỉ giải được các bài toán có các bài toán con trùng lắp nhau.

Ở trên chỉ là cái nhìn thiển cận của mình mong bạn @tomorrowneverdies đóng góp thêm ý kiến::)

 

[Gaique9x]

Bạn @Gaique9x có ý tưởng rất độc đáo, nhưng rất tiếc cách giải của bạn không cho ra đáp án tối ưu.

Tại sao giải thuật của em không cho kết quả tối ưu.
Anh có thể cho ví dụ demo được không.

Nếu cải tiến giải thuật này 1 chút cho phép ta mở rộng bài toán ra, bằng cách cho các phần tử có thể đi nhiều hơn N bước (nhưng không được đi lùi)

Mấy anh xem công thức truy hồi của bài toán mở rộng đúng không.
b[i,j]=a[i,j]+max(b[i-1,j-1],b[i,j-1],b[i+1,j-1],b[i-1,j],b[i+1,j]).
(tức là ngoài việc xét 3 thằng kề trước nó, ta phải xét thêm 2 thằng kề cạnh nó)

 

[tomorrowneverdies]

Qui hoạch động để tìm ra công thức truy hồi trước hết phải định nghĩa được công thức truy hồi nữa, mà 1 bài toán có thể giải được nhiều cách, vì vậy việc tổ chức bộ nhớ để làm toán cũng khác nhau. Cùng 1 bài có thể bạn dùng tới mảng 2 chiều, có người chỉ dùng tới mảng 1 chiều thôi. Không nhất thiết qui hoạch động là tốn bộ nhớ '.' .

 

[bachkhoapro1204]

Mấy ông giải thích chẳng hiểu gì cả???

Ví dụ như bài tìm tất cả số nguyên tố nhỏ hơn n.
Ta biết: số nguyên tố là số chỉ chia hết cho 1 và chính nó.
Tức là số nào không chia hết cho các số nguyên tố đứng trước nó thì gọi là số nguyên tố.
Cách giải:
+ Giả sử ta có 1 mảng chứa số nguyên tố (lúc đầu rổng)
+ Cho vòng for i = 2 đến n.
+ Mổi lần lặp ta kiểm tra xem i có chia hết cho số nào trong mảng NT không
+ Nếu không chia hết tức i là số nguyên tố, ta đưa i vào mảng NT.
+ Cứ thế cho tới hết vòng for.
*Mảng NT dùng để chứa kết quả trung gian của các bài toán con trước đó.

Vậy ở trên tôi đang sử dụng giải thuật qui hoặch động phải không?

 

[tomorrowneverdies]

Mấy ông giải thích chẳng hiểu gì cả???

Ví dụ như bài tìm tất cả số nguyên tố nhỏ hơn n.
Ta biết: số nguyên tố là số chỉ chia hết cho 1 và chính nó.
Tức là số nào không chia hết cho các số nguyên tố đứng trước nó thì gọi là số nguyên tố.
Cách giải:
+ Giả sử ta có 1 mảng chứa số nguyên tố (lúc đầu rổng)
+ Cho vòng for i = 2 đến n.
+ Mổi lần lặp ta kiểm tra xem i có chia hết cho số nào trong mảng NT không
+ Nếu không chia hết tức i là số nguyên tố, ta đưa i vào mảng NT.
+ Cứ thế cho tới hết vòng for.
*Mảng NT dùng để chứa kết quả trung gian của các bài toán con trước đó.

Vậy ở trên tôi đang sử dụng giải thuật qui hoặch động phải không?

cái này thuật toán sàng Eratosthenes mà '.'.

 

[bachkhoapro1204]

thuật toán sàng Eratosthenes là gì vậy?
Cái phương pháp trên là do tôi tự chế ra mà!

 

[canh en buon]

Sàng Eratosthenes là tên gọi của phương pháp xác định (nhanh) tất cả các số nguyên tố nhỏ hơn một số N cho trước. Ban đầu, ta viết tất cả các số nguyên từ 2 đến N. P = 2. Gạch bỏ các bội số của P có dạng 2*P; điều này có thể thực hiện dễ dàng bằng cách gạch bỏ tất cả các số ở các vị trí thứ P. Sau đó tăng P lên số kế tiếp không bị loại bỏ trong dãy số. Lại gạch bỏ các bội số của P (mới). Lặp các bước này cho đến khi P lớn hơn căn N
___________________________
Các số còn lại sau khi sàng là số nguyên tố.

 

[canh en buon]

Tại sao giải thuật của em không cho kết quả tối ưu.
Anh có thể cho ví dụ demo được không.

Ví dụ:
1 3 2
4 3 2
3 1 0
đáp án:
1 3 2
4 3 1
3 3 0
Nhưng theo giải thuật của em thì:
1 3 2
4 3 4
3 1 0
=>gameover

Mấy anh xem công thức truy hồi của bài toán mở rộng đúng không.
b[i,j]=a[i,j]+max(b[i-1,j-1],b[i,j-1],b[i+1,j-1],b[i-1,j],b[i+1,j]).
(tức là ngoài việc xét 3 thằng kề trước nó, ta phải xét thêm 2 thằng kề cạnh nó)

b[i,j]=a[i,j]+min(b[i-1,j-1],b[i,j-1],b[i+1,j-1],b[i-1,j],b[i+1,j]???)
Công thức truy hồi trên trúng nhưng chưa đúng bởi vì thằng b[i+1,j] em chưa biết làm sao mà tính b[i,j].

Ở đây ta phải chia làm 2 bước:
1\ b[i,j]=a[i,j]+min(b[i-1,j-1], b[i, j-1], b[i+1,j-1])
tính tất cả giá trị của cột j xong rồi mới qua bước 2
2\ b[i,j]=min(b[i-1,j], b[i,j], b[i+1,j])
___________________________
2\ b[i,j]=min(b[i-1,j] + a[i,j], b[i,j], b[i+1,j] + a[i,j])
sơ suất, sorry

 

[canh en buon]

Anh không biết sao?

Vậy thì khổ thật::( ::( ::(

Thực ra em có viết 1 minigame bằng C nhưng khi đem qua máy nhỏ bạn chạy thì nó báo thiếu thư viện.
Vào lớp hỏi ông thầy mới biết đó là thư viện động (nhưng ổng cũng không biết cách link cái thư viện đó vào chương trình, bó tay)

Giờ chỉ còn mong 1 siêu pro nào xuất hiện mà thôi (hic hic)

Bạn Gaique9x viết game à?
Ghê vậy:o

Còn về cách add thư viện động vào chương trình trong C thì mình chỉ biết cách add trong Linux còn Win thì bó tay:p
(đễ mình lên mạng search thử coi).

 

[bachkhoapro1204]

game hả?
game gì vậy?
sao không post lên cho mọi người mở rộng tầm mắt

 

[Gaique9x]

Sorry @bachkhoapro1204, em tìm hoài mà không thấy chỗ đính kèm file.
Để em tìm cách khác thử xem.

 

[canh en buon]

@Gaique9x, bạn phải post đủ 50 bài mới đính kèm file được.

Vậy bạn gửi file đó qua mail của mình đi, mình upload lên cho.

 

[canh en buon]

Đây là game bạn @Gaique9x nhờ mình gửi lên

Nội dung Game:

Tên minigame: "Truy tìm kho báu"
Các đối tượng trong game:
+ Quỷ: xung quanh quỷ có mùi hôi (người chơi vào ô này sẽ bị gameover)
+ Hang động: xung quanh hanh có gió (người chơi vào ô này sẽ bị gameover)
+ Me: người tìm kho báu
+ Kho báu (người chơi vào ô này sẽ chiến thắng)
*** Tóm lại trên bản đồ trò chơi có 6 đối tượng: quỷ, hang động, gió, mùi hôi, người chơi và kho báu.
Cách chơi: người chơi phải tìm cách lấy kho báu nhưng không bị quỷ ăn thịt hoặc rơi xuống hang động
Yêu cầu bài toán: lập trình cho máy chơi (không nhất thiết phải tìm ra kho báu)

Đây là game đầu tay của em nên không tránh khỏi sơ suất mong các bạn đóng góp thêm ý kiến:p

Lưu ý: phải cài VC++ (nếu không sẽ gặp tình trạng thiếu thư viện động)

Mình đã chạy thử rồi!!!
Nếu đây là game đầu tay của bạn thì quả là đáng nể :o (mình không có nịnh đâu)
Nhưng mình có 1 vài nhận xét sau:
+ Giao diện khá bắt mắt
+ Nhưng, cái timer của bạn thiết kế chưa ổn
+ Ngoài ra, sao bạn không sử dụng cơ chế định thời (thread)
mổi lần chơi là phải đợi đến khi kết thút mới tắt được game, rất khó chịu
* Cuối cùng, mình có chút ý kiến, nếu viết game mình khuyên bạn nên viết theo hướng đối tượng, chứ viết theo hướng cấu trúc này thì mình phụt bạn thiệt đấy (không biết bạn debug lỗi làm sao nổi nữa).

 

[Arc Of Triumph]

làm game trong C thì nên dùng WinAPI, chứ đừng nên dùng MFC...
mà mấy cái ảnh .ico đó bạn kiếm ở đâu vậy?

 

[bachkhoapro1204]

game hay lắm, tự làm thiệt hả???:o :o :o

Tui đây cũng thích làm game nhưng không biết bắt đầu từ đâu.
Ai pro chỉ tui nên học cái gì đề làm game với...

 

[Gaique9x]

Em đây cũng thích làm game lắm nhưng khi bắt tay vào làm thì mới thấy nó hết sức khó khắn.
Chỉ có 1 minigame nho nhỏ thôi mà em thức trắng 3 đêm viết tới 1000 dòng code
(nhớ lại còn thấy ngán ngẫm )

Em nghỉ nếu làm game thì phải có phương pháp cụ thể với công cụ đủ mạnh chứ viết bằng C như vậy, cứ vác sức trâu ra mà viết không có định hướng gì cả thì chịu.