Деньги. Много денег
2009-08-12 22:07![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
fregimusЗадача простая, даже, пожалуй, детская: fregima привела более изящное доказательство решения, чем я.
Выложен ряд из N монет орлом вверх. На первом шаге переворачивают каждую монету, начиная с первой. На втором — каждую вторую, начиная со второй, на третьем — каждую третью, начиная с третьей, и так далее. На N-ом шаге переворачивают последнюю монету.
Требуется ответить, сколько монет будет лежать вверх решкой после того, как будет перевернута последняя монета. Решение должно быть в O(1), то есть количество вычислений не должно зависеть от числа монет N.
Комментарии не скрываю, так что в них вы можете неожиданно обнаружить ответ, поэтому рекомендую подумать, не заглядывая. Обсуждение, разумеется, всяко приветствуется.
Выложен ряд из N монет орлом вверх. На первом шаге переворачивают каждую монету, начиная с первой. На втором — каждую вторую, начиная со второй, на третьем — каждую третью, начиная с третьей, и так далее. На N-ом шаге переворачивают последнюю монету.
Требуется ответить, сколько монет будет лежать вверх решкой после того, как будет перевернута последняя монета. Решение должно быть в O(1), то есть количество вычислений не должно зависеть от числа монет N.
Комментарии не скрываю, так что в них вы можете неожиданно обнаружить ответ, поэтому рекомендую подумать, не заглядывая. Обсуждение, разумеется, всяко приветствуется.
Tags:
