VPF::[C++] Работа с массивом - Форум программистов

SunRaider

Дата 27.2.2009, 17:45 (ссылка)

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

Загрузка ...

Шустрый

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

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

Есть вот такая задача:

Код


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

В общем ничего умного по части алгоритма я придумать не смог. Может кто уже с таким сталкивался?

Заранее спасибо.

ЗЫ. Просьба не предлагать просто сравнивать соседние элементы - такое решение правильным не является.

Kakadu

Дата 28.2.2009, 10:41 (ссылка)

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

Загрузка ...

Опытный

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

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

sortedarr.c

Код


#include <stdio.h>

int main() {
    int n, a[50];
    freopen("sortedarr.in",  "rt", stdin);
    //freopen("sortedarr.out", "wt", stdout);

    int i, j, k;
    
    scanf("%d", &n);
    for (i=0; i<n; i++)
        scanf("%d", &a[i]);
    
    int ans[50];
    ans[0]=1;
    for (i=1; i<n; i++) {
        if (a[i]>a[i-1])
            ans[i]=ans[i-1]+1;
        else {
            k=-1;
            for (j=i-1; j>=0; j--) {
                if (a[j]<a[i]) {
                    k=j;
                    break;
                }
            }
            //printf("k=%d\n", k);
            if (k==-1)
                ans[i]=1;
            else ans[i]=ans[k]+1;
        }
    }
    /*printf("ans:\n");
    for (i=0; i<n; i++)
        printf("%d ", ans[i]);
    printf("\n");*/
    int max=0;
    for (i=1; i<n; i++)
        if (ans[i]>ans[max])
            max = i;
    int mark[50];
    for ( i=0; i<n; i++)
        mark[i] = 0;
    //printf("=)\n");
    mark[max] = 1;
    while (ans[max]>0) {
        for (j=max-1; j>=0; j++)
            if (ans[j] == ans[max]-1) {
                mark[j]=1;
                max = j;
                break;
            }
    }

    for (i=0; i<n; i++)
        if (mark[i])
            printf("%d ", a[i]);
    printf("\n");


}

sortedarr.in

Код


9
1 2 3 4 1 2 3 4 5

Это сообщение отредактировал(а) Kakadu - 28.2.2009, 10:48

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

Добрые мариносы долго кормили украдкой маленьких зерлингов. От этой украдки зерлинги пухли и дохли

SunRaider

Дата 28.2.2009, 13:32 (ссылка)

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

Загрузка ...

Шустрый

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

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

Kakadu, спасибо, но не могли бы Вы привести небольшое словесное описание алгоритма решения? Я немного не понял некоторые моменты.

Kakadu

Дата 28.2.2009, 21:58 (ссылка)

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

Загрузка ...

Опытный

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

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

Проходим по массиву и заполняем ans:
ans[i] - максимальная длина неубывающего массива, для которого элемент a[i] был бы последним.
Потом берем в ans[i] максимум и восстанавливаем ответ.

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

Добрые мариносы долго кормили украдкой маленьких зерлингов. От этой украдки зерлинги пухли и дохли

SunRaider

Дата 4.3.2009, 21:50 (ссылка)

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

Загрузка ...

Шустрый

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

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

В общем алгоритм не проходит. Падает если даже совсем немного изменить последовательность. Я попытался реализовать так:

Код


int Array_1(int *Array)
{
    int i, j, k, tmp=Array[0];
    int* asd = new int [ size ];
    asd[0] = 1;
    for (int i = 1; i < size; ++i)
    {
        if(Array[i] > tmp)
        {asd[i] = asd[i-1]+1;tmp=Array[i];}
        else
        {
            k = -1;
            for (j = i-1; j >= 0; --j)
            {
                if(Array[j] < Array[i])
                {
                    k = j;
                    break;
                }
            }
            //cout << k;
            if(k == -1)
                asd[i] = asd[i-1];
            else
                asd[i] = asd[k] + 1;
        }
    }
        cout << endl<<endl;
        for (i = 0; i < size; ++i)
            cout << asd[i] << "\t";
        
        
        cout <<"\n\n\n";
        int max = 0;
        for (i = 1; i < size; ++i)
            if(asd[i] > asd[max])
                max = i;
        int* mark = new int [ size ];
        for (i = 0; i < size; ++i)
            mark[i] = 0;
        
        mark[max] = 1;
        tmp = asd [ max ] - 1;
        for (j = max; j >= 0; --j){
                //bla=j;
                if(asd[j+1]!=asd[j])
                {
                    mark[j] = 1;
                    tmp--;
                }

        }

        cout <<"\n\n\n";    
        for (i = 0; i < size; ++i) 
            cout << mark[i] << "\t";
        cout <<"\n\n\n";
        for (i = 0; i < size; ++i)
            if(mark[i])
                cout << Array[i] << "\t";
        cout << endl;
        delete mark;
        delete asd;
        return 0;
}

Но это не прокатывает для следующего случая: 12 14 1 3 5 7 9 9 8.
Может кто подскажет где я накосячил?

zim22

Дата 5.3.2009, 09:09 (ссылка)

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

Загрузка ...

depict1

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

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

Цитата(SunRaider @ 4.3.2009, 21:50

)

