2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:20 
Аватара пользователя
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$. И вообще, официального решения я не понимаю, а моё какое-то "не так, как у людей". У меня так часто бывало с олимпиадными задачами по математике.
Что-то я не так делаю? Пожалуйста, помогите разобраться, а может, и решить.

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:37 
Аватара пользователя
Нет никакого официального решения, решение - то что работает :)
У вас оно рабочее, вот вам еще одно, тоже с двумя переменными:

Используется синтаксис Javascript
...
for(i=1; i<=n; i++) {
    a=a+b;
    b=a-b;
}
return a;
 


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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:40 
Аватара пользователя
Нормальное решение.

Ktina в сообщении #1324124 писал(а):
Проверяю -- кажется, работает.

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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:43 
Аватара пользователя
Geen в сообщении #1324129 писал(а):
Такие вещи лучше доказывать. :-)

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

-- 03.07.2018, 10:43 --

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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:47 
Аватара пользователя
Пара советов по "стилю" (ИМХО конечно).

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

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

-- 03.07.2018, 10:52 --

Ktina в сообщении #1324130 писал(а):
Каким образом?

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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:56 
Аватара пользователя
Geen в сообщении #1324132 писал(а):
Пара советов по "стилю" (ИМХО конечно).

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

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

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

-- 03.07.2018, 10:57 --

Geen в сообщении #1324132 писал(а):
А в общем, лучше посмотреть как это делается в "алгоритмических" статьях.

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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 11:07 
Аватара пользователя
Ktina в сообщении #1324138 писал(а):
О каких статьях Вы ведёте речь?

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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 17:21 
В общем, резюмируя, никакого особенного «информатического» доказательства и не нужно, обычное математическое, использующее представления (не обязательно досконально формализованные) о модели вычислений используемого языка.

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 18:11 
Ktina в сообщении #1324130 писал(а):
Мне знакомо понятие математического доказательства. А про информатическое доказательство впервые слышу
Вроде б как, пошло от Дейкстры. Попробуйте почитать его книги, вот в какой конкретно он это описывает — не помню.
Грубо говоря, каждый оператор позволяем высказать некое утверждение. Например, после
Код:
a:=0
можно утверждать $a=0$. У Дейкстры получалось писать программу одновременно с доказательством корректности.

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 18:16 
У Кнута в «Искусстве программирования» примеры доказательств тоже есть. Кнут, понятно, уже позже Дейкстры, но может быть толк.

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 13:29 
И какой код быстрее исполнится, первый или второй?

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 13:53 
Ktina в сообщении #1324130 писал(а):
Каким образом?
Мне знакомо понятие математического доказательства. А про информатическое доказательство впервые слышу.
Обычно индуктивно, через сохранение инварианта цикла. Инвариант цикла - это истинное логическое выражение над значениями переменных в коде, которое остаётся истинным при переходе к следующей итерации. Если инвариант цикла сохраняется, он истинный на первом входе в цикл и цикл останавливается, то на выходе из цикла инвариант цикла будет истинным.

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

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 14:51 
Моя попытка реализации функции:
код: [ скачать ] [ спрятать ]
Используется синтаксис 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;
}
 

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 18:14 
За всю предыдущую жизнь не видел столько странных реализаций этой функции. Хотя видел их немало :-)

 
 
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 18:54 
Оптимизация. В начальном посте лучший вариант по быстродействию, но через раз он делает лишний шаг в цикле.
Используется синтаксис 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;
}
 

 
 
 [ Сообщений: 27 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group