Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.232.88.17] |
|
Сообщ.
#1
,
|
|
|
Дано 3 (или N рядов) ряда камней, по 3,5,7 (или M1,M2,M3) камней в каждом ряду, максимум можно брать по тому количеству сколько осталось в ряду камней. Проигрывает тот, кто берет последний камень.
Как реализовать беспройгрышный алгоритм игры с компьютером на VB по теореме Шпрага-Гранди? |
Сообщ.
#2
,
|
|
|
Что это за теорема?
Выигрышная стратегия проста: после твоего хода XOR-сумма (побитовая) чисел камней в кучках должна быть равна нулю. Если она уже равна нулю перед твоим ходом, позиция выигрышна для твоего противника. Остаётся только делать произвольные ходы в надежде, что противник ошибётся. Интересно, но стратегия почти не меняется, если изменить условие выигрыша (проигрывает взявший последний камень). Пока есть больше одной кучки, в которых больше одного камня, надо придерживаться этой же стратегии. А потом оставить нечётное число кучек по одному камню. |
Сообщ.
#3
,
|
|
|
amk
да стратегию я видел. Но как вычислить XOR-сумму чисел камней, и организовать какие фишки будет брать следующим ходом компьютер, для создания выйгрышной ситуации? Добавлено пример видел тут на паскале Алгоритм для игры "НИМ". не совсем разобрался в нем. нужен на VB |
Сообщ.
#4
,
|
|
|
http://e-maxx.ru/algo/sprague_grundy
>Но как вычислить XOR-сумму чисел камней Как в VB оператор побитового исключающего или выглядит? XorSum = N1 xor N2 xor N3... |
Сообщ.
#5
,
|
|
|
Private Sub picX1_Click(Index As Integer) picX1(Index).Visible = False End Sub Private Sub picX2_Click(Index As Integer) picX2(Index).Visible = False End Sub Private Sub picX3_Click(Index As Integer) picX3(Index).Visible = False End Sub Private Sub Command1_Click() Rem -------Ход компьютера----------------------- For I = 0 To 2 If picX1(I).Visible = True Then N1 = N1 + 1 Next For I = 0 To 4 If picX2(I).Visible = True Then N2 = N2 + 1 Next For I = 0 To 6 If picX3(I).Visible = True Then N3 = N3 + 1 Next M = 1 For I1 = 0 To N1 xorsum = I Xor N2 Xor N3 If xorsum = 0 Then GoTo 10 Next M = 2 For I2 = 0 To N2 xorsum = N1 Xor I Xor N3 If xorsum = 0 Then GoTo 10 Next M = 3 For I3 = 0 To N3 xorsum = N1 Xor N2 Xor I If xorsum = 0 Then GoTo 10 Next Rem -----Нет позиций=0 Exit Sub 10: If M = 1 Then For I = 0 To I1 If picX1(I).Visible = True Then picX1(I).Visible = False Next End If If M = 2 Then For I = 0 To I2 If picX2(I).Visible = True Then picX2(I).Visible = False Next End If If M = 3 Then For I = 0 To I3 If picX3(I).Visible = True Then picX3(I).Visible = False Next End If End Sub Получается как то так, значит. Но всегда есть позиции =0 |
Сообщ.
#6
,
|
|
|
Цитата artur44 @ Я, слава богу, бейсик давно забыл. Так что, даже не скажу.Но как вычислить XOR-сумму чисел камней Цитата artur44 @ Ну, как вариант, посчитай XOR-сумму всех кучек. Далее, сколько фишек должно остаться в каждой куче, если брать фишки из неё (XOR-сумма остальных кучек или XOR вычисленой суммы и числа фишек в кучке). В каких-то кучках надо будет "оставить" больше, чем в них лежит (но для этого пришлось бы докладывать). В каких-то надо будет оставить меньше. Фишки, естественно, можно брать из той, где нужный остаток меньше текущего количества (таких кучек может быть и несколько). какие фишки будет брать следующим ходом компьютер |