thuật toán quay lùi------>

[ktx.de]

em đang giải bài toán liệt kê các tổ hợp chập k của n phần tử
dùng thuật toán quay lùi nhưng mà vẫn chưa ra kết quả
các anh có thuật toán giúp giùm em
em cảm ơn !

[mr_hoang]

anh cũng đang bí ne`

[mr_hoang]

hôm nào anh làm xong thì share cho
đợi nghe

[blackart_vn]

Đây là thuật toán chung chung, từ đây bạn phát triển theo bài tập của bạn nhé. (hy vọng ko bị sai chỗ nào :emlaugh:)
void Try(i){
for(j = cận dưới đến cận trên){
if (chấp nhận j){
Lưu trạng thái cũ và chuyển sang trạng thái mới.
xi được tính theo trạng thái j
if (x1..xi là nghiệm)
In kết quả.
else
Try(i+1)
Trả lại trạng thái cũ.
}
}
}

[ilu2009]

cách làm như sau (ko đệ quy)
vd tìm tổ hop cap 3 cua 12345
liet ke theo thứ tự tăng dần
123
124
125
134
135
....
bạn tự viet source nhen (viet 1 hàm tim cấu hình tiep theo)

[thanhhuy191188]

[ Thanhhuy191188@gmail.com]


Đây là thuật toán chung chung, từ đây bạn phát triển theo bài tập của bạn nhé. (hy vọng ko bị sai chỗ nào :emlaugh:)
void Try(i){
for(j = cận dưới đến cận trên){
if (chấp nhận j){
Lưu trạng thái cũ và chuyển sang trạng thái mới.
xi được tính theo trạng thái j
if (x1..xi là nghiệm)
In kết quả.
else
Try(i+1)
Trả lại trạng thái cũ.
}
}
}
Minh co CODE muon share cho các bạn cùng tham khảo . nhưng cái chính là đoạn hướng dẫn bên trên. dựa vào đó ta có thể giải quyết được nhiều bài toán khác ,...

/////////////////////////////
// chinh hop lap chap k phan tu n mu k
#include<stdio.h>
#include<conio.h>
void write();
void try1(int i);
int x[30];
int n,k;

void write()
{
int i;
FILE *f2;
f2=fopen("nchapk.out","a");
for(i=1;i<=k;i++)
{
fprintf(f2,"%d",x[i]);
}
fprintf(f2,"\n");
fclose(f2);
}
void try1(int i)
{
int j;
for(j=0;j<=n;j++)
{
x[i]=j;
if(i==k)
write();
else try1(i+1);
}
}
void main()
{
FILE *f1;
f1=fopen("nchapk.inp","r");
fscanf(f1,"%d %d",&n,&k);
try1(1);
fclose(f1);
}
//////////////////////////////////////////

[ngtrhieu0011]

đệ quy way lui...
chẳng khác với đệ qyu đâu...
nói chung nó là zậy...
procedure try (...);
var...;
begin
if (đk) then exit (đúng thì thoát)
else
begin
try(..);
try(..);
(đoạn này để đệ quy vô lần nữa)
(trả lại thiết lập ban đầu trước khi đệ quy vô);
end;
end;

ý nghĩa
khi gặp một lối đúng thì thoát;
không thì đệ quy vô
gặp đướng cụt thì way ra bằng cách trả thiết lập lại

Ví dụ: bài mã đi tuần

[blackcactus]

Bài toán tìm tổ hợp chập k trong n phần tử theo phương pháp quay lui:
try(i):=
for (j = 1; j <= n; j++)
if(x[i-1] + 1 <= j <= n - k + i)
{
x[i] = j;
if (i < k)
try(i + 1);
else
Xuất(x);
}

[knattanwar]

Viết chương trình trò chơi cờ vua mà dùng thuật toán quay lui thì viết sao mọi người! Giúp mình với nha!

[kimduquan]

cách làm như sau (ko đệ quy)
vd tìm tổ hop cap 3 cua 12345
liet ke theo thứ tự tăng dần
123
124
125
134
135
....
bạn tự viet source nhen (viet 1 hàm tim cấu hình tiep theo)

đấy là phương pháp sinh mà ko phải phương pháp quay lui.

[pdah]

đấy là phương pháp sinh mà ko phải phương pháp quay lui.

Nó là 2 vấn đề khác nhau.
Có *thuật toán* sinh số tiếp theo, và code cho thuật toán này có thể dùng *phương pháp* đệ quy quay lui hoặc không đệ quy.

[kimduquan]

vd nếu tìm tổ hợp chặp 3 của 5 phần tử là{1,2,3,4,5} có phải là
123;124;125;135;145;245;345 có 7 cái phải ko?

[nguyen cao dinh]

sao ko có bài nào về thuật toán đệ quy quay lui vay?tôi đang cần mà ko thấy.chán wa!!!!!!!!!!!!!!!

[i4share.com]

theo minh biet thi tt quay lui la de qui roi con j

[maivancuong46e3]

phuong phap quay lui ai giup tui voi thank you

[=========> Bổ sung bài viết <=========]

định nghĩa về phương pháp quay lui?

[chaudocng]

các anh (chị) ơi!giúp em mấy bài toán rời rạc này có chết!sắp thi rồi mà chưa biét gì hết!
BÀI TẬP THỰC HÀNH TOÁN RỜI RẠC.
Bài tập 1: Bài toán đếm – bài toán liệt kê
1) Đếm số xâu nhị phân độ dài n :
a)bất kì
b)không có hai bit 0 kề nhau
c) có ít nhất hai bít 0 kề nhau
2)Viết chương trình liệt kê tất cả xâu nhị phân độ dài n như yêu cầu của bài toán 1.Liệt kê có số thứ tự để kiểm tra các kết quả đã đếm được . Thử nhập các giá trị khác nhau của n (lưu ý các giá trị n=1 và n=2).
3)Lập trình giải phương trình : x1+x2+…+xn=k (n,k nhập từ bàn phím)
4)Viết chương trình phát sinh ngẫu nhiên ma trận trọng số Amxn =(aij)mxn của đồ thị vô hướng liên thông G gồm n đỉnh (aij=aji, i,j từ 1 đến n)
a)Kiểm tra G có phải là đồ thị vô hướng hay không?
b)Nhập hai đinh x,y và dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ x đến y
c)Dùng thuật toán Prim tìm cây phủ nhỏ nhất của đồ thị G
5)Viết chương trình nhập n là số đỉnh và nhập ma trận khoản cách khả năng thông qua của các cung Cnxn=(cij)mxn với quy ước đỉnh v1 là đỉnh nguồn và đỉnh Vn là đỉnh đích .Dùng thuật toán ford-fulkerson để tìm luồn cực đại trên mạng đã nhập.

[bumzunpilo]

Đây là thuật toán chung chung, từ đây bạn phát triển theo bài tập của bạn nhé. (hy vọng ko bị sai chỗ nào :emlaugh:)
void Try(i){
for(j = cận dưới đến cận trên){
if (chấp nhận j){
Lưu trạng thái cũ và chuyển sang trạng thái mới.
xi được tính theo trạng thái j
if (x1..xi là nghiệm)
In kết quả.
else
Try(i+1)
Trả lại trạng thái cũ.
}
}
}


Cách giải này sao giống thuật toán sinh quá?
Bài này dùng generation là ổn.

[bumzunpilo]

phuong phap quay lui ai giup tui voi thank you

[=========> Bổ sung bài viết <=========]

định nghĩa về phương pháp quay lui?


Thử với cấu hình x+1 nếu thấy k ổn thì quay lại sử dụng cấu hình x.
Đó là quay lui, quay lui thực chất là đệ qui nhưng ở 1 bậc cao hơn thôi.

[=========> Bổ sung bài viết <=========]


các anh (chị) ơi!giúp em mấy bài toán rời rạc này có chết!sắp thi rồi mà chưa biét gì hết!
BÀI TẬP THỰC HÀNH TOÁN RỜI RẠC.
Bài tập 1: Bài toán đếm – bài toán liệt kê
1) Đếm số xâu nhị phân độ dài n :
a)bất kì
b)không có hai bit 0 kề nhau
c) có ít nhất hai bít 0 kề nhau
2)Viết chương trình liệt kê tất cả xâu nhị phân độ dài n như yêu cầu của bài toán 1.Liệt kê có số thứ tự để kiểm tra các kết quả đã đếm được . Thử nhập các giá trị khác nhau của n (lưu ý các giá trị n=1 và n=2).
3)Lập trình giải phương trình : x1+x2+…+xn=k (n,k nhập từ bàn phím)
4)Viết chương trình phát sinh ngẫu nhiên ma trận trọng số Amxn =(aij)mxn của đồ thị vô hướng liên thông G gồm n đỉnh (aij=aji, i,j từ 1 đến n)
a)Kiểm tra G có phải là đồ thị vô hướng hay không?
b)Nhập hai đinh x,y và dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ x đến y
c)Dùng thuật toán Prim tìm cây phủ nhỏ nhất của đồ thị G
5)Viết chương trình nhập n là số đỉnh và nhập ma trận khoản cách khả năng thông qua của các cung Cnxn=(cij)mxn với quy ước đỉnh v1 là đỉnh nguồn và đỉnh Vn là đỉnh đích .Dùng thuật toán ford-fulkerson để tìm luồn cực đại trên mạng đã nhập.



Bài 1, bạn bik cách liệt kê các dãy nhị phân độ dài n rồi chứ, có nói ở trên đó. Bài liệt kê các dãy nhị phân độ dài n dùng phương pháp sinh là ổn. Liệt kê rồi thì chỉ việc đếm là xong. CÒn các điều kiện ở câu b, c thì cho thêm 2 biến đếm, ghép điều kiện vào để tăng biến đếm đó lên.
Bài 2, tớ chưa rõ đề lắm.
bài 3, tớ nghĩ là đề còn thiếu, phải có điều kiện x1, x2,... xn thuộc N chứ.
CÒn nếu đề là x1,x2,...,k thuộc N để tìm các giá trị x1, x2... thì bạn dùng đệ qui, thử gán cho x1 các giá trị từ k về 0, rồi đệ qui tìm tương tự các giá trị x2, x3...
Bài 4, 5 tớ chưua học tới thì phải.