Programing

숫자가 피보나치인지 테스트

lottogame 2020. 10. 28. 07:39
반응형

숫자가 피보나치인지 테스트


피보나치 수 목록을 만드는 방법을 알고 있지만 주어진 숫자가 피보나치 목록에 속하는지 어떻게 테스트 할 수 있는지 모르겠습니다. 염두에 두는 한 가지 방법은 fib 목록을 생성하는 것입니다. 그 숫자까지 숫자를 입력하고 그것이 배열에 속하는지 확인하십시오. 그러나 더 간단하고 빠른 또 다른 방법이 있어야합니다.

어떤 아이디어?


아주 좋은 테스트는 N은 피보나치 수의 경우에만, 점이다 5 N^2 + 4또는 5N^2 – 4정사각형 숫자입니다. 숫자가 정사각형인지 효율적으로 테스트하는 방법에 대한 아이디어는 SO 토론을 참조하십시오 .

도움이 되었기를 바랍니다


그리고 경우에만 5ω 중 하나가 양의 정수 ω는 피보나치 수를 2 + 4 5ω 2 (4)는 완벽한 정사각형 -.

자세한 내용은 The Faboulous Fibonacci Numbers 를 참조하십시오.

대체 텍스트


여러 사람이 완전 제곱 해를 지적하지만 피보나치 수를 제곱하여 종종 거대한 제품을 생성합니다.

표준 64 비트 정수에 담을 수있는 피보나치 수는 80 개 미만입니다.

테스트 할 수보다 완전히 작게 작동하는 내 솔루션 이 있습니다.
( double같은 기본 유형을 사용하여 C #으로 작성되었습니다 long. 그러나 알고리즘은 더 큰 유형에 대해 잘 작동합니다.)

static bool IsFib(long T, out long idx)
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    idx    = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == T);
}


이 답변을 작성한 지 4 년이 지난 후 한 댓글 작성자가 out.

매개 변수 # 2는 피보나치 수열의 "색인"입니다.
테스트 할 값 T이 피보나치 수이면 idx피보나치 수열에서 해당 수의 1 기반 인덱스가됩니다. (한 가지 주목할만한 예외가 있음)

피보나치 수열은 1 1 2 3 5 8 13등입니다.
3은 수열에서 네 번째 숫자입니다 : IsFib(3, out idx);will return true및 value 4.
8은 시퀀스에서 6 번째 숫자입니다. IsFib(8, out idx);will return true및 value 6.
13은 7 번째 숫자입니다. IsFib(13, out idx);반환 true및 값 7.

한 가지 예외는이며 IsFib(1, out idx);, 2값 1이 인덱스 1과 2에 모두 표시 되더라도 반환 됩니다.

경우 IsFib비 피보나치 수를 전달, 그것은 반환 false, 그리고 값 idx보다 가장 큰 피보나치 수의 인덱스가됩니다 T.

16은 피보나치 값이 아닙니다.
IsFib(16, out idx);반환 false및 값 7. Binet의 공식
사용 하여 인덱스 7을 16보다 작은 가장 큰 숫자 인 피보나치 값 13으로 변환 할 수 있습니다 .


#!/bin/bash
victim="144"
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null
if [[ $? -eq 0 ]] ; then
    echo "$victim is a fibonacci number"
else
    echo "$victim aint"
fi

숫자가 제한된 크기 인 경우 단순히 상한 아래의 모든 피보나치 숫자를 해시 테이블에 넣는 것보다 격리 테스트가 트릭을 수행합니다. 피보나치 수는 기하 급수적으로 증가하기 때문에 매우 적습니다 (예 : 5mln 미만 38 개).

숫자가 제한된 크기 아닌 경우 제곱 테스트를 사용하는 제안 된 트릭은 숫자를 찾거나 초과 할 때까지 피보나치 수열을 생성하는 것보다 거의 확실히 느립니다.


해결책을 위해 Binet의 Formula를 살펴보십시오.
( Wikipedia의 Fibonacci Number 에서 "Closed-Form Expression"을 찾으십시오. )

피보나치 수의 시퀀스는 간단한 닫힌 공식에 의해 생성됩니다.

대체 텍스트

를 풀고 정수 n인지 테스트하면 n답을 얻을 수 있다고 믿습니다 .

편집 으로 같은 위키 백과 문서는 피보나치 수의 검출에 대한 섹션을 가지고 점을 @psmears. Wikipedia는 훌륭한 소스입니다.


양의 정수 ω는 피보나치 수입니다.

그리고 경우에만 경우 중 하나2 + 4 5ω 2 - 4는 정사각형이다

에서 알프레드 Posamentier 및 잉마르 레만에 의해 (멋진) 피보나치 수

bool isFibonacci(int  w)
{
       double X1 = 5 * Math.Pow(w, 2) + 4;
       double X2 = 5 * Math.Pow(w, 2) - 4;

       long X1_sqrt = (long)Math.Sqrt(X1);
       long X2_sqrt = (long)Math.Sqrt(X2);   

       return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ;
}

이 소스에서 복사했습니다.


1k사이의 피보나치 수를 인쇄하는 스 니펫 10k.

for (int i = 1000; i < 10000; i++)
{
         if (isFibonacci(i))
              Console.Write(" "+i);
}

OMG 4 개 밖에 없어요 !!!

다른 방법으로

from math import *

phi = 1.61803399
sqrt5 = sqrt(5)

def F(n):
    return int((phi**n - (1-phi)**n) /sqrt5)

def isFibonacci(z):
    return F(int(floor(log(sqrt5*z,phi)+0.5))) == z

print [i for i in range(1000,10000) if isFibonacci(i)]

피보나치 수에 대한 위키피디아 문서의 "피보나치 수 인식"섹션을 참조하십시오 .


피보나치 수는 기하 급수적으로 증가하기 때문에 제안하는 방법은 매우 빠릅니다. 또 하나는 이것 입니다.


나와 psmears의 이전 답변을 기반 으로이 C # 코드를 작성했습니다.

단계를 천천히 거치며 명확하게 줄이고 최적화 할 수 있습니다.

// Input: T: number to test.
// Output: idx: index of the number in the Fibonacci sequence.
//    eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8)
// Return value: True if Fibonacci, False otherwise.
static bool IsFib(long T, out int idx)
{
    double root5 = Math.Sqrt(5);
    double PSI = (1 + root5) / 2;

    // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number

    double a;

    a = T*root5;
    a = Math.Log(a) / Math.Log(PSI);
    a += 0.5;
    a = Math.Floor(a);
    idx = (Int32)a;

    long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5);

    if (u == T)
    {
        return true;
    }
    else
    {
        idx = 0;
        return false;
    }
}

테스트 결과 처음 69 개의 ​​피보나치 수에 대해 작동하지만 70 번째에 대해서는 분해됩니다.

F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails

대체로 어떤 종류의 BigInt 라이브러리를 사용하지 않는 한, 알고리즘을 실행하는 것보다 피보나치 숫자의 간단한 조회 테이블을 가지고 확인하는 것이 좋습니다.

처음 300 개의 번호 목록은 온라인에서 쉽게 확인할 수 있습니다.

그러나이 코드는 충분한 정밀도가 있고 숫자 표현 시스템을 오버플로하지 않는 경우 실행 가능한 알고리즘을 설명합니다.


Wikipedia에서 : http://en.wikipedia.org/wiki/Fibonacci_number

양의 정수 z는 5z ^ 2 + 4 또는 5z ^ 2 − 4 중 하나가 완전 제곱 인 경우에만 피보나치 수입니다.


Re : Ahmad의 코드-재귀 나 포인터가없는 더 간단한 접근 방식, 상당히 순진하지만 정말 거대한 숫자 (최신 기계에서는 밀리 초가 걸리는 N 번째 fib 번호를 확인하기 위해 대략 2N 추가)가 필요하지 않습니다. 아무리 나빠도)

// 무언가를 찾으면 pos를 반환하고, 찾지 못하면 0을 반환합니다 (C / C ++는 모든 값을! = 0으로 처리하므로 동일한 최종 결과).

int isFib (long n)
{
    int pos = 2;
    long last = 1;
    long current = 1;
    long temp;

    while (current < n)
    {
        temp = last;
        last = current;
        current = current + temp;
        pos++;
    }

    if (current == n)
        return pos;
    else
        return 0;

}

피보나치 수에 대한 일반적인 표현은 F (n) = [[(1 + sqrt (5)) / 2] sup n + 1-[(1-sqrt (5)) / 2] sup n + 1] / sqrt입니다. (5) ..... (*) 두 번째 지수는 큰 n에 대해 0이되고 수치 연산을 수행하면 F (n) = [(1.618) sup n + 1] / 2.236

K가 테스트 할 숫자이면 log (k * 2.2336) / log (1.618)는 정수 여야합니다!

K가 13 인 경우 내 계산기는 7.00246 답을 제공합니다. K가 14 인 경우 답은 7.1564입니다.

답에 가장 가까운 정수를 취하고 (*)로 대체하여 결과가 K인지 확인하여 결과의 ​​신뢰도를 높일 수 있습니다.


당신이 다루는 숫자는 얼마나 큽니까?

조회 테이블이 도움이 될 수 있습니까? (검색 할 수있는 미리 계산 된 숫자 목록)

분석적으로 답을 얻기 위해 뒤집을 수 있는 폐쇄 형 표현 도 있습니다 (나는 수학자는 아니지만이 제안이 의미가 있다고 약속 할 수는 없습니다)


간단한 추가, 배열 사전 계산, 결과를 해시로 메모하는 것과 함께 여기에 제시된 방법에 대한 몇 가지 벤치 마크를 실행했습니다. Perl의 경우 적어도 제곱 방법은 로그 방법보다 약간 빠르며 아마도 20 % 더 빠릅니다. abelenky가 지적했듯이, 비트 수를 제곱 할 여지가 있는지 여부 사이의 상충 관계입니다.

확실히 가장 빠른 방법은 도메인 공간의 모든 피보나치 수를 해시하는 것입니다. abelenky가 만드는 또 다른 점의 선을 따라 2 ^ 64보다 작은이 빨판은 94 개뿐입니다.

