Как найти произведение элементов массива, которые расположены между максимальным и минимальным элементами?
-
А если все элементы равны? А если минимальных элементов много?– VladD28 ноя 2016 в 16:51
-
@VladD, это второй этап, не спешите, мы еще с Вами увидим эти вопросы ))))– isnullxbh28 ноя 2016 в 16:53
-
@VladD может сразу ссылку на вопросы о длинном умножении чисел? А то не влезет в __int128– pavel28 ноя 2016 в 16:53
-
1@pavel: Хм. Нужно произведение от минимума до текущего элемента, текущее произведение от текущего минимума до кекущего максимума, ну и сами текущий минимум и текущий максимум. Вроде достаточно. Если так прокатит, можно вполне написать читабельно.– VladD28 ноя 2016 в 17:03
-
6@Даша Новикова Максимальных и минимальных элементов может быть много. Более того диапазон между максимальным и минимальным элементами может отличаться от диапазона между минимальным и максимальным элементами. Поэтому уточните условия задачи. Например, задача может звучать так: найти произведение элементов в диапазоне от первого минимального до последнего максимального элемента, или как-нибудь по-другому.– Vlad from Moscow28 ноя 2016 в 17:28
4 ответа
Решение не лучшее, далеко не лучшее, но опробуйте:
int data[] = { 2, 4, 5, 2, -3, 5, 2, 33, 5, 3, -45, 2 };
std::pair<int *, int *> pr = std::minmax_element( std::begin( data ), std::end( data ) );
if( std::distance( std::begin( data ), pr.second ) < std::distance( std::begin( data ), pr.first ) )
std::swap( pr.first, pr.second );
if( pr.first != pr.second && ++pr.first != pr.second )
{
int res = std::accumulate( pr.first, pr.second, 1, std::multiplies<int>() );
}
-
-
@Qwertiy, там ведь префиксный оператор ++, он ведь там не просто так ) 29 ноя 2016 в 10:09
-
Я вообще-то хотел вот это заменить:
if( std::distance( std::begin( data ), pr.second ) < std::distance( std::begin( data ), pr.first ) )
, а не второе условие.– Qwertiy ♦29 ноя 2016 в 10:10 -
-
@Qwertiy, извиняюсь, не правильно Вас понял. Возможно здесь это будет приемлемо, просто даже не знаю, норм так адреса сравнивать ? 29 ноя 2016 в 10:16
Мое решение порождает и другие вопросы, но тем не менее.
#include "stdafx.h"
#include <iostream>
#include <conio.h>
int main()
{
int n = 0;
std::cout << "n = ";
std::cin >> n;
int* mass = new int[n];
for (int i(0); i < n; i++)
std::cin >> mass[i];
int max = 0, min = 0;
for (int i(0); i < n; i++)
{
if (i == 0 && mass[i] == mass[max])
max = i;
else if (mass[i]> mass[max])
max = i;// ищем номер максимального элемента
if (i == 0 && mass[i] == mass[min])
min = i;
else if (mass[i] < mass[min])
min = i;// ищем номер минимального элемента
}
std::cout << "min = " << min << std::endl;
std::cout << "max = " << max << std::endl;
int proizvedenie = 1;
if (max < min)
{
for (int i = max + 1; i < min; i++)
proizvedenie *= mass[i];// производим умножение в заданном диапазоне
}
else if (min < max)
{
for (int i = min + 1; i < max; i++)
proizvedenie *= mass[i];
}
std::cout << proizvedenie;
_getch();
return 0;
}
-
-
@ДашаНовикова, попробуйте поиграть значениями, например поставьте
max = n-1;
вместо нуля. Экспериментируйте. 29 ноя 2016 в 9:18 -
Расчеты на "все случаи жизни" :)
Код ищет один и более одного результата, если таковые имеются. После поиска - есть примеры сортировки результатов по различным критериям.
Онлайн версия тут - http://ideone.com/4CGmoo
#include <algorithm>
#include <iostream>
#include <vector>
//////////////////////////////////////////////////////////////////
// Ищем произведение элементов массива, которые расположены между
// максимальным и минимальным элементами
//
// Дополнительно (чего не уточнено в задании):
//
// 1. Не ищем в обратном порядке (от минимального к максимальному)
// 2. Возможные варианты заносим в вектор результатов и их
// разновсячески сортируем в порядке нужного
//////////////////////////////////////////////////////////////////
typedef std::pair<std::size_t,std::size_t> PairType;
typedef std::vector<PairType> ResType;
void FuncMul(std::vector<int> Vec, ResType &Res) {
// в векторе длиной меньше 3-х искать нечего
if (Vec.size()<3) throw std::runtime_error("ничего не найдено");
// определяемся с минимумами и максимумами
auto Min = *std::min_element(Vec.begin(),Vec.end());
auto Max = *std::max_element(Vec.begin(),Vec.end());
// ищем все пары мах-min
std::size_t I = 0, S = Vec.size(), X;
int M = 0;
while(I<S) {
if (M == 0) {
if (Vec[I]==Max) { M=1; X=I; }
} else {
if (Vec[I]==Min) {
if (I>X+1) Res.push_back({X,I});
M=0;
} else if (Vec[I]==Max) X=I;
}
I++;
}
if(Res.size()<1) throw std::runtime_error("ничего не найдено");
}
int main() {
std::vector<int> Vec = {3,-4,1,3,4,9,1,-4,9,9,2,-3,-4,9,1};
ResType Res;
try {
FuncMul(Vec,Res);
// лямбда вывода на печать
auto PrnPair = [&](const PairType &P) {
std::cout << P.first << ":" << P.second << " = " <<
std::accumulate(Vec.begin()+P.first+1, Vec.begin()+P.second, 1, std::multiplies<int>()) <<
std::endl;
};
// лямбда сортировки по величине произведения
auto SortMul = [&] (const PairType &P1, const PairType &P2) {
return std::accumulate(Vec.begin()+P1.first+1, Vec.begin()+P1.second, 1, std::multiplies<int>()) <
std::accumulate(Vec.begin()+P2.first+1, Vec.begin()+P2.second, 1, std::multiplies<int>());
};
// лямбда сортировки по количеству множимых
auto SortDis = [&] (const PairType &P1, const PairType &P2) {
return P1.second - P1.first < P2.second-P2.first;
};
// 1) печать "сырого" несортированного результата --------------------------------------------
for(const auto &i:Res) PrnPair(i);
std::cout << "=========================" << std::endl;
// 2) печать отсортированного результата по возрастанию величины произведения ----------------
std::sort(Res.begin(),Res.end(),SortMul);
for(const auto &i:Res) PrnPair(i);
std::cout << "=========================" << std::endl;
// 3) печать отсортированного результата по убыванию количества элементов в произведении ----
std::sort(Res.begin(),Res.end(),SortDis);
for(const auto &i:Res) PrnPair(i);
std::cout << "=========================" << std::endl;
} catch(std::runtime_error &E) {
std::cout << "Ошибка: " << E.what() << std::endl;
} catch(...) {
std::cout << "Ошибка: что-то пошло не так!" << std::endl;
}
return 0;
}
#include <algorithm>
#include <iostream>
#include <vector>
int FuncMul(std::vector<int> Vec) {
if (Vec.size()>2) {
std::sort(Vec.begin(), Vec.end(), std::less<int>());
return std::accumulate(Vec.begin()+1, Vec.end()-1, 1, std::multiplies<int>());
}
return 0;
}
int main() {
std::vector<int> Vec = {9,1,2,3,4,1,1,-4};
std::cout << "FuncMul: " << FuncMul(Vec);
return 0;
}
-
-
-
@Majestio, Вы серьезно ? Нужно найти значение для текущего порядка, а не для того, который получится после сортировки. Поэтому ни о какой сортировке не может быть и речи. 29 ноя 2016 в 10:22
-
-
@Majestio, поймите, акцент и ставится на том, чтобы найти в входном множестве тот самый минимальный и максимальный элемент - при этом возможны различные варианты их расположения, что и осложняет задачу. А так, она становится гораздо более примитивной. 29 ноя 2016 в 10:37