Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

функция маккарти (немного математики)

Мне раньше не встречалась эта забавная функция.

Определение (рекурсивное):

  • g(x) = x-10 если x > 100
  • g(x) = g(g(x+11)) если x <= 100

g(x) называется 91-функцией Маккарти. Поведение g(x) для x>100 тривиально, как следует из первой строки определения; поведение для x<=100 на первый взгляд неочевидно.

Доказать: g(x)=91 для x<=101.

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

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments