그래서 저는 피보나치 수열 의 n 번째 숫자를 가능한 한 간결한 함수로 쓰려고했습니다 .
public uint fibn ( uint N )
{
return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}하지만 변경을 통해 이것을 더욱 간결하고 효율적으로 만들 수 있는지 궁금합니다.
(N == 0 || N == 1)단일 비교로. 이것을 할 수있는 멋진 비트 시프트 연산이 있습니까?
답변
이것도 작동합니다
Math.Sqrt(N) == N 0과 1의 제곱근은 각각 0과 1을 반환합니다.
답변
비트 산술을 사용하여 산술 테스트를 구현하는 방법에는 여러 가지가 있습니다. 당신의 표현 :
x == 0 || x == 1
논리적으로 다음 각 항목과 동일합니다.
(x & 1) == x(x & ~1) == 0(x | 1) == 1(~x | 1) == (uint)-1x >> 1 == 0
보너스:
x * x == x(증명에는 약간의 노력이 필요합니다)
그러나 실제로는 이러한 형식이 가장 읽기 쉽고 성능의 작은 차이는 비트 산술을 사용할 가치가 없습니다.
x == 0 || x == 1x <= 1(x부호없는 정수 이기 때문에 )x < 2(x부호없는 정수 이기 때문에 )
답변
인수가 uint( unsigned ) 이기 때문에
return (N <= 1) ? 1 : N * fibn(N-1);가독성이 떨어지지 만 (IMHO) 각 문자를 세는 경우 ( 코드 골프 또는 유사)
return N < 2 ? 1 : N * fibn(N-1);편집 : 편집 한 질문에 대해 :
return (N <= 1) ? 1 : fibn(N-1) + fibn(N-2);또는
return N < 2 ? 1 : fibn(N-1) + fibn(N-2);답변
다음과 같이 다른 모든 비트가 0인지 확인할 수도 있습니다.
return (N & ~1) == 0 ? 1 : N * fibn(N-1);Matt 덕분에 완성도를 높이 려면 더 나은 솔루션 :
return (N | 1) == 1 ? 1 : N * fibn(N-1);두 경우 모두 비트 연산자가.보다 우선 순위가 낮기 때문에 괄호를 처리해야합니다 ==.
답변
원하는 것이 함수를 더 효율적으로 만드는 것이라면 조회 테이블을 사용하십시오. 조회 테이블은 47 개 항목으로 놀라 울 정도로 작습니다. 다음 항목은 32 비트 부호없는 정수를 오버플로합니다. 물론이 함수는 작성하기가 수월합니다.
class Sequences
{
// Store the complete list of values that will fit in a 32-bit unsigned integer without overflow.
private static readonly uint[] FibonacciSequence = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073
};
public uint fibn(uint N)
{
return FibonacciSequence[N];
}
}팩토리얼에 대해서도 동일한 작업을 수행 할 수 있습니다.
답변
비트 시프트로 수행하는 방법
비트 시프트를 사용하고 코드를 다소 모호하게 (짧게) 만들고 싶다면 다음과 같이 할 수 있습니다.
public uint fibn ( uint N ) {
return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}N언어 c 의 부호없는 정수 의 경우,N>>1 경우 하위 비트를 버립니다. 그 결과가 0이 아니면 N이 1보다 크다는 것을 의미합니다.
참고 :이 알고리즘은 이미 계산 된 시퀀스의 값을 불필요하게 다시 계산하므로 매우 비효율적입니다.
더 빠른 방법
fibonaci (N) 크기의 트리를 암시 적으로 구축하는 대신 한 번의 패스를 계산합니다.
uint faster_fibn(uint N) { //requires N > 1 to work
uint a = 1, b = 1, c = 1;
while(--N != 0) {
c = b + a;
a = b;
b = c;
}
return c;
}일부 사람들이 언급했듯이 64 비트 부호없는 정수도 오버플로하는 데 오래 걸리지 않습니다. 얼마나 큰지에 따라 임의의 정밀도 정수를 사용해야합니다.
답변
음수가 될 수없는 단위를 사용하면 다음 사항을 확인할 수 있습니다. n < 2
편집하다
또는 특수한 기능의 경우 다음과 같이 작성할 수 있습니다.
public uint fibn(uint N)
return (N == 0) ? 1 : N * fibn(N-1);
}물론 추가 재귀 단계의 비용으로 동일한 결과를 얻을 수 있습니다.
