Фибоначчи на JavaScript, ошибки новичков

[Ktina]

C факториалом частично удалось разобраться, а вот с Фибоначчи -- как-то не очень.
Делаю робкую попытку:

Используется синтаксис Javascript

function fib(n) {
  var a=0;
  var b=1;
  var i;
  
  for(i=1; i<=n/2; i++) {
    a+=b;
    b+=a;
  }
    if(n%2) {
    return b;
    } 
  else {
  return a;
  }
}
 

Проверяю -- кажется, работает.
Только вот в официальном решении используются три переменные: $a, b, c$, а у меня только две: $a$ и $b$. И вообще, официального решения я не понимаю, а моё какое-то "не так, как у людей". У меня так часто бывало с олимпиадными задачами по математике.
Что-то я не так делаю? Пожалуйста, помогите разобраться, а может, и решить.

[eugensk]

Нет никакого официального решения, решение - то что работает :)
У вас оно рабочее, вот вам еще одно, тоже с двумя переменными:

Используется синтаксис Javascript

...
for(i=1; i<=n; i++) {
    a=a+b;
    b=a-b;
}
return a;
 

Чтобы понять, что происходит, надо "выполнить" программу с карандашом, выписывая в столбец значения переменных.
Если вы это проделаете со своим, с моим, и с "официальным" решением, то всё станет понятно.

[Geen]

Нормальное решение.

Ktina в сообщении #1324124 писал(а):

Проверяю -- кажется, работает.

Такие вещи лучше доказывать.

[Ktina]

Geen в сообщении #1324129 писал(а):

Такие вещи лучше доказывать.

Каким образом?
Мне знакомо понятие математического доказательства. А про информатическое доказательство впервые слышу.

-- 03.07.2018, 10:43 --

eugensk
Большое спасибо!

[Geen]

Пара советов по "стилю" (ИМХО конечно).

Стоило бы написать

Используется синтаксис Javascript

var a=0, b=1; // в этих переменных всегда лежат два последовательных ЧФ
for ( var i=1;....

последнее - чтобы подчеркнуть, что переменная i нигде кроме цикла не используется.

-- 03.07.2018, 10:52 --

Ktina в сообщении #1324130 писал(а):

Каким образом?

В данном случае, на мой взгляд, достаточно пояснить то, что я в примере в комментарии написал. А в общем, лучше посмотреть как это делается в "алгоритмических" статьях.

[Ktina]

Geen в сообщении #1324132 писал(а):

Пара советов по "стилю" (ИМХО конечно).

Стоило бы написать

Используется синтаксис Javascript

var a=0, b=1; // в этих переменных всегда лежат два последовательных ЧФ
for ( var i=1;....

последнее - чтобы подчеркнуть, что переменная i нигде кроме цикла не используется.

А вот за это - отдельное спасибо! У меня со "стилем" трудности ещё очень долго будут.

-- 03.07.2018, 10:57 --

Geen в сообщении #1324132 писал(а):

А в общем, лучше посмотреть как это делается в "алгоритмических" статьях.

Не совсем Вас понимаю. О каких статьях Вы ведёте речь?

[Geen]

Ktina в сообщении #1324138 писал(а):

О каких статьях Вы ведёте речь?

О статьях, в которых описываются новые алгоритмы.

[arseniiv]

В общем, резюмируя, никакого особенного «информатического» доказательства и не нужно, обычное математическое, использующее представления (не обязательно досконально формализованные) о модели вычислений используемого языка.

[iifat]

Ktina в сообщении #1324130 писал(а):

Мне знакомо понятие математического доказательства. А про информатическое доказательство впервые слышу

Вроде б как, пошло от Дейкстры. Попробуйте почитать его книги, вот в какой конкретно он это описывает — не помню.
Грубо говоря, каждый оператор позволяем высказать некое утверждение. Например, после

a:=0

можно утверждать $a=0$. У Дейкстры получалось писать программу одновременно с доказательством корректности.

[arseniiv]

У Кнута в «Искусстве программирования» примеры доказательств тоже есть. Кнут, понятно, уже позже Дейкстры, но может быть толк.

[yk2ru]

И какой код быстрее исполнится, первый или второй?

[realeugene]

Ktina в сообщении #1324130 писал(а):

Каким образом?
Мне знакомо понятие математического доказательства. А про информатическое доказательство впервые слышу.

Обычно индуктивно, через сохранение инварианта цикла. Инвариант цикла - это истинное логическое выражение над значениями переменных в коде, которое остаётся истинным при переходе к следующей итерации. Если инвариант цикла сохраняется, он истинный на первом входе в цикл и цикл останавливается, то на выходе из цикла инвариант цикла будет истинным.

У вас $i$ в цикле только возрастает и ограничен сверху, так что, цикл останавливается. Значит, вам нужно доказать, что переменные $a$ и $b$ хранят два последовательных числа Фибоначчи (с уточнением зависимости от $i$), и что это утверждение истинно на входе в цикл и сохраняет истинность при переходе к следующей итерации цикла, будучи истинным на предыдущей.

[yk2ru]

Моя попытка реализации функции:

Используется синтаксис Javascript

function fib(n) {

  if(n==0) return 0;

  var a=0;
  var b=1;
  var i=0;
  var m=0;
 
  for(i=1; i<n; i++) {
    if (m==0) a+=b;
    else b+=a;
    m=1-m;
  }
  if(m==0) return b;
  return a;
}
 

[_Ivana]

За всю предыдущую жизнь не видел столько странных реализаций этой функции. Хотя видел их немало

[yk2ru]

Оптимизация. В начальном посте лучший вариант по быстродействию, но через раз он делает лишний шаг в цикле.

Используется синтаксис Javascript

function fib(n) {
  var a=0;
  var b=1;
  var i;
  var d=n%2;
  for(i=0; i<n/2-d; i++) {
    a+=b;
    b+=a;
  }
  if (d) return b;
  return a;
}