Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Перебор вариантов подпоследовательностей

10K
03 декабря 2006 года
Omega Red
49 / / 15.10.2006
Дана последовательность из N целых чисел, среди которых нет 2 одинаковых.
Требуется вычеркнуть минимально возможное количество чисел, так чтобы оставшиеся числа шли в порядке возрастания.

1 тест - есть одинаковые числа. (2 3 4 2).
2 тест - невозможно составить никакой последовательности. (5 4 3 2).
3 тест - есть две последовательности с одинаковым количеством подряд идущих элементов. (1 3 2 4)=>(1 3 4), (1 2 4)

Код:
#include "iostream.h"

int main()
{
    int i, j, k, *a, *b, *c, n, count, max, x;

    cout<<"Vvedite chislo elementov massiva:"<<endl;
    cin>>n;
a = new int [n];
b = new int [n];

cout<<"Vvedite elementi massiva:"<<endl;
    for (i = 0; i < n; i++)
    {
        cin>>a;  
        b = 0;
    }

/*Тест 1*/
    for (i = 0; i < n; i++)
        for (j = i+1; j < n; j++)
            if (a[j] == a)
            {
                cout<<"Est' odinakovie elementi"<<endl;
                return 1;
            }
/*----------*/

/*Находим, сколько последующих элементов массива а
больше текущего элемента, полученный результат записываем в массив b*/
    for (k = 0; k < n-1; k++)          
    for (i = k; i < n; i++)            
    {
        if (a > a[k])            
            b[k]++;          

    }

/*Тест 2*/
    count = 0;
    for (i = 0; i < n; i++)
        if (b == 0)
            count++;

        if (count == n)
        {
            cout<<"Nelzya sostavit' nikakoy posledovatelnosti"<<endl;
            return 2;
        }
/*---------*/

/*Находим максимальный элемент среди массива b,
после нахождения переходим к этому элементу и считаем от него.
*/
x = 0;
k = 0;
count = 0;
while (k < n)
{
    max = b[k];
    for (i = k+1; i < n; i++)
    {
        if (b > b[i-1] && b > b[k])
        {
            max = b;
            x = i+1;
        }
    }
    if (max == b[k])
    {
            ++x;
    }
    count++;
    k = x;
}
/*Создаём массив с размерностью count, делаем предыдущую операцию,
записывая в массив с элементы массива а с номерами максимальных элементов массива b*/
c = new int [count];

x = 0;
k = 0;
for (j = 0; j < count, k < n; j++)
{
    max = b[k];
    for (i = k+1; i < n; i++)
    {
        if (b > b[i-1] && b > b[k])
        {
            max = b;
            x = i+1;
        }
    }
    if (max == b[k])
        {
            ++x;
        }
    k = x;
    c[j] = a[k-1];
}

for (i = 0; i < count; i++)
cout<<c<<" ";
cout<<endl;
        return 0;
}


Есть такая проблема, что работают не все варианты. Допустим для
8 3 5 2 9 6 4 (должно напечатать 3 5 9, а печатает 2 9 6 4).
И ещё вопрос: как реализовать 3-ий тест (5 3 2 6 4 8)?
63
04 декабря 2006 года
Zorkus
2.6K / / 04.11.2006
Цитата: Omega Red
Дана последовательность из N целых чисел, среди которых нет 2 одинаковых.
Требуется вычеркнуть минимально возможное количество чисел, так чтобы оставшиеся числа шли в порядке возрастания.

1 тест - есть одинаковые числа. (2 3 4 2).
2 тест - невозможно составить никакой последовательности. (5 4 3 2).
3 тест - есть две последовательности с одинаковым количеством подряд идущих элементов. (1 3 2 4)=>(1 3 4), (1 2 4)


Не понял.

Цитата: Omega Red

Есть такая проблема, что работают не все варианты. Допустим для
8 3 5 2 9 6 4 (должно напечатать 3 5 9, а печатает 2 9 6 4).
И ещё вопрос: как реализовать 3-ий тест (5 3 2 6 4 8)?


Ты что, пишешь для каждого теста свой код? А если я их буду автоматически генерить?;)

10K
04 декабря 2006 года
Omega Red
49 / / 15.10.2006
Эти тесты как раз такие и нужны. Вдруг пользователь захочет ввести одинаковые числа, программа должна напомнить про условие. Можно конечно при вводе проверять и откатывать на один ввод назад, если бы не требование делать 4-5 тестов.

А для каждого теста конечно нужен отдельный код, как же иначе? И что значит "автоматически генерить"? Заполнять массив функцией rand()?

Вот придумал как 3-ий тест реализовать, искать в массиве b рядом стоящие одинаковые элементы, кроме 0. Но думаю, что так неправильно решаю.
63
04 декабря 2006 года
Zorkus
2.6K / / 04.11.2006
Тьфу, так ты под словом тест понимаешь - возможная ошибка, что ли??
10K
04 декабря 2006 года
Omega Red
49 / / 15.10.2006
Допустим задача: Найи максимальное чётное до первого нечётного.
1 Тест. Нет ни чётных ни нечётных (1.7, 2.5 допустим)
2 Тест. Нет чётных
3 Тест. Нет нечётных
4 Тест. Нет чётных чисел перед нечётным
5 Тест. Всё нормально.

Тест - это как бы различные варианты, которые могут не работать на твоей проге.
263
04 декабря 2006 года
koltaviy
816 / / 16.12.2004
Цитата: Omega Red
Допустим задача: Найи максимальное чётное до первого нечётного.
1 Тест. Нет ни чётных ни нечётных (1.7, 2.5 допустим)
2 Тест. Нет чётных
3 Тест. Нет нечётных
4 Тест. Нет чётных чисел перед нечётным
5 Тест. Всё нормально.

Тест - это как бы различные варианты, которые могут не работать на твоей проге.


Да не парься ты.. По-моему нормально сформулировал.. Только это не "тест", а вариант называется;) А так, в целом можно было догадаться:)
Пока что первая твоя ошибка:

 
Код:
for (i = 0; i < n; i++)  //koltaviy: нужно i < n - 1
for (j = i + 1; j < n; j++)
if (a[j] == a)
{
cout<<"Est' odinakovie elementi"<<endl;
return 1;
}

Под третим вариантом ты имеешь вииду, что если существует несколько наборов с одинаковым количеством элементов, нужно запоминать их все?!!
А вообще алгоритм сильно у тебя замудреный, на вскидку.. Будет время, поправим..;)
10K
05 декабря 2006 года
Omega Red
49 / / 15.10.2006
Первая ошибка пока не так сильно важна. Одинаковые элементы не пропускаются.
А алгоритм я думал такой:
Допустим есть последовательность, 1 3 7 8 4 5 6, ищем среди последующих элементов, сколько элементов больше первого, второго и т.д. элемента и записываем данные в другой массив.
6 5 1 0 2 1 0 получится.
Ищем максимальные числа, после нахождения начинаем отсчёт от этого числа.
Получится:
6 5 2 1 0.
Переводим этот массив в соответствующие числа, получаем 1 3 4 5 6
Для таких комбинация нормально, но для нескольких вариантов (тот же 1 2 3 5 4) не будет работать.
242
05 декабря 2006 года
Оlga
2.2K / / 04.02.2006
[COLOR=red]пожалуйста! в своем первом посте поменяй тэг quote на code.[/COLOR]
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог