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. 

я так ничего не понял 


 

Добавлено @ 14:33
число знаков n в записи неотрицательного числа x по основанию b определяется несложной процедурой


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

Что вы имеете ввиду под основанием? 10. Да если х делить  на 10 так оно никогда не будет 0. Как и на другое иное. Может в коле цыкла должно быть: КОГДА (х>b). Например 1734 =173.4=17.34=1.734-от так действительно просто. И еще код приведу: public class K { int fibo(int f) { if (f=0) return 0; else if (f=1) return fibo (f-1)+fibo(f-2);} System.out.print(fibo(3));}-вот наткнулся на кое недельной давности. Извиняюсь что не по строкам. Нету ПК под руками. Но вот в строки где метод систем ошибки аж 5:identifier expected; ; expected возле числа 3. Illegal start of type возле первой закрывающийся скобки. Вобщем все ошибки возле (fibo(3))  

неужто  

Добавлено через 15 секунд
поделите 5 яблок на 10 человек

Добавлено через 5 минут и 16 секунд
зы. я виноват. надо было добавить, что х целочисленная (мне казалось это очевидным). для нецелых все похоже, только конечно число знаков надо ограничить

Как говорил дедушка один, ученье свет иное тьма. Потому хотел бы знать подход знатоков к такой задаче. Вот есть к-значимое число. Надо найти числа фибон. кпторые имеют или все парные или только первую четную цыфру. Здесь без разложение числа на масив симболов не обойтись. Тем более к-значное число в цыкле не задаш напрямую. Хотя какой то цыкл надо использовать. Или ФО. Или ВАЙЛ. Хотел бы знать ваш подход. Ибо такое задание действительно озадачило.

знатоки спят уже, потому я отвечу


любую численную задачу можно решить без "разложения на массив символов": символьная запись числа это лишь один из вариантов кодирования числа. это кодирование заключается в получении некоторых чисел и преобразования их в символы (цифры). ясно, что для решения достаточно значений цифр, их символьные коды не важны (и могут быть разными в разных кодировках)


вы задачу-то изложите.


т.е. k-значное? в какой системе счисления?


супер. а "к-значимое число" причем тут?

давайте я протелепатирую. задача такая: 
Дано целое число (это число может быть числом Фибоначчи или полученным иным путем, не важно).
Требуется: определить, является его первая цифра в десятичной записи четной или нечетной
Решение: 

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

Здесь я синтезировал две задачи. K-значное число это для того чтобы обозначить интервал. То есть надо вывести все k-зн. числа в которых первая или все цыфры четные/нечетные. Может ваш метод о деление на 10 и подходит. Хотя я не настолько опытный. Но разве разложение числа в масив символов (превращение в строку кажется ничего не даст) не подходит под решение задачи. Тогда надо каждую цыфру превращать в int и проверять не делится ли она на 2. Кажется задача поставлена. Хотя снова. Второй вопрос эфективности: надо как то определить этот интервал что бы не идти от 0 к нему вхолостую?/ Кстати вы код привели: вы сперва проверяете делится ли число на два. Но это надо проверять делится ли первая цифра на 2. То есть эту цыфру надо как то отделить. А если все цифры проверять. Ну хорошо поделили вы например 177 на 2. Выходит 88. И остача 1. Но если будет 176 то остачи не будет. Тогда что первая цифра изменилась как была 1 так и осталась. Зачем на 18 делить . Код точно не помню. А система-10ричная.

Ну что вам слабо написать часть кода хотя бы для обозначание интервала или этих к-значных чисел фибоначчи? Сегодня знатоки еще не должны спать.

От у меня снова вопрос по поводу поиска
на неком интервале [m;n] чисел фибоначчи где одна из цыфр есть нечетной (первая или последняя). То есть основная идея надо найти первое число в интервале.
int t;
while (t) {
                 int  k=fibo(t);
                  if (k>=m AND k=<n) {int j=k;
                                                   while(k) {if (k%2=1) break;
                                                                  int g=k%10;
                                                                  k=g;}
                                                    if(k=0)   {
                                                                  System.out.print(j);
                                                                  System.out.println;
                                                                  }

                                                     }
                  else if (k>n) break;
                  t++;
                  }
               Потом делитьчисло фиб.  на 2 если остача 1 выход из цыкла, если нет уменьшение десятичного разряда и далее повторять цыкл. Хотя догадуюсь что надо do while ибо первую точно не прихопят?