Pytanie, które otrzymałem podczas mojej ostatniej rozmowy:
Zaprojektuj funkcję
f
taką, aby:f(f(n)) == -n
Gdzie
n
jest 32-bitowa liczba całkowita ze znakiem ; nie można używać arytmetyki liczb zespolonych.Jeśli nie możesz zaprojektować takiej funkcji dla całego zakresu liczb, zaprojektuj ją dla największego możliwego zakresu.
Jakieś pomysły?
Odpowiedzi:
Co powiesz na:
W Pythonie:
Python automatycznie promuje liczby całkowite do dowolnych długości. W innych językach przepełni się największa dodatnia liczba całkowita, więc będzie działać dla wszystkich liczb całkowitych oprócz tej.
Aby działało dla liczb rzeczywistych, musisz zastąpić nw (-1) n przez
{ ceiling(n) if n>0; floor(n) if n<0 }
.W języku C # (działa dla każdego podwójnego, z wyjątkiem sytuacji przepełnienia):
źródło
Nie powiedziałeś, jakiego języka się spodziewają ... Oto rozwiązanie statyczne (Haskell). Zasadniczo zadziera z 2 najbardziej znaczącymi bitami:
Jest to o wiele łatwiejsze w dynamicznym języku (Python). Po prostu sprawdź, czy argument jest liczbą X i zwróć lambda, która zwraca -X:
źródło
class C a b | a->b where { f :: a->b }
;instance C Int (()->Int) where { f=const.negate }
;instance C (()->Int) Int where { f=($()) }
.Oto dowód, dlaczego taka funkcja nie może istnieć dla wszystkich liczb, jeśli nie używa dodatkowych informacji (z wyjątkiem 32 bitów int):
Musimy mieć f (0) = 0. (Dowód: Załóżmy, że f (0) = x. Następnie f (x) = f (f (0)) = -0 = 0. Teraz, -x = f (f (x )) = f (0) = x, co oznacza, że x = 0.)
Ponadto, dla każdego
x
iy
, przypuśćmyf(x) = y
. Chcemyf(y) = -x
więc. If(f(y)) = -y => f(-x) = -y
… Podsumowując: jeślif(x) = y
, tof(-x) = -y
, if(y) = -x
, if(-y) = x
.Musimy więc podzielić wszystkie liczby całkowite oprócz 0 na zestawy 4, ale mamy nieparzystą liczbę takich liczb całkowitych; nie tylko to, że jeśli usuniemy liczbę całkowitą, która nie ma dodatniego odpowiednika, nadal będziemy mieć 2 (mod4) liczby.
Jeśli usuniemy 2 maksymalne liczby, które pozostały (według wartości abs), możemy uzyskać funkcję:
Oczywiście inną opcją jest nieprzestrzeganie 0 i otrzymanie 2 liczb, które usunęliśmy jako bonus. (Ale to tylko głupie, jeśli.)
źródło
n = -2147483648
(minimalna wartość); nie możeszabs(n)
w takim przypadku, a wynik będzie niezdefiniowany (lub wyjątek).Dzięki przeciążeniu w C ++:
źródło
Lub możesz nadużyć preprocesora:
źródło
Dotyczy to wszystkich liczb ujemnych.
Ponieważ istnieje jeszcze jedna liczba ujemna niż liczba dodatnia dla dwóch liczb całkowitych uzupełniających,
f(n) = abs(n)
jest ważna dla jednego przypadku więcej niżf(n) = n > 0 ? -n : n
rozwiązanie, które jest takie samo jakf(n) = -abs(n)
. Mam cię po jednym ...: DAKTUALIZACJA
Nie, nie dotyczy to więcej niż jednego przypadku, jak właśnie rozpoznałem w komentarzu litba ...
abs(Int.Min)
po prostu się przepełni ...Myślałem też o użyciu informacji o modzie 2, ale doszedłem do wniosku, że to nie działa ... na początku. Jeśli zrobisz to poprawnie, zadziała dla wszystkich liczb oprócz
Int.Min
tego, że się przepełni.AKTUALIZACJA
Bawiłem się nim przez pewien czas, szukając ładnej sztuczki manipulacji, ale nie mogłem znaleźć ładnego jednoliniowego, podczas gdy rozwiązanie mod 2 pasuje do jednego.
W języku C # wygląda to następująco:
Aby to działa dla wszystkich wartości, trzeba wymienić
Math.Abs()
z(n > 0) ? +n : -n
obejmują obliczenia wunchecked
bloku. Następnie zostajesz nawetInt.Min
zmapowany do siebie, tak jak robi to niesprawdzona negacja.AKTUALIZACJA
Zainspirowany inną odpowiedzią wyjaśnię, jak działa ta funkcja i jak ją zbudować.
Zacznijmy od samego początku. Funkcja
f
jest wielokrotnie stosowana do danej wartościn
dając ciąg wartości.Pytanie wymaga
f(f(n)) = -n
, aby były to dwa kolejne zastosowaniaf
negacji argumentu. Dwa kolejne zastosowaniaf
- w sumie cztery - negują ponownie ten argumentn
ponownie.Teraz jest oczywisty cykl długości czterech. Podstawiając
x = f(n)
i zauważając, że otrzymane równanief(f(f(n))) = f(f(x)) = -x
zachowuje, otrzymujemy następujące wyniki.Otrzymujemy więc cykl długości cztery z dwiema liczbami i dwie liczby zanegowane. Jeśli wyobrażasz sobie cykl jako prostokąt, zanegowane wartości znajdują się w przeciwległych rogach.
Jednym z wielu rozwiązań pozwalających skonstruować taki cykl jest początek od n.
Konkretnym przykładem takiego cyklu jest
+1 => -2 => -1 => +2 => +1
. Prawie skończyliśmy. Zwracając uwagę, że skonstruowany cykl zawiera nieparzystą liczbę dodatnią, jego parzysty następca i obie liczby negują, możemy z łatwością podzielić liczby całkowite na wiele takich cykli (2^32
jest wielokrotnością czterech) i znaleźliśmy funkcję, która spełnia warunki.Ale mamy problem ze zerem. Cykl musi zawierać,
0 => x => 0
ponieważ zero jest negowane samo w sobie. A ponieważ cykl stwierdza,0 => x
że już następuje0 => x => 0 => x
. Jest to tylko cykl długości dwóch ix
zamienia się w siebie po dwóch aplikacjach, a nie w-x
. Na szczęście jest jeden przypadek, który rozwiązuje problem. JeśliX
jest równy zeru, otrzymujemy cykl długości zawierający tylko zero i rozwiązaliśmy ten problem, stwierdzając, że zero jest stałym punktemf
.Gotowy? Prawie. Mamy
2^32
liczby, zero to stały punkt pozostawiający2^32 - 1
liczby i musimy podzielić tę liczbę na cykle czterech liczb. Złe, że2^32 - 1
nie jest wielokrotnością czterech - pozostaną trzy liczby nie w żadnym cyklu długości czterech.Wyjaśnię pozostałą część rozwiązania przy użyciu mniejszego zestawu 3-bitowych liczb całkowitych ze znakiem od
-4
do+3
. Skończyliśmy z zerem. Mamy jeden pełny cykl+1 => -2 => -1 => +2 => +1
. Teraz skonstruujmy cykl zaczynając od+3
.Powstaje problem polegający na tym, że
+4
nie jest reprezentowana jako 3-bitowa liczba całkowita. Chcielibyśmy uzyskać+4
poprzez zanegowanie-3
się+3
- co jest jeszcze ważne całkowitą 3 bit - ale potem dodając jeden do+3
(binarnie011
) daje100
binarny. Jest interpretowany jako liczba całkowita bez znaku,+4
ale musimy interpretować go jako liczbę całkowitą ze znakiem-4
. Tak więc w rzeczywistości-4
w tym przykładzie lubInt.MinValue
w ogólnym przypadku jest drugim stałym punktem całkowitej negacji arytmetycznej -0
iInt.MinValue
są one odwzorowane na nich samych. Tak więc cykl jest następujący.Jest to cykl długości dwóch i dodatkowo
+3
wchodzi w cykl poprzez-4
. W konsekwencji-4
jest poprawnie odwzorowany na siebie po dwóch aplikacjach funkcyjnych,+3
jest poprawnie odwzorowany na-3
dwóch aplikacjach funkcyjnych, ale-3
błędnie jest odwzorowany na sobie po dwóch aplikacjach funkcyjnych.Stworzyliśmy więc funkcję, która działa dla wszystkich liczb całkowitych oprócz jednej. Czy możemy zrobić lepiej? Nie, nie możemy. Dlaczego? Musimy skonstruować cykle o długości czterech i jesteśmy w stanie objąć cały zakres liczb całkowitych do czterech wartości. Pozostałe wartości są dwa punkty stałe
0
iInt.MinValue
które muszą być przypisane do siebie i dwóch dowolnych liczb całkowitychx
i-x
które muszą być przypisane do siebie przez dwa wnioski funkcyjnych.Mapować
x
do-x
i odwrotnie muszą tworzyć cztery cyklu i muszą być umieszczone na przeciwległych rogach tego cyklu. W konsekwencji0
iInt.MinValue
muszą znajdować się również w przeciwległych rogach. To będzie poprawnie mapx
i-x
jednak zamienić dwa punkty stałe0
iInt.MinValue
po dwóch zastosowaniach funkcyjnych i zostawić nas z dwoma wejściami upadających. Dlatego nie jest możliwe zbudowanie funkcji, która działa dla wszystkich wartości, ale mamy taką, która działa dla wszystkich wartości oprócz jednej i jest to najlepsze, co możemy osiągnąć.źródło
Używając liczb zespolonych, możesz skutecznie podzielić zadanie negowania liczby na dwa etapy:
Wspaniałą rzeczą jest to, że nie potrzebujesz specjalnego kodu obsługi. Po prostu pomnożenie przez i wykonuje pracę.
Ale nie wolno ci używać liczb zespolonych. Musisz więc jakoś stworzyć własną wyobrażoną oś, wykorzystując część swojego zakresu danych. Ponieważ potrzebujesz dokładnie tyle wyimaginowanych (pośrednich) wartości, co wartości początkowe, pozostaje Ci tylko połowa zakresu danych.
Próbowałem to wyobrazić na poniższym rysunku, zakładając podpisane dane 8-bitowe. Trzeba to skalować dla 32-bitowych liczb całkowitych. Dopuszczalny zakres dla początkowego n wynosi od -64 do +63. Oto, co funkcja robi dla dodatniego n:
Dla ujemnego n funkcja wykorzystuje zakres pośredni -65 ..- 128.
źródło
float
porównaniu doint
). „4-elementowy pierścień”, który opisuje wiele odpowiedzi, wymaga 4 stanów, które można przedstawić jako 2 wymiary, każdy z 2 stanami. Problem z tą odpowiedzią jest to, że wymaga dodatkowej przestrzeni procesowej (tylko „działa” na -64..63 jeszcze potrzeby -128..127 kosmiczne) i nie ma jednoznacznie stwierdzić, napisany formuły!Działa z wyjątkiem int.MaxValue i int.MinValue
źródło
0
do0
i-2147483648
do-2147483648
ponieważ te dwie liczby stałych punktów dla operatora negacjix => -x
. W przypadku pozostałych liczb postępuj zgodnie ze strzałkami na obrazku powyżej. Jak wynika z odpowiedzi i komentarzy SurDin, w tym przypadku będą dwie liczby2147483647
i-2147483647
nie pozostanie żadna inna para na zamianę.Pytanie nie mówi nic o tym, jaki
f
musi być typ wejścia i zwracana wartość funkcji (przynajmniej nie tak, jak to przedstawiłeś) ...... tylko wtedy, gdy n jest 32-bitową liczbą całkowitą
f(f(n)) = -n
A co powiesz na coś takiego
Jeśli n jest 32-bitową liczbą całkowitą, wówczas instrukcja
f(f(n)) == -n
będzie prawdziwa.Oczywiście to podejście można rozszerzyć na jeszcze szerszy zakres liczb ...
źródło
dla javascript (lub innych języków dynamicznie wpisywanych) możesz mieć funkcję akceptującą int lub obiekt i zwracającą drugą. to znaczy
dający
alternatywnie możesz użyć przeciążenia w silnie typowanym języku, chociaż może to złamać zasady tj
źródło
W zależności od platformy niektóre języki umożliwiają zachowanie stanu funkcji. VB.Net, na przykład:
IIRC, C ++ również na to pozwoliły. Podejrzewam jednak, że szukają innego rozwiązania.
Innym pomysłem jest to, że skoro nie zdefiniowali wyniku pierwszego wywołania funkcji, można użyć nieparzystości / parzystości do kontrolowania, czy odwrócić znak:
Dodaj jeden do wielkości wszystkich liczb parzystych, odejmij jeden od wielkości wszystkich liczb nieparzystych. Wynik dwóch wezwań ma taką samą wielkość, ale jedno wywołanie, w którym nawet zamieniamy znak. W niektórych przypadkach to nie zadziała (-1, maks. Lub min. Int), ale działa o wiele lepiej niż cokolwiek innego sugerowanego do tej pory.
źródło
Wykorzystywanie wyjątków JavaScript.
źródło
Dla wszystkich wartości 32-bitowych (z zastrzeżeniem, że -0 wynosi -2147483648)
Zasadniczo musisz sparować każdą pętlę -x => x => -x z pętlą ay => -y => y. Więc sparowałem przeciwne strony
split
.np. dla 4-bitowych liczb całkowitych:
źródło
Wersja C ++, prawdopodobnie nieco zginająca reguły, ale działa dla wszystkich typów liczbowych (liczba zmiennoprzecinkowa, liczba całkowita, liczba podwójna), a nawet typów klas, które przeciążają jednoargumentowy minus:
źródło
x86 asm (styl AT&T):
Kod sprawdzony, wszystkie możliwe 32-bitowe liczby całkowite przeszły, błąd -2147483647 (niedopełnienie).
źródło
Używa globali ... ale tak?
źródło
To rozwiązanie Perla działa na liczbach całkowitych, zmiennoprzecinkowych i ciągach .
Wypróbuj niektóre dane testowe.
Wynik:
źródło
n
byłbym ciągiem, który mógłbym zrobić, 548 staje się „First_Time_548”, a następnie następnym razem przechodzi przez funkcję ... jeśli (przedrostek == First_Time_ ”) zamień„ First_Time_ ”na„ - ”Nikt nigdy nie powiedział, że f (x) musi być tego samego typu.
źródło
Właściwie nie próbuję rozwiązać samego problemu, ale mam kilka komentarzy, ponieważ pytanie mówi, że ten problem został postawiony w ramach wywiadu (pracy?):
int.MinValue
doint.MaxValue
, i dla każdegon
w tym zakresie wywołanief(f(n))
i sprawdzenie wyniku to-n
), mówiąc, że użyję Test Driven Development, aby dostać się do takiej funkcji.Och, ta odpowiedź zakłada, że wywiad dotyczył stanowiska związanego z programowaniem w języku C #. Byłoby oczywiście głupią odpowiedzią, gdyby wywiad dotyczył stanowiska matematycznego. ;-)
źródło
Chciałbym zmienić 2 najbardziej znaczące bity.
Jak widać, to tylko dodatek, pomijając przeniesiony kawałek.
Jak dotarłem do odpowiedzi? Moją pierwszą myślą była potrzeba symetrii. 4 obroty, by wrócić tam, gdzie zacząłem. Na początku myślałem, że to 2-bitowy kod Graya. Pomyślałem wtedy, że wystarczy standardowy plik binarny.
źródło
Oto rozwiązanie inspirowane wymogiem lub twierdzeniem, że nie można użyć liczb zespolonych do rozwiązania tego problemu.
Pomnożenie przez pierwiastek kwadratowy z -1 jest pomysłem, który wydaje się zawodzić, ponieważ -1 nie ma pierwiastka kwadratowego nad liczbami całkowitymi. Ale zabawa z programem takim jak matematyka daje na przykład równanie
i jest to prawie tak dobre, jak posiadanie pierwiastka kwadratowego z -1. Wynikiem funkcji musi być liczba całkowita ze znakiem. Dlatego zamierzam użyć zmodyfikowanych modów operacji modulo (x, n), które zwracają liczbę całkowitą y przystającą do x modulo n, która jest najbliższa 0. Tylko kilka języków programowania ma operację modulo, ale można ją łatwo zdefiniować . Np. W python jest to:
Korzystając z powyższego równania, problem można teraz rozwiązać jako
Spełnia to
f(f(x)) = -x
wszystkie liczby całkowite w zakresie . Wyniki są również w tym zakresie, ale oczywiście obliczenia wymagałyby 64-bitowych liczb całkowitych.[-2
31
-2, 2
31
-2]
f(x)
źródło
C # dla zakresu 2 ^ 32-1 liczb, wszystkie liczby int32 oprócz (Int32.MinValue)
drukuje:
źródło
Zasadniczo funkcja musi podzielić dostępny zakres na cykle wielkości 4, przy czym -n na przeciwległym końcu cyklu n. Jednak 0 musi być częścią cyklu o rozmiarze 1, ponieważ w przeciwnym razie
0->x->0->x != -x
. Ponieważ 0 jest sam, muszą być 3 inne wartości w naszym zakresie (których rozmiar jest wielokrotnością 4), które nie są w prawidłowym cyklu z 4 elementami.Wybrałem te dodatkowe wartości dziwne być
MIN_INT
,MAX_INT
iMIN_INT+1
. Co więcej,MIN_INT+1
odwzorujeMAX_INT
poprawnie, ale utknie tam i nie odwróci mapy. Myślę, że jest to najlepszy kompromis, ponieważ ma tę fajną właściwość, że ekstremalne wartości nie działają poprawnie. Oznacza to również, że będzie działać dla wszystkich BigInts.źródło
Nikt nie powiedział, że to musi być bezpaństwowiec.
Oszukiwanie, ale nie tak wiele przykładów. Jeszcze większym złem byłoby zerknięcie na stos, aby sprawdzić, czy adres dzwoniącego to & f, ale będzie on bardziej przenośny (chociaż nie jest bezpieczny dla wątków ... wersja dla wątków używa TLS). Jeszcze więcej zła:
Oczywiście żadne z tych nie działa zbyt dobrze w przypadku MIN_INT32, ale niewiele można na to poradzić, chyba że pozwolimy ci zwrócić szerszy typ.
źródło
Mogę sobie wyobrazić, że użycie 31-go bitu jako fikcyjnego ( i ) bitu byłoby podejściem, które obsługiwałoby połowę całkowitego zakresu.
źródło
działa dla n = [0 .. 2 ^ 31-1]
źródło
Problem mówi „32-bitowe liczby całkowite ze znakiem”, ale nie określa, czy są one dopełniane do dwóch, czy do jednego .
Jeśli użyjesz jedynego uzupełnienia, wówczas wszystkie wartości 2 ^ 32 występują w cyklach o długości czwartej - nie potrzebujesz specjalnego przypadku dla zera, a także nie potrzebujesz warunków warunkowych.
W C:
Działa to przez
Po dwóch przejściach mamy bitową odwrotność oryginalnej wartości. Które w reprezentacji jednego dopełniacza jest równoważne negacji.
Przykłady:
źródło
:RE
źródło
źródło
Chciałbym podzielić się moim poglądem na ten interesujący problem jako matematyk. Myślę, że mam najbardziej wydajne rozwiązanie.
Jeśli dobrze pamiętam, negujesz 32-bitową liczbę całkowitą ze znakiem, po prostu odwracając pierwszy bit. Na przykład, jeśli n = 1001 1101 1110 1011 1110 0000 1110 1010, to -n = 0001 1101 1110 1011 1110 0000 1110 1010.
Jak więc zdefiniować funkcję f, która pobiera 32-bitową liczbę całkowitą ze znakiem i zwraca kolejną 32-bitową liczbę całkowitą ze znakiem, że dwukrotne pobranie f jest tym samym, co odwrócenie pierwszego bitu?
Pozwól, że sformułuję to pytanie, nie wspominając o pojęciach arytmetycznych, takich jak liczby całkowite.
Jak zdefiniujemy funkcję f, która pobiera sekwencję zer i jedynek o długości 32 i zwraca sekwencję zer i jedynek o tej samej długości, z właściwością, że pobranie f dwa razy jest takie samo jak przerzucenie pierwszego bitu?
Uwaga: Jeśli możesz odpowiedzieć na powyższe pytanie w przypadku 32 bitów, możesz także odpowiedzieć w przypadku 64 bitów, 100 bitów itp. Po prostu zastosuj f do pierwszego 32 bitów.
Teraz, jeśli możesz odpowiedzieć na pytanie w przypadku 2 bitów, Voila!
I tak, okazuje się, że wystarczy zmienić pierwsze 2 bity.
Oto pseudo-kod
Uwaga: Krok 2 i krok 3 razem można zapisać na lato jako (a, b) -> (-b, a). Wygląda znajomo? To powinno przypominać o obróceniu płaszczyzny o 90 stopni i pomnożeniu przez pierwiastek kwadratowy z -1.
Gdybym sam przedstawił pseudo-kod bez długiego preludium, wyglądałoby to jak królik z kapelusza, chciałem wyjaśnić, skąd mam rozwiązanie.
źródło