Реферат Курсовая Конспект
The Solution - раздел Философия, Recursive factorials To Solve The Eight Queens Problem, We Use A Backtracking Algorithm. The Algor...
|
To solve the Eight Queens problem, we use a backtracking algorithm. The algorithm involves placing queens, column by column, onto the chessboard. The algorithm terminates when it places all eight queens on the board with no two queens attacking each other. The algorithm backtracks when it reaches a situation where a new queen cannot be placed on the board without attacking a queen already on the board. When the algorithm reaches this situation, it moves the piece that it most recently added to the board to another location. The idea here is that moving this piece may create a combination that allows the algorithm to add more pieces. For example, consider the chessboard in Figure 6. Here, we have placed seven queens successfully in the first seven columns such that no two queens are attacking each other. We must backtrack, however, since no legal space in column eight exists where we can place the eighth queen.
Figure 6 Seven queens placed, but we must backtrack
The backtracking portion of the algorithm would then attempt to move the seventh queen to another spot in the seventh column to open a spot in the eighth column for the eighth queen. If the seventh queen cannot be moved because no other legal spaces exist in column seven, the algorithm must remove that queen and back up and consider moving the queen in column six. Eventually, the algorithm repeats this process of placing queens and backing up until it finds a combination that solves the problem.
The above implementation of the Eight Queens problem outputs the first solution it finds and then terminates. As an exercise, can you extend it to find and display all possible solutions?
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: | #include <iostream> #include <cstdlib> #include <string> using namespace std; int factorial(int n) { if (n == 0) { // base case return 1; } else { // recursive call int value = factorial(n - 1); return n * value; } } int main(int argc, char* argv[]) { cout << factorial(5) << endl; return EXIT_SUCCESS; } |
Listing 1Calculating a factorial recursively |
Выполнение программы в листинге 1 выводит, разумеется - 120. Мы знаем, что это корректно, но как получен этот результат? Добавим операторы вывода, чтобы увидеть, как этот пример работает. Листинг 2 содержит обновленную функцию factorial, которая выводит строку, указывающую, когда экземпляр функции начинается и когда экземпляр функции заканчивается. Эта измененная версия также выводит возвращаемое значение функции factorial.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: | int factorial(int n) { cerr << "factorial(" << n << ") begin" << endl; if (n == 0) { cerr << "factorial(" << n << ") returns 1" << endl; return 1; // base case } else { int ret = n * factorial(n - 1); // recursive call cerr << "factorial(" << n << ") returns " << ret << endl; return ret; } } |
Listing 2A verbose function factorial |
Пример 4 содержит Output of Listing 2, программы factorial после добавления операторов вывода.
factorial(5) begin factorial(4) begin factorial(3) begin factorial(2) begin factorial(1) begin factorial(0) begin factorial(0) returns 1 factorial(1) returns 1 factorial(2) returns 2 factorial(3) returns 6 factorial(4) returns 24 factorial(5) returns 120 |
Example 4 Output of Listing 2 |
Вывод в примере 4 показывает, что программа сначала вызывает функцию factorial с параметром 5. Функция main выполняет этот начальный вызов. Во время выполнения factorial (5) вызывает функцию factorial со значением аргумента 4. Экземпляр factorial (4) начинает выполнение и вызывает factorial (3), который последовательно вызывает factorial (2). Так продолжается, пока factorial (0) не возвращает значение 1. После этого factorial (1) возвращает значение 1 в factorial (2), factorial (2) возвращает значение 2 в factorial (3), и так далее до factorial (5) которое возвращает в main значение 120.
– Конец работы –
Эта тема принадлежит разделу:
Example contains the output of the factorial program after the addition of the output statements to function factorial factorial begin... The output in Example shows that the program first calls function factorial... Problem Solving with Recursion Divide and...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: The Solution
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов