Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.77/30: Рейтинг темы: голосов - 30, средняя оценка - 4.77
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637

Реализовать алгоритм всех возможных комбинаций восьми ферзей

19.05.2016, 05:11. Показов 7322. Ответов 119

Студворк — интернет-сервис помощи студентам
Доброго времени суток! Мне стыдно задавать такой вопрос, но всё же, как реализовать алгоритм всех возможных комбинаций восьми ферзей?

Используйте исчерпывающий «лобовой» подход, т.е. попробуйте все возможные комбинации восьми ферзей на шахматной доске.


Я, думаю, что как-то так: Пройтись по всем строкам и столбцам, выяснить возможно ли поставить ферзей с таких то координат, (0, 0), (0, 1), (0, 2)....(0, 7) , (1, 0) (1, 1) .... ну и так далее до (7, 7) и каждую координату обрабатывать, выясняя, если поставить первого ферзя на на эти коордитаты, то остальные семь ферзей возможно ли разместить на доске. Вот такая вот идея решения) Но решение не могу написать, функция обработки не получается почему-то...
Кликните здесь для просмотра всего текста
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include <iostream>
#include <iomanip>
//#include "CyrIOS.h"
 
const int hor[8] = {1,1,0,-1,-1,-1,0,1};
const int ver[8] = {0,-1,-1,-1,0,1,1,1};
 
void printBoard(int [][8]);
void resetBoard(int [][8]);
bool checkBoard(int [][8]);
void tryQueen(int [][8], int&, int&);
int helpUpdateBoard(int [][8], int&, int&, bool);
 
using namespace std;
int main()
{
    int board[8][8];
    int cnt = 0;
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                resetBoard(board);
                tryQueen(board, i, j);
                if(checkBoard(board))
                {
                    printBoard(board);
 
                }
                else
                    continue;
            }
                
        }
        return 0;
}
 
bool checkBoard(int brd[][8])  //проверяем, расставлены ли все восемь ферзей.
{
    int counter = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(brd[i][j] == 100)
                counter++;
        }
    }
    return (counter == 8 ? true : false);
}
 
void printBoard(int brd[][8])  //выводим массив
{
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            cout << setw(5) << (brd[i][j] == 100 ? "[]" : ".");
        }
        cout << endl << endl;
    }
}
 
void resetBoard(int brd[][8]) //обнуляем массив
{
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            brd[i][j] = 0;
        }
    }
}
 
void tryQueen(int brd[][8], int& row, int& col)
{
    brd[row][col] = 100; //Постановка первого ферзя
    helpUpdateBoard(brd, row, col, true);
    static int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
          if(brd[i][j] != 100 && brd[i][j] != 99)
          {
              brd[i][j] = 100;         //пробуем поставить следующего ферзя
              helpUpdateBoard(brd, i, j, true);  //убиваем клетки которые ферзь бъёт.
             
          }
        }
    }
}
 
int helpUpdateBoard(int brd[][8], int& row, int& col, bool label)
{
    int currentRow, currentColumn;
    int moveNumber;
    int counter = 0;
    
    currentRow = row;
    currentColumn = col;
    while(currentRow < 7)
    {
        moveNumber = 0;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
            
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow < 7 && currentColumn > 0)
    {
        moveNumber = 1;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentColumn > 0)
    {
        moveNumber = 2;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow > 0 && currentColumn > 0)
    {
        moveNumber = 3;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow > 0)
    {
        moveNumber = 4;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow > 0 && currentColumn < 7)
    {
        moveNumber = 5;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentColumn < 7)
    {
        moveNumber = 6;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow < 7 && currentColumn < 7)
    {
        moveNumber = 7;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
        
    }
    return counter;
}


Я уже несколько дней с этой задачей маюсь, надо всё же понять как решать подобное, не просто скопировать код, а понять как это решать, ну и подобные, соответственно.

Смотрел примеры решения, но не понял код, что, куда, зачем, например
C++
1
2
bool tst(int i, int j, int k) {
    return k==i ? 1 : m[k]!=j && (i-k)!=(j-m[k]) && (i-k)!=(m[k]-j) && tst(i,j,k+1);}
Ясно, что фуркция что-то проверяет и возвращает истину или ложь, но вникнуть не могу в суть функции, если кто может, объясните что к чему).


