Lính canh ?

[m2mpro]

Em có nghe một anh nói kĩ thuật lính canh trong lập trình nhưng không hiểu nó dùng để làm gì ? Và kĩ thuật cài đặt nó ra sao ?
{*Tiện thể "đệ quy quay lui" và "vét cạn" là gì và cài đặt như thế nào ạ ? *}

[phuclun]

bạn hiểu nhiều về QHĐ thế mà chưa học mấy cái này sao.Chẳng biết có đúng ko nhưng tui cứ nói đại nha
Kỹ thuật lính canh là kỹ thuật dùng 1 biến để chặn đầu{để ngăn ko cho làm phép tính toán hay so sánh nữa}.Tôi nhớ là có 1 thuật toán sắp xếp nào đó cũng dùng phương pháp này{mà hình như quên tên mất rồi.Xin lỗi nha}
Còn ''đệ quy quay lui'' thì chưa nghe.Chắc cũng giống quay lui.Cái này chắc bạn học rồi.
''Vét cạn''là phương pháp kiểm tra tất cả các trườnng hợp có thể xảy ra của bài toán.Hầu hết các bài toán mình làm trước đây đều xài vét cạn.Xài vét cạn có ưu điểm là kiểm tra đc tất cả nhưng phải xài bộ nhớ nhiều=chạy lâu=dễ mất điểm.

[m2mpro]

Quy hoạch động là copy lại thôi mà.
- Dù sao cũng cám ơn bạn nhé.
"Đệ quy quay lui" là quay lui, giờ mới biết, có cái hàm try(i+1) nên mới gọi là đệ quy quay lui.
"Vét cạn" thì xài nhiều quá rồi.

[Master_Baby]

Hơ hơ, giờ tui mới biết cái tên "kỹ thuật lính canh" đó ạ :D

[whitepenguin]

Em chẳng hiểu anh nói Lính canh là cái gi , Never heard of that
Dạo này chế ra tùm lum kỹ thuật ,em cũn thua luôn :D

[mr_invincible]

Cái kĩ thuật lính canh này tôi cũng mới nghe lần đầu, không hiểu bạn đọc đâu ra vậy.
Còn đệ quy quay lui hay vét cạn theo tôi cũng chỉ là một, là cách kiểm tra tất cả các khả năng, như kiểu liệt kê hoán vị hay tìm đường trên đồ thị.

[bete]

Nếu tui không lầm thì thuật ngữ tiếng Anh của "kỹ thuật lính canh" là "sentinel technique". Nó là như bạn phuclun đã nói: đặt 1 phần tử có giá trị đặc biệt vô cuối mảng để chặn đuôi khi duyệt 1 mảng (ví dụ: chuỗi ký tự trong C được tận cùng là 1 ký tự NULL)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[m2mpro]

Cám ơn mọi người đã hướng dẫn.

[whitepenguin]

Nếu vậy thì tại sao lại gọi là kỹ thuật. Nó giông như 1 cái cờ để nhận biết thôi mà.
Em Search hết rồi mà chẳng thấy nói gì đến việc này cả.


Kỹ thuật lính canh là kỹ thuật dùng 1 biến để chặn đầu{để ngăn ko cho làm phép tính toán hay so sánh nữa

Hay là ý anh nói đến cái
Do

Lính đó làm 1 cái Break thế là thoát
không phải làm gì thêm

while(1)

[bete]

Thân gửi bạn whitepenguin,

Nếu vậy thì tại sao lại gọi là kỹ thuật......Em Search hết rồi mà chẳng thấy nói gì đến việc này cả.

http://www.google.com/search?q=%22sentinel+technique%22+programming

nếu bạn thấy chữ "kỹ thuật" nghe nặng nề quá thì "thủ thuật" được hay không ?

-thân

[phuclun]

àh,hình như mình nói nhầm chút xíu,ko phải thuật toán sắp xếp mà là bài toán trộn 2 mảng tăng dần{hoặc giảm dần} lại với nhau để thành 1 mảng co thứ tự giống{hoặc ngược} với thứ tự của 2 mảng trên.
Cách làm với 2 mảng tăng dần.Khởi gán i=1,j=1,so sánh a[i] và b[j],số nào bé hơn thì cho vào mảng c,tăng i hoặc j lên{tăng cái số bé đó}.Cho đến khi nào tất cả các số đều ở trong mảng c.Cái bài này thì sẽ có 1 mảng sẽ hết số để so sánh trước nên ta sẽ đặt a[n+1]=maxint1,b[n+1]=maxint2 để chặn lại
.Chắc nói vậy hơi khó hiểu nhỉ.Tớ VD nha
VD:a= 1 4 5
b=7 9 12 13
Sau khi gán thì sẽ là
a= 1 4 5 maxint1{số rất lớn,tùy theo đề bài}
b= 7 9 12 13 maxint2{cũng là số rất lớn}
Sau khi chạy ta sẽ có lần lượt các biến là
c=rỗng.i=1,j=1
c=1 i=2,j=1
c=1 4 i=3 ,j=1
c=1 4 5 i=4,j=1
c=1 4 5 7 i=4,j=2
c=1 4 5 7 9 i=4,j=3
.....
c=1 4 5 7 9 12 13 maxint1 maxint2 i=4,j=5.Thoát khỏi vòng lặp
Lúc in thì in ra mảng c có 7 phần tử thôi.
Bài này thì cũng có nhiều cách để làm nhưng vì bạn mm2pro hỏi về pp lính canh thì mình cũng xin giới thiệu .
Chúc bạn vui vẻ.
Happy New Year mọi người nhá.

[m2mpro]

Cám ơn mọi người đã hướng dẫn.
Happy holiday