Даны N чисел. Нужно расставить + и * между ними и получить максимум.
К примеру - 1,2,3,1,2,3
Ответ - 1+2*3*1*2*3 = 37
Есть ли у Вас идеи, может алгоритмы какие-либо, или статьи с объяснением решения, поделитесь, пожалуйста.
-
1если первое число 1, то поставить +, а между остальными *, если не нулевые– AR Hovsepyan25 июн 2018 в 23:36
-
Числа всегда положительные?– HolyBlackCat25 июн 2018 в 23:37
-
1@AR Hovsepyan, тоже думал об этом, но мне кажется что тут не всё так просто. А если 1 стоит в середине где-нибудь, например 2,1,1,1,2.– Нормандия Лис25 июн 2018 в 23:51
-
@HolyBlackCat, да, положительные– Нормандия Лис25 июн 2018 в 23:52
-
2Какие ограничения на количество чисел? Кстати, предельное значение тоже важно - в плане реализации уже: нужна ли длинная арифметика или вписываемся в стандартные типы...– Harry26 июн 2018 в 3:51
1 ответ
Вы можете использовать рекурсию и сделать это перебором вариантов. Не самая красивая реализация в плане производительности, но в плане читаемости очень даже.
Получится дерево переборов. В листах дерева (когда будет получена полная подстановка знаков) вычисляете выражение и сравниваете с максимумом.
Код будет что-то наподобие такого:
using namespace std;
vector<char> signs = { '+', '-', '*', '%', '/' };
int maxValue = 0;
vector<char> combin;
int calculateExpression(const vector<int> &, const vector<char> &);
void recursiveFunction(const vector<int> & values, vector<char> & combination, size_t level)
{
if(level == combination.size()) // Комбинация сформирована, можно вычислять.
{
int value = calculateExpression(values, combination);
if(value > maxValue) {
combin = combination;
maxValue = value;
}
return;
}
for(int i = 0; i < signs.size(); i++) {
combination[level] = signs[i];
recursiveFunction(values, combination, level + 1);
}
}
int main()
{
vector<int> digits { 1, 2, 3, 4, 5};
vector<char> combinations(digits.size() - 1);
recursiveFunction(digits, combinations, 0);
cout << "Максимальное значение: " << maxValue << endl;
cout << "Комбинация знаков: ";
for(int i = 0; i < combin.size(); ++i) {
cout << digits[i] << " " << combin[i] << " " << digits[i + 1] << " ";
}
cout << endl;
}
Функцию calculateExpression напишите сами. И вектора также исправите на обычные массивы, если нужно.
Что касается вычисления выражения, то здесь вам в помощь обратная польская запись. Реализуется просто, статей предостаточно.
-
1Необязательно рекурсию здесь делать, если изначально поставить все знаки как
+
, то дальше можно просто перебирать маски. Для N чисел будет N-1 позиций куда можно поставить*
, это можно представить как число из N-1 бит, и получим 2^(N-1) комбинаций, которые нужно проверить. Но мне кажется что здесь нужно идти от подпоследовательностей единиц в последовательности. Только единицы мешают поставить везде знаки умножения 26 июн 2018 в 8:42 -
Да, необязательно. Как уже сказал, МОЖНО использовать рекурсию. Перебор циклами, к сожалению, не сделаешь, если не знаешь заранее, сколько можно вариантов перебрать. Данное же решение обладает вполне неплохой гибкостью.– Desmoond26 июн 2018 в 8:47
-
1
-
1