рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

The Solution

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.

  • queens.cpp - Includes main and the backtracking algorithm
  • Queenboard.h - Defines a class that models a chessboard of only queens

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?

 

 

Рекурсивные функции Рекурсивная функция это функция, которая может вызывать саму себя. Использование рекурсивных функций может привести к изящным решениям сложных проблем. C++, как многие другие языки программирования, поддерживает рекурсию. Программист должен использовать рекурсивные функции осторожно, чтобы избежать создание функции, которая вызывает себя вечно. Псевдокод типовой рекурсивной функции имеет следующий вид. if (simplest case) then solve directly else make recursive call to a simpler case Пример 1 типовая рекурсивная функция Создание и использование эффективных рекурсивных функций это разбиение большого на меньшие. В итоге, проблема становится достаточно маленькой, чтобы можно было решить ее, не используя рекурсию. Её вызывают base case. Вычисление факториалов является примером, как решается проблема рекурсией. Факториал числа N есть произведение целых чисел от N до единицы. Например, факториал пять равняется 5 * 4 * 3 * 2 * 1. Как известно, оно равно 120. Факториал от 3 (3 * 2 * 1) равняются значению 6. Восклицательный знак обозначает факториал числа. Таким образом, "пять факториалов" могут быть показаны так 5!. В примере 2 приведены несколько положительных целых чисел и вычисление их факториалов. Факториал нуля является особым случаем и всегда равен 1.   5! = 5 * 4 * 3 * 2 * 1 = 120 4! = 4 * 3 * 2 * 1 = 24 3! = 3 * 2 * 1 = 6 2! = 2 * 1 = 2 1! = 1 0! = 1 Пример 2 Некоторые факториалы Выразим факториалы рекурсивно, то есть, с точки зрения других факториалов. Рассмотрим вычисление факториала для значения 5. Из примера 2, видим 5! = 5 * 4 * 3 * 2 * 1. Но, для 4, мы знаем это 4! = 4 * 3 * 2 * 1. Тогда рекурсивно, 5! = 5 * 4!. В примере 3 приведены рекурсивные определения тех же самых чисел примера 2. Так как мы не можем выразить нулевой факториал рекурсивно, это - base case.   5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! 0! = 1 Пример 3 Рекурсия факториалов Листинг 1 содержит код C++, который рекурсивно вычисляет факториалы.  
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.

– Конец работы –

Эта тема принадлежит разделу:

Recursive factorials

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

The Call Stack
The call stack is an area of a program's memory used to manage the currently executing function and all pending function calls. Figure 3 lends some insight into what is meant by a "pend

Removing Recursion
Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recu

Divide and Conquer
Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the r

Backtracking. The Concept
Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to

The Problem
A classic problem that we can solve using backtracking is the Eight Queens problem. This difficult problem deals with placing eight queens on a chessboard such that no two queens are attacking each

The Call Stack
Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято

Замена рекурсии
Рекурсия имеет собственное решение: т.е. система времени выполнения должна поддержать сложный стек вызовов, сверх необходимости выполнять обычные оценки в функции. Часто бывает выгодно заменить рек

Отслеживание в обратном порядке. Понятие
Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процес

Проблема
Классической проблемой, решения задачи методом «отслеживание в обратном порядке», является проблема Восьми Королев. Эта трудная проблема соглашения с размещением восьми королев на шахматной доске т

Решение
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, ко

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги