juan_gandhi: (Default)
[personal profile] juan_gandhi
Вспомнил тут задачу, запощенную недавно [livejournal.com profile] 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.

Ну это так, пример был, иллюстрация к общей проблеме компенсации недостатка образования умением быстро писать код.
This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

Profile

juan_gandhi: (Default)
Juan-Carlos Gandhi

June 2025

S M T W T F S
1 234567
891011121314
15161718192021
22232425262728
2930     

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 5th, 2025 02:56 pm
Powered by Dreamwidth Studios