Backtracking (quay lui) hoạt động như thế nào?

#1

Mình có code liệt kê nhị phân như sau:

#include <iostream>
#include <iomanip>
using namespace std;

int n,a[100];

void result(){
    for(int i = 1; i <= n; i++){
        cout << setw(5) << a[i];
    }
    cout << endl;
}

void Try(int i){
    for(int j = 0; j <= 1; j++){
        a[i] = j;
        if(i == n){
           result();
        } else{
            Try(i+1);
        }
    }
}

int main(){
    cin >> n;
    Try(1);
    return 0;
}

Giả sử với n = 3;
ỏ Try: khi i = 3; j = 1; thì vì sao nó có thể gọi tiếp i = 2 được Try(2)

#2

Code này trông hư cấu quá :v ai lại code backtrack như thế này :v

1      1
      |  \
2     0    1
      | \  | \
3     0  1 0  1 
4    ....

Giả sử ta đang ở i = 1, j = 1. Ta có thể đi đến trạng thái i = 2, j = 0 hoặc i = 2, j = 1. Khi ta đã xây dựng xong dãy với trạng thái (gần như ban đầu) là i = 2, j = 0, ta còn trạng thái i = 2, j = 1 chưa được thử. Lập tức ta nhảy sang trạng thái i = 2, j = 1.
Có 1 ví dụ của thầy Trần Đỗ Hùng rất hay và dễ hiểu, tuy nhiên hơi khó để tìm trên mạng.

1 Like
#3

Try(3) kết thúc thì nó trở ngược về hàm gọi nó ra là Try(2) thôi. Try(3) với try(2) có j = 0 sẽ khác try(3) nãy.

#4

Mã try(3) với j = 1 thì kết thúc rồi mà.

#5

làm sao nó có thể gọi ra Try(2) vậy chế

#6

làm sao có thể đi với code như vậy

#7

Ý bạn là sao?
Bạn tìm code khác dễ hiểu hơn code này đi.

#8

mình chỉ thắc mắc với i = 3 và j = 1 thì nó thoát khỏi vòng for và đi ra khỏi hàm Try chứ nhỉ?
sao nó có thể đi tiếp với những cấu hình tiếp theo được

#9

Hàm Try chỉ kết thúc khi nó duyệt hết tất cả các cấu hình có thể.

#10

Tìm hiểu kỹ về đệ quy. Thì cái này dễ hiểu mà

#11

Cho mình hỏi với n=3, mình muốn in ra tất cả các dãy nhị phân cho tới 1 con số cụ thể nào đó (101 chẳng hạn) sau đó kết thúc chương trình thì phải làm sao ạ?

#12

Yêu cầu đó dùng pp sinh sẽ tốt hơn, muốn dừng là dừng được ngay :slight_smile:

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