Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770
Форумы портала PHP.SU :: Версия для печати :: Вопрос на собеседовании
Форумы портала PHP.SU » PHP » Напишите за меня, пожалуйста » Вопрос на собеседовании

Страниц (3): [1] 2 3 »
 

1. Akar - 07 Апреля, 2011 - 19:53:38 - перейти к сообщению
Добрый день,
Проходил сегодня собеседование на должность ПХП программиста, и не смог справиться с одним заданием, и теперь мой моск не может выкинуть эту задачку из головы.

Итак дана функция:
PHP:
скопировать код в буфер обмена
  1. q($n){
  2.     if ($n<=2){
  3.         return 1;
  4.     }else{
  5.         return q($n-q($n-1))+q($n-q($n-2))
  6.     }
  7. }

Как видно тут рекурсия и очень убийственная, настолько что даже при $n=3, апачь ругаеться благим матом что нехватает места в оперативке.

Задание переделать алгоритм так чтобы она работала при q(77)

ПС Остольные вопросы были тревиальными, вывести числа до 100 что деляться на 3 и 5, переделать говнокод в ООП стиль, реализовть паттерн singelton и составить пачку мускл запросов.




UPDATE

ответ найден:
PHP:
скопировать код в буфер обмена
  1. <?PHP
  2. function q($n){
  3.     $n--;
  4.     $array[0]=1;
  5.     $array[1]=1;
  6.  
  7.     for ($i=2; $i<=$n; $i++){
  8.        
  9.             $array[$i] = $array[$i-$array[$i-1]]+$array[$i-$array[$i-2]];
  10.             //echo ($i+1).":".$array[$i]."<br>";
  11.            
  12.     }
  13.     echo "Itog:".$array[$n];
  14. }
  15.  
  16. q(77);
  17. ?>
2. Мелкий - 07 Апреля, 2011 - 20:13:49 - перейти к сообщению
Akar пишет:
Как видно тут рекурсия и очень убийственная

Не видно. Переменная $n не инициализирована и при любом значении аргумента функция будет возвращать 1, проследовав по первой ветке условия. Ну и E_NOTICE генерируется, само собой.

Это уж не говоря о синтаксической ошибке, но это, видимо, опечатка.
3. tr0y - 07 Апреля, 2011 - 20:43:24 - перейти к сообщению
А чему равна $n?
4. movEAX - 07 Апреля, 2011 - 20:46:54 - перейти к сообщению
По-моему тут кодобред.. Где вы тут рекурсию увидели?
5. Akar - 07 Апреля, 2011 - 22:11:59 - перейти к сообщению
Исправил )

сорри писал втарапях )
6. movEAX - 07 Апреля, 2011 - 22:34:56 - перейти к сообщению
А вот это уже интересней, пока вариантов нет)
7. OrmaJever - 07 Апреля, 2011 - 23:30:06 - перейти к сообщению
функция не имеет смысла.
CODE (htmlphp):
скопировать код в буфер обмена
  1. $n = 5
  2. (5 - (5 - 1)) + (5 - (5 - 2)) = (5 - 4) + (5 - 3) = 1 + 2 = 3
  3. $n = 34
  4. (34 - (34 - 1)) + (34 - (34 - 2)) = (34 - 33) + (34 - 32) = 1 + 2 = 3

При любом $n ответ всегда 3
8. IgVlGr - 07 Апреля, 2011 - 23:47:39 - перейти к сообщению
Akar пишет:
даже при $n=3, апачь ругаеться

При $n=3 Апач ругаться не должен
9. Akar - 07 Апреля, 2011 - 23:51:53 - перейти к сообщению
*facemoptable*

точно ))) чуствую себя по идиотски. пробывал перебрать до 5ти на собеседовании, но не получилось.. видать перенервничал.
10. Мелкий - 08 Апреля, 2011 - 00:05:10 - перейти к сообщению
OrmaJever пишет:
При любом $n ответ всегда 3

PHP:
скопировать код в буфер обмена
  1. for ($i=2; $i<10; $i++) echo q($i),'<br>';

Цитата:
1
2
3
3
4
5
5
6

Как-то не похоже.
11. IgVlGr - 08 Апреля, 2011 - 00:28:34 - перейти к сообщению
Может, я что-то не понимаю, но задачу можно переписать так:
PHP:
скопировать код в буфер обмена
  1. q($n){
  2.     if ($n<=2){
  3.         return 1;
  4.     }else{
  5.         return q($n)
  6.     }
  7. }

