Разложить число.

[AlexCooper]

Сообщение от alatar

Не думаю, что это задание из универа. Больше похоже на тестовое задание при приеме на работу.

Тогда печально, для работодателя.

[-De-]

Сообщение от AlexCooper

Тогда печально, для работодателя.

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

[Котяра]

Это почти стандартная "задача о сдаче".
Обычно она реализуется "жадным" алгоритмом. Т.е. выдачей минимального количества монет (благо в условии номиналы подходящие). Но тут доп.условие на строгое количество монет.
Проходимся жадным алгоритмом периодически исключая номиналы, пока получим (или не получим) искомое количество.

[alatar]

Это как раз то, на что я кидал ссылку и о чем говорил Zebestov.

[КорДум]

Сообщение от iflamberg

Да, ладно разлагольствовать. Автор темы уже давным-давно взял решение из №6. Которое, кстати не сработает на сложных случаях, типа:
Номиналы: [1.1, 1, 0.2]
Нарезать 2.3

Но, такой случай не реалистичен, конечно.

Почему не сработает? Я хоть и писал на коленке, но так сходу узреть алгоритмический косяк не могу. А проверять лень =)
Или имеется в виду, что я не учел количество монеток в разложении? Это да.

[iflamberg]

Нарезает же тупо от большего к меньшему. Он нарежет 1.1(остаток 1.2), 1.1 (остаток 0.1), 0.2(остаток -0.1, ошибка).
А надо 1.1, 1, 0.2

[КорДум]

Да, верно, не учел )

[alatar]

Сообщение от -De-

А как растягиваем? Например если монеты 10, 11, 110, число 110, из 11 монет собрать.

На втором проходе исключается номинал использованный для этой ячейки. Если после полного перебора у нас не выполняются условия, то пытаемся добавить "монету" из исходного набора (последовательно берем из набора монету, если условия не выполняются меняем ее на следующую из набора), если дошли до конца исходного набора и условия не выполняются, говорим что решения нет.

Т.е. в начале получим 10 раз по 11. После попытки удлинить получим 10 раз по 10. Прибавляем 11, не получилось. Прибавляем 10, все сошлось.

[Nooob]

ответ такой:

trace(searchCoins(new <Number>[0.01, 0.1, 0.25, 0.5, 1, 5], 2.53, 7));
 
function searchCoins (nominals:Vector.<Number>, sum:Number, n:uint, level:int = 0, result:Vector.<Number> = null):Vector.<Number>
{
	result ||= new Vector.<Number>();
	var length:uint = nominals.length;
	for (var i:int = 0; i < length; i++)
	{
		if (level == n)
		{
			var sumOut:Number = 0;
			for (var j:int = 0; j < n; j++)
			{
				sumOut += result[j];
			}
			if (sumOut == sum)
			{
				return result;
			}
			continue;
		}
 
		result[level] = nominals[i];
		if (searchCoins(nominals, sum, n, level + 1, result) != null)
		{
			return result;
		}
	}
	return null;
}

иногда лучше перебором решить вопрос, чем астронавтить графами или ещё чем в поисках оптимальности. 2-3 мс погоды не сделают

[KumoKairo]

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

package 
{
	import flash.display.Sprite;
 
	public class Main extends Sprite 
	{
		private var nominals:Array;
		private var initialNumber:Number;
		private var quantity:uint;
		public function Main():void 
		{
			nominals = [0.01, 0.1, 0.25, 0.5, 1, 5];
			initialNumber = 2.53;
			quantity = 7;
			extendInitialNumber(nominals, initialNumber, quantity);
		}
		//Функция нахождения наибольшего номинала для искомого числа. возвращает индекс
		private function maximumDivider(_nominals:Array, _number:Number):int
		{
			var i:int = -1;
			while (int(_number / _nominals[++i]) >= 1 && i < _nominals.length);
			return i - 1;
		}
		//Функция нахождения разложения по номиналам.
		//Стоит отметить, что в случае невозможности разложения на заданное количество номиналов, выдаст сообщение
		private function extendInitialNumber(_nominals:Array, _number:Number, _quantity:uint):Array
		{
			var currentNumber:Number = _number;
			var desiredOutput:Array = new Array();
			var counter:uint = 0;
			do
			{
				do
				{
					trace(currentNumber);
					var div:int = maximumDivider (_nominals, currentNumber);
					if (div != -1)
					{
						desiredOutput.push(_nominals[div]);
						currentNumber = toFixed((currentNumber - _nominals[div]),100);
						counter++;
					}
				}
				while (div != -1);
 
				if (counter > _quantity)
				{
					trace("Невозможно разложить число заданным количеством номиналов");
					break;
				}
				else if (counter == _quantity)
				{
					trace("Решение найдено");
					break;
				}
				currentNumber = desiredOutput[int(Math.random() * desiredOutput.length)];
			}
			while (counter != _quantity);
 
			trace(desiredOutput);
			return desiredOutput;
		}
		//Вспомогательная функция округления для избежания ошибок, когда в результате вычитания
		// 2.53 - 1 получается 1.52999999 и прочих присущих AS3 ошибок
		private function toFixed(number:Number, factor:Number):Number
		{
			return (Math.round(number * factor)/factor);
		}
 
	}
 
}