Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
scream_cha
1 / 1 / 0
Регистрация: 21.09.2015
Сообщений: 10
1

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

19.03.2017, 12:37. Просмотров 679. Ответов 10

Задаётся натуральное число n. Двое играющих называют по очереди числа, меньшие 107, по следующим правилам. Начиная с числа n, каждое новое число должно увеличивать одну из цифр предыдущего числа (возможно незначащий нуль) на 1, 2 или 3. Проигравшим считается тот, кто называет число 9 999 999. Для заданного n необходимо определить, может ли выиграть игрок, делающий первый ход, при оптимальной игре противника. Вывести сообщение "First win" или "Second win". В случае возможности выигрыша первым игроком требуется вывести все его возможные выигрышные первые ходы.

Формат входного файла: в первой строке содержится единственное число n (1 ≤ n ≤ 9 999 998).

Формат выходного файла: выведите сообщение "First win" или "Second win". В случае возможности выигрыша первым игроком, во второй строке выходного файла через пробел выводятся все его выигрышные первые ходы в порядке возрастания.

Ограничение по времени: 1с.

Пример:

input.txt output.txt
16 "First win"
19 36 216

Мне нужен не сам код программы, а скорее примерный алгоритм для неё.
Спасибо за помощь!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2017, 12:37
Ответы с готовыми решениями:

Динамическое программирование - задача
Добрый вечер! На днях попалась такая задача: Миша записывает 2 числа: n и m, а Маша должна...

Динамическое программирование (задача)
Помогите советом. Есть задача: В арифметическом выражении разрешается использовать число 1,...

задача динамическое программирование
В город N приехал цирк с комндой атлетов. Они хотят удивить горожан города N -- выстроить из своих...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

Какой придумать алгоритм для расстановки фигур в определённом порядке. По-сути это игра "пятнашки"
Нужно придумать алгоритм нахождения оптимального решения, то есть наименьшее количество...

10
TopLayer
881 / 638 / 316
Регистрация: 23.10.2016
Сообщений: 1,523
Завершенные тесты: 7
20.03.2017, 01:12 2
Цитата Сообщение от scream_cha Посмотреть сообщение
примерный алгоритм для неё
Надо определять для каждого числа, является оно выигрышным для стартующего игрока или нет.
Число 9 999 999 является проигрышным.
Число k является проигрышным тогда и только тогда, когда из него нельзя сделать ход в выигрышную позицию.
Поскольку каждый ход увеличивает число, то можно решать задачу итеративно уменьшая k от 9 999 998 до n
0
scream_cha
1 / 1 / 0
Регистрация: 21.09.2015
Сообщений: 10
20.03.2017, 11:42  [ТС] 3
Цитата Сообщение от TopLayer
Поскольку каждый ход увеличивает число, то можно решать задачу итеративно уменьшая k от 9 999 998 до n.
А что делать на каждой из итераций?
0
TopLayer
881 / 638 / 316
Регистрация: 23.10.2016
Сообщений: 1,523
Завершенные тесты: 7
20.03.2017, 15:34 4
Цитата Сообщение от scream_cha Посмотреть сообщение
А что делать на каждой из итераций?
Искать всевозможные ходы из числа k. Если есть ход в выигрышное число, то число k - выигрышное, иначе проигрышное.
0
20.03.2017, 15:34
scream_cha
1 / 1 / 0
Регистрация: 21.09.2015
Сообщений: 10
20.03.2017, 16:34  [ТС] 5
Видимо, мне нужен более примерный алгоритм
0
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,651
20.03.2017, 21:50 6
У Вас 7 равноценных кучек.

Для одной кучки выигрышные значения 123567.
Проведите такой же анализ для двух кучек.
0
scream_cha
1 / 1 / 0
Регистрация: 21.09.2015
Сообщений: 10
21.03.2017, 14:21  [ТС] 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
У Вас 7 равноценных кучек.
Для одной кучки выигрышные значения 123567.
Проведите такой же анализ для двух кучек.
Каких кучек? Не понял вас.
0
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,651
21.03.2017, 16:58 8
Семь цифр в числе - это семь независимых кучек. Каждый ход - добавление 1-3 камней в одну из кучек.
0
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,651
26.03.2017, 21:55 9
Цитата Сообщение от scream_cha Посмотреть сообщение
input.txt output.txt
16 "First win"
19 36 216
Непонятно:
Если ход 216 выигрышный, то ход 2016 тоже должен быть выигрышным. Почему его нет в списке?
0
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,651
30.03.2017, 17:14 10
Задача:
7 кучек камней. За ход можно добавить в одну из кучек от 1 до 3 камней. Максимум 9 камней в кучке.

Алгоритм:
Для каждой позиции в игре вычисляем, выигрышная она или нет для того, чей ход.
Начинаем с заключительной (9999999) позиции.
1. Ближайшую позицию, из которой можно попасть только в выигрышную (для оппонента, так как ход будет его), помечаем как прогрышную (для ходящего).
2. Все позиции, из которых есть ход в эту (проигрышную) позицию помечаем как выигрышные.
3. Повторяем 1-2, пока есть непомеченные позиции.

Реализация:
Позицию (state) храним в виде словаря (map), где каждому возможному количеству камней сопоставлено количество кучек. Храним только значимые (есть кучки) пары ключ-значение. Например, {3 2, 9 1} - это две кучки по 3 камня и одна кучка 9 камней.
Взять 2 камня из кучки с 9 камнями - уменьшить на 1 значение для ключа 9 и увеличить на 1 значение для ключа 7 (= 9 - 2).
Значения (true/false) для позиций храним в словаре (state-values). (На C# я бы использовал массив.)
calculate - заполняет state-values, выполняя в цикле два шага: find-state и update-values.
Строки 27 и ниже отвечают за ввод-вывод.

Lisp
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
(def max-piles-count 7)
(def max-stones-count 10)
 
(defn inc-val [col key] (assoc col key (inc (col key 0))))
(defn dec-val [col key] (let [val (col key)] (if (== 1 val) (dissoc col key) (assoc col key (dec val)))))
(defn take-stones [state position count] (inc-val (dec-val state position) (- position count)))
 
(defn move-from [state] 
    (for [pos (keys state) cnt (range 1 4) :when (<= cnt pos)] 
        (take-stones state pos cnt)))
 
(defn next-state [state]
    (let [pos (first (filter #(< 0 %) (sort < (keys state))))]
        (case pos
            nil nil
            1 (-> state (dec-val 1) (inc-val 0))
            (let [val (+ (state 0 0) (state (dec pos) 0) 1)]
                (-> state (dec-val pos) (dissoc 0) (assoc (dec pos) val))))))
       
(defn update-values [[state-values state]] [(reduce (fn [sv st] (assoc sv st true)) state-values (move-from state)) state])
(defn find-state [[state-values state]] [state-values (->> (iterate next-state state) (drop 1) (drop-while #(state-values %)) first)])
  
(defn calculate []
    (let [root {(dec max-stones-count) max-piles-count}] 
        (->> (iterate (comp update-values find-state) [{root true} root])  
            (some #(when (nil? (% 1)) (% 0)))))) 
            
(defn number->state [number]
    ((reduce (fn [[st n] _] [(inc-val st (rem n 10)) (quot n 10)]) [{} number] (range max-piles-count)) 0))
            
(defn get-moves [number]
    (for [[pos tens] (take  max-piles-count (iterate (fn [[n e]] [(inc n) (* 10 e)]) [0 1])) cnt (range 1 4) 
        :when (< cnt (-  max-stones-count (rem (quot number tens) 10)))] (+ number (* cnt tens))))
            
(defn solve [number] 
    (let [state-values (calculate)] 
        (if (state-values (number->state number))
            (do (println "First win")
                (doseq [move (filter #(not (state-values (number->state %))) (get-moves number))] 
                    (print (str move " "))))
            (println "Second win"))))
 
;main
(solve 16)
http://ideone.com/7vusZg
0
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,651
01.04.2017, 22:08 11
Я тут подумал, что функцию calculate лучше переписать по-другому - более выразительно:
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defn inc-val [col key] (assoc col key (inc (col key 0))))
(defn dec-val [col key] (let [val (col key)] (if (== 1 val) (dissoc col key) (assoc col key (dec val)))))
 
(defn move-from [state] 
    (for [pos (keys state) count (range 1 4) :when (<= count pos)] 
        (inc-val (dec-val state pos) (- pos count))))
 
(defn next-state [state]
    (when-let [pos (first (filter #(< 0 %) (sort < (keys state))))]
        (if (< 1 pos)
            (let [val (+ (state 0 0) (state (dec pos) 0) 1)]
                (-> state (dec-val pos) (dissoc 0) (assoc (dec pos) val)))
            (-> state (dec-val 1) (inc-val 0)))))
            
(defn calculate []
    (let [root {(dec max-stones-count) max-piles-count}] 
        (loop [state-values {root true}, state root]
            (if-let [state (->> (iterate next-state state) (drop 1) (drop-while #(state-values %)) first)]
                (recur (reduce (fn [sv st] (assoc sv st true)) state-values (move-from state)) state)
                state-values))))
0
01.04.2017, 22:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2017, 22:08

Игра "Быки и коровы"
Сделайте алгоритм пожалуйста а то алгоритмы вообще не понимаю. Только играть нужно до тех пор пока...

Игра "Спички Бергсона"
Здравствуйте. Не знаю, правильно ли я выбрал тему, но пока пишу сюда. Есть такая задача-игра:...

Игра "5 в ряд"
Дали задачу по написанию игры &quot;5 в ряд&quot;. Крестики-нолики, но на длинном поле, где надо собрать...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru