Найти числа произведение которых самое большое

[Arn1]

Здраствуйте,такая вот задача
Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально. Формат входных данных Во входном файле записано сначала число N - количество чисел в последовательности (3<=N<=100). Далее записана сама последовательность: N целых чисел, по модулю не превышающих 1000. Формат выходных данных В выходной файл выведите три искомых числа в любом порядке. Если существует несколько различных троек чисел, дающих максимальное произведение, то выведите любую из них.

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

Код

#include<iostream>
using namespace std;
int main(){
int i,j,z,n,c1=0,c2=0,c3=0,a[100];

cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
}
while(i!=j && j!=z && i!=z){
for(i=0;i<n;i++){
if(a[i]>c1)
c1=a[i];
}
for(j=0;j<n;j++){
if(a[j]>c2)
c2=a[j];
}
for(z=0;z<n;z++){
if(a[z]>c3)
c3=a[z];

}
}
cout<<c1<<" "<<c2<<" "<<c3;

return 0;

}

[Serge_Bliznykov]

проще, имхо, отсортировать массив по убыванию.
и взять первые три числа из образованного массива.

p.s. можно и без сортировки обойтись. И даже за один проход решить задачу. Но алгоритм такой должен быть. Нужно где-то хранить три индекса найденных максимальных значений (вначале все три индекса положить какому-то невозможному индексу. ну, например, в вашем случае, вначале все индексы положить равными -1). И дальше, сравнивать очередное число, размещает индексы очередных элементов по степени возрастания величин соответствующих им значений в массиве. При необходимости "сдвигая" остальные среди этих трёх максимальных.
понимаю, что написал запутанно... если будет интерес и не разберётесь - постараюсь объяснить на примере. Кодом, к сожалению, помочь не могу - ибо C не знаю. Код на Паскаль устроит?

[evg_m]

отсортировать массив по убыванию.
и взять первые три числа из образованного массива.

поойдет для НЕотрицательых, но у нас

Дано N целых чисел

пример массива
-10000 -1 1 2 3 4 5 6 7

-10000 * -1 * 7 =70000 НАИБОЛЬШЕЕ произведение ТРЕХ.
5 * 6 * 7 = 210 произведение трех максимальных.
надо еще добавить проверку двух наименьших отрицательных и одного максимального
положительного. И еще пожалуй случай когда в эти три максимальные(минимальные) попадет 0.

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

с1=a[0]; c2=a[1]; c3=a[3]; //берем первые три как начальные максимальные
for(i=0;i<n;i++) // перебираем первый 
{  for(j=i+1;j<n;j++)// перебираем второй но только те которые ПОСЛЕ первого j=i+1
//те которые были до первого мы уже проверили считая их первым числом.
   {  for(z=j+1;z<n;z++) // перебирам третий после второго
      { if(a[i]*a[j]*a[z]>c1*c2*c3) // если надо
         { c1=a[i]; c2=a[j]; c3=a[z]; //меняем компоненты максимального }
      }
   }
}

[Serge_Bliznykov]

согласен с замечанием.

хорошая задачка!

ну тогда лучше, имхо, сортировать по модулям.

И выбирать сложнее прийдётся, пропуская некоторые числа и анализируя другие, например, так, чтобы если есть выбор - отрицательных брать пару. А если оно (отрицательное число - одно - игнорировать!) и, похоже, всё таки, в некоторых случаях прийдётся перебирать варианты из отсортированного массива...
впрочем. я вижу всего несколько вариантов.
если произведение первых трёх чисел имеет положительный знак - ответ очевиден.
иначе, надо сравнить произведения
P1:= первое отрицательное числа из этих трёх * на первое положительное число из 3-х и на первое встречное отрицательное число (оно может быть в отсортированном массиве на любом месте, хоть крайнее!)
и P2: произведение первых трёх положительных чисел с верхушки массива...

p.s. возможно, что есть ещё какой-то вариант. но от тут же, рядом с верхушкой отсортированного массива...

[Vanta11a]

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

Если отрицательных >2, то сравниваем произведение двух наименьших отрицательных и наибольшего положительного с произведением трех последних положительных.

Если же отрицательных чисел одно или вообще нет, то просто смотрим произведение максимальных положительных.

Если положительных одно или два - берем тройку, состоящую из двух наименьших отрицательных + наибольшее положительное.

Ну и, конечно же, надо предусмотреть вариант, что все числа отрицательны. Тогда берем произведение трех максимальных.