Попрошу сильно не пинать, форум насколько я понял для начинающих!
Спасибо!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.05.2016, 05:11
Ответы с готовыми решениями:

Сортировка всех возможных комбинаций 4 из 8
Задача состоит в том, что бы сложить 4 элемента массива, который состоит из 8 элементов, во всех возможных комбинациях int array; //...

Создание всех возможных комбинаций английского алфавита
Подскажите пожалуйста код для создания всех возможных комбинаций английского алфавита. И чтобы эти комбинации выводились в Memo.

Перебор всех возможных комбинаций
Доброго дня. Есть задание, написать брутфорс, по заданному алфавиту. То что представлено ниже, вроде успешно работает, но с 1...

119
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 06:41  [ТС]
Студворк — интернет-сервис помощи студентам
Mr.X
Я так и делаю. Но до полной расстановки у меня всего один раз доходит) Просто я после установки ферзя помечаю клетки которые он может бить как занятые, я их 99 помечаю, и до 8 ферзей, в итоге, дохожу только один раз.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 06:41
Цитата Сообщение от Liss29 Посмотреть сообщение
Разобраться и написать самомоу, я вначале темы так и написал
Я уже прочитал
Цитата Сообщение от Liss29 Посмотреть сообщение
надо всё же понять как решать подобное, не просто скопировать код, а понять как это решать, ну и подобные, соответственно
и могу вам сказать, что вам не повредит разобраться в моем коде, хотя его все критикуют не стесняясь в выражениях. Ищите в коде женщину алгоритм, и станет гораздо проще разобрать реализацию. Поставьте везде отладочный вывод, смотрите за изменением локальных и тем более глобальных переменных для начала...
0
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 06:43  [ТС]
Mr.X
Цитата Сообщение от Mr.X Посмотреть сообщение
Многие специалисты считают, что это даже важнее быстродействия и экономии памяти.
Да, дейтелы тоже так считают, но как то он более красиво выглядит, и иногда и о производительности думать надо. Хотя меня пока такие детали не беспокоят, мне сейчас нужно в построении алгоритмов разбираться!
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 06:46
Цитата Сообщение от Liss29 Посмотреть сообщение
Я так и делаю. Но до полной расстановки у меня всего один раз доходит)
Когда у меня не было компьютера, я на бумажке по этому алгоритму нашел все расстановки.
0
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 06:48  [ТС]
Цитата Сообщение от _Ivana Посмотреть сообщение
что вам не повредит разобраться в моем коде
Дык я так и делаю, правда пока безуспешно, но продолжаю настойчиво ковырять код.

А как поставить отладочный вывод, а то в моём древнем VC 6.0 такого не наблюдал)))
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 06:48
Цитата Сообщение от Liss29 Посмотреть сообщение
но как то он более красиво выглядит, и иногда и о производительности думать надо
приятно наконец встретить человека, понимающего красоту! За это даже готов вам рассказать по шагам логику работы этой функции Хотите? Или не подсказывать и подумаете сами?
0
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 06:54  [ТС]
Цитата Сообщение от Mr.X Посмотреть сообщение
Когда у меня не было компьютера, я на бумажке по этому алгоритму нашел все расстановки.
Значит я не совсем так делаю. После того как упирается в конец( <= 7) нужно что, начать с следующей строки и нулевого столбца? Или как...

Добавлено через 1 минуту
Цитата Сообщение от _Ivana Посмотреть сообщение
логику работы этой функции Хотите?
Конечно, хочу
Потом думать или додумывать буду...
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 06:55
Щас напишу. Но только одной этой функции tst - остальное самостоятельно
0
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 07:00  [ТС]
Цитата Сообщение от Liss29 Посмотреть сообщение
Когда у меня не было компьютера, я на бумажке по этому алгоритму нашел все расстановки.
Да ладно, я по бумажке едва два нашёл)))

