На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Игра Ним (теорема Шпрага-Гранди) , Реализовать на VB
    Дано 3 (или N рядов) ряда камней, по 3,5,7 (или M1,M2,M3) камней в каждом ряду, максимум можно брать по тому количеству сколько осталось в ряду камней. Проигрывает тот, кто берет последний камень.
    Как реализовать беспройгрышный алгоритм игры с компьютером на VB по теореме Шпрага-Гранди?
      Что это за теорема?

      Выигрышная стратегия проста: после твоего хода XOR-сумма (побитовая) чисел камней в кучках должна быть равна нулю. Если она уже равна нулю перед твоим ходом, позиция выигрышна для твоего противника. Остаётся только делать произвольные ходы в надежде, что противник ошибётся.
      Интересно, но стратегия почти не меняется, если изменить условие выигрыша (проигрывает взявший последний камень). Пока есть больше одной кучки, в которых больше одного камня, надо придерживаться этой же стратегии. А потом оставить нечётное число кучек по одному камню.
        amk
        да стратегию я видел. Но как вычислить XOR-сумму чисел камней, и организовать какие фишки будет брать следующим ходом компьютер, для создания выйгрышной ситуации?

        Добавлено
        пример видел тут на паскале
        Алгоритм для игры "НИМ".
        не совсем разобрался в нем. нужен на VB
          http://e-maxx.ru/algo/sprague_grundy

          >Но как вычислить XOR-сумму чисел камней
          Как в VB оператор побитового исключающего или выглядит?
          XorSum = N1 xor N2 xor N3...
            ExpandedWrap disabled
              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
              Цитата artur44 @
              Но как вычислить XOR-сумму чисел камней
              Я, слава богу, бейсик давно забыл. Так что, даже не скажу.
              Цитата artur44 @
              какие фишки будет брать следующим ходом компьютер
              Ну, как вариант, посчитай XOR-сумму всех кучек. Далее, сколько фишек должно остаться в каждой куче, если брать фишки из неё (XOR-сумма остальных кучек или XOR вычисленой суммы и числа фишек в кучке). В каких-то кучках надо будет "оставить" больше, чем в них лежит (но для этого пришлось бы докладывать). В каких-то надо будет оставить меньше. Фишки, естественно, можно брать из той, где нужный остаток меньше текущего количества (таких кучек может быть и несколько).
              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
              0 пользователей:


              Рейтинг@Mail.ru
              [ Script execution time: 0,0333 ]   [ 16 queries used ]   [ Generated: 28.03.24, 21:50 GMT ]