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

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Вопрос на собеседовании

 PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


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

> Без описания
Akar
Отправлено: 07 Апреля, 2011 - 19:53:38
Post Id


Новичок


Покинул форум
Сообщений всего: 18
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




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

Итак дана функция:
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. ?>


Отредактировано модератором: Champion, 07 Апреля, 2011 - 20:53:01
 
 Top
Мелкий Супермодератор
Отправлено: 07 Апреля, 2011 - 20:13:49
Post Id



Активный участник


Покинул форум
Сообщений всего: 11926
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 618 раз(а)




Akar пишет:
Как видно тут рекурсия и очень убийственная

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

Это уж не говоря о синтаксической ошибке, но это, видимо, опечатка.

(Отредактировано автором: 07 Апреля, 2011 - 20:17:44)



-----
PostgreSQL DBA
 
 Top
tr0y
Отправлено: 07 Апреля, 2011 - 20:43:24
Post Id


Новичок


Покинул форум
Сообщений всего: 25
Дата рег-ции: Сент. 2010  


Помог: 0 раз(а)




А чему равна $n?
 
 Top
movEAX
Отправлено: 07 Апреля, 2011 - 20:46:54
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 750
Дата рег-ции: Авг. 2009  


Помог: 16 раз(а)




По-моему тут кодобред.. Где вы тут рекурсию увидели?


-----
армия.. самое убогое место
 
 Top
Akar
Отправлено: 07 Апреля, 2011 - 22:11:59
Post Id


Новичок


Покинул форум
Сообщений всего: 18
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




Исправил )

сорри писал втарапях )
 
 Top
movEAX
Отправлено: 07 Апреля, 2011 - 22:34:56
Post Id



Частый посетитель


Покинул форум
Сообщений всего: 750
Дата рег-ции: Авг. 2009  


Помог: 16 раз(а)




А вот это уже интересней, пока вариантов нет)


-----
армия.. самое убогое место
 
 Top
OrmaJever
Отправлено: 07 Апреля, 2011 - 23:30:06
Post Id



Активный участник


Покинул форум
Сообщений всего: 7540
Дата рег-ции: Янв. 2010  
Откуда: Чернигов


Помог: 299 раз(а)




функция не имеет смысла.
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


-----
Если вы хотя бы 3-4 раза не решите всё выкинуть и начать заново - вы явно что-то делаете не так.
 
 Top
IgVlGr
Отправлено: 07 Апреля, 2011 - 23:47:39
Post Id


Новичок


Покинул форум
Сообщений всего: 14
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




Akar пишет:
даже при $n=3, апачь ругаеться

При $n=3 Апач ругаться не должен
 
 Top
Akar
Отправлено: 07 Апреля, 2011 - 23:51:53
Post Id


Новичок


Покинул форум
Сообщений всего: 18
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




*facemoptable*

точно ))) чуствую себя по идиотски. пробывал перебрать до 5ти на собеседовании, но не получилось.. видать перенервничал.
 
 Top
Мелкий Супермодератор
Отправлено: 08 Апреля, 2011 - 00:05:10
Post Id



Активный участник


Покинул форум
Сообщений всего: 11926
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 618 раз(а)




OrmaJever пишет:
При любом $n ответ всегда 3

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

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

Как-то не похоже.


-----
PostgreSQL DBA
 
 Top
IgVlGr
Отправлено: 08 Апреля, 2011 - 00:28:34
Post Id


Новичок


Покинул форум
Сообщений всего: 14
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




Может, я что-то не понимаю, но задачу можно переписать так:
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)

Изменить условие.
 
 Top
OrmaJever
Отправлено: 08 Апреля, 2011 - 01:00:06
Post Id



Активный участник


Покинул форум
Сообщений всего: 7540
Дата рег-ции: Янв. 2010  
Откуда: Чернигов


Помог: 299 раз(а)




Мелкий точно Растерялся Я сидел на листке расписывал как она работает но так и не нашёл закономерности Хм

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



-----
Если вы хотя бы 3-4 раза не решите всё выкинуть и начать заново - вы явно что-то делаете не так.
 
 Top
Akar
Отправлено: 08 Апреля, 2011 - 01:02:35
Post Id


Новичок


Покинул форум
Сообщений всего: 18
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




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. //Возможно чтото напутал но пишу в попыхах )

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

 
 Top
MAXUS
Отправлено: 08 Апреля, 2011 - 01:51:35
Post Id


Посетитель


Покинул форум
Сообщений всего: 329
Дата рег-ции: Апр. 2011  


Помог: 7 раз(а)




Akar пишет:

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


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

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


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


Рекурсию потерялУлыбка Там не все так просто. Саму рекурсию менять нельзя, насколько я понимаю, т.к. результат изменится. Но мысль, имхо, правильная.
 
 Top
Akar
Отправлено: 08 Апреля, 2011 - 02:21:22
Post Id


Новичок


Покинул форум
Сообщений всего: 18
Дата рег-ции: Апр. 2011  


Помог: 0 раз(а)




Рекурсию сохранять не обязательно. Мы последовательно вычусляем все значиения от $n=1 и выше, а патом вместо вызова
q(n) смотрим уже готовый результат и подставляем конкретную цифру. Апача под рукой нет но вроде должно работать.

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

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


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

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

 
 Top
Страниц (3): [1] 2 3 »
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Напишите за меня, пожалуйста »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB