Анализ алгоритма удаления мрамора из банки - PullRequest
Новая
       62

Анализ алгоритма удаления мрамора из банки

1 голос
/ 05 февраля 2020

Ниже приведено упражнение из моего курса «Алгоритмы и структуры данных», целью которого является научить анализу алгоритмов с использованием l oop -инвариантов.

Настройка следующая; У нас есть банка с n мрамором. Мрамор или красный или синий. У нас также есть бесконечная куча красных мраморов. Мы стремимся опустошить банку с помощью этого алгоритма

Алгоритм выглядит следующим образом: 

input: Jar with *n* marbles each of color RED or BLUE
i <- n
while i > 1 do
  Pick two arbitrary marbles m1, m2 from the jar.
  if Color(m1) == Color(m2) then
    Throw the two marbles away
    Place a RED marble in the jar
  end
  else
    Throw away the RED marble
    Put the BLUE marble back in the jar
  end
  i = i - 1
end

1) Утверждают, что в конце алгоритма у нас остался 1 шарик в банка Моя идея состоит в том, чтобы сказать, что у нас есть al oop -инвариант, следующий:

В начале итерации, пока l oop, осталось n- (ni) шариков.

Затем покажите, что инвариант верен во время инициализации, обслуживания и завершения, однако я не уверен, как мне следует подходить к этому, может кто-нибудь помочь здесь?

Например, при инициализации ясно, что l oop -инвариант является тем, что у нас в банке n мрамор и, таким образом, n-0 = n из инвариант, но как мне подойти к остальным?

1 Ответ

1 голос
/ 05 февраля 2020

Поскольку это домашнее задание, я не хочу делать всю проблему за вас, но я могу помочь вам начать в правильном направлении.

Давайте начнем с одной из самых простых форм вопроса: n = 2

Теперь есть 3 варианта:

  1. 2 Красный
  2. 2 Синий
  3. 1 Красный и 1 Синий

Варианты 1 и 2:

Вытяните оба шарика, они одного цвета, поэтому выбросьте оба шарика и вытащите красный мрамор из кучи и поместите его в банку. В банке остался один мрамор, поэтому мы остановимся.

Случай 3:

Вытяните оба шарика, они не одного цвета, поэтому отбросьте красный и отложите синий в. В банке остался один мрамор, поэтому мы останавливаемся.

Теперь, когда учтено n = 2, докажите, что вы можете попасть в это состояние из 3, 4, 5 ... n мрамора. Для n = 1, очевидно, в банке будет только один мрамор, потому что вы никогда не войдете в l oop. Я не знаю, что вы хотите сделать для n = 0, это единственный случай, когда вы можете получить пустую банку.

...