Динамическое программирование / метод "Разделяй и властвуй"

@xmmmm · Регистрация: 28.11.2019

Студворк — интернет-сервис помощи студентам

Условие:
«Одинокий король» долго ходил по бесконечной шахматной
доске. Известна последовательность из N его ходов (вверх, вниз,
влево, вправо, вверх-влево и т.п.). Написать программу,
определяющую побывал ли король дважды на одном и том же
поле за минимально возможное при заданном N число
вычислений.

Мой код (рабочий):

Java
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
import java.util.ArrayList;
import java.util.Scanner;
 
public class King {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = 500;
        int steps = 0;
        int[][] visited = new int[size][2];
        visited[0][0] = 250;
        visited[0][1] = 250;
        int[][] move = {{-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}};
        ArrayList<Integer> moves = new ArrayList<Integer>();
        int menu = 1;
        while (true)
        {
            System.out.println("Выберите пункт соответствующий ходу короля: ");
            System.out.println("1 - вверх влево");
            System.out.println("2 - вверх");
            System.out.println("3 - вверх вправо");
            System.out.println("4 - вправо");
            System.out.println("5 - вправо вниз");
            System.out.println("6 - вниз");
            System.out.println("7 - вниз влево");
            System.out.println("8 - влево");
            System.out.println("9 - закончить ввод");
            menu = in.nextInt();
            if (menu == 9)
                break;
            if ((menu < 1) || menu > 9)
            {
                System.out.println("Введен не корректный пункт меню, попробуйте снова!");
            }
            else
            {
                moves.add(menu);
                steps++;
            }
        }
 
        // выполняем ходы, записываем текущие координаты в массив
        for (int i = 1; i < steps+1; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                visited[i][j] = visited[i - 1][j] + move[moves.get(i - 1)-1][j];
            }
        }
        System.out.println();
 
        // проверка были ли совпадения координат x и y, то есть был ли король на 1-ом месте 2 раза
        int temp_steps = steps;
        for (int i = 0; i < temp_steps + 1; i++)
        {
            for (int j = i + 1; j < temp_steps + 1; j++)
            {
                if ((visited[i][0] == visited[j][0]) && (visited[i][1] == visited[j][1]))
                {
                    System.out.println("Совпадение на ходах " + i + " и " + j);
                }
            }
        }
        System.out.println();
 
        // вывод координат
        for(int i = 0; i <= steps; i++)
        {
            System.out.print(i + ": ");
            for(int j = 0; j < 2; j++)
            {
                System.out.printf("%d\t", visited[i][j]);
            }
            System.out.println();
        }
        System.out.println(steps);
    }
}

Надо написать алгоритм используя динамическое программирование, либо метод "Разделяй и властвуй". Читал статьи по этому поводу, понял лишь то, что надо использовать рекурсию. Но как её здесь применить не совсем представляю, может есть у кого идеи?

@wizard41 · 15.11.2022, 22:01

xmmmm, немного пересмотрим подход.. Как закончу - скину.

Добавлено через 9 минут

Сообщение от Coffeini

Короче, я думаю, что надо заменить диагональные методы:

Сообщение от Coffeini

На такие:

Coffeini, я вчера с замыленными глазами не разглядел. Так тут ничего не поменялось - эти методы уже сделаны в классе Point. Зачем дублировать код, если при диагональном перемещении можно вызывать уже готовые методы прямолинейных?
Т.е. методы moveN() и moveW() сделают свое дело (проверки) сами.

@xmmmm · 15.11.2022, 22:36 **[ТС]**

Ну у меня пока вот что получилось:

Кликните здесь для просмотра всего текста

Java
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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
package Divide_and_Conquer;
 
import java.util.HashSet;
import java.util.Scanner;
 
public class DivideAndConquer {
    public static void main(String[] args) {
        int y = 5, x = 100;
        int menu;
        Scanner in = new Scanner(System.in);
        int[][] ChessMate = new int[y][x];
        System.out.println("King posed in {0, 0}...");
        King king = new King(new Point(0,0), ChessMate);
        if(king.makesMoves()){
            System.out.println("The king has been to the same place twice!");
        } else System.out.println("The king has not been in the same place twice!");
    }
}
 
class Point {
    int X, Y;
 
