Delving into Fibonacci Numbers.hy.md

Խնդիր համար 4 - Գտնել Ֆիբոնաչչիի հաջորդականության n-երորդ թիվը։

Բոլորն են լսել Ֆիբոնաչչիի հաջորդականության մասին։ Հաջորդականությունը կոչվում է ի պատիվ միջնադարյան մաթեմատիկոս Լեոնարդո Պիզանոյի (Պիզացու), ով առավելապես հայտնի է Ֆիբոնաչչի անունով։ Լեոնարդո Պիզանոն համարվում է միջնադարյան Եվրոպայի առաջին խոշոր մաթեմատիկոսը։ Ապրել է Իտալիայի Տոսկանա մարզում՝ Պիզա քաղաքում (Ծննդյան և մահվան թվականը ենթադրվում է 1170-1240թվ․)։ Քանի որ նրա հայրը առևտրական էր, և գործով շատ էր լինում տարբեր երկրներում,նա նույնպես շատ է ճանապարհորդել և հատկապես մաթեմատիկայի հիմնարար գիտելիքները ստացել է միջնադարյան արաբ մաթեմատիկոսների մոտ։ Հենց նրա շնորհիվ է Եվրոպայում տարածվել արաբական թվանշանների օգտագործումը և տասական համակարգը, մինչ այդ օգտագործվում էին հռոմեական թվանշանները։ Ձեռք բերված գիտելիքների հիման վրա Ֆիբոնաչչին գրում է մի շարք գիտական աշխատություններ, որոնք շատ մեծ ձեռքբերումներ էին համարվում միջնադարյան Եվրոպայի գիտության մեջ։ XIX դարում Պիզայում գիտնականի պատվին նույնիսկ արձան տեղադրվեց։

Ֆիբոնաչչիի թվերը կամ Ֆիբոնաչչիի հաջորդականությունը դա թվային հաջորդականություն է, որում առաջին երկու թվերն են 0 և 1, իսկ յուրաքանչյուր հաջորդ թիվը հավասար է նախորդ երկու թվերի գումարին։ Այս թվերը Ֆիբոնաչչին ներկայացրեց 1202 թվականին, թեև կան տեղեկություններ, որ հաջորդականութունը ավելի վաղ նույնպես հայտնի է եղել, մասնավորապես Հնդկաստանում։ Բնության մեջ այս հաջորդականությամբ օրինաչափություններ շատ են հանդիպում, սկսած օրինակ խխունջների պատյանի ձևից մինչև պարուրաձև գալակտիկաներ։

Իսկ հիմա պատմական անդրադարձից անցնենք խնդրին։ Պահանջվում է ստեղծել ֆունկցիա, որը կհաշվի, Ֆիբոնաչչիի հաջորդականության n-րդ անդամը։ Խնդիրն ունի լուծման մի քանի հետաքրքիր տարբերակներ, որոնք տարբեր արդյունավետությամբ են աշխատում։ Առաջինը դիտարկենք պարզ իտերատիվ տարբերակը։

const fibonacci = (n) => {
  let prev = 0,
    next = 1;
  for (let i = 0; i < n; i++) {
    next = prev + next;
    prev = next - prev;
  }
  return prev;
};

Ովքեր դժվարանում են օգտագործել arrow function-ները, կամ դեռ չեն ծանոթացել դրա հետ, նույնը գրեմ նաև դասական function declaration-ի միջոցով։

function fibonacci(n) {
  let prev = 0,
    next = 1;
  for (let i = 0; i < n; i++) {
    next = prev + next;
    prev = next - prev;
  }
  return prev;
}

Ֆունկցիայի մեջ ստեղծում ենք երկու փոփոխականներ, և քանի որ մեզ հայտնի է հաջորդականության առաջին և երկրորդ թվերը, դրանք վերագրում ենք փոփոխականներին։ Ցիկլի ամեն իտերացիային, next փոփոխականը ստանում է ընթացիկ և նախորդ թվերի գումարը,իսկ ընթացիկ թվի արժեքը փոխանցվում է prev փոփոխականին։ Մենք կարող ենք ֆունկցիան էլ ավելի ընթեռնելի դարձնել,ներմուծելով ևս մեկ ժամանակավոր փոփոխական,որին բերեք անվանենք temp.

const fibonacci = (n) => {
  let prev = 0,
    next = 1;
  for (let i = 0; i < n; i++) {
    let temp = next;
    next = prev + next;
    prev = temp;
  }
  return prev;
};

