mẹo hay

Bài toán tháp hà nội c++ cấu trúc dữ liệu năm 2024

Chương trình áp dụng giải thuật AKT, mội trạng thái được mô tả bằng mảng hai chiều. Để ước lượng đối với trạng thái của trò chơi, ta sẽ tính trạng thái của cột thứ ba. Tại một trạng thái, thì số bước để đưa cột thứ ba về đúng như trạng thái đích là bao nhiêu? Ta thấy tại một trạng thái của cột thứ ba thì có một số đĩa nằm đúng vị trí của nó, và cũng có một số đĩa không nằm đúng vị trí của nó. Số lượt để ta có thể đưa cột thứ ba về đúng trạng thái đích bằng tổng số lượt mang những đĩa không đúng vị trí ra khỏi cột thứ ba cộng với số lượt mang những đĩa còn lại vào cho đúng vị trí của nó trong cột thứ ba. Một số hàm chính trong chương trình:

int GetNumberOfDiskOfPillar[Integer[] pPillar] Tính tổng số đĩa hiện có trong một cột nào đó. int GetRightPositions[Integer[] pPillar] Tính số đĩa nằm đúng vị trí trong một cột nào đó void H[] // Là hàm tri thức bổ sung có giá trị bằng số vị trí sai trên cột thứ 3. Void Generate[] Tính toán các bước đi cho bài toán Áp dụng giải thuật AKT Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy [tiếng Anh sequential advancement] để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó. Mặc dù không biết được chính xác cần bao nhiêu lần di chuyển, có thể có một vài kết quả tiệm cận. Có một “lời giải được coi như tối ưu” có thể áp dụng một cách đệ quy để tìm một lời giải–xem giải thích cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer. 3.5. Cấu trúc dữ liệu Xem một tháp Hà Nội được kết cấu từ một mảng hai chiều có 3 dòng và số cột là số đĩa mà chương trình cho phép mô phỏng. Mảng hai chiều này chỉ chứa những số tự nhiên. Những vị trí có đĩa thì các số tự nhiên sẽ xếp theo chiều giảm dần của các số tự nhiên lớn hơn 0 như: – 3 đĩa sẽ là: 2,1,0 – 4 đĩa sẽ là: 3,2,1,0 … Còn những vị trí không có đĩa sẽ chứa lưu số -1. Như vậy, ban đầu khi khởi tạo chương trình thì mảng hai chiều sẽ là: S0={{2,1,0},{-1,-1,-1},{-1,-1,-1}} Ứng với một trạng thái của chương trình thì còn có những thuộc tính tương ứng như: • Chi phí đi từ trạng thái khởi đầu đến trạng thái hiện tại. • Chỉ số ước lượng Heuristic, là chi phí để đi đến đích từ trạng thái đó. • Chỉ số f là tổng hai chi phí bên trên. • Và trạng thái cha của trạng thái hiện tại. Trong đó hàm ước lượng sẽ như sau:

public void heuristic[]

{  
    this.valueH = this.disks[2].length;  
    for [int i = 0; i < this.disks[2].length; i++]  
    {  
        if [this.disks[2][i].getDiskId[] == i + 1]  
        {  
            this.valueH--;  
        }  
    }  
}

Hàm tính toán khá đơn giản, chi phí để đưa trạng thái về trạng thái đích là chi phí bỏ các đĩa nằm không đúng vị trí trong cột thứ ba ra, cộng với chi phí đưa những đĩa còn lại vào cột thứ ba cho đúng vị trí của nó. Hàm quan trọng trong chương trình là hàm tính giải thuật AKT:

public void resolve[]

{  
    Snapshot originalSnapshot = new Snapshot[this.diskCount];  
    this.lstOpenedSnapshots.add[originalSnapshot];
    while [this.lstOpenedSnapshots.size[] > 0]  
    {  
        Snapshot processingSnapshot = this.lstOpenedSnapshots.get[0];  
        this.lstSteps.add[processingSnapshot];  
        this.lstOpenedSnapshots.remove[0];  
        if [processingSnapshot.getValueH[] == 0]  
        {  
            break;  
        }  
        List lstGeneratedSnapshots = new ArrayList[];  
        processingSnapshot.getAllGeneratedSnapshot[lstGeneratedSnapshots];
        for [Snapshot snap : lstGeneratedSnapshots]  
        {  
            if [!this.isValidSnapshot[snap]]  
            {  
                continue;  
            }  
            int i = 0;  
            while [i < this.lstOpenedSnapshots.size[]  
                    && snap.getvalueF[] > this.lstOpenedSnapshots.get[i].getvalueF[]]  
            {  
                i++;  
            }  
            this.lstOpenedSnapshots.add[i, snap];
        }  
    }  
}

