Определение, является ли числом Число Фибоначчи
Я должен для написания кода Java, который проверяет, является ли пользователь оценочное число в последовательности Fibonacci.
У меня нет проблемы, пишущий последовательность Fibonacci для вывода, но (вероятно, потому что поздно вечером) я изо всех сил пытаюсь думать о последовательности того, является ли это Числом Фибоначчи. Я продолжаю запускаться много раз. Его действительно выполнение в моей голове.
То, что я в настоящее время имею, является энным.
public static void main(String[] args)
{
ConsoleReader console = new ConsoleReader();
System.out.println("Enter the value for your n: ");
int num = (console.readInt());
System.out.println("\nThe largest nth fibonacci: "+fib(num));
System.out.println();
}
static int fib(int n){
int f = 0;
int g = 1;
int largeNum = -1;
for(int i = 0; i < n; i++)
{
if(i == (n-1))
largeNum = f;
System.out.print(f + " ");
f = f + g;
g = f - g;
}
return largeNum;
}
10 ответов
Прочтите раздел под названием «распознавание чисел Фибоначчи» в википедии .
В качестве альтернативы положительное целое число z является числом Фибоначчи тогда и только тогда, когда одно из 5z ^ 2 + 4 или 5z ^ 2-4 является полным квадратом. [17]
В качестве альтернативы вы можете продолжать генерировать числа Фибоначчи до тех пор, пока один становится равным вашему числу: если это так, то ваше число является числом Фибоначчи, если нет, числа в конечном итоге станут больше, чем ваше число, и вы можете остановиться. Однако это довольно неэффективно.
Если моя Java не слишком ржавая...
static bool isFib(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}
Положительное целое число x является числом Фибоначчи тогда и только тогда, когда одно из 5x ^ 2 + 4 и 5x ^ 2 - 4 является полным квадратом
Вместо передачи индекса, n , напишите функцию, которая принимает предел, и заставит ее генерировать числа Фибоначчи до этого предела включительно. Заставьте его вернуть логическое значение в зависимости от того, превышает ли он предел или пропускает его, и вы можете использовать это, чтобы проверить, входит ли это значение в последовательность.
Так как это домашнее задание, такой толчок, вероятно, все, что мы должны вам дать ...
Существует ряд методов, которые можно использовать для определения того, входит ли данное число в последовательность Фибоначчи, выбор из которых можно увидеть в википедии .
Однако, учитывая то, что вы уже сделали, я бы, вероятно, использовал более грубый подход, например следующий:
- Сгенерируйте число Фибоначчи
- Если оно меньше целевого числа, сгенерируйте далее фибоначчи и повторить
- Если это целевое число, тогда успех
- Если оно больше целевого числа, то неудача.
Я бы, вероятно, использовал рекурсивный метод, передав текущее n-значение (т. Е. Чтобы вычислялось n-е число Фибоначчи) и целевое число.
Если я правильно понимаю, что вам нужно сделать (вместо того, чтобы записывать первые n числа Фибоначчи), - это определить, является ли n числом Фибоначчи.
Таким образом, вам следует изменить свой метод, чтобы продолжать генерировать последовательность Фибоначчи, пока вы не получите число> = n. Если оно равно, n является числом Фибоначчи, в противном случае - нет.
Обновление: из-за неоднократных заявлений @ Moron о том, что алгоритм, основанный на формулах, превосходит по производительности простой вышеописанный, я действительно провел сравнительное сравнение - конкретно между решением Якопо как алгоритмом генератора и Последняя версия Стивена как алгоритм, основанный на формулах . Для справки, вот точный код:
public static void main(String[] args) {
measureExecutionTimeForGeneratorAlgorithm(1);
measureExecutionTimeForFormulaAlgorithm(1);
measureExecutionTimeForGeneratorAlgorithm(10);
measureExecutionTimeForFormulaAlgorithm(10);
measureExecutionTimeForGeneratorAlgorithm(100);
measureExecutionTimeForFormulaAlgorithm(100);
measureExecutionTimeForGeneratorAlgorithm(1000);
measureExecutionTimeForFormulaAlgorithm(1000);
measureExecutionTimeForGeneratorAlgorithm(10000);
measureExecutionTimeForFormulaAlgorithm(10000);
measureExecutionTimeForGeneratorAlgorithm(100000);
measureExecutionTimeForFormulaAlgorithm(100000);
measureExecutionTimeForGeneratorAlgorithm(1000000);
measureExecutionTimeForFormulaAlgorithm(1000000);
measureExecutionTimeForGeneratorAlgorithm(10000000);
measureExecutionTimeForFormulaAlgorithm(10000000);
measureExecutionTimeForGeneratorAlgorithm(100000000);
measureExecutionTimeForFormulaAlgorithm(100000000);
measureExecutionTimeForGeneratorAlgorithm(1000000000);
measureExecutionTimeForFormulaAlgorithm(1000000000);
measureExecutionTimeForGeneratorAlgorithm(2000000000);
measureExecutionTimeForFormulaAlgorithm(2000000000);
}
static void measureExecutionTimeForGeneratorAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByGeneration(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running generator algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static void measureExecutionTimeForFormulaAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByFormula(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running formula algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static boolean isFibByGeneration(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}
private static boolean isFibByFormula(int num) {
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static boolean isWholeNumber(double num) {
return num - Math.round(num) == 0;
}
Результаты удивили даже меня:
Running generator algorithm 1000000 times for 1 took 0.007173537000000001 seconds
Running formula algorithm 1000000 times for 1 took 0.223365539 seconds
Running generator algorithm 1000000 times for 10 took 0.017330694 seconds
Running formula algorithm 1000000 times for 10 took 0.279445852 seconds
Running generator algorithm 1000000 times for 100 took 0.030283179 seconds
Running formula algorithm 1000000 times for 100 took 0.27773557800000004 seconds
Running generator algorithm 1000000 times for 1000 took 0.041044322 seconds
Running formula algorithm 1000000 times for 1000 took 0.277931134 seconds
Running generator algorithm 1000000 times for 10000 took 0.051103143000000004 seconds
Running formula algorithm 1000000 times for 10000 took 0.276980175 seconds
Running generator algorithm 1000000 times for 100000 took 0.062019335 seconds
Running formula algorithm 1000000 times for 100000 took 0.276227007 seconds
Running generator algorithm 1000000 times for 1000000 took 0.07422898800000001 seconds
Running formula algorithm 1000000 times for 1000000 took 0.275485013 seconds
Running generator algorithm 1000000 times for 10000000 took 0.085803922 seconds
Running formula algorithm 1000000 times for 10000000 took 0.27701090500000003 seconds
Running generator algorithm 1000000 times for 100000000 took 0.09543419600000001 seconds
Running formula algorithm 1000000 times for 100000000 took 0.274908403 seconds
Running generator algorithm 1000000 times for 1000000000 took 0.10683704200000001 seconds
Running formula algorithm 1000000 times for 1000000000 took 0.27524084800000004 seconds
Running generator algorithm 1000000 times for 2000000000 took 0.13019867100000002 seconds
Running formula algorithm 1000000 times for 2000000000 took 0.274846384 seconds
Короче говоря, алгоритм алгоритма генератора превосходит решение, основанное на формуле, для всех положительных значений int - даже близко к максимальному значению int, это больше, чем вдвое быстрее! Вот и все об оптимизации производительности на основе убеждений; -)
Для записи, изменение приведенного выше кода для использования переменных long вместо int , алгоритм генератора становится медленнее (как и ожидалось, так как теперь он должен складывать long значений), а точка переключения, при которой формула начинает работать быстрее, составляет около 1000000000000L, то есть 10 12 .
Update2: Как отметили IVlad и Moron, я не совсем разбираюсь в вычислениях с плавающей запятой :-) на основе их предложений я улучшил формулу до следующего:
private static boolean isFibByFormula(long num)
{
double power = (double)num * (double)num;
double first = 5 * power + 4;
double second = 5 * power - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
Это снизило точку переключения до прибл.10 8 (для длинной версии - генератор с int все еще быстрее для всех значений int). Несомненно, замена вызовов sqrt чем-то вроде предложенного @Moron еще больше снизит точку переключения.
Моя (и IVlad) точка зрения заключалась просто в том, что всегда будет точка переключения, ниже которой алгоритм генератора работает быстрее. Таким образом, утверждения о том, какой из них работает лучше, не имеют значения в целом, только в контексте.
Пытаясь использовать уже написанный вами код, я бы сначала предложил следующее, так как это простейшее решение (но не самое эффективное):
private static void main(string[] args)
{
//This will determnine which numbers between 1 & 100 are in the fibonacci series
//you can swop in code to read from console rather than 'i' being used from the for loop
for (int i = 0; i < 100; i++)
{
bool result = isFib(1);
if (result)
System.out.println(i + " is in the Fib series.");
System.out.println(result);
}
}
private static bool isFib(int num)
{
int counter = 0;
while (true)
{
if (fib(counter) < num)
{
counter++;
continue;
}
if (fib(counter) == num)
{
return true;
}
if (fib(counter) > num)
{
return false;
}
}
}
Я бы предложил более элегантное решение при генерации чисел Фибоначчи, которые используют рекурсию следующим образом:
public static long fib(int n)
{
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2);
}
Чтобы получить дополнительную информацию, прочтите: http: //en.wikipedia.org / wiki / Fibonacci_number # Recognizing_Fibonacci_numbers
Вы увидите, что есть несколько более эффективных способов проверить, входит ли число в ряд Фибоначчи , а именно: (5z ^ 2 + 4 или 5z ^ 2 - 4) = полный квадрат.
//(5z^2 + 4 or 5z^2 − 4) = a perfect square
//perfect square = an integer that is the square of an integer
private static bool isFib(int num)
{
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static bool isWholeNumber(double num)
{
return num - Math.round(num) == 0;
}
Я не знаю, существует ли реальная формула, которую можно применить к пользовательскому вводу, однако вы можете сгенерировать последовательность Фибоначчи и сравнить ее с пользовательским вводом, пока она не станет меньше, чем последнее сгенерированное число.
int userInput = n;
int a = 1, b = 1;
while (a < n) {
if (a == n)
return true;
int next = a + b;
b = a;
a = next;
}
return false;
Вы можете сделать это двумя способами: рекурсивным и математическим. рекурсивный способ начните генерировать последовательность Фибоначчи, пока не наберете число или не передадите его математический способ, красиво описанный здесь ... http://www.physicsforums.com/showthread.php?t=252798
удачи.
Хорошо. Поскольку люди утверждали, что я просто говорю в воздухе («факты» против «предположений») без каких-либо данных, подтверждающих это, я написал собственный тест.
Не java, а код C # ниже.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SO
{
class Program
{
static void Main(string[] args)
{
AssertIsFibSqrt(100000000);
MeasureSequential(1);
MeasureSqrt(1);
MeasureSequential(10);
MeasureSqrt(10);
MeasureSequential(50);
MeasureSqrt(50);
MeasureSequential(100);
MeasureSqrt(100);
MeasureSequential(100000);
MeasureSqrt(100000);
MeasureSequential(100000000);
MeasureSqrt(100000000);
}
static void MeasureSequential(long n)
{
int count = 1000000;
DateTime start = DateTime.Now;
for (int i = 0; i < count; i++)
{
IsFibSequential(n);
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Sequential for input = " + n +
" : " + duration.Ticks);
}
static void MeasureSqrt(long n)
{
int count = 1000000;
DateTime start = DateTime.Now;
for (int i = 0; i < count; i++)
{
IsFibSqrt(n);
}
DateTime end = DateTime.Now;
TimeSpan duration = end - start;
Console.WriteLine("Sqrt for input = " + n +
" : " + duration.Ticks);
}
static void AssertIsFibSqrt(long x)
{
Dictionary<long, bool> fibs = new Dictionary<long, bool>();
long a = 0;
long b = 1;
long f = 1;
while (b < x)
{
f = a + b;
a = b;
b = f;
fibs[a] = true;
fibs[b] = true;
}
for (long i = 1; i <= x; i++)
{
bool isFib = fibs.ContainsKey(i);
if (isFib && IsFibSqrt(i))
{
continue;
}
if (!isFib && !IsFibSqrt(i))
{
continue;
}
Console.WriteLine("Sqrt Fib test failed for: " + i);
}
}
static bool IsFibSequential(long x)
{
long a = 0;
long b = 1;
long f = 1;
while (b < x)
{
f = a + b;
a = b;
b = f;
}
return x == f;
}
static bool IsFibSqrt(long x)
{
long y = 5 * x * x + 4;
double doubleS = Math.Sqrt(y);
long s = (long)doubleS;
long sqr = s*s;
return (sqr == y || sqr == (y-8));
}
}
}
И вот результат
Sequential for input = 1 : 110011
Sqrt for input = 1 : 670067
Sequential for input = 10 : 560056
Sqrt for input = 10 : 540054
Sequential for input = 50 : 610061
Sqrt for input = 50 : 540054
Sequential for input = 100 : 730073
Sqrt for input = 100 : 540054
Sequential for input = 100000 : 1490149
Sqrt for input = 100000 : 540054
Sequential for input = 100000000 : 2180218
Sqrt for input = 100000000 : 540054
Метод sqrt превосходит наивный метод, когда сам n = 50, возможно, из-за наличия аппаратной поддержки на моей машине. Даже если бы оно было 10 ^ 8 (как в тесте Питера), под этим пороговым значением находится не более 40 чисел Фибоначчи, которые можно было бы легко поместить в таблицу поиска и при этом превзойти наивную версию для меньших значений.
Кроме того, у Питера плохая реализация SqrtVersion. На самом деле ему не нужно вычислять два квадратных корня или вычислять степени с помощью Math.Pow. Он мог бы хотя бы попытаться сделать это лучше, прежде чем опубликовать результаты своих тестов.
В любом случае, я позволю этим фактам говорить сами за себя, а не так называемым «догадкам».