В результате - зацикливание. В первом случае было почти тоже, только аргумент менялся
(можно было написать return q($n-1+2/7+766557-7687+q($n-$n+676))) и тд. Смысл, по моему, тот-же.
Результаты, которые выводит браузер при n>3, видимо, не есть корректными.
Возможно, я не прав.
Akar пишет:
Задание переделать алгоритм так чтобы она работала при q(77)

Изменить условие.
12. OrmaJever - 08 Апреля, 2011 - 01:00:06 - перейти к сообщению
Мелкий точно Растерялся Я сидел на листке расписывал как она работает но так и не нашёл закономерности Хм
13. Akar - 08 Апреля, 2011 - 01:02:35 - перейти к сообщению
IgVlGr пишет:
Боюсь вы не правы. Достаточно хотябы посмотреть на пост выше вашего где до $n=10 скрипт отработал.




Кстати об этом. Промелькнула мысль.

А что если не пытаться сходу отработать скрипт для 77, а начать последовательно с n-1 до n-77 записывая промежуточные значения в масив. Ведь цикл меньше ресурсоемкий процесс чем рекурсия. А от большенства рекурсий мы избавляемся.

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

PHP:
скопировать код в буфер обмена
  1. q($n){
  2.     $n--;
  3.     $array[0]=1;
  4.     $array[1]=1;
  5.  
  6.     for ($i=2; $i<$n; $i++){
  7.        if(isset($array[$i])){
  8.            return $array[$i];
  9.        }
  10.        else{
  11.             $array[$i] = $array[$i-$array[$i-1]]+$array[$i-$array[$i-2]];
  12.             echo $array[$i]."<br>";
  13.        }
  14.     }
  15.     echo $array[$n];
  16.  
  17. }
  18.  
  19.  
  20. //Возможно чтото напутал но пишу в попыхах )
14. MAXUS - 08 Апреля, 2011 - 01:51:35 - перейти к сообщению
Akar пишет:

А что если не пытаться сходу отработать скрипт для 77, а начать последовательно с n-1 до n-77 записывая промежуточные значения в масив.


Ватета здравая мысль. Расписывая ручками дошел до 16, при этом все q($n) до где $n<=15 уже выписаны на бумажке. На $n=16, я к тому же пришелУлыбка Все впредыдущие значения-то вычислены... Для интереса посмотрел сколько циклов эта рекурсия делает на $n=30. оказалось за 4000 зашкаливает. Всяко сохранять уже вычисленные значения быстрее будетУлыбка Только как в массив затолкать пока не дотумкал.

Ваще, занимаясь этой головоломкой, пришел к мысли, что ДНК - это ни что иное, как хитроопая рекурсия.
(Добавление)
Akar пишет:
Добрый день,
Проходил сегодня собеседование на должность ПХП программиста, и не смог справиться с одним заданием, и теперь мой моск не может выкинуть эту задачку из головы.


У меня моск не справляется от вопроса, а куда требуются такие php-программисты?! И прошел ли ты в итоге собеседование, Ну и сколько давалось времени на решение?
(Добавление)
Akar пишет:
//Возможно чтото напутал но пишу в попыхах )[/PHP]


Рекурсию потерялУлыбка Там не все так просто. Саму рекурсию менять нельзя, насколько я понимаю, т.к. результат изменится. Но мысль, имхо, правильная.
15. Akar - 08 Апреля, 2011 - 02:21:22 - перейти к сообщению
Рекурсию сохранять не обязательно. Мы последовательно вычусляем все значиения от $n=1 и выше, а патом вместо вызова
q(n) смотрим уже готовый результат и подставляем конкретную цифру. Апача под рукой нет но вроде должно работать.

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

Было первое в моей жизне собеседование на должность программиста. но оно мне не показалось сложным, ну кроме последнего задания, каторое как мне кажеться я вот щас решил.
Результат неизвестен... особо не надеюсь так как еще не все хитроумные запросы в мускл сумел сделать (бд немного запутаная была и дана не в виде диаграммы, а текстом брр... ) )


ПС никому не нужен кодер работающий за еду и опыт?

 

Powered by ExBB FM 1.0 RC1