Проблема в рекурсивной фукции?

Question

[Андрей Бойченко]

Добрый вечер! Есть задача поиска ближайшего значения. Например есть товар с ценой 12, кто-то ставить такую же цену, система должна понять, что товар с такой ценой есть и добавить 0.1 к цене. Чтобы вышло 12.1, но если и эта цена занята то добавить еще 0.1.

В двух словах, нужно найти ближайшую от введенной, свободную цену с шагом 0.1

public function findCorrectClosestPrice($price, $products)
    {
        foreach ($products as $product)
        {
            if ($product->price === $price)
            {
                $price = $price + 0.1;
                return $this->findCorrectClosestPrice($price, $products);
            }
            else
            {
                return $price + 0.1;
            }
        }

        return null;
    }

Проблема в том, что если уже есть цены 12, 12.1 и я допустим ставлю 12, то появляеться 2 товара с ценой 12.1, хотя должа установиться 12.2. Вопрос простой, но я правда не вижу ошибки в своем коде, тыкните носом, очень прошу.

Comments

[Дмитрий]

Помоему чтоб такое заработало, надо $product передавать по ссылке

[Андрей Бойченко]

Дмитрий, попробовал, ничего не изменилось

Answer 1

[twobomb]

Кстате можно и без рекурсии. Только при сравнении делайте округление, а то может оказаться что 12.3 != 12.3 , ох уж эти числа с плавающей точкой и php...

public function findCorrectClosestPrice($price, $products){
	do{
		$finded = false;
	foreach ($products as $product){		
			if (round($product->price,1) == round($price,1)){
				$price += 0.1;
				$finded = true;
				break;
			}
	}
	}while($finded);
    return $price;
}

P.S. Рекурсией будет так

public function findCorrectClosestPrice($price, $products){
	foreach ($products as $product)		
			if (round($product->price,1) == round($price,1))
				return $this->findCorrectClosestPrice($price + 0.1,$products);
    return $price;
}

Comments

[Adamos]

Да, это будет работать. Но сложность O(n^3), как я понимаю. Если не больше. Для каждого элемента крутятся и крутятся циклы по всему массиву вместо того, чтобы отсортировать его заранее и работать только с ближайшими соседями.

[twobomb]

Adamos, Согласен, но вопрос был не по оптимизации.

Answer 2

[Adamos]

Так возьмите массив [12, 12.1, 12] и прокрутите свой код.
Сами увидите, что ваша функция делает отнюдь не то, что вы заявляете.
Вам нужно делать не рекурсию, а сортировку по цене вверх и вложенный цикл.
Как только во внешнем цикле находится повтор, запускаете внутренний, чтобы определить, куда переставить текущий элемент. Переставляете, назначаете ему цену предыдущего + 0.1 и возвращаетесь на то же место внешнего цикла, поскольку массив сполз назад из-за перестановки.

Comments

[Андрей Бойченко]

А почему рекурсия здесь не подойдет и ваше решение, мне выглядит сумбурным, вероятно я не до конца понимаю как реализовать ваш пример...

[Adamos]

Андрей Бойченко, ваша рекурсивная функция находит первую же цену в массиве, не совпадающую с данной, и радостно возвращает эту цену + 0.1, не проверяя, нет ли товара с такой ценой. Я бы ее просто выкинул и начал думать сначала.

[tendkuh]

очень хороший ответ

[Adamos]

tendkuh, спасибо. Не могу сказать того же о богатстве вашей фантазии, к сожалению...

[tendkuh]

Adamos, супер, спасибо вам за ответ