int* asd = new int [ size ];

Цитата(SunRaider @ 4.3.2009, 21:50

)

delete asd;

тебя разве мама не учила использовать удалять массивы элементов так:

Код


delete [] asd;

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

C++ FAQ Lite

mrbrooks

Дата 5.3.2009, 09:26 (ссылка)

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

Загрузка ...

трололомен

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

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

Цитата(zim22 @ 5.3.2009, 09:09

)

тебя разве мама не учила использовать удалять массивы элементов так

Этому учит мама? smile

zim22

Дата 5.3.2009, 12:10 (ссылка)

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

Загрузка ...

depict1

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

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

mrbrooks, smile

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

C++ FAQ Lite

SunRaider

Дата 6.3.2009, 18:47 (ссылка)

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

Загрузка ...

Шустрый

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

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

zim22, если ты думаешь что твоя шутка очень смешная, то разочарую - она таковой не является. Это во-первых. А во-вторых ты что считаешь, что сказал своим комментом что то полезное? Я не просил искать косяки в оформлении кода, тем более несущественные. Я просил просчеты алгоритма.

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

zim22

Дата 6.3.2009, 20:39 (ссылка)

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

Загрузка ...

depict1

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

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

SunRaider, кушай с булочкой

Код


// 329.cpp : Defines the entry point for the console application.
//

#include <vector>
#include <iostream>
#include <list>

int main(int argc, char *argv[])
{
    //int ia[] = {1, 2, 1, 9, 5, 6, 2, 3, 4, 7, 2, 2, 3, 3, 3, 4, 8, 2, 9, 10, 15};
    //int ia[] = {12, 14, 1, 3, 5, 7, 9, 9, 8};
    //int ia[] = {3, 2, 7, 9, 12, 82, 99, 23, 11, 85, 24, 12, 8, 8, 11};
    //int ia[] = {1, 2, 3, 4, 5, 6};
    //int ia[] = {6, 5, 4, 3, 2, 1};
    int ia[] = {1, 2, 3, 6, 5, 4, 3, 2, 1};


    std::vector<int> vi(ia, ia + sizeof(ia) / sizeof(*ia));
    std::cout << "Before: " << std::endl;
    int max_cnt = 15, cur_cnt = 1;
    for (std::vector<int>::const_iterator cit = vi.begin(); cit != vi.end(); ++cit, ++cur_cnt)
    {
        if (cur_cnt == max_cnt) 
        {
            std::cout << *cit << std::endl;
            cur_cnt = 1;
        }
        else        
            std::cout << *cit << ", ";
    }    
    std::cout << std::endl;
    struct sequence
    {
        std::vector<int>::size_type beg;
        std::vector<int>::size_type size;
    };
    std::vector<sequence> vs;
    
    sequence sqc;
    sqc.beg = 0;
    sqc.size = 1;

    int max = vi.front();
    for (std::vector<int>::size_type index = 1; index != vi.size(); ++index)
    {                
        if (max <= vi[index])
        {    
            max = vi[index];            
            ++sqc.size;

            if (index == vi.size() - 1)
                vs.push_back(sqc);
        }
        else
        {
            vs.push_back(sqc);
            
            max = vi[index];
            sqc.size = 1;
            sqc.beg = index;

            if (index == vi.size() - 1)
                vs.push_back(sqc);
        }
    }

    std::vector<int>::size_type max_size = 0;
    std::vector<sequence>::const_iterator max_pos = vs.end();
    for (std::vector<sequence>::const_iterator cit = vs.begin(); cit != vs.end(); ++cit)
    {
        //std::cout << cit->size << ": " << cit->beg << std::endl;

        if (cit == vs.begin())
        {  
            max_pos = cit;
            max_size = cit->size;
        }

        if (max_size < cit->size)
        {
            max_size = cit->size;
            max_pos = cit;
        }
    }    
    
    int min = vi[max_pos->beg];
    for (std::vector<int>::size_type index = max_pos->beg - 1; index != -1; --index)
    {
    
        if (vi[index] <= min)
            min = vi[index];
        else
            vi[index] = 666;
    }

    int max_n = vi[max_pos->beg + max_pos->size - 1];
    for (std::vector<int>::size_type index = max_pos->beg + max_pos->size - 1; index != vi.size(); ++index)
    {
    
        if (vi[index] >= max_n)
            max_n = vi[index];
        else
            vi[index] = 666;
    }    

    std::cout << "After: " << std::endl;
    cur_cnt = 1;
    for (std::vector<int>::const_iterator cit = vi.begin(); cit != vi.end(); ++cit)
    {
         if (cur_cnt == max_cnt) 
         {             
             if (*cit != 666)                        
             {                
                 std::cout << *cit << ", " << std::endl;                
                cur_cnt = 1;
             }
             else             
             {
                 std::cout << std::endl;
                 cur_cnt = 1;
             }
         }
        else
            if (*cit != 666)            
            {
                std::cout << *cit << ", ";
                ++cur_cnt;
            }
    }    
    std::cout << std::endl;

    return 0;
}

Это сообщение отредактировал(а) zim22 - 6.3.2009, 22:12

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

C++ FAQ Lite

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