Tháp Hà Nội là một bài toán kinh điển có thể giải bằng đệ quy. Đó là một câu đố bao gồm ba cọc và một số đĩa có kích thước khác nhau, có thể đặt lên bất kỳ cọc nào. Câu đố bắt đầu với các đĩa xếp thành chồng theo thứ tự kích thước tăng dần trên một cọc, nhỏ nhất ở trên cùng, do đó tạo thành hình nón.

Mục tiêu của câu đố là di chuyển toàn bộ đĩa sang một cọc khác, tuân theo quy tắc đơn giản sau:

Mỗi lần chỉ có thể di chuyển một đĩa.
Mỗi lần di chuyển : lấy đĩa từ một cọc nguồn và đặt nó lên một cọc đích. Ở cọc đích có thể đã có sẵn các đĩa.
Không có đĩa nào có thể được đặt trên một đĩa nhỏ hơn.
Có thể chuyển đĩa vào cọc trung gian miễn là tuân thủ 3 quy tắc trên.

Giải bằng cơm trước khi code

Để dễ hình dung hơn các bước giải, chúng ta sẽ lấy ví dụ cụ thể. Giả sử chúng ta có 3 cọc A, B, C tương trưng cho 3 tháp và có 3 đĩa. Ảnh dưới là trạng trái ban đầu

Để đưa toàn bộ 3 đĩa ở cọc A tới cọc C, bạn cần:

Chuyển đĩa 1 và 2 sang cọc trung gian B.
Di chuyển đĩa 3 sang cọc C
Chuyển đĩa 1 và 2 sang cọc C

Bước 1: chuyển đĩa 1 từ cọc A sang cọc C

Bước 2: chuyển đĩa 2 từ cọc A sang cọc B

Bước 3: chuyển đĩa 1 từ cọc C sang cọc B

Mục đích bước này để dành chỗ ở cọc C chuyển đĩa 3 từ cọc A sang

Bước 4: chuyển đĩa 3 từ cọc A sang cọc C

Bước 5: chuyển đĩa 1 từ cọc B sang cọc A

Bước 6: chuyển đĩa 2 từ cọc B sang cọc C

Bước 7: chuyển đĩa 1 từ cọc A sang cọc C

Đến bước này ta đã hoàn thành nhiệm vụ

Thuật toán đệ quy

Di chuyển n-1 đĩa trên cùng từ cọc nguồn sang cọc trung gian.
Di chuyển đĩa thứ n từ cọc nguồn đến cọc đích.
Di chuyển n-1 đĩa từ cọc trung gian sang cọc đích, sử dụng cọc nguồn làm trung gian.
Trường hợp cơ bản của đệ quy là khi chỉ có một đĩa để di chuyển. Trong trường hợp này, chúng ta chỉ cần di chuyển đĩa từ cọc nguồn đến cọc đích.

public class HanoiTower {

public static void solveHanoi[int n, char source, char destination, char auxiliary] {
    if [n == 1] {
        System.out.println["Move disk 1 from " + source + " to " + destination];
        return;
    }
    solveHanoi[n-1, source, auxiliary, destination];
    System.out.println["Move disk " + n + " from " + source + " to " + destination];
    solveHanoi[n-1, auxiliary, destination, source];
}
public static void main[String[] args] {
    int n = 3;
    solveHanoi[n, 'A', 'C', 'B'];
}

java

Có thể viết dưới dạng hàm trong unit test bằng JUnit5

package leetcode; import org.junit.jupiter.api.Test; public class HanoiTower { public static void solveHanoi[int n, char source, char destination, char auxiliary] {

if [n == 1] {
  System.out.println["Move disk 1 from " + source + " to " + destination];
  return;
}
solveHanoi[n - 1, source, auxiliary, destination];
System.out.println["Move disk " + n + " from " + source + " to " + destination];
solveHanoi[n - 1, auxiliary, destination, source];

  }
  @Test void test[] {int n = 3;
solveHanoi[n, 'A', 'C', 'B'];
  }
}

java

Kết quả in ra màn hình các bước

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C