VPF::помогите решить задачу - Форум программистов

Гость_гость

Дата 7.1.2005, 11:57 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Есть массив из элементов типа интегер. Мы
можем в этом массиве взять наразрывную цепочку(от такого-то до такого-то
элемента) далее считаем сумму элементов в этой цепи.
задача - найти цепочку с максимальной суммой без ограничения на длинну цепочки.

Alexandr87

Дата 7.1.2005, 19:15 (ссылка)

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

Загрузка ...

дыкий псых

Профиль
Группа: Завсегдатай
Сообщений: 1459
Регистрация: 27.11.2004
Где: Алматы, Казахстан

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

скажу глупость, но нужно делать перебор

Это сообщение отредактировал(а) Alexandr87 - 7.1.2005, 19:20

Wowa

Дата 8.1.2005, 02:39 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Админ
Сообщений: 15017
Регистрация: 14.9.2000
Где: Винград

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

Модератор: Название темы должно отражать ее суть!

Гость_гость

Дата 8.1.2005, 13:12 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Извините, что не правильно назвал тему. Учту.
А перебором, в конечном итоге комп виснет.

volvo877

Дата 8.1.2005, 13:21 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

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

Гость_гость

Цитата

найти цепочку с максимальной суммой без ограничения на длинну цепочки

Очень странное задание, потому что если длина не ограничена, то цепочкой с максимальной суммой будет весь массив...

Dov

Дата 8.1.2005, 14:14 (ссылка)

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

Загрузка ...

аСинизатор

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

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

Цитата(volvo877 @ 8.1.2005, 13:21)

А если массив такой {1, 2, -100, 3, 4}? Тогда цепочкой с максимальной суммой будет 3, 4.
Вот такой вариант:

Код

#include <iostream.h>
#include <iomanip.h>
#define SIZE 10

void main()
{
    int ar[]   = {5, -5, 8, -2, 9, -4, 8, -3, 3, -99};
    int sum    = 0;
    int max    = 0;
    int iBeg   = 0;
    int iEnd   = 0;
    int iFirst = 0;
	
    for(int i = 0; i < SIZE; i++)
    { 
        sum += ar[i];
        if(sum <= 0)
        {
            sum    = 0;
            iFirst = i + 1;
        }
        else if(sum > max)
        {
            max  = sum;
            iBeg = iFirst;
            iEnd = i;
        }
    }

    cout << "Index :";
    for(i = 0; i < SIZE; i++)
        cout << setw(4) << i;

    cout << "\nArray :";
    for(i = 0; i < SIZE; i++)
        cout << setw(4) << ar[i];

    cout << "\nMySeq :";
    for(i = 0; i <= iEnd; i++)
        i < iBeg ? (cout << setw(4) << ' ') : (cout << setw(4) << ar[i]);

    cout << "\n\nMaxSum: " << max 
         << "\nIndBeg: "   << iBeg
         << "\nIndEnd: "   << iEnd << endl;
}

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

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

Гость_гость

Дата 8.1.2005, 14:42 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Цитата (volvo877 @ 8.1.2005, 13:21)

Цитата

Я с вами согласен, но всё равно спасибо!!!! smile

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