1. Акция на весь декабрь! Получай оплату х2 за уникальные статьи, объемом от 200 слов, если в заголовке темы и теле статьи присутствует слово Python
    Скрыть объявление

C++ подмассив

Тема в разделе "C/C++/C#", создана пользователем Azgor, 28 сен 2010.

  1. Azgor

    Azgor Member

    Регистрация:
    15 май 2010
    Сообщения:
    7
    Симпатии:
    0
    приёмы написания эффективных алгоритмов (вместо трёх и более циклов всего два или один - максимальная сложность алгоритма указана в условии, О(х)), решать всё всем: все размерности всех одномерных массивов 100000
    -в массиве целых чисел найти непрерывный подмассив, сумма элементов которого максимальная; вывести два индекса (начало, конец) и получившуюся сумму ( O(n) )


    Код (C++):
    #include <iostream>
    #include <time.h>
    #include <stdlib.h>
    #include <iomanip.h>
    using namespace std;
    const int max_kl=100000;

    int main()
    {
    int n,l=0,r,ts=0,ms=0,temp;
    int mas[max_kl];
    bool b1=0;
    srand((unsigned)time(NULL));
    cout << "Vvedite razmernost' massiva -> ";cin>>n;cout <<endl;
    for(int i=0;i<n;i++)
    {
    /*cout << "Wwedite " << i+1 << "-element: " << endl;
    cin >> mas[i];*/

    mas[i]=rand()%(99+99)-99;
    cout << setw(5)<< mas[i];
    }
    cout <<endl;
    ts=mas[0];
    temp=1;
    for(int i=1;i<n;i++)
    {
    if(mas[i]>0){b1=1;break;}
    if(mas[i]>ts){ts=mas[i];temp=i+1;}
    }
    if(b1==1)
    {
    for(int i=1;i<n;i++)
    {
    ts=ts+mas[i];
    if(ts<0)
    {
    temp=i;ts=0;
    }
    if(ts>ms)
    {
    ms=ts;r=i;l=temp;
    }
    }
    cout <<"Otvet-> l: "<<l+1<<" r: "<<r+1<<" ms: "<<ms<<endl;
    }
    else cout<<"Otvet-> " << temp <<" "<< ts<<endl;  
    system("pause");
    return 0;
    }
    Проблема состиит в том, что если например массив заполнить так -7 5 -9 то программа не работает.... Объясните причину, кому не длень разбираться, и , если можно, методы преодоления этого. Зарание спасибо.
     
  2. Azgor

    Azgor Member

    Регистрация:
    15 май 2010
    Сообщения:
    7
    Симпатии:
    0
    Программа написана мною, алгоритм разработался по ходу.
    Не всегда одекватно берется левая граница подмассива и вычисляется сумма( пример я привел выше).

    И по поводу тегов CODE поподробней, если можно.
     
  3. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    2Автор: непрерывный подмассив - это что такое? последовательность (1..9...20......)? или все же любя последовательность чисел где каждое последующее является инкр. текущего???
     
  4. Azgor

    Azgor Member

    Регистрация:
    15 май 2010
    Сообщения:
    7
    Симпатии:
    0
    это любая последовательность чисел в массиве(непрырывная) на пример с a[2] po a[9](т.е. берется сумма элементов начиная со 2 и заканчивая 9, причем левая и правая граница последовательности выбирается так, дабы сумма была максимальной.)
     
  5. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Все равно смутно понимаю что же нужно сделать.

    И алгоритм что по-пьяне особо разобрать не могу....

    Но а на твой вопрос ответ
    Код (C++):
                    if(ts>ms)
    {
    ms=ts;r=i;l=temp;
    }
    Вот этот код в твоей последовательности не выполниться никогда....
    тоесть ms всегда 0
    r - не определена вообще
    l - тоже ноль

    А вообще лично я бы сделал вот так:
    Код (C++):
        const int N = 4;

    int Mass[]={-7,5,-9,4};

    int Mass2[N][N];

    int Sumatory = -99999999; //Ничтожно малая сумма для определения макс. послед.
    int Start,End=0; //Начальный и конечный индекс;
    int MaxLen=0; //длина послед. разность нач. индекса и кон. индекса

    //Заполняем двумерный массив Mass2[Начало индекс][Конец индекс] = Сумме элементов
    for (int i=0;i<N;i++)
    {
    int Sum = Mass[i];
    for (int j=i+1;j<N;j++)
    {
    Sum += Mass[j];
    Mass2[i][j] = Sum;
    //cout<<Sum<<endl;
    //Ну и сразу же проверим что бы не в пустую (Но массив если что мы сохраняем, так что проверить можем в любой момент программы
    if (Sumatory < Mass2[i][j]) //Если работать без дв. массива сюда просто Sum для сравнения!!! Но ИМХО, с дв. массивом красивее смотрится
    {
    Sumatory = Mass2[i][j]; //Та же история что и с прошлым комментом
    Start = i; End = j; MaxLen = j-i; // К Start и к End тут сразу смело можно плюсовать 1, что бы в конце не делать
    }

    if (Sumatory == Mass2[i][j]) //а вот если они равны, то уже проверяем длину цепочки MaxLen
    {
    if (MaxLen < j-i) //Ну длина в этом случае, как ты сам понимаешь 1, кстати именно из этой логики я инициализировал j как ты видишь выше
    {
    Sumatory = Mass2[i][j]; //У кого длинее тот и прав... :-)
    Start = i; End = j; MaxLen = j-i;
    }
    }      
    }
    }

    cout<<Sumatory<<endl<<Start+1<<" "<<End+1<<endl;
     
  6. Azgor

    Azgor Member

    Регистрация:
    15 май 2010
    Сообщения:
    7
    Симпатии:
    0
    l не 0, и r определена и находит верно. А двумерный массив зачем? " одномерных можно же ввести .... Даже короче полуится... Но, все равно - спасибо. Приму к сведенью и такой алгоритм.
     
  7. Azgor

    Azgor Member

    Регистрация:
    15 май 2010
    Сообщения:
    7
    Симпатии:
    0
    Можно проще. Примерно вот так:

    Код (C++):
    #include "stdio.h"
    #include "stdlib.h"
    #include "time.h"

    #define SIZE 3

    int main()
    {
    int mass[SIZE];
    int i = 0, j = 0, s = 0;
    int i_best = 0, j_best = 0, s_best = 0;

    srand((unsigned)time(0));

    for (i = 0; i < SIZE; i++)
    {
    mass[i] = (rand() % 100) * (rand() % 2 == 0 ? 1 : -1);

    }
    for (i = 0; i < SIZE; i++)
    printf("%d ", mass[i]);


    s_best=mass[0];
    i_best=0;
    j_best=0;

    for (j = 0, i = 0; j < SIZE; j++)
    {
    s += mass[j];

    if (s<mass[j])
    {
    s = mass[j];
    i=j;
    }

    if (s_best < s)
    {
    i_best = i;
    j_best = j;
    s_best = s;
    }
    }

    printf("\n\n");
    printf("start = %d\nstop = %d\nsum = %d\n", i_best, j_best, s_best);
    printf("\n\n");

    for (i = i_best; i <= j_best; i++)
    printf("%d ", mass[i]);

    printf("\n\n");
    system("pause");
    return 0;
    }/*rand генерит число, берем от него остаток от деления на 100,
    получаем число от 0 до 99, умножаем на остаток от деления на 2
    нового генерированного числа (результат 0 или 1),
    возвращаем 1 либо -1. вторая часть ранда нужна,
    чтобы подмешать в массив отрицательные числа.*/
     
  8. hosm

    hosm * so what *

    Регистрация:
    18 май 2009
    Сообщения:
    2.450
    Симпатии:
    7
  9. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Согласен, алгоритм действительно рабочий, кроме одного НО...
    Он может выдавать начало и конец одного и того же индекса(!!!), а один элемент - это не последовательность.....
    {2,-3,40,-50,-60} - это контр. пример... по данному алгоритму будет s-2, e-2, sum - 40; а по идеи должно быть s-0,e-2,sum - 39;

    Но а свой алгоритм я писал еще на то что бы был учет максимальной последовательности подмассива(по кол-ву элементов)....
    А массив двумерный был нужен только для наглядности...
     
Загрузка...
Похожие Темы - C++ подмассив
  1. Nadia_IT
    Ответов:
    0
    Просмотров:
    16
  2. kmm96
    Ответов:
    1
    Просмотров:
    21
  3. TriXel_01
    Ответов:
    5
    Просмотров:
    97
  4. acs-nexus
    Ответов:
    0
    Просмотров:
    87
  5. Ramzay
    Ответов:
    3
    Просмотров:
    129

Поделиться этой страницей