![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
корень из отрицания
Feb. 9th, 2008 07:15 amВспомнил тут задачу, запощенную недавно ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
avva: на целых 32-битных числах найти функцию чтобы f(f(x)) == -x.
Ну если ты типа изучал что-то вроде алгебры и в курсе что за орбиты такие бывают, то понятно, что на ZBase где Base=2N это решение возможно только при N=2, а на Z оно очевидно.
Интересно другое - только двое признали невозможность решения для конечного числа бит; остальные не брали в голову такие мелочи или признавали "исключительные случаи".
Такие дела; и что делать? Ведь приходится каждый день с таким оппортунизмом сталкиваться; и ни хрена не объяснишь и не докажешь. Или надо таки пробовать?
Ну вот к примеру эта задача.
0 и число, у которого в старшем бите единица а остальные нули (назовём его M), отрицанием переходят сами в себя. На остальных 2^n-2 числах отрицание переводит число в другое число, не равное исходному.
Теперь, если мы изобретём такую функцию f, то посмотрим на орбиты: множества вида (x, f(x), и т.д.). Весь набор чисел разбивается на непересекающиеся орбиты. У нуля и у того длина орбиты максимум 2; у остальных длина орбиты 4. Может ли f(0) быть чем-то отличным от 0 и М? Нет, потому что тогда оно попадёт в чужую орбиту. Поэтому у нас два варианта для f(0): или M, или 0. Собственно, пофиг.
Остальные же числа состоят из непересекающихся орбит длины 4. А всего этих остальных чисел 2^n-2. Что делится нацело на 4 только при n=0.
Ну это так, пример был, иллюстрация к общей проблеме компенсации недостатка образования умением быстро писать код.
avva: на целых 32-битных числах найти функцию чтобы f(f(x)) == -x.Ну если ты типа изучал что-то вроде алгебры и в курсе что за орбиты такие бывают, то понятно, что на ZBase где Base=2N это решение возможно только при N=2, а на Z оно очевидно.
Интересно другое - только двое признали невозможность решения для конечного числа бит; остальные не брали в голову такие мелочи или признавали "исключительные случаи".
Такие дела; и что делать? Ведь приходится каждый день с таким оппортунизмом сталкиваться; и ни хрена не объяснишь и не докажешь. Или надо таки пробовать?
Ну вот к примеру эта задача.
0 и число, у которого в старшем бите единица а остальные нули (назовём его M), отрицанием переходят сами в себя. На остальных 2^n-2 числах отрицание переводит число в другое число, не равное исходному.
Теперь, если мы изобретём такую функцию f, то посмотрим на орбиты: множества вида (x, f(x), и т.д.). Весь набор чисел разбивается на непересекающиеся орбиты. У нуля и у того длина орбиты максимум 2; у остальных длина орбиты 4. Может ли f(0) быть чем-то отличным от 0 и М? Нет, потому что тогда оно попадёт в чужую орбиту. Поэтому у нас два варианта для f(0): или M, или 0. Собственно, пофиг.
Остальные же числа состоят из непересекающихся орбит длины 4. А всего этих остальных чисел 2^n-2. Что делится нацело на 4 только при n=0.
Ну это так, пример был, иллюстрация к общей проблеме компенсации недостатка образования умением быстро писать код.
