VPF::Max произведение k чисел массива[n]

Master_

Дата 7.4.2009, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 247
Регистрация: 31.1.2007

Репутация: нет
Всего: нет

Есть одномерный массив n размерности.

Есть int k=количеству чисел, которые составляют максимальное произведение.

Пример:

Код

Введите количество чисел: 4
2 4 1 3 5

k (максимальное произведение k чисел): 3
Максимальные элементы:
A[4]=5 A[1]=4 A[3]=3 
Произведение: 60

Считает в принципе правильно, НО... как быть с отрицательными числами?
Например:

Код

Введите количество чисел: 4
-2 -4 1 3 5

k (максимальное произведение k чисел): 3
Максимальные элементы:
A[4]=5 A[3]=3 A[2]=1
Произведение: 15

По моему алгоритму находятся просто k максимальных чисел, потом они умножаются. Но ведь в примере выше получается, что максимальное произведение будет = -2*-4*5=40, а не 15...

Пока не могу додуматься до алгоритма... Исходник прилагается:

Код

см следующие листинги

Это сообщение отредактировал(а) Master_ - 7.4.2009, 16:41

andrew_121

Дата 7.4.2009, 11:38 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 6
Всего: 33

Master_, Используя векторы, не разумно использовать индексы. Используй итераторы.
Собственно вопроса не понял...?

--------------------

Удалил аккаунт. Прощайте!

zim22

Дата 7.4.2009, 11:41 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69

Цитата(Master_ @ 7.4.2009, 11:29

)

Введите количество чисел: 4 2 4 1 3 5

чисел 4 ввести надо, а вводишь 5

--------------------

C++ FAQ Lite

Master_

Дата 7.4.2009, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 247
Регистрация: 31.1.2007

Репутация: нет
Всего: нет

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

Цитата

Введите количество чисел: 4
-2 -4 1 3 5
k (максимальное произведение k чисел): 3
Максимальные элементы:
A[4]=5 A[3]=3 A[2]=1
Произведение: 15

По моему алгоритму находятся просто k максимальных чисел, потом они умножаются. Но ведь в примере выше получается, что максимальное произведение будет = -2*-4*5=40, а не 15...

xvr

Дата 7.4.2009, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Замечание 1: k максимальных чисел можно найти отсортировав массив и взяв k последних элементов
Адаптация для отрицатеьных чисел:

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

Master_

Дата 7.4.2009, 12:48 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 247
Регистрация: 31.1.2007

Репутация: нет
Всего: нет

Спасибо

Код


Введите количество чисел: 5
-10 6 -9 4 -8
k=3

Отсортированный масив (по модулю)
4 6 -8 -9 -10

Отрицательные (чет/нечет): 3
Результат:
-10*-9*6=540

Получился такой код:

Код


int main()
{
    setlocale(0, "Russian");

    unsigned int i,k,n,max_i=0;
    int result = 1;
    cout << "Введите количество чисел: ";
    cin >> n;

    vector<int> arr(n);
    for ( i=0; i<n; ++i )
        cin >> arr[i];

    cout  << "k=";
    cin >> k;

    bubblesort(arr);
    cout << endl << "Отсортированный масив (по модулю)" << endl;
    for ( i=0; i<n; ++i )
        cout << arr[i] << " ";

    unsigned short int negative = 0;
    for ( i=(n-1); i>=(n-k); --i )
        if ( arr[i] < 0 )
            ++negative;
    cout << endl << endl << "Отрицательные (чет/нечет): " << negative << endl << "Результат: ";
    if ( !(negative & 1) )
    {
        cout << endl;
        
        for ( i=(n-1); i>=(n-k); --i )
        {
            cout << arr[i] << "*";
            result *= arr[i];
        }
        cout << "=" << result;
    }
    else
    {
        cout << endl;
        int minimum = arr[n-1], maximum = 0;
        for ( i=(n-1); i>=(n-k); --i )
        {
            if ( arr[i] > minimum )
                minimum = arr[i];
        }
        for ( i=0; i<=(n-k); ++i )
        {
            if ( arr[i] > maximum)
                maximum = arr[i];
        }
        for ( i=(n-1); i>=(n-k); --i )
        {
            if ( arr[i] == minimum )
                continue;
            cout << arr[i] << "*";
            result *= arr[i];
        }
        result *= maximum;
        cout << maximum << "=" << result;
    }
    cout << endl;
    return 0;
}

