C ++ рекурсия: найти все возможные комбинации покупок товаров с разными ценами
Предположим, у меня есть n денег, а пункт A стоит 1, пункт B стоит 2 и пункт C стоит 3.
Как я могу распечатать все возможные комбинации покупок с заданной суммой денег?
Вывод для n = 3 должен выглядеть так: C — A, B — B, A — A, A, A
Решение, к которому я пришел, к сожалению, не работает.
void purchase(int money)
{
if (money == 0)
{
return;
}
else
{
if (money > 3)
{
cout << "C ";
purchase(money - 3);
}
else if (money > 2)
{
cout << "B ";
purchase(money - 2);
}
else if (money == 1)
{
cout << "A ";
}
}
}
Решение
Вы должны следить за своим путем, а также проверять правильные значения и включать все возможности.
void purchase(int money, string path = "")
{
if (money == 0)
{
return;
}
if (money > 2)
{
string p = path + "C ";
cout << p << "- ";
purchase(money - 3, p);
}
if (money > 1)
{
string p = path + "B ";
cout << p << "- ";
purchase(money - 2, p);
}
string p = path + "A ";
cout << p << "- ";
purchase(money - 1, p);
}
Это решение перечисляет все возможные покупки, в том числе те, которые не исчерпывают вашу наличность.
Другие решения
Используя вспомогательный буфер и буферную функцию, эта операция может быть легко реализована. Вот str работает как буфер, где я сохраняю встреченные буквы до сих пор, пока depth используется для поддержания уровня.
void purchase_impl(int money, char * str, int depth) {
if (money == 0) {
if (depth > 0) {
str[depth] = '\0';
std::cout << str << std::endl;
}
return;
}
if (money >= 3) {
str[depth] = 'C';
purchase_impl(money-3, str, depth+1);
}
if (money >= 2) {
str[depth] = 'B';
purchase_impl(money-2, str, depth+1);
}
if (money >= 1) {
str[depth] = 'A';
purchase_impl(money-1, str, depth+1);
}
}
void purchase(int money)
{
char * str = (char *) malloc(money+1);
purchase_impl(money, str, 0);
free(str);
}