45 и 46 чичла находит правильно а вот 47 выдает -1323752223, это притом что тип беззнаковый, не могу понять почему так, тем более что это упражнение из книги и там нормально находит и 100 число.



Модератор: не забываем пользоваться кнопочкой "Код"

1. Возвращаете-то вы int, о какой уж тут беззнаковости говорить...
2. + переполнение...
 
3. 100-е число Фибоначчи равно 354224848179261915075, а максимум 64-битного беззнакового - 18446744073709551615. Так что что-то не очень версится в просто так, без ухищрений вычисленное сотое число Фибоначчи...


Это сообщение отредактировал(а) disputant - 23.8.2012, 17:45

Спасибо за ответ, глупая ошибка, значит 100 число с unsigned int неправильно выдаст?

> значит 100 число с unsigned int неправильно выдаст? 

> 100-е число Фибоначчи равно 354224848179261915075
Ты бы лучше спросил disputant как он это посчитал   
Вики не в счёт

Ну так C++ - не единственный язык.   Если взять что-то с бесконечнозначной арифметикой и, по-возможности, функциональное, то это несложно. Вот, например, на Прологе

Можно заменить int на double - для больших чисел результат будет хотя и приближённый, но правильный, отрицательных чисел не будет. Но при очень больших n тоже будет переполнение.

Ну а как найти числа фибоначчи на некотором интервале [m;n]. Это для меня несколько затруднительная задача. Ведь так надо сперва найти первый элемент фибоначчи. А как это сделать? То есть я так понимаю что надо использовать цикл for (i=M; i<N;i++) и если встречается первое число фибонач. надо запомнить его и выходит из цыкла но тогда такой алгоритм должен выглядять for(i=m; i<n; i++)  if (i=fibo(j)) {f1=i} break; так тогда еще надо цыкл и для j. Вообщем тогда выходит что и последний элемент фибон. из интервала тоже надо находит. То есть надо как то взаимосвязать i и j.

не надо. есть явная (не рекуррентная) формула (т.н. Формула Бине)

Ой не думаю что там аж такие формулы применяются. Тем более хотел бы увидеть формулу бине на примере алгоритма. В общем то проблема в том что например надо k-значные числа вывести. Например од милиона до 10 млн. Для чего тогда проходить цыкл от 0 до 1млн. Хотя если применять рекуренцию то она и так очень большые расчеты делает начиная с наименьшых ибо надо знать значение предыдущих. В моем задание стояла задача найти наиболее эфективный метод. А рекурсия это вряд ли. И еще цыкл до числа m. Знаю есть формула где как раз числа добавляются в сравнение с предыдущим уровнем. Но полюбому надо знать первое число в интервале и потом от него отталкиватся и уже потом проверять меньше ли следующи числа фибоначчи конца интервала. Хотя кончено интегви может быть и  17-19, и 173-284, и 10000-200000. Ну полюбому число m как то связано с предыдущим числом фибоначчи. Да и каждое такое число имеет свои номер в порядке этих чисел.   

а, так нужно не n-e число, а число из интервала... я не понял сразу


просто последовательно рассчитывать, типа



если надо считать числа не по порядковому номеру, а в указанном интервале, то переполнение не имеет значения: если числа, определяющие границы интервала, представимы в компьютере, то и при расчете переполнения не будет


это алгоритм (логарифмической сложности) возведения матрицы 2x2 в степень. тут его смысла использовать нет, т.к. нужно не одно число, а последовательность

Это сообщение отредактировал(а) baldina - 23.10.2013, 00:04

Может случиться так, что первое же число Фибоначчи после m вызовет переполнение, тогда цикл

пойдёт по-новой...

Может случиться и так, что первое же число Фибоначчи после n вызовет переполнение))))

Добавлено через 7 минут и 10 секунд
если заботиться о переполнении, можно применять проверку вида f0/2+f1/2 < m/2-2

Это не слишком сильно усложняет задачу. Из той же формулы Бине следует, что для подсчета n-ого числа Фибоначчи достаточно просто взять целую часть от f^n/sqrt(5), где f=(1+sqrt(5))/2. Соответственно, если есть нижняя граница интервала x, то номер первого числа, попадающего в интервал, считается как n=log(sqrt(5)*x)/log(f)+1. С верхней границей ситуация аналогична.

это её меняет

 довольно трудоёмко при большом n. даже используя эффективный метод O(logN) при расчете N чисел даст O(NlogN) против O(N) последовательного сложения

Добавлено через 4 минуты и 3 секунды

да, я тоже подумал об этом. использовать разные методы для нахождения первого числа в диапазоне и последующих ТС'у имхо сложновато

Такое условие на фирме мне задавали. Сперва интерва потом k значомкз число. Я так понял в последнем варианте от число от 1 и (k-1) нулей до 1 и k нулей. Но снова таки числом это трудно задать. Потому надо было парсить кажется toChаrArray проверять равно ли количество знаков числу k. Но цыкл фибоначчи начинался от i=0. Тогда наверное надо было применять цыкл while (i) в конце блока его увеличивать на 1 и если число фибоначчи было бы k+1 значное тогда выходить из цыкла. Через брейк. Ну то что я написал о взаимосвязи числа m и числа фибоначчи перед ним я имел ввиду что это число q должно быть как минимум не в два рады меньше m. Может есть какая то формула. Например для 10 это число 8, для  20-13, 100-79. Как и зависимость числа фибон. от порядкового номера i.