    //<editor-fold desc="Getters & Constructor">
    public int getX() {
        return X;}
 
    public int getY() {
        return Y;}
 
    public Point (int x, int y) {
        X = x; Y = y;}
    //</editor-fold>
 
    //<editor-fold desc="Public Methods">
    //North
    public boolean moveN(int[][] field) {
        if (Y < field.length - 1) {
            Y++; return true;}
        return false;
    }
 
    //South
    public boolean moveS() {
        if (Y > 0) {
            Y--; return true;}
        return false;
    }
 
    //West
    public boolean moveW() {
        if (X > 0) {
            X--; return true;}
        return false;
    }
 
    //East
    public boolean moveE(int[][] field) {
        if (X < field[Y].length - 1) {
            X++; return true;}
        return false;
    }
 
    //North-East
    public boolean moveNE(int[][] field) {
        if (X < field[Y].length-1 && Y < field.length-1)
        {
            X++;
            Y++;
            return true;
        }
        return false;
    }
 
    //South-East
    public boolean moveSE(int[][] field) {
        if (X < field.length-1 && Y > 0)
        {
            X++;
            Y--;
            return true;
        }
        return false;
    }
 
    //South-West
    public boolean moveSW() {
        if (X > 0 && Y > 0)
        {
            X--;
            Y--;
            return true;
        }
        return false;
    }
 
    //North-West
    public boolean moveNW(int[][] field) {
        if(Y < field.length-1 && X > 0){
            Y++;
            X--;
            return true;
        }
        return false;
    }
    //</editor-fold>
 
    @Override
    public String toString() { return "{" + X + ", " + Y + "}"; }
}
 
class King {
    Point position;
    int[][] chess;
    private final String moveSuccess = "King moved into position: ";
    private final String moveDenied = "Moving is not possible!";
 
    public King (Point pos, int[][] chessm) {
        if (pos.getY() < 0 || pos.getX() < 0) throw new IllegalArgumentException("!IAE");
        if (pos.getY() > chessm.length - 1 || pos.getX() > chessm[pos.getY()].length - 1)
            throw new ArrayIndexOutOfBoundsException("!AIE");
        position = pos;
        chess = chessm;
    }
 
    public boolean makesMoves()
    {
        Scanner in = new Scanner(System.in);
        int menu;
        boolean isKingVisitedPlaceTwice = false;
        HashSet<Point> points = new HashSet<>();
        points.add(new Point(position.X, position.Y));
        while (true)
        {
            this.printMenu();
            menu = in.nextInt();
            switch (menu)
            {
                case 1:
                    this.moveNW();
                    break;
                case 2:
                    this.moveN();
                    break;
                case 3:
                    this.moveNE();
                    break;
                case 4:
                    this.moveE();
                    break;
                case 5:
                    this.moveSE();
                    break;
                case 6:
                    this.moveS();
                    break;
                case 7:
                    this.moveSW();
                    break;
                case 8:
                    this.moveW();
                    break;
                case 9:
                    System.out.println(points);
                    return isKingVisitedPlaceTwice;
                default:
                    System.out.println("Invalid menu item entered");
                    break;
            }
            if(menu > 1 && menu < 9 && isMoveComplete)
            {
                isMoveComplete = false;
                if(points.add(new Point(position.X, position.Y)))
                {
                    isKingVisitedPlaceTwice = false;
                } else isKingVisitedPlaceTwice = true;
            }
        }
    }
 
    public void printMenu()
    {
        System.out.println("Choose the item to the king's move: ");
        System.out.println("1 - вверх влево");
        System.out.println("2 - вверх");
        System.out.println("3 - вверх вправо");
        System.out.println("4 - вправо");
        System.out.println("5 - вниз вправо");
        System.out.println("6 - вниз");
        System.out.println("7 - вниз влево");
        System.out.println("8 - влево");
        System.out.println("9 - finish the input");
    }
    //<editor-fold desc="Public Methods">
    boolean isMoveComplete = false;
 
