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 :: Версия для печати :: Вопрос на собеседовании [2]
Форумы портала PHP.SU » PHP » Напишите за меня, пожалуйста » Вопрос на собеседовании

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

16. Haron - 08 Апреля, 2011 - 02:30:53 - перейти к сообщению
Изменил немного код:
PHP:
скопировать код в буфер обмена
  1. <?PHP
  2. function q($n)
  3. {
  4.     if ($n<=2){
  5.         return 1;
  6.     }else{
  7.         return q($n-q($n-1)) . '+' . q($n-q($n-2));
  8.     }
  9. }
  10.  
  11. $k = 0;
  12. while ($k <= 12) {
  13. echo $k . ' : ' . count(explode('+',q($k))) . '<br />';
  14. $k++;
  15. }


На выходе получил:
0 : 1
1 : 1
2 : 1
3 : 2
4 : 4
5 : 8
6 : 16
7 : 32
8 : 64
9 : 128
10 : 256
11 : 512
12 : 1024

Может натолкнёт на решение?
17. Akar - 08 Апреля, 2011 - 03:04:16 - перейти к сообщению
Haron, хм ну тогда все просто 2^$n-2. Но это не верно.

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

Так что нужно думать дальше. Ктонить попробуйте мой вариант плз
18. Haron - 08 Апреля, 2011 - 05:30:13 - перейти к сообщению
Дело в том, что таким образом я попытался посмотреть, а что-же он там собственно, считает?
Выяснилось, что считает он единички:

PHP:
скопировать код в буфер обмена
  1. echo $k . ' : ' . q($k) . '<br />';


На выходе:
0 : 1
1 : 1
2 : 1
3 : 1+1
4 : 1+1+1+1
5 : 1+1+1+1+1+1+1+1
6 : 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
7 : 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
8 : <здесь их уже будет 64>
9 : <128>
10: ...

Я чувствую, что разгадка близка, и гениально проста.
19. Akar - 08 Апреля, 2011 - 05:50:36 - перейти к сообщению
Нет Вы не правы. Разберем несколько примеров в ручную

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
20. Haron - 08 Апреля, 2011 - 06:14:04 - перейти к сообщению
Я знаю что я неправ Улыбка

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

PHP:
скопировать код в буфер обмена
  1.         return q($n-q($n-1)) . '+' . q($n-q($n-2));


Я убил суммирование обеих выражений, справа и слева, а вместо суммирования - вывел + текстом (чисто для наглядности).

В итоге получил те самые результаты. Всё что я хотел - это чисто умозрительное упрощение.
21. Akar - 08 Апреля, 2011 - 06:16:46 - перейти к сообщению
И тем самым Вы полностью переписали функцию, а значит она даст не верный результат. Отменять сумирвоание нельзя.
22. Haron - 08 Апреля, 2011 - 06:22:45 - перейти к сообщению
Akar пишет:
И тем самым Вы полностью переписали функцию, а значит она даст не верный результат. Отменять сумирвоание нельзя.


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

Вообще-то, по условию задачи - допустимо переделать алгоритм. Т.е. можно сделать альтернативный алгоритм, который будет работать в N раз быстрее, но при этом делать то же самое.
23. Akar - 08 Апреля, 2011 - 06:32:44 - перейти к сообщению
Дык и переделывайте но так чтоб она работала единтично предыдущей )
Но судя по тому что я просчитал в ручную, нету никакой зависимости у функции. Так что пока считаю что мой вариант с циклом и массивом единственно правильное решение.... через 2 часа опробую наконец.
24. Haron - 08 Апреля, 2011 - 06:44:54 - перейти к сообщению
Мне кажется - безперспективно.

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

Отсюда и нужно копать я думаю.
25. Akar - 08 Апреля, 2011 - 06:49:06 - перейти к сообщению
Задание всеже на программирование, а не на математику. Плюс оно было на фоне довольно простых заданий. Да и время на него было максимум пол часа.
(Добавление)
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(105000);
  17. ?>



окончательный вариант. как видите работает не то что с 77 а с 105000.
Жаль что на собеседование я не догадался.. а ведь знал что нужно рекурсию заменить на цикл.
26. MAXUS - 08 Апреля, 2011 - 08:45:44 - перейти к сообщению
Akar пишет:
Рекурсию сохранять не обязательно.


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

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

PHP:
скопировать код в буфер обмена
  1. $res=array();
  2.  
  3. function q($n){
  4.         global $res;
  5.         if ($n<=2){
  6.                 return 1;
  7.         }elseif($res[$n]){
  8.                 return $res[$n];       
  9.         }else{
  10.                 $res[$n]=q($n-q($n-1))+q($n-q($n-2));
  11.                 return q($n-q($n-1))+q($n-q($n-2));
  12.         }
  13. }

(Добавление)
Akar пишет:
Да и время на него было максимум пол часа.


При $n=77, функция ввернет 24, кстатиУлыбка
(Добавление)
Akar пишет:
Да и время на него было максимум пол часа.

У меня ощущение, что это задание на проверку системного образования. Предполагаю, что подобные конструкции разбирают в ВУЗах и, если ты знаешь, как это делать, то решишь за 5 минут. А мне часа 4 в общей сложности понадобилось.
27. Akar - 08 Апреля, 2011 - 09:03:00 - перейти к сообщению
Мой вариант более оптимизирован.
Ваш загибается на цифре 1 250, мой отрабатывает при 105 000
Кто круче?Улыбка
(Добавление)
При $n=77 функции возвращают 42 ), что Ваша, что моя.
28. movEAX - 08 Апреля, 2011 - 10:05:15 - перейти к сообщению
Akar пишет:
Ваш загибается на цифре 1 250, мой отрабатывает при 105 000

PHP:
скопировать код в буфер обмена
  1. function q($n){
  2.     static $cache;
  3.     if ($n<=2){
  4.         return 1;
  5.     }elseif($cache && isset($cache[$n])){
  6.         return $cache[$n];
  7.     }else{
  8.         $cache[$n] = q($n-q($n-1))+q($n-q($n-2));
  9.         return $cache[$n];
  10.     }
  11. }
  12.  
  13. echo q(1500000); //750658


При добавлении еще одного нулика линь убил процесс через определенное время.

На 3000000 уже кряхтит: 1494578
29. Akar - 08 Апреля, 2011 - 10:26:20 - перейти к сообщению
movEAX, похоже у меня чтото с настройками апача но Ваш вариант тоже умирает на 1250.

Попробуйте мой, он должен быть легче т.к. там нету вызовов функций, только обработка массива
30. movEAX - 08 Апреля, 2011 - 10:52:19 - перейти к сообщению
И вправду: 9999999 - 4891202
Akar пишет:
у меня чтото с настройками апача

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

 

Powered by ExBB FM 1.0 RC1