Добавлено через 2 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Но только одной этой функции tst - остальное самостоятельно
Хорошо, для начала и одной хватит, я потом, если не пойму что, доспрошу. Теперь можно отдохнуть немного)
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 07:11
Начнем с того, что каждая текущая расстановка хранится в массиве длиной 8: это столбцы, значение в каждом индексе равно номеру строки в текущем столбце, в котором стоит ферзь. Это допустимо потому, что очевидно у нас не могут 2 ферзя стоять в одном столбце. И поэтому никаких квадратных массовов, "заполняю клетки, которые бьет каждый ферзь" и прочей ереси не надо . Так вот, на очередном шаге у нас есть некоторое количество установленных фигур - значения массива (номера строк фигур) от 0 до какого-то столбца, причем, в этой расстановке никакой ферзь не бьет никакого другого. От функции tst требуется проверить, что если мы поставим ферзя в следующий по счету столбец на определенную строку - будет ли сохранено условие небития никого никем. Проверяется это следующим образом - мы ПОСЛЕДОВАТЕЛЬНО перебираем все существующие фигуры от 0-го столбца до предыдущего проверяемому и для каждой фигуры смотрим, что она не бьет нашего ферзя по горизонтали: m[k]!=j и по диагонали слевавнизу вправонаверх: (i-k)!=(j-m[k]) и по другой диагонали (см кот). Это тривиальная арифметика на уровне 5 класса. тут у нас последовательный оператор И: &&. Как известно. он ЛЕНИВЫЙ - то есть первое ложное условие ПРЕКРАЩАЕТ дальнейшее вычисление и функция возвращает ложь - ведь если какой-то ферзь как-либо бьет нашего тестируемого - нам не надо смотреть дальше. Именно поэтому для организации ПОСЛЕДОВАТЕЛЬНОГО ИТЕРАТИВНОГО ПЕРЕБОРА я смело добавляю в эту цепочку && РЕКУРСИВНЫЙ ВЫЗОВ этой же функции на следующем столбце (как раз тот параметр k ) - если у нас на каком-то столбце уже фигура бьется, то В СИЛУ ЛЕНИВОСТИ ВЫЧИСЛЕНИЯ && эта рекурсивная ветка не продолжится Ну и конечно, дойдя до нашего проверяемого столбца: k==i мы проверили, что все предыдущие фигуры на предыдущих столбцах не бьют нашу тестируемую - значит надо вернуть тру = 1

Ваши впечатления про алгоритм и кота?
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 08:49
Ну, вот в этом коде и разбираться не надо, и так все понятно:
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
static  const   int     CHESSBOARD_DIM  =   8;
static  const   int     QUEENS_TOTAL    =   CHESSBOARD_DIM;
 
static  const   int     CELLS_TOTAL     =       CHESSBOARD_DIM
                                            *   CHESSBOARD_DIM;
