Условие
Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче. Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.
Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]a[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].
Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]\text{a}[/latex]–[latex]\text{h}[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]–[latex]8[/latex]), задающая строку на шахматной доске.
Для каждого теста вывести одну строку следующего содержания: «To get from [latex]\text{xx}[/latex] to [latex]\text{yy}[/latex] takes [latex]n[/latex] knight moves.»
Тестирование
| № | Входные данные | Выходные данные |
| 1 | 1 | -1 |
| 2 | 0.25 | -0.75 |
| 3 | 0.1 | -0.861111 |
| 4 | 0.01 | -0.827962 |
| 5 | 0.0000001 | -0.822467 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <string> #include <cmath> using namespace std; // Клетка шахматной доски struct cell { int a; // Вертикальная координата (числа) int b; // Горизонтальная координата (буквы) int d; // Расстояние до этой клетки из начальной }; // Узел. Используется в очереди struct node { cell val; node *next; node(cell v, node *n = NULL) { val = v; next = n; } }; // Очередь. Используется для поиска в ширину struct Queue { node *head; Queue(node *h = NULL) { head = h; } void push(cell v) { // Добавить элемент в очередь head = new node(v, head); } cell pop() { // Изъять элемент из очереди if((head -> next) != NULL) { node *i = head; node *p = i; while(i -> next != NULL) { p = i; i = i -> next; } cell v = i -> val; p -> next = NULL; delete i; return v; } else { node *n = head; cell v = head -> val; head = head -> next; delete n; return v; } } void clear() { // Очистить очередь head = NULL; } }; int main() { string r; // Строка для запроса Queue q; // Очередь cell current, goal, next; // Текущая, конечная и следующая клетки bool visited[8][8]; // Посещенные клетки while(getline(cin, r)) { // Готовим текущую и конечную клетки current.a = (int)(r[1] - '1'); current.b = (int)(r[0] - 'a'); goal.a = (int)(r[4] - '1'); goal.b = (int)(r[3] - 'a'); current.d = 0; // Готовим массив посещенных клеток for(int i = 0; i < 8; i++) for(int j = 0; j < 8; j++) visited[i][j] = false; visited[current.a][current.b] = true; // Готовим очередь q.push(current); // Выполняем поиск в ширину while( !(current.a == goal.a && current.b == goal.b) ) { // Пока координаты очередной клетки из очереди не совпадут с координатами конечной current = q.pop(); // Достаем новую клетку из очереди next.d = current.d + 1; // Расстояние до клеток нового слоя поиска будет на 1 больше, чем до клеток предыдущего // Перебираем 8 потенцальных ходов из текущей клетки комбинациями сдвигов по координатам for(int i = -2; i <= 2; i++) if(i != 0) for(int j = -(3 - abs(i)); j <= 3 - abs(i); j += 2 * (3 - abs(i))) { // Присваиваем следующей клетке новые координаты next.a = current.a + i; next.b = current.b + j; if(0 <= next.a && next.a <= 7 && 0 <= next.b && next.b <= 7 && !visited[next.a][next.b]) { // Если следующая клетка находится в пределах доски и не была посещена q.push(next); // Добавляем ее в очередь visited[next.a][next.b] = true; // Отмечаем ее посещенной } } } // Выводим ответ cout << "To get from " << r[0] << r[1] << " to " << r[3] << r[4] << " takes " << current.d << " knight moves." << endl; // Очищаем очередь для следующего теста q.clear(); } return 0; } |
Решение
Вычисление суммы ряда с точностью [latex]\varepsilon[/latex] представляет собой процесс нахождения членов ряда и их суммирования до тех пор, пока значение очередного члена по модулю не окажется меньше указанной точности.
Прежде всего найдем зависимость [latex]a_{n+1}[/latex] от [latex]a_n[/latex] и выведем рекуррентную формулу для очередного члена:
[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]
Для вычислений мы используем рекуррентное соотношение, поэтому до выполнения цикла, накапливающего сумму, переменным члена ряда a и суммы sum потребуется присвоить значение [latex]a_1 = \frac {(-1)^1}{1^2} = -1[/latex]:
|
1 |
double a = -1, sum = -1, E; |
Теперь опишем, каким образом будет работать цикл:
- Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
- Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
- В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].
Реализуем описанный алгоритм с помощью цикла for. Чтобы сократить количество операций в теле цикла до одной, вычислять очередной член ряда будем при проверке выполнения условия продолжения. При присвоении переменной a нового значения воспользуемся кастингом (double) ; в противном случае уже второй член ряда будет обнуляться из-за умножения на дробь с целой частью [latex]0[/latex]:
|
1 2 |
for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++) sum += a; |
Наконец, выведем требуемое значение — сумму ряда:
|
1 |
cout << sum; |