Я так думаю нужно еще сделать проверку

Цитата

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

Ведь в не результирующем наборе чисел все они могут быть отрицательными smile

Посмотрите код, может что где не дописал, или написал, но не очень smile

Цитата

Используя векторы, не разумно использовать индексы. Используй итераторы.

Тогда мне лучше переделать все на итераторы, или же без использования векторов новый массив создавать через new int[n] ?

Цитата(zim22 @ 7.4.2009, 11:41

)

Введите количество чисел: 4 2 4 1 3 5

чисел 4 ввести надо, а вводишь 5

Там 4 - количество элементов, а сами значения введены начиная с двойки.

xvr

Дата 7.4.2009, 13:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(Master_ @ 7.4.2009, 12:48)

Я так думаю нужно еще сделать проверку

Цитата

Ведь в не результирующем наборе чисел все они могут быть отрицательными smile

Точно. В таком случае нужно поменять меньшее положительное (вошедшее в набор) на большее отрицательное (не вошедшее).
Кстати, это можно сделать даже если положительные числа еще остались, и выбрать из 2х вариантов лучший

Цитата

Посмотрите код, может что где не дописал, или написал, но не очень smile

Не очень. В stl есть стандартный алгоритм sort. Делать свои bublesort'ы совсем не обязательно

andrew_121

Дата 7.4.2009, 13:42 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 6
Всего: 33

Цитата(Master_ @ 7.4.2009, 12:48

)

Тогда мне лучше переделать все на итераторы

Я бы именно так и сделал.

--------------------

Удалил аккаунт. Прощайте!

Master_

Дата 7.4.2009, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 247
Регистрация: 31.1.2007

Репутация: нет
Всего: нет

О ужас...

Код


Введите количество чисел: 6
1 -2 -4 6 9 10
k=4

Отсортированный масив (по модулю)
1 -2 -4 6 9 10

Отрицательные (чет/нечет): 1

Результат:
10*9*6*1=540

Вместо 6*1 нужно -2*-4...
Вот как же теперь это сделать.. да и куча намешанная уже получилась..

Код