///////////////////////////////////////////////////////////////////////////////
typedef int                             T_cell;
typedef std::vector     < T_cell    >   T_position;
typedef std::complex    < T_cell    >   T_cell_2;
///////////////////////////////////////////////////////////////////////////////
T_cell_2    get_cell_2( T_cell  cell )
{
    return  {
                cell / CHESSBOARD_DIM,
                cell % CHESSBOARD_DIM
            };
}
///////////////////////////////////////////////////////////////////////////////
bool    attack
    (
        T_cell  A,
        T_cell  B
    )
{
    T_cell_2    AA  =   get_cell_2(A);
    T_cell_2    BB  =   get_cell_2(B);
 
    auto    delta_real  =   abs (
                                        AA.real()
                                    -   BB.real()
                                );
 
    auto    delta_imag  =   abs (
                                        AA.imag()
                                    -   BB.imag()
                                );
 
    return          delta_real
                *   delta_imag
 
                *   (
                            delta_real
                        -   delta_imag
                    )
 
            ==  0;
}
///////////////////////////////////////////////////////////////////////////////
bool    cell_is_valid_in_position
    (
        T_cell                  cell,
        T_position  const   &   position
    )
{
    for (
            auto    pos_cell    :
            position
        )
    {
        if  (
                attack  (
                            pos_cell,
                            cell
                        )
            )
        {
            return  false;
        }
    }//for
 
    return  true;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_add_queen( T_position  &   position )
{
    T_cell  cell_start  =   position.empty()
                                ?   0
                                :   position.back() + 1;
 
    for( T_cell  cell{ cell_start }; cell < CELLS_TOTAL; ++cell )
    {
        if  (
                cell_is_valid_in_position
                    (
                        cell,
                        position
                    )
            )
        {
            position.push_back( cell );
            return  true;
        }//if
    }//for
 
    return  false;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_fill_position( T_position  &   position )
{
    while   (
                    int (
                            position.size()
                        )
 
                <   QUEENS_TOTAL
            )
    {
        if  (
                !successfully_add_queen( position )
            )
        {
            return  false;
        }
    }//while
 
    return  true;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_inc_position( T_position  &   position )
{
    while   (
                !position.empty()
            )
    {
        auto    last_pos    =   position.back();
        position.pop_back();
 
        for( T_cell  cell{ last_pos + 1 }; cell < CELLS_TOTAL; ++cell )
        {
            if  (
                    cell_is_valid_in_position
                        (
                            cell,
                            position
                        )
                )
            {
                position.push_back( cell );
                return  true;
            }
        }//for
    }//while
 
    return  false;
}
///////////////////////////////////////////////////////////////////////////////
void    print_position( T_position  const   &   position )
{
    for (
            auto    pos_cell    :
            position
        )
    {
        std::cout   <<  get_cell_2( pos_cell )
                    <<  '\t';
    }//for
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
void    print_all_queens_positions()
{
    T_position  position;
    int         position_ind{};
 
    for(;;)
    {
        if  (
                successfully_fill_position( position )
            )
        {
            std::cout   <<  "# "
                        <<  ++position_ind
                        <<  "\t";
 
            print_position( position );
        }//if
 
        if  (
                !successfully_inc_position( position )
            )
        {
            break;
        }//if
    }//for
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    print_all_queens_positions();
}
Добавлено через 1 минуту
Цитата Сообщение от Liss29 Посмотреть сообщение
Да ладно, я по бумажке едва два нашёл)))
Ну, вы пока и на компьтере мало что нашли!

Добавлено через 4 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Начнем с того, что каждая текущая расстановка хранится в массиве длиной 8: это столбцы, значение в каждом индексе равно номеру строки в текущем столбце, в котором стоит ферзь. Это допустимо потому, что очевидно у нас не могут 2 ферзя стоять в одном столбце. И поэтому никаких квадратных массовов, "заполняю клетки, которые бьет каждый ферзь" и прочей ереси не надо . Так вот, на очередном шаге у нас есть некоторое количество установленных фигур - значения массива (номера строк фигур) от 0 до какого-то столбца, причем, в этой расстановке никакой ферзь не бьет никакого другого. От функции tst требуется проверить, что если мы поставим ферзя в следующий по счету столбец на определенную строку - будет ли сохранено условие небития никого никем. Проверяется это следующим образом - мы ПОСЛЕДОВАТЕЛЬНО перебираем все существующие фигуры от 0-го столбца до предыдущего проверяемому и для каждой фигуры смотрим, что она не бьет нашего ферзя по горизонтали: m[k]!=j и по диагонали слевавнизу вправонаверх: (i-k)!=(j-m[k]) и по другой диагонали (см кот). Это тривиальная арифметика на уровне 5 класса. тут у нас последовательный оператор И: &&. Как известно. он ЛЕНИВЫЙ - то есть первое ложное условие ПРЕКРАЩАЕТ дальнейшее вычисление и функция возвращает ложь - ведь если какой-то ферзь как-либо бьет нашего тестируемого - нам не надо смотреть дальше. Именно поэтому для организации ПОСЛЕДОВАТЕЛЬНОГО ИТЕРАТИВНОГО ПЕРЕБОРА я смело добавляю в эту цепочку && РЕКУРСИВНЫЙ ВЫЗОВ этой же функции на следующем столбце (как раз тот параметр k ) - если у нас на каком-то столбце уже фигура бьется, то В СИЛУ ЛЕНИВОСТИ ВЫЧИСЛЕНИЯ && эта рекурсивная ветка не продолжится Ну и конечно, дойдя до нашего проверяемого столбца: k==i мы проверили, что все предыдущие фигуры на предыдущих столбцах не бьют нашу тестируемую - значит надо вернуть тру = 1
Ваши впечатления про алгоритм и кота?
Страшно представить, пояснение какой длины вам пришлось бы писать, если бы ваша программа была эдак на несколько тысяч строк!
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 14:17
Ну вот только не надо опять заезженную пластинку про самодокументирующихся котов и т.п. Не надо думать, что никто ничего не знает. Воспринимайте это как ребус, как квест

ЗЫ надеюсь, что вот это
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, вот в этом коде и разбираться не надо, и так все понятно:
вы тоже написали в качестве шутки И не надо оппонировать и убеждать, что вы серьезно - свой кот всегда понятнее
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 15:52
Цитата Сообщение от _Ivana Посмотреть сообщение
вы тоже написали в качестве шутки
Не, ну чтобы понять мою программу, ее достаточно просто прочитать.
Ну и меня просто ужаснул размер вашего пояснения к однострочной программе!
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 15:58
Так и на мою одну строку достаточно взглянуть - и сразу все понятно

Треть этого пояснения - введение в контекст - окружение, в котором вызывается функция и соглашения по ее вызову, на какие данные она опирается - по сути основа алгоритма решения всей задачи, частью которого она является. Еще треть - детальное разжевывание тривиальных моментов реализации (как задать условие "бьет по диагонали" и т.п.) И последняя треть - объяснение рекурсивного вызова в контексте ленивого условия, без уточнений, что это в конечном счете реализация моноида 'All' с ассоциативной бинарной операцией && и единичным элементом true
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 16:22
Цитата Сообщение от _Ivana Посмотреть сообщение
Так и на мою одну строку достаточно взглянуть - и сразу все понятно
Осталось только понять кому! Через некоторое время вы сами можете забыть какие буковки что означают.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 17:00
Ну там же все просто - настолько, что даже вспоминать не надо, из самой функции все видно. Например, тривиальное упражнение - переписать ее с моноида 'All' на моноид 'Any' (то есть, если раньше она возвращала тру, когда поле никто не бьет, то теперь надо наоборот), и поставить НЕ перед ее вызовом в коде.
0
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 21:13  [ТС]
Ваши впечатления про алгоритм и кота?
Впечатления впечатлительные) Пока разбираюсь, но....

