마지막 인터뷰에서 얻은 질문 :
다음
f과 같은 기능을 설계하십시오 .f(f(n)) == -n
n32 비트 부호있는 정수 는 어디에 있습니까 ? 복소수 산술을 사용할 수 없습니다.전체 범위의 숫자에 대해 이러한 기능을 설계 할 수없는 경우 가능한 가장 큰 범위에 맞게 설계하십시오.
어떤 아이디어?
답변
어때요?
f (n) = 부호 (n)-(-1) n * n
파이썬에서 :
def f(n):
if n == 0: return 0
if n >= 0:
if n % 2 == 1:
return n + 1
else:
return -1 * (n - 1)
else:
if n % 2 == 1:
return n - 1
else:
return -1 * (n + 1)
파이썬은 정수를 임의의 길이로 자동 승격시킵니다. 다른 언어에서는 가장 큰 양의 정수가 오버플로되므로 해당 정수를 제외한 모든 정수에서 작동합니다.
그것은 실수 작동하려면 당신은 교체해야 N 에서 (-1) N 과 함께 { ceiling(n) if n>0; floor(n) if n<0 }.
C #에서 (오버플로 상황을 제외하고 두 배로 작동) :
static double F(double n)
{
if (n == 0) return 0;
if (n < 0)
return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
else
return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}답변
당신은 그들이 어떤 종류의 언어를 기대했는지 말하지 않았다 … 정적 솔루션 (Haskell)이있다. 기본적으로 가장 중요한 2 비트를 망칩니다.
f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
| otherwise = complementBit x 30동적 언어 (Python)에서는 훨씬 쉽습니다. 인수가 숫자 X인지 확인하고 -X를 반환하는 람다를 반환하십시오.
def f(x):
if isinstance(x,int):
return (lambda: -x)
else:
return x()답변
추가 정보를 사용하지 않는 경우 (32 비트 int 제외) 모든 숫자에 대해 그러한 함수가 존재하지 않는 이유에 대한 증거는 다음과 같습니다.
f (0) = 0이어야합니다. (증거 : f (0) = x라고 가정 한 다음 f (x) = f (f (0)) = -0 = 0이라고 가정하십시오. )) = f (0) = x, 이는 x = 0을 의미합니다.)
또한 임의의 x및 y에 대해 가정 f(x) = y합니다. 우리는 f(y) = -x그때 원합니다 . 그리고 f(f(y)) = -y => f(-x) = -y. 요약하면 : 만약 f(x) = y, 다음 f(-x) = -y,와 f(y) = -x,와 f(-y) = x.
따라서 0을 제외한 모든 정수를 4 개의 세트로 나눌 필요가 있지만 홀수의 정수가 있습니다. 뿐만 아니라 양의 상대가없는 정수를 제거해도 여전히 2 (mod4) 개의 숫자가 있습니다.
남아있는 최대 값 2 개를 제거하면 (abs 값으로) 함수를 얻을 수 있습니다.
int sign(int n)
{
if(n>0)
return 1;
else
return -1;
}
int f(int n)
{
if(n==0) return 0;
switch(abs(n)%2)
{
case 1:
return sign(n)*(abs(n)+1);
case 0:
return -sign(n)*(abs(n)-1);
}
} 물론 다른 옵션은 0을 준수하지 않고 보너스로 제거한 2 개의 숫자를 얻는 것입니다. (그러나 그것은 바보 같은 경우입니다.)
답변
C ++의 과부하로 인해 :
double f(int var)
{
return double(var);
}
int f(double var)
{
return -int(var);
}
int main(){
int n(42);
std::cout<<f(f(n));
}답변
또는 전처리기를 남용 할 수 있습니다.
#define f(n) (f##n)
#define ff(n) -n
int main()
{
int n = -42;
cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}답변
이것은 모든 음수에 해당됩니다.
f (n) = abs (n)
2의 보수 정수에 대한 양수보다 하나 이상의 음수가 있기 때문에 와 동일한 해보다 f(n) = abs(n)하나 이상의 경우에 유효합니다 . 하나 하나 당신이 … : Df(n) = n > 0 ? -n : nf(n) = -abs(n)
최신 정보
아니요, 방금 litb의 의견으로 인식 한대로 더 이상 유효하지 않습니다 abs(Int.Min)…
나는 mod 2 정보 사용에 대해서도 생각했지만 초기에는 작동하지 않는다고 결론지었습니다. 올바르게 수행 Int.Min하면 오버플로되기 때문에 모든 숫자에 대해 작동합니다 .
최신 정보
나는 잠시 동안 그것을 가지고 놀면서 멋진 비트 조작 트릭을 찾았지만 멋진 2 라이너를 찾을 수 없지만 mod 2 솔루션은 1에 맞습니다.
f (n) = 2n (abs (n) % 2)-n + sgn (n)
C #에서는 다음과 같습니다.
public static Int32 f(Int32 n)
{
return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}
이 모든 값에 대한 작업을하려면, 당신은 교체해야 Math.Abs()와 (n > 0) ? +n : -n와의 계산에 포함 unchecked블록. 그런 다음 Int.Min확인되지 않은 부정과 마찬가지로 자체 매핑됩니다.
최신 정보
다른 답변에서 영감을 얻어 함수가 작동하는 방식과 그러한 함수를 구성하는 방법에 대해 설명하겠습니다.
처음부터 시작할 수 있습니다. 함수 f는 주어진 값에 반복적으로 적용되어 n일련의 값을 산출합니다.
n => f (n) => f (f (n)) => f (f (f (n))) => f (f (f (f (n)))) => ...
의문 f(f(n)) = -n을 f무효화하는 두 가지 연속적인 적용이다 . f총 4 건의 2 건의 추가 적용은 논증을 다시 무효화 n합니다.
n => f (n) => -n => f (f (f (n))) => n => f (n) => ...
이제 길이 4의 명백한주기가 있습니다. x = f(n)획득 된 방정식이 f(f(f(n))) = f(f(x)) = -x보유 하고 있음을 대체 하고 주목 하면 다음과 같은 결과가 나온다.
n => x => -n => -x => n => ...
따라서 우리는 두 개의 숫자를 가진 길이가 4이고 두 개의 숫자는 부정됩니다. 주기를 직사각형으로 가정하면 무시 된 값이 반대편 모서리에 있습니다.
이러한주기를 구성하는 많은 솔루션 중 하나는 n부터 시작하는 다음과 같습니다.
n => 부정하고 빼기 -n-1 =-(n + 1) => 하나 추가 -n => 부정하고 하나 추가 n + 1 => 하나 빼기 엔
구체적인 예는 다음과 같습니다 +1 => -2 => -1 => +2 => +1. 우리는 거의 끝났습니다. 생성 된 사이클에 홀수 양수가 포함되어 있고 짝수의 후속 숫자도 무시하고 정수를 여러 사이클 ( 2^324의 배수) 로 쉽게 분할 할 수 있으며 조건을 만족시키는 함수를 찾았습니다.
그러나 우리는 0에 문제가 있습니다. 0 => x => 00은 자체적으로 부정되므로 주기가 포함되어야합니다 . 그리고주기 상태는 이미 0 => x다음과 같습니다 0 => x => 0 => x. 이것은 단지 길이가 2의주기 일 뿐이며, x두 번의 애플리케이션이 아닌 자체로 바뀝니다 -x. 운좋게도 문제를 해결하는 한 가지 사례가 있습니다. 경우 X등호 제로 우리는 제로를 포함하는 길이 하나의 사이클을 얻고 제로의 고정 점이라고 우리는 그 문제의 결론을 해결 f.
끝난? 거의. 우리는 2^32숫자가 있고, 0은 2^32 - 1숫자를 남기는 고정 소수점 이며, 그 숫자를 4 개의 숫자로 나누어야합니다. 2^32 - 14의 배수가 아닌 나쁜 것 -길이 4의 어떤주기에도 3 개의 숫자가 남아 있습니다.
나는 이르기까지 3 비트 부호 itegers의 작은 세트를 사용하여 솔루션의 나머지 부분 설명 할 것 -4을을 +3. 우리는 0으로 끝납니다. 하나의 완전한주기가 +1 => -2 => -1 => +2 => +1있습니다. 이제부터 시작하는 사이클을 구성하겠습니다 +3.
+3 => -4 => -3 => +4 => +3
발생하는 문제는 +43 비트 정수로 표현할 수 없다는 것입니다. 우리는 얻을 것이다 +4부정에 의해 -3에 +3여전히 유효한 3 비트 정수 무엇인지 – -하지만 하나를 추가 +3(이진은 011) 산출 100진. 부호없는 정수로 해석되지만 부호있는 정수 +4로 해석해야합니다 -4. 그래서, 실제로 -4이 실시 예 또는 Int.MinValue일반적인 경우는 정수 산술 부정의 제 2 고정 점 인 – 0 및 Int.MinValuethemselve 매핑된다. 따라서주기는 실제로 다음과 같습니다.
+3 => -4 => -3 => -4 => -3
길이가 2의주기이고 +3를 통해 추가 로주기에 들어갑니다 -4. 결과적 -4으로 두 기능 응용 프로그램 후에 +3올바르게 맵핑되고 -3두 기능 응용 프로그램 후에 올바르게 맵핑 되지만 -3두 기능 응용 프로그램 후에는 자체적으로 잘못 맵핑됩니다.
그래서 우리는 하나를 제외한 모든 정수에서 작동하는 함수를 만들었습니다. 더 잘할 수 있을까요? 아니야 우리는 할 수 없어. 왜? 우리는 길이가 4 인 사이클을 구성해야하며 전체 정수 범위를 최대 4 개의 값까지 포함 할 수 있습니다. 나머지 값은 두 개의 고정 된 점 0이며 Int.MinValue두 개의 임의의 정수 x와 두 개의 임의의 정수 -x로 맵핑되어야하며 두 개의 함수 애플리케이션으로 서로 맵핑되어야합니다.
지도하기 x로 -x하고 그 그들이 네 사이클을 형성해야하며, 그들이 그주기의 반대 모서리에 위치해야합니다 마찬가지입니다. 결과에서 0와 Int.MinValue도 반대 모서리에 있어야합니다. 이것은 올바르게 매핑 x되고 -x두 개의 고정 점 0과 Int.MinValue두 개의 함수 응용 프로그램을 바꾼 다음 두 개의 실패한 입력으로 남겨 둡니다. 따라서 모든 값에 대해 작동하는 함수를 구성 할 수는 없지만 하나를 제외한 모든 값에 대해 작동하는 함수가 있으며 이것이 달성 할 수있는 최선입니다.
답변
복소수를 사용하면 숫자 무효화 작업을 두 단계로 효과적으로 나눌 수 있습니다.
- n에 i를 곱하면 n * i를 얻게되는데, n은 시계 반대 방향으로 90도 회전합니다.
- 다시 i를 곱하면 -n이됩니다
가장 좋은 점은 특별한 처리 코드가 필요 없다는 것입니다. i를 곱하면 작업이 수행됩니다.
그러나 복잡한 숫자는 사용할 수 없습니다. 따라서 데이터 범위의 일부를 사용하여 자신 만의 가상 축을 만들어야합니다. 초기 값만큼의 가상 (중간) 값이 정확히 필요하므로 데이터 범위의 절반 만 남습니다.
서명 된 8 비트 데이터를 가정하여 다음 그림에서 이것을 시각화하려고했습니다. 이것을 32 비트 정수로 확장해야합니다. 초기 n에 허용되는 범위는 -64 ~ +63입니다. 양의 n에 대해 함수가 수행하는 작업은 다음과 같습니다.
- n이 0..63 (초기 범위) 인 경우 함수 호출은 64를 추가하여 n을 64..127 (중간 범위) 범위에 매핑합니다.
- n이 64..127 (중간 범위)에 있으면 함수는 64에서 n을 빼서 n을 0 ..- 63 범위에 매핑합니다.
음수 n의 경우이 함수는 중간 범위 -65 ..- 128을 사용합니다.
