Определение алгоритма оптимальной игры

@Veyron · Регистрация: 02.06.2009

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

Всем привет!

Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.

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

PS: На всякий случай: для оптимальной игры не всегда обязательно выбирать максимальное число с краев. Например, в ситуации [3 2 5 4 ] если выбирать наибольший из краев, то будет ничья. На самом деле выиграет первый игрок, т.е. он сначала возьмет 3, чтобы второй игрок взял 4. Тогда первый берет 5 и у него в сумме получается больше. Именно из-за этого я и завис в решении

(((((((((((

@TanT · 28.10.2009, 16:49

Задача на динамическое программирование

поясните что вы понимаете под этим самым програмировнием и на всякий случай какой язык программирования вы знаете?

@snake32 · 28.10.2009, 17:41

А если идти от противного - брать то число, после которого второму игроку придётся брать меньшее?
Те. Если я возьму чисо 4 то противник явно выберет большее из 3 и 5 -> беру 3, и противнику достаётся максимум 4.
Только игра уже будет называтся 'подставь товарища' =)

Добавлено через 11 минут
да...только я не подумал, что противник может играть по тому же алгоритму.
Итого:
[3 2 5 4]
Player 1 = 3+5 - You win
Player 2 = 2+4 - You лузер
А если второй игрок будет просто максимум, то
Player 1 = 3+5 - You win
Player 2 = 4+2 - You лузер
Опять второй лузер. =)
Ого! крутой алгоритм, если:
1. Ходит первый
2. последовательность = [3 2 5 4]. На остальных не проверял - лень.

Добавлено через 4 минуты
ОЙ я недочитал твой пост.... тупо повторил....
Дык какой аго нужен? Что бы всегда ничья чтоли была?

Добавлено через 9 минут
Короче, (бессоная ночь даёт о себе знать) При таком раскладе всё зависит от первого = [3 2 5 4] игрока - если он протупит то - неичья если нет - выиграет. Ну как и в крестиках-ноликах, если в центр не поставил - то максимум будет ничья(при адекватном поведении второго плеера)

@odip · 29.10.2009, 14:19

2TanT:
Это метод такой для решения задач.
http://ru.wikipedia.org/wiki/Д... ммирование

@TanT · 29.10.2009, 15:42

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

2TanT:
Это метод такой для решения задач.
http://ru.wikipedia.org/wiki/Д... ммирование

odip, я в курсе, мне интересно было как понимает это Veyron :р

@Splitter · 29.10.2009, 15:50

можно попробовать рекурсивно перебрать все возможные варианты и выбрать наилучший :/

@Veyron · 30.10.2009, 10:43 **[ТС]**

поясните что вы понимаете под этим самым програмировнием и на всякий случай какой язык программирования вы знаете?

Под этим динамическим программированием я ничо в голову взять не могу - поэтому и спрашиваю. Язык С++.

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

В условиях задачи нельзя. Ограничения - 1 секунда, а максимальное число целых чисел может быть 30000...

@Random · 31.10.2009, 21:20

не факт, что тут задача на динамическое программирование, т.к. стратегия второго игрока нам неизвестна, наверно это ближе к теории игр

@odip · 01.11.2009, 14:52

2Random: Прочитай еще раз условие.
Там написано:

при условии, что игроки будут играть оптимально.

Это значит что оба стараются выиграть, причем оптимальным способом

@Veyron · 01.11.2009, 16:53 **[ТС]**

Если поможет: То что задача на динамо - не из воздуха взято. Задача с /acmp.ru/ По обсуждениям на форуме я так понял, что нужно как бы делать акцент на первом игроке, стараться сделать так, чтобы выиграл именно он. И всё же, насчет динамы - что тут взять за элементарный случай?

@odip · 01.11.2009, 19:01

нужно как бы делать акцент на первом игроке, стараться сделать так, чтобы выиграл именно он

Неправильно понял.
Каждый игрок старается выиграть !
Но исходная ситуация может быть такая, что при любом ходе первого игрока все равно выйграет второй !

Задача с /acmp.ru/

Если так - то приведи полный текст. Там задания не так формулируются

@Veyron · 01.11.2009, 20:57 **[ТС]**

Задача:

Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
Входные данные

В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.

Примеры:

пример 1:
вход:
4
3 2 5 4
выход: 1

пример 2:
вход:
6
5 5 5 5 5 5
выход: 0

пример 3:
вход:
9
2 1 3 2 9 1 2 3 1
выход: 2

пример 4:
вход:
10
2 5 3 12 4 6 13 7 1 3
выход:
1

Вот все условие. Насчет

нужно как бы делать акцент на первом игроке, стараться сделать так, чтобы выиграл именно он

извиняюсь, невнимательно читал

@Random · 02.11.2009, 01:12

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

Это значит что оба стараются выиграть, причем оптимальным способом

это и есть теория игр)

@odip · 02.11.2009, 19:38

Вот эта задача
http://www.acmp.ru/index.asp?main=task&id_task=38
Сдал

@Veyron · 02.11.2009, 21:18 **[ТС]**

Вот эта задача
http://www.acmp.ru/index.asp?main=task&id_task=38
Сдал

А что надо брать за основу решения? Динамическое программирование?

@odip · 02.11.2009, 22:29

Берем матрицу состояний a[n+1][n+1].
Рассмотрим элемент a[i][j].
В данном случае i - это сколько чисел сняли слева в оригинальной посл-ти.
j - сколько сняли справа.
Начальное состояние - это a[0][0] - то есть ничего не сняли.
Конечное состояние a[i][j], где i+j==n.
В конечом состоянии мы сняли все числа и ходов больше нет.

Кроме этого состояние содержит:
1) sum[0] - сумма чисел набранная 0-ым игроком
2) sum[1] - сумма чисел набранная 1-ым игроком

Какой игрок ходит из данного состояния a[i][j] однозначно определяется по i,j
Из состояния a[0][0] ходит 0-ой игрок.
Из состояния a[1][0] ходит 1-ый игрок.
Из состояния a[0][1] ходит 1-ый игрок.

Кроме этого удобно в каждое состояние записать наилучший вариант хода: best_var.
Очевидно что из каждого состояния a[i][j] мы можем снять либо слева число,
тогда мы попадем в a[i+1][j] - это будет вариант хода best_var == 0
либо мы снимем число справа - тогда мы попадем в a[i][j+1], это будет best_var == 1.

Начальное положение.
После снятия последнего числа мы будем в состоянии a[i][j], где i+j==n.
Нужно заполнить все такие состояния.

Очередной ход.
Перебираем назад. Мы двигаемся по побочным диагоналям матрицы.
for ( level= n-1; level>=0; level -- ) {
// тут перебираем всем a[i][j], где i+j==level
}

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

Кто выиграл.
Обратим внимание на самое начальное состояние - a[0][0].
Если в этом состоянии sum[0] > sum[1], то значит выиграл 0-ой игрок.
Если sum[0] < sum[1], то значит выиграл 1-ый игрок.
Ну и остался последний вариант - если суммы равны, значит ничья.

@Veyron · 03.11.2009, 09:07 **[ТС]**

Спасибо большое! Щас пойду кодить... :-)

09.02.2010, 19:22

to odip:
Не могли бы вы показать конечную матрицу состояний для чисел 2 3 5 4 ?

@Asker · 18.06.2013, 23:13

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

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

Кто-нибудь может объяснить, как именно нужно заполнять?

Добавлено через 39 секунд

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

Нужно заполнить все такие состояния.

А чем их заполнять?

@NurlashKO · 21.06.2013, 21:24

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
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
 
using namespace std;
 
#define sz 111
#define for(xx1 , yy1 , zz1) for(int zz1 = xx1 ; zz1 <= yy1 ; zz1++)
 
int d[2][sz][sz], n, a[sz], s[sz];
bool was[2][sz][sz];
 
int sum(int l, int r)
{
    return s[r] - s[l - 1];
}
 
int calc(int p, int l, int r)
{
    if (was[p][l][r])
        return d[p][l][r];
    was[p][l][r] = true;
    if (l == r)
        return d[p][l][r] = a[l];
    return d[p][l][r] = max(sum(l + 1, r) - calc(p ^ 1, l + 1, r) + a[l],
                            sum(l, r - 1) - calc(p ^ 1, l, r - 1) + a[r]);
}
 
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    cin >> n;
    for (1, n, i)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
 
    if (calc(0, 1, n) > s[n] / 2)
        cout << 1;
    else
    if ((calc(0, 1, n) < s[n] / 2 && n % 2 == 0) || (calc(0, 1, n) <= s[n] / 2 && n % 2 == 1))
        cout << 2;
    else
        cout << 0;
    
        return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@snake32 3510 / 1693 / 236 Регистрация: 26.02.2009 Сообщений: 8,463 Записей в блоге: 6
	28.10.2009, 17:41
	А если идти от противного - брать то число, после которого второму игроку придётся брать меньшее? Те. Если я возьму чисо 4 то противник явно выберет большее из 3 и 5 -> беру 3, и противнику достаётся максимум 4. Только игра уже будет называтся 'подставь товарища' =) Добавлено через 11 минут да...только я не подумал, что противник может играть по тому же алгоритму. Итого: [3 2 5 4] Player 1 = 3+5 - You win Player 2 = 2+4 - You лузер А если второй игрок будет просто максимум, то Player 1 = 3+5 - You win Player 2 = 4+2 - You лузер Опять второй лузер. =) Ого! крутой алгоритм, если: 1. Ходит первый 2. последовательность = [3 2 5 4]. На остальных не проверял - лень. Добавлено через 4 минуты ОЙ я недочитал твой пост.... тупо повторил.... Дык какой аго нужен? Что бы всегда ничья чтоли была? Добавлено через 9 минут Короче, (бессоная ночь даёт о себе знать) При таком раскладе всё зависит от первого = [3 2 5 4] игрока - если он протупит то - неичья если нет - выиграет. Ну как и в крестиках-ноликах, если в центр не поставил - то максимум будет ничья(при адекватном поведении второго плеера) 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	29.10.2009, 14:19
	2TanT: Это метод такой для решения задач. http://ru.wikipedia.org/wiki/Д... ммирование 0

@Splitter 203 / 145 / 16 Регистрация: 13.01.2009 Сообщений: 554
	29.10.2009, 15:50
	можно попробовать рекурсивно перебрать все возможные варианты и выбрать наилучший :/ 0

@Random 8 / 8 / 0 Регистрация: 25.11.2008 Сообщений: 32
	31.10.2009, 21:20
	не факт, что тут задача на динамическое программирование, т.к. стратегия второго игрока нам неизвестна, наверно это ближе к теории игр 0

@Veyron 107 / 107 / 9 Регистрация: 02.06.2009 Сообщений: 578
	01.11.2009, 16:53 [ТС]
	Если поможет: То что задача на динамо - не из воздуха взято. Задача с /acmp.ru/ По обсуждениям на форуме я так понял, что нужно как бы делать акцент на первом игроке, стараться сделать так, чтобы выиграл именно он. И всё же, насчет динамы - что тут взять за элементарный случай? 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	02.11.2009, 19:38
	Вот эта задача http://www.acmp.ru/index.asp?main=task&id_task=38 Сдал 1

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	02.11.2009, 22:29
	Сообщение было отмечено как решение Решение Берем матрицу состояний a[n+1][n+1]. Рассмотрим элемент a[i][j]. В данном случае i - это сколько чисел сняли слева в оригинальной посл-ти. j - сколько сняли справа. Начальное состояние - это a[0][0] - то есть ничего не сняли. Конечное состояние a[i][j], где i+j==n. В конечом состоянии мы сняли все числа и ходов больше нет. Кроме этого состояние содержит: 1) sum[0] - сумма чисел набранная 0-ым игроком 2) sum[1] - сумма чисел набранная 1-ым игроком Какой игрок ходит из данного состояния a[i][j] однозначно определяется по i,j Из состояния a[0][0] ходит 0-ой игрок. Из состояния a[1][0] ходит 1-ый игрок. Из состояния a[0][1] ходит 1-ый игрок. Кроме этого удобно в каждое состояние записать наилучший вариант хода: best_var. Очевидно что из каждого состояния a[i][j] мы можем снять либо слева число, тогда мы попадем в a[i+1][j] - это будет вариант хода best_var == 0 либо мы снимем число справа - тогда мы попадем в a[i][j+1], это будет best_var == 1. Начальное положение. После снятия последнего числа мы будем в состоянии a[i][j], где i+j==n. Нужно заполнить все такие состояния. Очередной ход. Перебираем назад. Мы двигаемся по побочным диагоналям матрицы. for ( level= n-1; level>=0; level -- ) { // тут перебираем всем a[i][j], где i+j==level } Заполняем часть матрицы от побочной диагонали до левого верхнего угла. Кто выиграл. Обратим внимание на самое начальное состояние - a[0][0]. Если в этом состоянии sum[0] > sum[1], то значит выиграл 0-ой игрок. Если sum[0] < sum[1], то значит выиграл 1-ый игрок. Ну и остался последний вариант - если суммы равны, значит ничья. 3

@Veyron 107 / 107 / 9 Регистрация: 02.06.2009 Сообщений: 578
	03.11.2009, 09:07 [ТС]
	Спасибо большое! Щас пойду кодить... :-) 0

asnow
	09.02.2010, 19:22
	to odip: Не могли бы вы показать конечную матрицу состояний для чисел 2 3 5 4 ?

Определение алгоритма оптимальной игры

Решение