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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

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

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

Решение