    public void moveN() {
        if (position.moveN(chess))
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
 
    public void moveS() {
        if (position.moveS())
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
 
    public void moveW() {
        if (position.moveW())
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
 
    public void moveE() {
        if (position.moveE(chess))
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
 
    public void moveNE() {
        if (position.moveNE(chess))
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
 
    public void moveNW() {
        if (position.moveNW(chess))
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else  System.out.println(moveDenied);
    }
 
    public void moveSE() {
        if (position.moveSE(chess))
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
 
    public void moveSW() {
        if (position.moveSW())
        {
            System.out.println(moveSuccess + position);
            isMoveComplete = true;
        } else System.out.println(moveDenied);
    }
}

Но тут проблема есть с HashSet<>.

@wizard41 · 15.11.2022, 23:29

Сообщение от xmmmm

Ну у меня пока вот что получилось:

Меню зря в Короля встроил. Оно должно быть отдельным методом.
И не привыкай к while (true). Это дурной тон.

@wizard41 · 16.11.2022, 01:05

xmmmm, в общем, делай пока так, остальное завтра:

Java
1
2
3
enum moveDirection {
    NW, N, NE, E, SE, S, SW, W
}

class Point

Java
1
2
3
4
5
6
7
8
9
class Point {
    public int R, C;
    public Point (int r, int c) {
        if (r < 0 || c < 0) throw new IllegalArgumentException("!IArgEx");
        R = r; C = c;
    }
    @Override
    public String toString() { return "{" + R + ", " + C + "}"; }
}

class King

Java
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
class King {
    private Point position;
    private int[][] chessboard;
    private int countOfMoved;
 
    public Point getPosition() {return position;}
    public int getCountOfMoved() {return countOfMoved;}
 
    public King (int[][] chessboard) {
        position = new Point(0, 0);
        this.chessboard = chessboard;
    }
 
    //<editor-fold desc="Public Methods">
    public boolean move(moveDirection dir) {
        if (dir == moveDirection.NW) {
            if (position.R > 0 && position.C > 0) {
                position.R--;
                position.C--;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.N) {
            if (position.R > 0) {
                position.R--;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.NE) {
            if (position.R > 0 && position.C < chessboard[position.R].length - 1) {
                position.R--;
                position.C++;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.E) {
            if (position.C < chessboard[position.R].length - 1) {
                position.C++;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.SE) {
            if (position.R < chessboard.length - 1 && position.C < chessboard[position.R].length - 1) {
                position.R++;
                position.C++;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.S) {
            if (position.R < chessboard.length - 1) {
                position.R++;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.SW) {
            if (position.R < chessboard.length - 1 && position.C > 0) {
                position.R++;
                position.C--;
                countOfMoved++;
                return true;}}
        else if (dir == moveDirection.W) {
            if (position.C > 0) {
                position.C--;
                countOfMoved++;
                return true;}}
        return false;
    }
    //</editor-fold>
}

public class DivideAndConquer

Java
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
public class DivideAndConquer {
 
    public static void main(String[] args) {
        int[][] chessBoard = createChessBoard(2, 100);
        King king = new King(chessBoard);
 
        kingMove(king, 5);
        kingMove(king, 2);
        kingMove(king, 3);
        kingMove(king, 4);
    }
 
    static int[][] createChessBoard(int r, int c) {
        if (r < 2 || c < 2) throw new IllegalArgumentException("!IArgEx");
        return new int[r][c];
    }
 
    static void kingMove(King king, int select) {
        final String moveSuccess = "King moved into position: ";
        final String moveDenied = "Moving is not possible!";
        final String invalidEnter = "Invalid Enter!";
 
        switch (select) {
            case 1 -> {
                if (king.move(moveDirection.NW)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 2 -> {
                if (king.move(moveDirection.N)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 3 -> {
                if (king.move(moveDirection.NE)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 4 -> {
                if (king.move(moveDirection.E)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 5 -> {
                if (king.move(moveDirection.SE)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 6 -> {
                if (king.move(moveDirection.S)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 7 -> {
                if (king.move(moveDirection.SW)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 8 -> {
                if (king.move(moveDirection.W)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            default -> System.out.println(invalidEnter);
        }
    }
}

@wizard41 · 16.11.2022, 10:02

Обновленный класс King с HashSet-ом:

Кликните здесь для просмотра всего текста

Java
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
class King {
    private Point position;
    private int[][] chessboard;
    private int countOfMoved;
    private HashSet<String> hs = new HashSet<>();
    private HashSet<String> dmove = new HashSet<>();
 
    public Point getPosition() {return position;}
    public int getCountOfMoved() {return countOfMoved;}
    public HashSet<String> getDmove() {return dmove;}
 
    public King (int[][] chessboard) {
        position = new Point(0, 0);
        this.chessboard = chessboard;
    }
 
    //<editor-fold desc="Public Methods">
    public boolean move(moveDirection dir) {
        if (dir == moveDirection.NW) {
            if (position.R > 0 && position.C > 0) {
                position.R--;
                position.C--;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.N) {
            if (position.R > 0) {
                position.R--;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.NE) {
            if (position.R > 0 && position.C < chessboard[position.R].length - 1) {
                position.R--;
                position.C++;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.E) {
            if (position.C < chessboard[position.R].length - 1) {
                position.C++;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.SE) {
            if (position.R < chessboard.length - 1 && position.C < chessboard[position.R].length - 1) {
                position.R++;
                position.C++;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.S) {
            if (position.R < chessboard.length - 1) {
                position.R++;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.SW) {
            if (position.R < chessboard.length - 1 && position.C > 0) {
                position.R++;
                position.C--;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        else if (dir == moveDirection.W) {
            if (position.C > 0) {
                position.C--;
                countOfMoved++;
                if (!hs.add(position.toString())) dmove.add(position.toString());
                return true;}}
        return false;
    }
    //</editor-fold>
}

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    public static void main(String[] args) {
        int[][] chessBoard = createChessBoard(2, 100);
        King king = new King(chessBoard);
 
        kingMove(king, 5);
        kingMove(king, 2);
        kingMove(king, 3);
        kingMove(king, 4);
        kingMove(king, 8);
 
        System.out.println("Всего сделано ходов: " + king.getCountOfMoved());
        System.out.println("Совпадение на ходах:");
        System.out.println(king.getDmove());
    }

Code
1
2
3
4
5
6
7
8
1: King moved into position: {1, 1}
2: King moved into position: {0, 1}
Moving is not possible!
3: King moved into position: {0, 2}
4: King moved into position: {0, 1}
Всего сделано ходов: 4
Совпадение на ходах:
[{0, 1}]

Осталось только прикрутить меню (отдельным методом).

@xmmmm · 16.11.2022, 11:21 **[ТС]**

Сообщение от wizard41

Java
1
2
3
4
5
6
else if (dir == moveDirection.N) {
      if (position.R > 0) {
          position.R--;
          countOfMoved++;
          if (!hs.add(position.toString())) dmove.add(position.toString());
          return true;}}

Почему когда идем на север(вверх), координата R (привычный Y) уменьшается? Должна ведь наоборот увеличиваться.

Добавлено через 18 минут

Сообщение от wizard41

Осталось только прикрутить меню (отдельным методом).

Сейчас код пересмотрю, переварю, и буду думать над этим, спасибо

Сообщение от wizard41

И не привыкай к while (true). Это дурной тон.

А чем while(true) плох? Другой цикл использовать, или пересмотреть вообще подход к этому, избавляться от "бесконечных" циклов как то?

@wizard41 · 16.11.2022, 11:51

Сообщение от xmmmm

Почему когда идем на север(вверх), координата R (привычный Y) уменьшается?

потому что двумерный массив начинается с верхнего левого угла.

Сообщение от xmmmm

избавляться от "бесконечных" циклов как то?

Да. Условие выхода должно быть.

@xmmmm · 16.11.2022, 19:17 **[ТС]**

Сообщение от wizard41

потому что двумерный массив начинается с верхнего левого угла.

Ну для пользователя мне кажется привычней будет, ориентироваться как в системе координат(как на реальной шахматной доске), то бишь если ход вверх, то y инкрементируется.

Сообщение от wizard41

Осталось только прикрутить меню (отдельным методом)

Отдельным методом, имелось ввиду не в классах King и Point?

Ну так прикрутил:

Кликните здесь для просмотра всего текста

Java
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
import java.util.Scanner;
 
public class DivideAndConquer {
    public static void main(String[] args) {
        int[][] chessBoard = createChessBoard(100, 2);
        King king = new King(chessBoard);
 
        inputKingMoves(king);
 
        System.out.println("Всего сделано ходов: " + king.getCountOfMoved());
        System.out.println("Совпадение на ходах:");
        System.out.println(king.getDmove());
    }
 
    static void inputKingMoves(King king)
    {
        Scanner in = new Scanner(System.in);
        int menu = 0;
        while (menu != 9)
        {
            printMenu();
            menu = in.nextInt();
            kingMove(king, menu);
        }
    }
    static void printMenu()
    {
        System.out.println("Choose the item to the king's move: ");
        System.out.println("1 - вверх влево");
        System.out.println("2 - вверх");
        System.out.println("3 - вверх вправо");
        System.out.println("4 - вправо");
        System.out.println("5 - вниз вправо");
        System.out.println("6 - вниз");
        System.out.println("7 - вниз влево");
        System.out.println("8 - влево");
        System.out.println("9 - finish the input");
    }
    static int[][] createChessBoard(int x, int y) {
        if (x < 2 || y < 2) throw new IllegalArgumentException("!IArgEx");
        return new int[x][y];
    }
 
    static void kingMove(King king, int select) {
        final String moveSuccess = "King moved into position: ";
        final String moveDenied = "Moving is not possible!";
        final String invalidEnter = "Invalid Enter!";
 
        switch (select) {
            case 1 -> {
                if (king.move(moveDirection.NW)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 2 -> {
                if (king.move(moveDirection.N)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 3 -> {
                if (king.move(moveDirection.NE)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 4 -> {
                if (king.move(moveDirection.E)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 5 -> {
                if (king.move(moveDirection.SE)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 6 -> {
                if (king.move(moveDirection.S)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 7 -> {
                if (king.move(moveDirection.SW)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 8 -> {
                if (king.move(moveDirection.W)) System.out.println(king.getCountOfMoved() +
                        ": " + moveSuccess + king.getPosition());
                else System.out.println(moveDenied);
            }
            case 9 -> {
                System.out.println("Entry is over");
            }
            default -> System.out.println(invalidEnter);
        }
    }
}

Какой тут метод используется "динамическое программирование" или "разделяй и властвуй"? И в чем это проявляется/по чем это можно заметить?

@wizard41 · 16.11.2022, 19:56

Сообщение от xmmmm

Ну для пользователя мне кажется привычней будет

Для пользователя совершенно фиолетово как там реализована логика перехода по клеткам. Суть данной задачи совсем не в этом, а в:

Сообщение от xmmmm

Какой тут метод используется "динамическое программирование"

а именно - разбиение задач на более мелкие подзадачи.

Сообщение от xmmmm

Отдельным методом, имелось ввиду не в классах King и Point?

Именно так. Т.е. само "меню" тоже приобретает вид отдельной задачи и ни король ни тем более класс точки не имеют к меню никакого отношения.

Добавлено через 3 минуты
Если сильно хочется, то даже рекурсию сюда прикрутить можно, но в данной постановке задачи - это абсурд. Я еще понимаю, если бы задача была типа "указать точку, в которую фигура должна прийти за минимальное кол-во ходов..". Тут еще с натягом можно объяснить появление рекурсии. Но в этой задаче король ходит по указке с клавиатуры - какая тут нафиг рекурсия?

Добавлено через 3 минуты

Динамическое программирование.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

@xmmmm · 16.11.2022, 20:49 **[ТС]**

Сообщение от wizard41

а именно - разбиение задач на более мелкие подзадачи.

Понял

Сообщение от wizard41

Т.е. само "меню" тоже приобретает вид отдельной задачи и ни король ни тем более класс точки не имеют к меню никакого отношения.

Ну да, логика в этом есть

Сообщение от wizard41

Но в этой задаче король ходит по указке с клавиатуры - какая тут нафиг рекурсия?

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

Спасибо за помощь и просвещение в этом вопросе)

@wizard41 · 16.11.2022, 20:59

Давай, удачи!

Новые блоги и статьи Все статьи Все блоги /
Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .

@wizard41 3445 / 2765 / 575 Регистрация: 04.09.2018 Сообщений: 8,703 Записей в блоге: 3
	16.11.2022, 20:59
	Давай, удачи! 1

Динамическое программирование / метод "Разделяй и властвуй"

Решение