int main()
{
    setlocale(0, "Russian");

    unsigned int i,k,n,max_i=0;
    int result = 1;
    cout << "Введите количество чисел: ";
    cin >> n;

    vector<int> arr(n);
    for ( i=0; i<n; ++i )
        cin >> arr[i];

    cout  << "k=";
    cin >> k;

    bubblesort(arr);

    cout << endl << "Отсортированный масив (по модулю)" << endl;
    for ( i=0; i<n; ++i )
        cout << arr[i] << " ";

    unsigned short int negative = 0;
    for ( i=(n-1); i>=(n-k); --i )
        if ( arr[i] < 0 )
            ++negative;

    cout << endl << endl << "Отрицательные (чет/нечет): " << negative << endl << endl << "Результат: ";
    //если число отрицательных четное или весь массив положительный/отрицательный
    if ( !(negative & 1) || all_positive(arr) || all_negative(arr) )
    {
        cout << endl;
        
        for ( i=(n-1); i>=(n-k); --i )
        {
            cout << arr[i] << "*";
            result *= arr[i];
        }
        cout << "=" << result;
    }
    else
    {
        cout << endl;
        int minimum = arr[n-1], maximum = 0;
        for ( i=(n-1); i>=(n-k); --i )//минимальное вошедшее в набор
            if ( arr[i] < minimum )
                minimum = arr[i];

        for ( i=0; i<=(n-k); ++i )//максимальное не вошедшее в набор
            if ( arr[i] > maximum)
                maximum = arr[i];
        
        int min_positive_in=0;
        if ( !maximum && negative!=k )// если все не вошедшие в набор отрцательные :/
        {
            min_positive_in = arr[n-1];
            int min_out = arr[0];
            for ( i=(n-1); i>=(n-k); --i )//берем меньшнее положительное вошедшее в набор
                if ( (arr[i] < min_positive_in) && arr[i] > 0 )
                    min_positive_in = arr[i];

            for ( i=0; i<=(n-k); ++i )//минимальное (макс по модулю) отрицательное не вошедшее в набор
                if ( arr[i] < min_out )
                    min_out = arr[i];

            for ( i=(n-1); i>=(n-k); --i )//меньшее положительное (набор) на большее(модуль) отрицательное (не)
            {
                if ( arr[i] == min_positive_in )
                    continue;
                cout << arr[i] << "*";
                result *= arr[i];
            }
            result *= min_out;
            cout << min_out << "=" << result;
            cout << "tst";
        }
        else
        {
            cout << "else";
            for ( i=(n-1); i>=(n-k); --i )
            {
                if ( arr[i] == minimum )
                    continue;
                cout << arr[i] << "*";
                result *= arr[i];
            }
            result *= maximum;
            cout << maximum << "=" << result;
        }        
    }
    cout << endl << endl;
    return 0;
}

Что посоветуете?

xvr

Дата 7.4.2009, 18:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Это именно случай 'поменять меньшее положительное (вошедшее в набор) на большее отрицательное (не вошедшее)'. А сделать - для начала поделить функцию на логические части, явно поделить отсортированный массив на 2 части и сделать методы, которые позволили бы отдельно посчитать все вышеозвученные варианты не меняя сам массив. Вызвать их все и по результатам уже сделать выборку

Dov

Дата 9.4.2009, 02:37 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 15
Всего: 88

Цитата(Master_ @ 7.4.2009, 16:37

)

Что посоветуете?

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

По-моему, твой алгоритм втопку и начать всё сначала. Например, посчитать перебором, рекурсию организовать какую-нибудь и т.п.

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Dov

Дата 10.4.2009, 01:01 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 15
Всего: 88

Цитата(Dov @ 9.4.2009, 02:37

)

рекурсию организовать какую-нибудь и т.п.

Вот, хоть и корявенько получилось, но, всё-таки, лучше, чем ничего.. smile

Код

void solve(int * src, int * cur, int * res, int size, int len, int ind)
{
    static int   K     = len;
    int         P     = 1;
    static int   max_P = INT_MIN;

    if(len == 0)
    {
        for(int i = 0; i < K; i++)
            P *= cur[i];

        if(P > max_P)
        {
            max_P = P;
            for(int i = 0; i < K; i++)
                res[i] = cur[i];
        }        
    }
    else
    {
        for(int i = ind; i <= size - len; i++)
        {
            cur[K - len] = src[i];
            solve(src, cur, res, size, len - 1, i + 1);
        }
    }
}

int main()
{
    srand((unsigned)time(NULL));

    const int SIZE = 10;
    int      src_arr[SIZE];
    int *     cur_arr;
    int *     res_arr;
    int      i, k;

    cout << "Source array:";
    for(i = 0; i < SIZE; i++)
        cout << setw(4) << (src_arr[i] = rand() % 20 - 10);

    cout << "\nEnter  k    :   ";
    cin  >> k;

    cur_arr = new int[k];
    res_arr = new int[k];

    cout << "\nResult      :";
    solve(src_arr, cur_arr, res_arr, SIZE, k, 0);

    for(i = 0; i < k; i++ )
        cout << setw(4) << res_arr[i];
    cout << endl;

    delete [] cur_arr;
    delete [] res_arr;

    return 0;
}

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »