var x=0,
var y=1;
var z;
fib[0] = 0;
fib[1] = 1;
for(i=2; i<=10; i++)
{
alert(x+y);
fib[i]=x+y;
x=y;
z=y;
}
Я пытаюсь создать простую последовательность Фибоначчи, но нет выхода. Кто-нибудь может сообщить мне, что случилось?
Формирование последовательности Фибоначчи
Ответ 1
Вы никогда не объявляли fib массивом. Используйте var fib = []; чтобы решить это.
Кроме того, вы никогда не изменяете переменную y и не используете ее.
Приведенный ниже код имеет больше смысла, плюс он не создает неиспользуемые переменные:
var i;
var fib = []; // Initialize array!
fib[0] = 0;
fib[1] = 1;
for (i = 2; i <= 10; i++) {
// Next fibonacci number = previous + one before previous
// Translated to JavaScript:
fib[i] = fib[i - 2] + fib[i - 1];
console.log(fib[i]);
}Ответ 2
Согласно вопросу " Торт для интервью", последовательность идет 0,1,1,2,3,5,8,13,21. Если это так, то это решение работает и является рекурсивным без использования массивов.
function fibonacci(n) {
return n < 1 ? 0
: n <= 2 ? 1
: fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(4));
Думайте об этом так.
fibonacci(4) .--------> 2 + 1 = 3
| / |
'--> fibonacci(3) + fibonacci(2)
| ^
| '----------- 2 = 1 + 1 <----------.
1st step -> | ^ |
| | |
'----> fibonacci(2) -' + fibonacci(1)-'
Обратите внимание, что это решение не очень эффективно, хотя.
Ответ 3
Здесь простая функция для итерации последовательности Фибоначчи в массив с использованием аргументов в функции for больше, чем тело цикла:
fib = function(numMax){
for(var fibArray = [0,1], i=0,j=1,k=0; k<numMax;i=j,j=x,k++ ){
x=i+j;
fibArray.push(x);
}
console.log(fibArray);
}
fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Ответ 4
Сначала вы должны были объявить переменную fib как массив (например, var fib = [] или var fib = new Array()), и я думаю, вы немного запутались в алгоритме.
Если вы используете массив для хранения последовательности Фибоначчи, вам не нужны другие вспомогательные переменные (x,y,z):
var fib = [0, 1];
for(var i=fib.length; i<10; i++) {
fib[i] = fib[i-2] + fib[i-1];
}
console.log(fib);
Нажмите для демонстрации
Вам также следует рассмотреть рекурсивный метод (обратите внимание, что это оптимизированная версия):
function fib(n, undefined){
if(fib.cache[n] === undefined){
fib.cache[n] = fib(n-1) + fib(n-2);
}
return fib.cache[n];
}
fib.cache = [0, 1, 1];
и затем, после вызова функции fibonacci, у вас есть вся последовательность в поле fib.cache:
fib(1000);
console.log(fib.cache);
Ответ 5
Еще один ответ заключался бы в использовании функций генератора es6 .
function* fib() {
var current = a = b = 1;
yield 1;
while (true) {
current = b;
yield current;
b = a + b;
a = current;
}
}
sequence = fib();
sequence.next(); // 1
sequence.next(); // 1
sequence.next(); // 2
// ...
Ответ 6
Вы не назначаете значение z, так что вы ожидаете y=z;? Точно так же вы никогда не читаете из массива. Похоже, вы здесь пытаетесь сочетать два разных подхода: попробуйте полностью избавиться от массива и просто используйте:
// Initialization of x and y as before
for (i = 2; i <= 10; i++)
{
alert(x + y);
z = x + y;
x = y;
y = z;
}
EDIT: OP изменил код после добавления этого ответа. Первоначально последняя строка цикла была y = z; - и это имеет смысл, если вы инициализировали z в соответствии с моим кодом.
Если массив понадобится позже, то, очевидно, это необходимо заполнить, но в остальном код, который я дал, должен быть хорошим.
Ответ 7
Золотой рацион "phi" ^ n/sqrt (5) асимптотичен фибоначчи n, если мы округляем это значение вверх, мы действительно получаем значение фибоначчи.
function fib(n) {
let phi = (1 + Math.sqrt(5))/2;
let asymp = Math.pow(phi, n) / Math.sqrt(5);
return Math.round(asymp);
}
fib(1000); // 4.346655768693734e+208 in just 0.62s
Это выполняется быстрее на больших количествах по сравнению с решениями на основе рекурсии.
Ответ 8
function fib(n) {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
fib(10); // returns 55
Ответ 9
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>fibonacci series</title>
<script type="text/javascript">
function generateseries(){
var fno = document.getElementById("firstno").value;
var sno = document.getElementById("secondno").value;
var a = parseInt(fno);
var result = new Array();
result[0] = a;
var b = ++fno;
var c = b;
while (b <= sno) {
result.push(c);
document.getElementById("maindiv").innerHTML = "Fibonacci Series between "+fno+ " and " +sno+ " is " +result;
c = a + b;
a = b;
b = c;
}
}
function numeric(evt){
var theEvent = evt || window.event;
var key = theEvent.keyCode || theEvent.which;
key = String.fromCharCode(key);
var regex = /[0-9]|\./;
if (!regex.test(key)) {
theEvent.returnValue = false;
if (theEvent.preventDefault)
theEvent.preventDefault();
}
}
</script>
<h1 align="center">Fibonacci Series</h1>
</head>
<body>
<div id="resultdiv" align="center">
<input type="text" name="firstno" id="firstno" onkeypress="numeric(event)"><br>
<input type="text" name="secondno" id="secondno" onkeypress="numeric(event)"><br>
<input type="button" id="result" value="Result" onclick="generateseries();">
<div id="maindiv"></div>
</div>
</body>
</html>
Ответ 10
Быстрый способ получить ~ 75
ty @geeves для catch, я заменил Math.floor на Math.round, который, похоже, довел до 76, где возникают проблемы с плавающей запятой:/...
в любом случае, я бы не хотел использовать рекурсию и до этого момента.
/**
* Binet Fibonacci number formula for determining
* sequence values
* @param {int} pos - the position in sequence to lookup
* @returns {int} the Fibonacci value of sequence @pos
*/
var test = [0,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,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026];
var fib = function (pos) {
return Math.round((Math.pow( 1 + Math.sqrt(5), pos)
- Math.pow( 1 - Math.sqrt(5), pos))
/ (Math.pow(2, pos) * Math.sqrt(5)));
};
/* This is only for the test */
var max = test.length,
i = 0,
frag = document.createDocumentFragment(),
_div = document.createElement('div'),
_text = document.createTextNode(''),
div,
text,
err,
num;
for ( ; i < max; i++) {
div = _div.cloneNode();
text = _text.cloneNode();
num = fib(i);
if (num !== test[i]) {
err = i + ' == ' + test[i] + '; got ' + num;
div.style.color = 'red';
}
text.nodeValue = i + ': ' + num;
div.appendChild(text);
frag.appendChild(div);
}
document.body.appendChild(frag);Ответ 11
Существует также обобщение формулы Бине для отрицательных целых чисел:
static float phi = (1.0f + sqrt(5.0f)) / 2.0f;
int generalized_binet_fib(int n) {
return round( (pow(phi, n) - cos(n * M_PI) * pow(phi, -n)) / sqrt(5.0f) );
}
...
for(int i = -10; i < 10; ++i)
printf("%i ", generalized_binet_fib(i));
Ответ 12
Если используется es6
function fib(n, prev = 0, current = 1) {
return !n ? prev + current : fib(--n, current, prev+current)
}
var f = fib(10)
Ответ 13
Я знаю, что это немного старый вопрос, но я понял, что многие из ответов здесь используются для циклов, а не для циклов.
Иногда, в то время как циклы быстрее, чем для циклов, поэтому я решил, что внес бы некоторый код, который также запускает последовательность Фибоначчи в цикле while! Используйте все, что вам подходит, в соответствии с вашими потребностями.
function fib(length) {
var fibArr = [],
i = 0,
j = 1;
fibArr.push(i);
fibArr.push(j);
while (fibArr.length <= length) {
fibArr.push(fibArr[j] + fibArr[i]);
j++;
i++;
}
return fibArr;
};
fib(15);
Ответ 14
sparkida, нашел проблему с вашим методом. Если вы проверите положение 10, оно вернет 54 и приведет к неправильному изменению всех последующих значений. Вы можете увидеть это здесь: http://jsfiddle.net/createanaccount/cdrgyzdz/5/
(function() {
function fib(n) {
var root5 = Math.sqrt(5);
var val1 = (1 + root5) / 2;
var val2 = 1 - val1;
var value = (Math.pow(val1, n) - Math.pow(val2, n)) / root5;
return Math.floor(value + 0.5);
}
for (var i = 0; i < 100; i++) {
document.getElementById("sequence").innerHTML += (0 < i ? ", " : "") + fib(i);
}
}());<div id="sequence">
</div>Ответ 15
Вы можете получить некоторый кеш, чтобы ускорить алгоритм...
var tools = {
fibonacci : function(n) {
var cache = {};
// optional seed cache
cache[2] = 1;
cache[3] = 2;
cache[4] = 3;
cache[5] = 5;
cache[6] = 8;
return execute(n);
function execute(n) {
// special cases 0 or 1
if (n < 2) return n;
var a = n - 1;
var b = n - 2;
if(!cache[a]) cache[a] = execute(a);
if(!cache[b]) cache[b] = execute(b);
return cache[a] + cache[b];
}
}
};
Ответ 16
Ниже приведены примеры написания фибоначчи с использованием рекурсии, генератора и сокращения.
'use strict'
//------------- using recursion ------------
function fibonacciRecursion(n) {
return (n < 2) ? n : fibonacciRecursion(n - 2) + fibonacciRecursion(n - 1)
}
// usage
for (let i = 0; i < 10; i++) {
console.log(fibonacciRecursion(i))
}
//-------------- using generator -----------------
function* fibonacciGenerator() {
let a = 1,
b = 0
while (true) {
yield b;
[a, b] = [b, a + b]
}
}
// usage
const gen = fibonacciGenerator()
for (let i = 0; i < 10; i++) {
console.log(gen.next().value)
}
//------------- using reduce ---------------------
function fibonacciReduce(n) {
return new Array(n).fill(0)
.reduce((prev, curr) => ([prev[0], prev[1]] = [prev[1], prev[0] + prev[1]], prev), [0, 1])[0]
}
// usage
for (let i = 0; i < 10; i++) {
console.log(fibonacciReduce(i))
}Ответ 17
Я просто хотел бы внести вклад с оптимизированной версией хвоста с помощью ES6. Это довольно просто;
var fibonacci = (n, f = 0, s = 1) => n === 0 ? f : fibonacci(--n, s, f + s);
console.log(fibonacci(12));Ответ 18
Вы могли бы попробовать это решение Фибоначчи здесь
var a = 0;
console.log(a);
var b = 1;
console.log(b);
var c;
for (i = 0; i < 3; i++) {
c = a + b;
console.log(c);
a = b + c;
console.log(a);
b = c + a;
console.log(b);
}
Ответ 19
Другая реализация, хотя рекурсивная, очень быстрая и использует единственную встроенную функцию. Он достигает предела точности 64-битных чисел javascript, начиная 80-ю последовательность (как и все остальные алгоритмы): например, если вы хотите 78-й член (78 идет в последней скобке):
(function (n,i,p,r){p=(p||0)+r||1;i=i?i+1:1;return i<=n?arguments.callee(n,i,r,p):r}(78));
вернется: 8944394323791464
Это обратно совместимо вплоть до ECMASCRIPT4 - я протестировал его с IE7, и он работает!
Ответ 20
Фибоначчи 1000... 10000... 100000
Некоторые ответы сталкиваются с проблемами при попытке вычислить большие числа Фибоначчи. Другие являются приблизительными числами, используя фи. Этот ответ покажет вам, как вычислить точную серию больших чисел Фибоначчи, не сталкиваясь с ограничениями, установленными реализацией JavaScript с плавающей запятой.
Ниже мы генерируем первые 1000 чисел Фибоначчи за несколько миллисекунд. Позже мы сделаем 100 000!
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (1000))
console.timeEnd ('bigfib')
// 25 ms
console.log (seq.length)
// 1001
console.log (seq)
// [ 0, 1, 1, 2, 3, ... 995 more elements ]
Давайте посмотрим на тысячное число Фибоначчи
console.log (seq [1000])
// 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
10000
Это решение очень хорошо масштабируется. Мы можем вычислить первые 10000 чисел Фибоначчи менее чем за 2 секунды. На данном этапе последовательности числа превышают 2000 цифр, что намного превышает возможности чисел с плавающей запятой в JavaScript. Тем не менее, наш результат включает в себя точные значения без приближений.
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875
Конечно, вся эта магия происходит в Bignum, которой мы сейчас поделимся. Чтобы понять, как мы будем проектировать Bignum, вспомните, как вы добавили большие числа, используя ручку и бумагу в детстве...
1259601512351095520986368
+ 50695640938240596831104
---------------------------
?
Вы добавляете каждый столбец справа налево, и когда столбец переполняется до двух цифр, не забывая переносить 1 в следующий столбец...
... <-001
1259601512351095520986368
+ 50695640938240596831104
---------------------------
... <-472 Выше мы можем видеть, что если бы у нас было два 10-значных числа, то для вычисления ответа потребовалось бы приблизительно 30 простых сложений (по 3 на столбец). Вот как мы будем проектировать Bignum для работы
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
Мы проведем быстрый тест, чтобы проверить наш пример выше
const x =
fromString ('1259601512351095520986368')
const y =
fromString ('50695640938240596831104')
console.log (toString (add (x,y)))
// 1310297153289336117817472
А теперь полная демонстрация программы. Разверните его, чтобы вычислить точное тысячное число Фибоначчи в вашем собственном браузере! Обратите внимание, что результат совпадает с ответом, предоставленным вольфрам альфа
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875Ответ 21
Этот script будет принимать номер как параметр, который вы хотите, чтобы ваша последовательность Фибоначчи прошла.
function calculateFib(num) {
var fibArray = [];
var counter = 0;
if (fibArray.length == 0) {
fibArray.push(
counter
);
counter++
};
fibArray.push(fibArray[fibArray.length - 1] + counter);
do {
var lastIndex = fibArray[fibArray.length - 1];
var snLastIndex = fibArray[fibArray.length - 2];
if (lastIndex + snLastIndex < num) {
fibArray.push(lastIndex + snLastIndex);
}
} while (lastIndex + snLastIndex < num);
return fibArray;
};
Ответ 22
Вот что я придумал
//fibonacci numbers
//0,1,1,2,3,5,8,13,21,34,55,89
//print out the first ten fibonacci numbers
'use strict';
function printFobonacciNumbers(n) {
var firstNumber = 0,
secondNumber = 1,
fibNumbers = [];
if (n <= 0) {
return fibNumbers;
}
if (n === 1) {
return fibNumbers.push(firstNumber);
}
//if we are here,we should have at least two numbers in the array
fibNumbers[0] = firstNumber;
fibNumbers[1] = secondNumber;
for (var i = 2; i <= n; i++) {
fibNumbers[i] = fibNumbers[(i - 1)] + fibNumbers[(i - 2)];
}
return fibNumbers;
}
var result = printFobonacciNumbers(10);
if (result) {
for (var i = 0; i < result.length; i++) {
console.log(result[i]);
}
}
Ответ 23
Начинающий, не слишком элегантный, но показывает основные шаги и выводы в JavaScript
/* Array Four Million Numbers */
var j = [];
var x = [1,2];
var even = [];
for (var i = 1;i<4000001;i++){
j.push(i);
}
// Array Even Million
i = 1;
while (i<4000001){
var k = j[i] + j[i-1];
j[i + 1] = k;
if (k < 4000001){
x.push(k);
}
i++;
}
var total = 0;
for (w in x){
if (x[w] %2 === 0){
even.push(x[w]);
}
}
for (num in even){
total += even[num];
}
console.log(x);
console.log(even);
console.log(total);
Ответ 24
Фибоначчи (однострочный)
function fibonacci(n) {
return (n <= 1) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
Фибоначчи (рекурсивный)
function fibonacci(number) {
// n <= 1
if (number <= 0) {
return n;
} else {
// f(n) = f(n-1) + f(n-2)
return fibonacci(number - 1) + fibonacci(number - 2);
}
};
console.log('f(14) = ' + fibonacci(14)); // 377Ответ 25
Мои 2 цента:
function fibonacci(num) {
return Array.apply(null, Array(num)).reduce(function(acc, curr, idx) {
return idx > 2 ? acc.concat(acc[idx-1] + acc[idx-2]) : acc;
}, [0, 1, 1]);
}
console.log(fibonacci(10));Ответ 26
Еще один простой способ добиться этого:
// declare the array starting with the first 2 values of the fibonacci sequence
var fibonacci = [0,1];
function listFibonacci() {
// starting at array index 1, and push current index + previous index to the array
for (var i = 1; i < 10; i++) {
fibonacci.push(fibonacci[i] + fibonacci[i - 1]);
}
console.log(fibonacci);
}
listFibonacci();
Ответ 27
Я хотел бы добавить еще один код в качестве ответа:), его никогда не поздно ввести код: P
function fibonacciRecursive(a, b, counter, len) {
if (counter <= len) {
console.log(a);
fibonacciRecursive(b, a + b, counter + 1, len);
}
}
fibonacciRecursive(0, 1, 1, 20);
Результат
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Ответ 28
function fibo(count) {
//when count is 0, just return
if (!count) return;
//Push 0 as the first element into an array
var fibArr = [0];
//when count is 1, just print and return
if (count === 1) {
console.log(fibArr);
return;
}
//Now push 1 as the next element to the same array
fibArr.push(1);
//Start the iteration from 2 to the count
for(var i = 2, len = count; i < len; i++) {
//Addition of previous and one before previous
fibArr.push(fibArr[i-1] + fibArr[i-2]);
}
//outputs the final fibonacci series
console.log(fibArr);
}
Независимо от того, что нам нужно, мы можем дать его выше fibo и получить ряд фибоначчи по счету.
fibo(20); //output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
Ответ 29
Вот функция, которая отображает сгенерированную последовательность Фибоначчи в полном объеме при использовании рекурсии:
function fibonacci (n, length) {
if (n < 2) {
return [1];
}
if (n < 3) {
return [1, 1];
}
let a = fibonacci(n - 1);
a.push(a[n - 2] + a[n - 3]);
return (a.length === length)
? a.map(val => console.log(val))
: a;
};
Выход для fibonacci(5, 5) будет:
1
1
2
3
5
Значение, назначенное для a является возвращаемым значением функции fibonacci. На следующей строке, следующее значение последовательности Фибоначчи вычисляются и подтолкнул к концу a массиве.
Параметр length функции fibonacci используется для сравнения длины последовательности, a массивом, и должен совпадать с параметром n. Когда длина последовательности соответствует параметру длины, массив выводится на консоль, в противном случае функция возвращает a a массив и повторы.
Ответ 30
es6 - функции Symbol.iterator и генератора:
let fibonacci = {
*[Symbol.iterator]() {
let pre = 0, cur = 1
for (;;) {
[ pre, cur ] = [ cur, pre + cur ]
yield cur
}
}
}
for (let n of fibonacci) {
if (n > 1000)
break
console.log(n)
}