미리 계산하고 Perl 해시, Python 사전 등에 넣어야합니다.

피보나치 수의 속성은 매우 흥미롭지 만 컴퓨터 프로그램의 정수가 하나인지 여부를 결정하는 데 사용하는 것은 프로그램이 시작될 때마다 pi를 계산하는 서브 루틴을 작성하는 것과 같습니다.


이것이 벤치 마크인지 확실하지 않은 내 솔루션입니다. 이게 도움이 되길 바란다!

def is_fibonacci?(i)
  a,b=0,1
    until b >= i
        a,b=b,a+b
        return true if b == i
    end
end

무엇을 A, B는 = B는 + b를 하고있다

 0, 1 = 1, 0 +1
 1, 1 = 1, 1 + 1
 1, 2 = 2, 1 + 2
 2, 3 = 3, 2 + 3

fib1 = fib2
fib2 = fib1 + fib2

스칼라 버전

def isFib(n: Int): Boolean = {

def checkFib(f1: Int = 1, f2: Int = 1): Boolean = {

if(n == f1 || n == f2) true
else if(n < f2) false
else checkFib(f2, f1+f2)

}

checkFib()

}

Java 솔루션은 다음과 같이 수행 할 수 있습니다. 하지만 여전히 최적화 할 수 있습니다.

다음 솔루션은

  1. 1≤T≤10 ^ 5
  2. 1≤N≤10 ^ 10

T는 테스트 케이스의 수, N은 수의 범위입니다.

    import java.util.Scanner;
    import java.math.BigDecimal;
    import java.math.RoundingMode;

    public class FibonacciTester {
        private static BigDecimal zero = BigDecimal.valueOf(0);
        private static BigDecimal one = BigDecimal.valueOf(1);
        private static BigDecimal two = BigDecimal.valueOf(2);
        private static BigDecimal four = BigDecimal.valueOf(4);
        private static BigDecimal five = BigDecimal.valueOf(5);

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            BigDecimal[] inputs = new BigDecimal[n];
            for (int i = 0; i < n; i++) {
                inputs[i] = sc.nextBigDecimal();
            }

            for (int i = 0; i < inputs.length; i++) {
                if (isFibonacci(inputs[i]))
                    System.out.println("IsFibo");
                else
                    System.out.println("IsNotFibo");
            }


        }

        public static boolean isFibonacci(BigDecimal num) {
            if (num.compareTo(zero) <= 0) {
                return false;
            }

            BigDecimal base = num.multiply(num).multiply(five);
            BigDecimal possibility1 = base.add(four);
            BigDecimal possibility2 = base.subtract(four);


            return (isPerfectSquare(possibility1) || isPerfectSquare(possibility2));
        }

        public static boolean isPerfectSquare(BigDecimal num) {
            BigDecimal squareRoot = one;
            BigDecimal square = one;
            BigDecimal i = one;
            BigDecimal newSquareRoot;
            int comparison = -1;

            while (comparison != 0) {
                if (comparison < 0) {
                    i = i.multiply(two);
                    newSquareRoot = squareRoot.add(i).setScale(0, RoundingMode.HALF_UP);
                } else {
                    i = i.divide(two);
                    newSquareRoot = squareRoot.subtract(i).setScale(0, RoundingMode.HALF_UP);
                }

                if (newSquareRoot.compareTo(squareRoot) == 0) {
                    return false;
                }

                squareRoot = newSquareRoot;
                square = squareRoot.multiply(squareRoot);
                comparison = square.compareTo(num);
            }

            return true;
        }
    }

int isfib(int n /* number */, int &pos /* position */)
{
   if (n == 1)
   {
      pos=2;  // 1 1
      return 1;
   }
   else if (n == 2)
   {
      pos=3;  // 1 1 2
      return 1;
   }
   else
   {
      int m = n /2;
      int p, q, x, y;
      int t1=0, t2 =0;
      for (int i = m; i < n; i++)
      {
        p = i;
        q = n -p;    // p + q = n
        t1 = isfib(p, x);
        if (t1) t2 = isfib(q, y);
        if (t1 && t2 && x == y +1)
        {
           pos = x+1;
           return 1; //true
        }
      }
      pos = -1;
      return 0; //false
   }
}

이것은 어떤가요?


#include <stdio.h>
#include <math.h>

int main()
{
int number_entered, x, y;

printf("Please enter a number.\n");
scanf("%d", &number_entered);
x = y = 5 * number_entered^2 + 4;        /*Test if 5N^2 + 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
        printf("That number is in the Fibonacci sequence.\n");
    }
x = y = 5 * number_entered^2 - 4;        /*Test if 5N^2 - 4 is a square number.*/
x = sqrt(x);
x = x^2;
if (x == y)
{
    printf("That number is in the Fibonacci sequence.\n");
}
else
{
    printf("That number isn't in the Fibonacci sequence.\n");
}
return 0;
}

작동할까요?

참고 URL : https://stackoverflow.com/questions/2432669/test-if-a-number-is-fibonacci

반응형