Цитата Сообщение от _Ivana Посмотреть сообщение
массиве длиной 8
Эта принципиальная нелюбовь к двумерным массивам

Цитата Сообщение от _Ivana Посмотреть сообщение
значение в каждом индексе равно номеру строки в текущем столбце
Индекс - это k, правильно) ну, а строка - столбец это соответственно i, j..

Цитата Сообщение от _Ivana Посмотреть сообщение
И поэтому никаких квадратных массовов, "заполняю клетки, которые бьет каждый ферзь" и прочей ереси не надо
К сожалению я пока что только так умею решать.

Цитата Сообщение от _Ivana Посмотреть сообщение
Это тривиальная арифметика на уровне 5 класса.
Я ж говорю, мне именно эти моменты покачто не понятны, я уяснил только движение ферзя на уровне того алгоритма, кторый есть у меня в коде, который я выложил, а это
C++
1
m[k] != j && (i - k) != (j - m[k])
на данном этапе не понятно. Условно говоря, я понял, здесь, в функции tst мы проверяем бъёт ли некий ферзь по определённым координатам другого ферзя, если хоть один поподает под бой, то возвращаем ложь.

Хоть про оператор И я знаю и то вперёд

Пока смотрю в отладчике, как говорится смотрю в книгу, вижу .. ну вы понимаете)

Добавлено через 2 минуты
_Ivana Mr.X
Цитата Сообщение от _Ivana Посмотреть сообщение
Ну там же все просто
Конечно просто, если сам написал и разобрался, но, как видите не для всех просто! Зачем других так приопускать то, обидно, однако.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 21:30
Цитата Сообщение от Liss29 Посмотреть сообщение
Индекс - это k, правильно) ну, а строка - столбец это соответственно i, j..
Нет, неправильно. В функции k - индекс столбцов по которым идет итерация, i,j - соответственно столбец и строка проверяемой клетки поля. m[8] - массив расставленных ферзей, m[a]=b означает, что в столбце a ферзь стоит на строке b.

C++
1
m[k] != j
в такой трактовке означает, что ферзь, стоящий в k столбце поля не находится на одной строке с нашей проверяемой клеткой (i,j)
0
 Аватар для Liss29
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
19.05.2016, 22:28  [ТС]
Привык уже i - строка, j - столбец.
если массив имеет вид, например, 0, 4, 7, 5, 2, 6, 1, 3. то это может означать, что ферзь установлен на столбец 0, строка 0, второй ферзь установлен в столбец 1, строка 4, третий на стролбец 2 строка 7...., если следовать определению, кторое вы дали
Цитата Сообщение от _Ivana Посмотреть сообщение
m[a]=b означает, что в столбце a ферзь стоит на строке b.
Смутные очертания понимания вроде вырисовываются, но пока они слишком расплывчаты чтобы что-то уверенно сказать.

