Пянтичное: опять фибоначчи

[venco]

А чего его запоминать, если вывести можно.

[vopros]

если бы что то подобное задаче фиб всплыло бы в реальноп проекте, то простейший вариант скорее всего бы выглядел так

Code: Select all

public class Fib {
	static int[] fibs = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ... xxxxx};
	
	static int getFibAt(int n) {
		try {
			return fibs[n-1];
		} catch (Exception e) {
			throw new InvalidParameterException(n+" is too big for this platform");
		}
	}
}

потому что это как бы константы.

[venco]

ЗЫ venco, нагуглил небось?

Обижаешь.

[Boriskin]

К слову, если углубить тему фиббоначах в программировании - то можно перетереть почему такой формулой не стоит пользоваться в реале...

[8K]

посчитать ... сумму целых чисел от 1 до N

А нафига считать, когда имеется аналитический ответ N*(N+1)/2 ?

Это же для затравки только.

Я понимаю, что кандидат может обидеться, что его всерьез не воспринимают. Если он в состоянии не накосячить в пяти строках кода, я усложню задачу. Например, пусть посчитает сумму каждого пятого числа в диапазоне. Или, скажем, пусть N неизвестно, но есть предикат, который для каждого X за O(1) времени говорит, является ли N строго меньше X. Или не за O(1).

Или вы предлагаете сразу со сложного начинать? Так ведь нам и юниоры нужны, с неубитым истимом.

[АццкоМото]

Ответишь вам про Фибоначчи, вы еще что-нибудь спросите. И еще. И еще. Пока не утопите. Потому что этого требует ваше ацки мото. Я давно понял: если начинают спрашивать какие-то голово%бки, можно вставать и уходить. Потому что им никто не нужен, они просто так развлекаются.

Если вам вычисление фибоначчи в лоб без всяких там оптимизаций кажется головоломкой, то нужно не "вставать и уходить", а не приходить вовсе.
Я бы не стал спрашивать чего-то еще. Я бы стерпел пару ошибок. Все что хотелось - увидеть, что чел хоть как-то умеет какой-то код написать. Все.

[8K]

ЗЫ venco, нагуглил небось?

Обижаешь.

В наше время мат. индукцию и простейшие операции с матрицами преподавали в школе, хотя и факультативно. Это в деревне, не в городе.

[oshibka_residenta]

Век живи, век учись.
Но запоминать все равно не буду.

ЗЫ venco, нагуглил небось?

Решается примерно как диффур. Ищем решение в виде а^n, получаем квадратное уравнение. Все.

[olis]

А что - кому то реально требуется вся эта математика на работе?

[avitya]

Конечно. Вы же хотите обоснованно говорить о сложности ваших алгоритмов. Не все формочки ресуют, так сказать...

[vopros]

Не все формочки ресуют, так сказать...

это точно, математиков желательно не допускать к рисованию формочек

[olis]

Конечно. Вы же хотите обоснованно говорить о сложности ваших алгоритмов. Не все формочки ресуют, так сказать...

Не все, согласен. Я больше в ядре ковыряюсь, сейчас вот криптографией занимаюсь. Как то арифметикой обхожусь без матриц и дифф уравнений.

[АццкоМото]

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

[avitya]

Конечно. Вы же хотите обоснованно говорить о сложности ваших алгоритмов. Не все формочки ресуют, так сказать...

Не все, согласен. Я больше в ядре ковыряюсь, сейчас вот криптографией занимаюсь. Как то арифметикой обхожусь без матриц и дифф уравнений.

Я тяжело себе представляю любую _инновационную_ работу в криптографии без серьёзного знания теории чисел, матриц и анализа.
А реализация алгоритмов, которые уже кто-то придумал -- да там особо матаппарата не надо.

[Boriskin]

ЗЫ venco, нагуглил небось?

Обижаешь.

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

[vopros]

дв.

[Flash-04]

Я тяжело себе представляю любую _инновационную_ работу в криптографии без серьёзного знания теории чисел, матриц и анализа.

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

[vopros]

пока все математики тут, подскажите, как решать такую задачу
2^(3^(4^(5^6)))
2^3 = 8
существует ли формула ?
я смог написать итеративный псевдо код, но работающий не смог, число слишком уж большое.

[Boriskin]

Нужна реализация числа любой величины, тогда заработает.

[avitya]

Я тяжело себе представляю любую _инновационную_ работу в криптографии без серьёзного знания теории чисел, матриц и анализа.

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

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

[venco]

пока все математики тут, подскажите, как решать такую задачу
2^(3^(4^(5^6)))
существует ли формула ?

А в чём задача? Число это содержит порядка 10^14910 десятичных цифр. Всё равно записывать некуда - в терабайте меньше 10^13 десятичных цифр.

[vopros]

Нужна реализация числа любой величины, тогда заработает.

эт понятно, есть такая реализация на яве, проблема в памяти, ну не влазит никак.
но все таки интересно, есть ли формула для такой последовательности

Code: Select all

2^(3^(4^(5^6)))

[venco]

но все таки интересно, есть ли формула для такой последовательности

Code: Select all

2^(3^(4^(5^6)))

Дык, вот она - формула.

[vopros]

пока все математики тут, подскажите, как решать такую задачу
2^(3^(4^(5^6)))
существует ли формула ?

А в чём задача? Число это содержит порядка 10^14910 десятичных цифр. Всё равно записывать некуда - в терабайте меньше 10^13 десятичных цифр.

вы еще раз подтвердили, что практически не решаема,
но интересно, как у вас получилось 10^14910 ?

[venco]

Число это содержит порядка 10^14910 десятичных цифр.

Я "немного" ошибся - пропустил одну степень. На самом деле только количество десятичных цифр содержит порядка 10^9407 цифр. Так что простой вопрос об ответе вообще бессмысленен.
Тем не менее, можно посчитать, например 10 последних цифр.