Вопрос на собеседовании

Изменил немного код:

-----
И чё?

Haron, хм ну тогда все просто 2^$n-2. Но это не верно.

Посчитал на листочке у меня вышло:
3: 2
4: 3
5: 3
6: 4
7: 5

Так что нужно думать дальше. Ктонить попробуйте мой вариант плз

(Отредактировано автором: 08 Апреля, 2011 - 05:58:09)

Дело в том, что таким образом я попытался посмотреть, а что-же он там собственно, считает?
Выяснилось, что считает он единички:

-----
И чё?

Нет Вы не правы. Разберем несколько примеров в ручную

N= 3
q(3-q(3-1))+q(3-q(3-2)) = q(3-q(2))+q(3-q(1)) = q(3-1)+q(3-1) = q(2)+q(2) = 1+1 = 2

N=4
q(4-q(4-1))+q(4-q(4-2)) = q(4-q(3))+q(4-q(2)) = q(4-2)+q(4-1) = q(2)+q(3) = 1+2 = 3

N=5
q(5-q(5-1))+q(5-q(5-2)) = q(5-q(4))+q(5-q(3)) = q(5-3)+q(5-2) = q(2)+q(3) = 1+2 = 3

N=6
q(6-q(6-1))+q(6-q(6-2)) = q(6-q(5))+q(6-q(4)) = q(6-3)+q(6-3) = q(3)+q(3) = 2+2 = 4

N=7
q(7-q(7-1))+q(7-q(7-2)) = q(7-q(6))+q(7-q(5)) = q(7-4)+q(7-3) = q(3)+q(4) = 2+3 = 5

(Отредактировано автором: 08 Апреля, 2011 - 06:18:53)

Я знаю что я неправ

Обратите внимание, как я вывел данные из функции:

-----
И чё?

И тем самым Вы полностью переписали функцию, а значит она даст не верный результат. Отменять сумирвоание нельзя.

Нельзя. Но меня интересует её поведение. Изучать поведение - ведь можно? В любом случае всегда можно вернуть всё назад как было.

Вообще-то, по условию задачи - допустимо переделать алгоритм. Т.е. можно сделать альтернативный алгоритм, который будет работать в N раз быстрее, но при этом делать то же самое.

-----
И чё?

Дык и переделывайте но так чтоб она работала единтично предыдущей )
Но судя по тому что я просчитал в ручную, нету никакой зависимости у функции. Так что пока считаю что мой вариант с циклом и массивом единственно правильное решение.... через 2 часа опробую наконец.

Мне кажется - безперспективно.

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

Отсюда и нужно копать я думаю.

-----
И чё?

Задание всеже на программирование, а не на математику. Плюс оно было на фоне довольно простых заданий. Да и время на него было максимум пол часа.
(Добавление)

Попробуй из интереса свой вариант.

А работать будет ватета:

Мой вариант более оптимизирован.
Ваш загибается на цифре 1 250, мой отрабатывает при 105 000
Кто круче?
(Добавление)
При $n=77 функции возвращают 42 ), что Ваша, что моя.

-----
армия.. самое убогое место

movEAX, похоже у меня чтото с настройками апача но Ваш вариант тоже умирает на 1250.

Попробуйте мой, он должен быть легче т.к. там нету вызовов функций, только обработка массива

(Отредактировано автором: 08 Апреля, 2011 - 10:28:10)

И вправду: 9999999 - 4891202

я из консоли запускаю

(Отредактировано автором: 08 Апреля, 2011 - 10:53:16)

-----
армия.. самое убогое место