Вот как меня торкнуло:
Вызов функции f, тут мы проверяем на равенство строки 8, если это так, то мы выводим на экран некий координаты и рекурсия продолжается до выполнения условия т.е
Code
1
i < 8
в функции show.
Если условие не выполняется, то мы попадаем в функцию loop её передаются параметры текущей строки и нуль.
В функции loop снова проверка, только теперь на равенство столбца
C++
1
j < 8
, если удовлетворяет, то идём в функцию tst с аргументами текущей строки и столбца и нуль для индекса столбцов k.
В функции tst (кстати ассоциативность справа налево это означает что она начинает проверять параметры справа т.е. сначала провериться
C++
1
tst(i, j, k + 1) && (i - k) != (m[k] - j)
.. и так далее, так что ли???)
тут пока есть затруднения с отчётливым пониманием, но то, что она проверяет что-то, что вы описали это ясно. Если справо налево то вызов рекурсивной функции
C++
1
tst(i, j, k + 1)
сравнивается с и.т.д условно говоря вызов функции tst с параметром k + 1 это следующий столбце, а сравнивается он с предыдущим столбцом в выражении
C++
1
(i - k) != (m[k] - j)
тут же k не на один меньше?!

Какой-то у меня бред сумасшедшего получился, а не текст)

Ну мы проверили и возвратились в loop, тут опять карусель, если истина, то массиву, точнее определённому параметру массива с индексом i присваиваем значение столбца, не понятно мне, а на фига) ну ладно, дальше мы вызываем функцию f для следующей строки
C++
1
(i + 1)
, так? То есть в предыдущей строке и столбце у нас всё в порядке, и фигура установлена.

Если ложь вернула функция, то мы вызываем loop для следующей клетки - столбца, а строка остаётся прежней.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.05.2016, 23:17
Ну вы прочитали кота по буквам, да. Но мне не кажется, что у вас полное понимание. Не обязательно видеть здесь обход графа в глубину и моноидальные свертки , но на пальцах представлять как это работает было бы неплохо. Вы постоянно путаете мои столбцы со своими строками - но самое смешное, что это абсолютно не важно - положите монитор набок и все встанет на свои места - задача симметрична относительно поворота доски

ЗЫ у функции tst своя локальная задача, она никак перекрестно-рекурсивно не связана с остальным клубком и наиболее проста для понимания (не считая show). Поэтому в ней путаться совсем не надо, тем более что логику ее работы я расписал выше.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.05.2016, 23:17

Генератор всех возможных комбинаций
Нужно написать генератор всех возможных комбинаций, допустим состоящих из 2-х, 3-х, 4-х символов и сохраняющих комбинации в файл, вот...

Генерация всех возможных комбинаций
Доброго времени суток, подскажите идею, нужно чтобы функция составила все возможные комбинации из цифр и английских букв.

Вывод всех возможных комбинаций
Здравствуйте! Определена строка русским алфавитом, необходимо вывести все возможные комбинации слов для данного алфавита длиной 4, при этом...

Выбор всех возможных комбинаций из Списка
Всех приветствую. Я понимаю,что задача очень простая,но всё же посоветуйте пожалуйста наилучший алгоритм выбора всех возможных комбинаций в...

Сумма вероятностей всех возможных комбинаций
Здравствуйте. Объясните, пожалуйста. Например, есть три символа, каждому присвоена вероятность, а в сумме эти вероятности дают...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Теория всего 12. ВГК
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики 1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание
Hrethgir 21.07.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .
Теория всего 11. Основные параметры
anaschu 21.07.2026
Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .
Теория всего 10. Клод трусишка
anaschu 21.07.2026
Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции"
anaschu 21.07.2026
Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .
Теория всего 8. Clauude трусишка. Ответ джемени
anaschu 21.07.2026
Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .
Теория всего 7. Дерево - это патриархат, грибы - это феминизм
anaschu 21.07.2026
Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат» Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .
История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры.
anaschu 21.07.2026
Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru