2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:20 
Аватара пользователя


01/12/11

8634
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 
Аватара пользователя


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

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


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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:40 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Нормальное решение.

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

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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:43 
Аватара пользователя


01/12/11

8634
Geen в сообщении #1324129 писал(а):
Такие вещи лучше доказывать. :-)

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

-- 03.07.2018, 10:43 --

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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 10:47 
Заслуженный участник
Аватара пользователя


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

Стоило бы написать
Используется синтаксис 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 
Аватара пользователя


01/12/11

8634
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 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Ktina в сообщении #1324138 писал(а):
О каких статьях Вы ведёте речь?

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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 17:21 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 18:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение03.07.2018, 18:16 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 13:29 


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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 13:53 


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

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

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 14:51 


03/10/06
826
Моя попытка реализации функции:
код: [ скачать ] [ спрятать ]
Используется синтаксис 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 


05/09/12
2587
За всю предыдущую жизнь не видел столько странных реализаций этой функции. Хотя видел их немало :-)

 Профиль  
                  
 
 Re: Фибоначчи на JavaScript, ошибки новичков
Сообщение04.07.2018, 18:54 


03/10/06
826
Оптимизация. В начальном посте лучший вариант по быстродействию, но через раз он делает лишний шаг в цикле.
Используется синтаксис 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  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group