Курсы по программированию

Формула программиста
основатель — Волосатов Евгений Витольдович
C# Олимпиада из Простоквашино

Морской Бой / Олимпиада - Самый лучший алгоритм

  • На участие в олимпиаде было прислано 10 работ.
    В этом видео мы проводим тестирование всех программ.
    Домашнее задание - составить словесный алгоритм ИИ.
  • Дата отправки отчёта: 11 июля 2015 г.
  • Задание выполнено: за 1 час. 00 мин.
  • Чему научился: Пока что ничему. Как правильно расставлять корабли и как их ловить давно известно, а кода здесь не было.
    Но планирую повнимательнее изучить сам код победителей, чтобы увидеть как вообще задавать выстрелы и определять зоны, в которые стрелять уже не надо.
  • Что было сложным: Просто нет необходимых знаний для переноса алгоритма из головы в программу.

    Лучший алгоритм у Оранжа 2775.
    У Елены 4004 отсутствует рандом, у нее всегда одинаковое количество ходов тратится на одну и ту же расстановку, минимум = среднему = максимуму.
    Она методично проходит по А4 - А8 - Б1 - Б5 и т.п. - ловит четырехпалубный.
    Затем так же методично проходит А2 - А6 - А10 - Б3 и т.п. и ловит двухпалубные.
    А затем просто проходит и методично добивает остальных.
    Но такой алгоритм очень предсказуем и можно просто добиться такой расстановки против нее, что количество ходов всегда будет 80, достаточно поместить однопалубный в самый конец сетки. Например, К9.
  • Комментарии: Думаю, что не совсем правильно начинать ловить корабли от левого верхнего угла.
    Люди больше тяготеют к расстановке кораблей внизу и справа. И при расстановке они ставят корабли так, чтобы не попасть сразу под ходы А4, А8, Б1, Б5 и т.п.
    Думаю, что нужно начинать выстрелы с клеток К4, К8, З10, Г10 и далее по кругу на вертикаль А и горизонталь 1.
    Затем пройти по спирали до центра.
    Аналогично пройти шагом 2 и выловить все корабли, кроме одиночных.

    Когда останутся только одиночные, то первые 3 выстрела в те клетки, которые имеют максимальное количество "неоткрытых" соседей, а 4-й - в клетку с минимальным количеством соседей. Необходимое соотношение выстрелов в наиболее выгодные клетки с выстрелами в клетки, у которых все соседние уже открыты, нужно определять опытным путем.
  • Оценка видео-уроку:
Отчёт от 4814 за Морской Бой / Олимпиада - Самый лучший алгоритм




Оцени работу

 
Сохранить страницу:

1. Евгений Волосатов
Евгений Волосатов
ответить
→  Дмитрий  # Морской Бой / Олимпиада - Самый лучший алгоритм / 2015-07-11 10:01

Люди - вообще очень хитрые.
Первый раз человек может и поставит снизу, а потом подумает, и сделает всё наоборот :)


1901. Neverwinter 2
Neverwinter 2
ответить
→  Дмитрий  # Морской Бой / Олимпиада - Самый лучший алгоритм / 2015-07-11 07:58

Отличные комментарии. Супер. Было приятно прочитать Ваш анализ!


  • Отчёт оценивали:
    7541Максим+1  

Начинаем практику по языку C#




Чтобы стать хорошим программистом — нужно писать программы. На нашем сайте очень много практических упражнений.

После заполнения формы ты будешь подписан на рассылку «C# Вебинары и Видеоуроки», у тебя появится доступ к видеоурокам и консольным задачам.

Несколько раз в неделю тебе будут приходить письма — приглашения на вебинары, информация об акциях и скидках, полезная информация по C#.

Ты в любой момент сможешь отписаться от рассылки.
Научился: Узнал о многих алгоритмах ИИ Морского боя.
Все отлично!! Понравился алгоритм 2775.
Научился: Просмотрела разные алгоритмы и их загрузку через абстрактный класс.
Трудности: Понять как это все работает. И алгоритмы и их загрузка.
Алгоритмы public и orange. Как я поняла, к любому из представленных алгоритмов можно найти более оптимальные расстановки. Есть мысль использовать в программе 2-3 алгоритма, выбирая номер алгоритма рандомно. Алгоритм. Найти все точки, где может быть четырехпалубный корабль. Выделить их в массив. Стрелять рандомно по свободным, пока есть не проверенные. Если корабль подбит, пометить соседние ячейки как пустые. Если ранен, рандомно проверить во всех направлениях, пока не останется одно. Добиваем корабль. Здесь можно сделать проверку какие корабли остались и определить может ли корабль быть размещен горизонтально/вертикально, сколько. И стрелять по наиболее удачной ячейке. Далее проверяем на двухпалубные корабли. Опять выделяем места, где они могут быть размещены и стреляем рандомно, пока не проверим все. Оставшиеся однопалубники ищем рандомно из числа не проверенных ячеек.