#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;
}
Перебор вариантов подпоследовательностей
Требуется вычеркнуть минимально возможное количество чисел, так чтобы оставшиеся числа шли в порядке возрастания.
1 тест - есть одинаковые числа. (2 3 4 2).
2 тест - невозможно составить никакой последовательности. (5 4 3 2).
3 тест - есть две последовательности с одинаковым количеством подряд идущих элементов. (1 3 2 4)=>(1 3 4), (1 2 4)
Код:
Есть такая проблема, что работают не все варианты. Допустим для
8 3 5 2 9 6 4 (должно напечатать 3 5 9, а печатает 2 9 6 4).
И ещё вопрос: как реализовать 3-ий тест (5 3 2 6 4 8)?
Цитата: 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)
Требуется вычеркнуть минимально возможное количество чисел, так чтобы оставшиеся числа шли в порядке возрастания.
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)?
Ты что, пишешь для каждого теста свой код? А если я их буду автоматически генерить?;)
А для каждого теста конечно нужен отдельный код, как же иначе? И что значит "автоматически генерить"? Заполнять массив функцией rand()?
Вот придумал как 3-ий тест реализовать, искать в массиве b рядом стоящие одинаковые элементы, кроме 0. Но думаю, что так неправильно решаю.
Тьфу, так ты под словом тест понимаешь - возможная ошибка, что ли??
1 Тест. Нет ни чётных ни нечётных (1.7, 2.5 допустим)
2 Тест. Нет чётных
3 Тест. Нет нечётных
4 Тест. Нет чётных чисел перед нечётным
5 Тест. Всё нормально.
Тест - это как бы различные варианты, которые могут не работать на твоей проге.
Цитата: Omega Red
Допустим задача: Найи максимальное чётное до первого нечётного.
1 Тест. Нет ни чётных ни нечётных (1.7, 2.5 допустим)
2 Тест. Нет чётных
3 Тест. Нет нечётных
4 Тест. Нет чётных чисел перед нечётным
5 Тест. Всё нормально.
Тест - это как бы различные варианты, которые могут не работать на твоей проге.
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;
}
for (j = i + 1; j < n; j++)
if (a[j] == a)
{
cout<<"Est' odinakovie elementi"<<endl;
return 1;
}
Под третим вариантом ты имеешь вииду, что если существует несколько наборов с одинаковым количеством элементов, нужно запоминать их все?!!
А вообще алгоритм сильно у тебя замудреный, на вскидку.. Будет время, поправим..;)
А алгоритм я думал такой:
Допустим есть последовательность, 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) не будет работать.
[COLOR=red]пожалуйста! в своем первом посте поменяй тэг quote на code.[/COLOR]