Стратегии выбывания в игре с 100 участниками: оптимизация выигрыша

Delphi , Синтаксис , Математика

Игра с участием 100 противников и k раундами представляет собой интересную математическую задачу. В каждом раунде вы можете выбыть хотя бы одного противника, за что вам начисляется награда. Сумма награды зависит от количества выбывших противников и общего количества оставшихся противников. Ваша задача — выработать стратегию, которая позволит получить максимально возможную сумму выигрыша.

Основные правила игры

• Количество раундов: k
• Начальное количество противников: 100
• Награда за выбытие противников: 100,000 * (количество выбывших противников / общее количество оставшихся противников), округление вниз.

Пример игры

• В первом раунде выбыли 50 противников, выигрыш составил 50,000.
• Во втором раунде выбыли 30 противников, выигрыш составил 60,000.
• В последнем раунде выбыли последние 20 противников, выигрыш составил 100,000.
• Общий выигрыш составил 210,000.

Разработка стратегии

Попытка написать программу для определения стратегии привела к использованию функции floor, которая, как оказалось, отсутствует в Pascal. Однако, после добавления Uses math;, функция заработала корректно.

Подход к решению

Для оптимизации выигрыша можно использовать динамический подход, который включает рекурсивный расчет максимального выигрыша для каждого раунда и количества оставшихся противников. Однако, такой подход может быть медленным для больших значений k из-за использования перебора.

Математическое решение

Задача имеет математическое решение, которое может быть вычислено заранее. В случае трех раундов, оптимальной стратегией является выбывание 90 противников в первом раунде, 9 противников во втором и одного в последнем. Это связано с тем, что максимальный выигрыш в третьем раунде не зависит от количества выбывших противников в предыдущих раундах.

Программа на Pascal

program Project1;
var
  x, xmax: byte;
  MaxRes, tmp: real;
begin
  xmax := 0;
  MaxRes := 0;
  for x := 1 to 99 do
  begin
    tmp := 100000 * x / 100 + 100000*(99 - x) / (100 - x) + 100000 * 1 / 1;
    if tmp > MaxRes then
    begin
      MaxRes := tmp;
      xmax := x;
    end;
  end;
  writeln(xmax);
  readln;
end.

Оптимизация

Для оптимизации можно использовать целочисленные вычисления и умножение на 100,000 только один раз после определения стратегии.

program Project1;
{$APPTYPE CONSOLE}
{$R *.res}
Uses System.SysUtils;
function Part(RemainingEnemies: byte; Depth: byte;
  var OutputString: string): integer;
var
  i: byte;
  tmp, MaxRes: integer;
  imax: byte;
  DaughterString: string;
begin
  OutputString := '';
  if Depth = 1 then
    exit(0);
  imax := 0;
  MaxRes := 0;
  for i := 1 to RemainingEnemies - Depth + 1 do
  begin
    tmp := (i*100000) div RemainingEnemies + Part(RemainingEnemies - i, Depth - 1,
      DaughterString);
    if tmp > MaxRes then
    begin
      MaxRes := tmp;
      imax := i;
      OutputString := inttostr(imax) + ' ' + DaughterString;
    end;
  end;
  result := MaxRes div 100000;
end;
begin
  writeln(Part(100, 3, s):10:1);
  writeln(s);
  readln;
end.

Форматирование вывода :10:1 в коде означает, что вывод будет содержать 10 символов в целом, включая 1 десятичное место после запятой.

Заключение

Оптимизация выигрыша в игре с выбыванием противников требует тщательного планирования и использования математических подходов. Разработанные стратегии могут быть реализованы с помощью программирования на Pascal, с учетом возможностей оптимизации для ускорения расчетов.

Создано по материалам из источника по ссылке.

Задача состоит в разработке стратегии для игры с 100 участниками, где цель - максимизировать выигрыш, выбывая противников в k раундах с учетом изменяющегося размера награды.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::