Նույնը՝ function declaration-ով։

function fibonacci(n) {
  let prev = 0,
    next = 1;
  for (let i = 0; i < n; i++) {
    let temp = next;
    next = prev + next;
    prev = temp;
  }
  return prev;
}

Սա խնդրի լուծման դասական և շատ էլեգանտ տարբերակ է։ Բայց կան նաև շատ այլ տարբերակներ,որոնցից մի քանիսին կանդրադառնամ։ Մենք կարող ենք խնդրի լուծման համար օգտագործել ռեկուրսիա։ Օրինակ՝

const fibonacci = (n) => {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
};

կամ՝

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

Սակայն այս տարբերակը պետք չէ օգտագործել։ Ես այն ուղղակի ներկայացնում եմ լուծման բոլոր հնարավոր տարբերակներին համակողմանի ծանոթանալու համար։ Իսկ թե ինչու պետք չի այսպես գրել,ուղղակի գնացեք կոնսոլ,և փորձեք ստանալ Ֆիբոնաչչիի ասենք թե 80-րդ թիվը։ Խորհուրդ եմ տալիս չսպասել,մինչև ֆունկցիան կհաշվի,կվերջացնի 😀 Որովհետև անգամ ամենաարագ համակարգչի վրա այն կտևի դարեր ու հազարամյակներ։ Իսկ պատճառը ալգորիթմի բարդության էքսպոնենցիալ աճն է։

Եթե այնուամենայնիվ ուզում եք օգտագործել ռեկուրսիա,բայց այնպես,որ արագ աշխատի,ապա դա էլ է հնարավոր 😀 Մի փոքր բերեք ձևափոխենք ֆունկցիան՝

const fibonacci2 = (n) => {
  if (n == 0) {
    return [0, 1];
  } else {
    const [prev, next] = fibonacci2(n - 1);
    return [next, prev + next];
  }
};

const fibonacci = (n) => fibonacci2(n)[0];

Այստեղ պետք եղավ ստեղծել «օժանդակ» ֆունկցիա, որը վերադարձնում է Ֆիբոնաչչիի n-րդ և n + 1-րդ թվերը՝ զանգվածի մեջ, իսկ հետո այդտեղից դուրս բերել մեզ անհաժեշտ n-րդը։

Իհարկե մենք կարող ենք օգտագործել memoization-ը (պարզ ասած դա մի մեթոդոլոգիա է, երբ մենք ֆունկցիայի կանչի արդյունքը պահում ենք,հետո նույն հաշվարկը կատարելուց ֆունկցիան կրկնակի չկանչելու համար), և ռեկուրսիվ եղանակով գրած անարդյունավետ տարբերակը կարող ենք վերափոխել շատ արագ ու արդյունավետ աշխատող տարբերակի։ Սակայն ռեկուրսիա օգտագործող վերևի մեթոդը շատ ավելի կարճ ու հասկանալի է, և իմաստ չկա ավելի բարդացնել ամեն ինչ։

Կարելի է խնդիրը ձևակերպել Binet's formula-ի միջոցով, ապա այն ներկայացնել ֆունկցիայի օգնությամբ։ Եթե հետաքրքիր է,կարող եք որոնել binet formula fibonacci, և մանրամասն կարդալ։ Ահա այդ ֆունկցիան՝

const fibonacci = (n) => {
  const a = (1 + 5 ** 0.5) / 2;
  const b = (1 - 5 ** 0.5) / 2;
  return (a ** n - b ** n) / 5 ** 0.5;
};

Ֆիբոնաչչիի հերթական թիվը գեներացնելու համար կարելի է օգտագործել նաև գեներատոր ֆունկցիաներ։ Օրինակ՝

function* fibonacciGenerator() {
  let a = 0,
    b = 1;

  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

const fib = fibonacciGenerator();
console.log(fib.next().value); // 0
console.log(fib.next().value); // 1
console.log(fib.next().value); // 1
console.log(fib.next().value); // 2
console.log(fib.next().value); // 3

Իսկ վերջում որպես բոնուս ներկայացնեմ ևս մի տարբերակ, որը դժվար հասկանալի և դժվար ընթեռնելի է, թեև գերազանց աշխատում է։ Կատակով կարող եք օգտագործել, լուրջ՝ ոչ, ավելի հասկանալի և հեշտ ընթեռնելի տարբերակներ կան 😀

const fibonacci = (n) => {
  let prev = 0,
    next = 1;
  while (n-- && (next = prev + (prev = next)));
  return prev;
};