VPF::backtracking/recursion - Форум программистов

Muerto

Дата 3.12.2010, 16:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1207
Регистрация: 23.9.2006

Репутация: 3
Всего: 4

Пытался перевести то что сегодня писал на Java на php

Если не говорить о том что понятие overloading процедурному php не знакомо

Этот скрипт не возвращает верного ответа

Код


<?
function rec($arr, $n){
     return rec2(count($arr)-1, $arr, $n);
}

function rec2($i,$arr, $n){
print_r($arr); echo "-> $i / $n <br/>";
     $answer=false;
        if( ($i==0) && ($arr[$i]==$n) ) {
            $answer=true;
        }else if($i>0){
            $answer=(rec2($i-1, $arr, $n+$arr[$i]))||(rec2($i-1,$arr, $n-$arr[$i]));
        }

     return $answer;
}

$arr=array(2,3,6,8);
$n=-5;
echo rec($arr,$n)?"true":"false";
?>

Я пытался отследить, не пойму в чем дело...
Похоже php ведет себя иначе...
Цель алгорима понять если можно намутить 2-3+6-10 и получить n=-5
он проходит через все возможные варианты

--------------------

Muerto

Дата 3.12.2010, 17:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1207
Регистрация: 23.9.2006

Репутация: 3
Всего: 4

Пару примеров
{2,4,6,10} ответ будет если -5 true -> 2-3+6-10
Если же {5,4,6,3} ответ будет если 11, false

--------------------

Muerto

Дата 3.12.2010, 18:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1207
Регистрация: 23.9.2006

Репутация: 3
Всего: 4

Если есть желание помочь понять что тут не так но задача все же не ясна, дайте знать!

--------------------

skyboy

Дата 3.12.2010, 23:28 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 75
Всего: 260

возьми простые входящие: $arr == array(1), $n == 1 и посмотри сам, почему функция возвращает false. для этого даже компьютер не нужен, достаточно только листа бумаги.

Muerto

Дата 3.12.2010, 23:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1207
Регистрация: 23.9.2006

Репутация: 3
Всего: 4

Проблема решена, кривой пример дал =-(

Вот такая статья в блоге вышла smile

http://learn-php.ru/2010/12/03/php-recursi...82%D0%BE%D0%BC/

Это сообщение отредактировал(а) Muerto - 4.12.2010, 00:01

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Общие вопросы \| Следующая тема »