Форум программистов, компьютерный форум CyberForum.ru

Путешествие коня. Почему конь не хочет пробежать все возможные варианты? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача на создание символьного файла http://www.cyberforum.ru/cpp-beginners/thread519721.html
Дан текстовый файл. Создать символьный файл, содержащий все сим-волы, встретившиеся в тексте, включая пробел и знаки препинания (без повторений). Символы располагать в порядке их первого появления в тек-сте.
C++ Кусочно-линейная аппроксимация Добрый времени суток всем. Необходима помощь в написание алгоритма кусочно-линейной аппроксимации. У меня дана таблица зависимости, грубо говоря градуировка сигнала x(Вход) и y(Выход). Например: x y 4 10 5 15 10 30 К примеру при входном сигнале 7, нужно определить в какой диапазон X-a попадает данное число, а потом применив алгоритм кусочно-линейной аппроксимации... http://www.cyberforum.ru/cpp-beginners/thread519713.html
Найти и вывести номера структур, содержащих числа больше заданного C++
Имеется база данных, содержащая числители и знаменатели дробных чисел. Например, последовательность чисел 5/18, 7/13, 9/8, … хранится в виде: Номер структуры 1 2 3 … Числитель 5 7 9 … Знаменатель 18 13 8 … Найти и вывести номера структур, содержащих числа больше заданного (оно вводится с клавиатуры в десятичной форме), и сами числа (тоже в десятичной форме).
C++ помогит пожалуйста с программой «Обработка массивов в С++»
Тема «Обработка массивов в С++» Задание: Необходимо написать и отладить программу в среде Borland C++ 3.1 по задан- ному варианту с обязательным применением массивов. В массивах вещественных чисел X и Y записаны координаты точек на плоскости. Найти длины отрезков Ri=((xi+1-xi)2+(yi+1-yi)2)1/2 и определить отрезок наибольшей и наименьшей длины.
C++ Созадать/записать в файл, из под другой учетки. http://www.cyberforum.ru/cpp-beginners/thread519673.html
Приветствую, не подскажите как произвести данную манипуляцию? Даже копать в какую сторону не знаю, была мысль создать доп. программу, запускать с помощью CreateProcessWithLogonW() и передавать ей параметры.
C++ Динамическая память, проблемы с освобождением Всем привет! Проблема стара как этот мир, но есть некая отличительная черта по которой я создал эту тему. Задача следующая. Создаю файл и кидаю в него строку, закрываю файл. Далее открываю этот файл и помещаю содержимое файла в динамическую строку. Так вот проблема возникает на третьей итерации при освобождении памяти. Почему так происходит, почему ошибка не выскакивает при первом удалении.... подробнее

Показать сообщение отдельно
fasked
Эксперт C++
 Аватар для fasked
4929 / 2509 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
16.03.2012, 08:11     Путешествие коня. Почему конь не хочет пробежать все возможные варианты?
Что-то у меня тут было про коней, кину на всякий случай, а то все равно не понятно, что делать надо:
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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <iomanip>
 
// массив всех возможных ходов фигуры (буквой Г)
const int move_types = 8;
int possible_moves[move_types][2]  = {
    {-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
    {-1,  2}, { 2, -1}, { 1,  2}, { 2,  1} 
};
 
int **desc_state;   // указатель на поле (доску)
int size_x, size_y; // размеры доски
int cur_x, cur_y;   // текущая позиция
 
int max_moves;      // максимальное количество ходов
unsigned int back_ret;
 
// определить возможно ли поставить фигуру на позицию x,y
bool position_possible(int x, int y)
{
    return x >= 0 && y >= 0 && x < size_x && y < size_y;
}
 
// определить возможно ли сделать ход на позицию x,y
// возможно если фигуру можно поставить на клетку x,y 
// и эта клетка не была пройдена ранее
bool move_possible(int x, int y) 
{
    return position_possible(x,y) && desc_state[x][y] == 0;
}
 
// рекурсивная функция поиска пути
bool find_path(int cur_x, int cur_y, int move_num)
{
    // занять клетку cur_x, cur_y
    // записать в нее номер хода
    desc_state[cur_x][cur_y] = move_num;
    
    // если номер текущего хода больше числа максимальных ходов 
    // то обход доски завершен
    if(move_num > max_moves)
        return true;
 
    // цикл проверки всех возможных ходов
    for(int i = 0; i < move_types; ++i)
    {
        int next_x = cur_x + possible_moves[i][0];
        int next_y = cur_y + possible_moves[i][1];
 
        // если возможен такой ход и следующий ход 
        // то вернуть true
        if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1))
            return true;
    }
 
    // этот участок кода отработает если такой ход невозможен
    // обнулить клетку и уменьшить число ходов на единицу
    desc_state[cur_x][cur_y] = 0;
    ++back_ret;
    --move_num;
 
    return false;
}
 
// начальная инициализация
void init(int **desc, int nrows, int ncols, int start_x, int start_y)
{
    desc_state = desc;  // указатель на двумерный массив - доска
    size_x = nrows;     // размеры доски
    size_y = ncols;
 
    // обнуление доски
    for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
            desc_state[i][j] = 0;
    }
 
    back_ret = 0;
 
    // количество ходов 
    max_moves = size_x * size_y - 1;
}
 
// это просто вывод доски
void output_path()
{
    for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
            std::cout << std::setfill('0') << std::setw(2) << desc_state[i][j] << ' ';
 
        std::cout << std::endl;
    }
}
 
int main() 
{
    int nrows = 0;
    int ncols = 0;
 
    int **desc = NULL;
    int sx = 0;
    int sy = 0;
 
    std::cout << "input vertical size: ";
    std::cin  >> nrows;
 
    std::cout << "input horizontal size : ";
    std::cin  >> ncols;
 
    std::cout << "input start X-position: ";
    std::cin  >> sx;
 
    std::cout << "input start Y-position: ";
    std::cin  >> sy;
 
    if(sx >= nrows || sy >= ncols) {
        std::cout << "start positions invalid" << std::endl;
        return -1;
    }
 
    // выделить память под двумерный массив (доску)
    desc = new int *[nrows];
    for(int i = 0; i < nrows; ++i) 
        desc[i] = new int[ncols];
 
    // инициализация
    init(desc, nrows, ncols, sx, sy);
 
    // если функция find_path вернет true
    // то обход существует
    // иначе не существует
    if(find_path(sx, sy, 1))
        output_path();
    else
        std::cout << "path not found" << std::endl;
 
//  std::cout << "\nback ret: " << back_ret;
//  std::cout << "\nmove num: " << move_num;
//  std::cout << std::endl;
 
    // освободить память
    for(int i = 0; i < nrows; ++i)
        delete[] desc[i];
    delete[] desc;
 
    return 0;
}
Как минимум здесь тоже перебирается все возможное количество ходов.
 
Текущее время: 19:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru