Форум программистов, компьютерный форум CyberForum.ru

Прога не всегда работает правильно.. - C++

Восстановить пароль Регистрация
 
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
17.01.2011, 09:33     Прога не всегда работает правильно.. #1
Задача: Построить максимальное множество, состоящее из попарно не сравнимых векторов v. Векторы v определяются парами чисел, выбираемые из данной последовательности чисел а1, ..аn , n>=1. Два вектора v=(а,в) и v'=(а',в') называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.

Псевдокод:
Пусть числа a[1], ..a[n] расположены в порядке неубывания (если это не так, то просто отсортируем массив). Будем выписывать искомые векторы v[1], ..следующим образом:

Пусть k - номер формируемого сейчас вектора.

Положим сначала индекс i первого элемента формируемого сейчас вектора v[k] равным 1, а индекс второго элемента j=N.
k:=0;
пока (i<j)>,a[j]);
полагаем i:=i+1; j:=j-1; {переходим к следующим элементам}
если v[k]=(a,a[j])
то пусть количество оставшихся в массиве A элементов справа
от а[i-1], равных a[i-1], есть u, т.е. a=a[i+1]=...=a[i+u],
а количество оставшихся в массиве A элементов слева от а[j+1],
равных a[j+1], есть v, т.е.
a[j]=a[j-1]=...=a[j-v].
если u>=v
то, так как мы стремимся получить максимальное число пар,
то мы отбросим все оставшиеся элементы со значением a[j]
и положим j:=j-v-1
иначе по аналогичной причине отбросим все оставшиеся элементы
со значением a, т.е. положим i:=i+u+1;
конец_если
конец_если
конец_пока
КОД С++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
void qs(int *items, int left, int right)//быстрая сортировка - по неубыванию
{
register int i, j;
char x, y;
 
i = left; j = right;
x = items[(left+right)/2];
 
do {
while((items[i] < x) && (i < right)) i++;
while((x < items[j]) && (j > left)) j--;
if(i <= j) {
y = items[i];
items[i] = items[j];
items[j] = y;
i++; j--;}} while(i <= j);
if(left < j) qs(items, left, j);
if(i < right) qs(items, i, right);
}
void quick(int *items, int count)
{qs(items, 0, count-1);}
 
 
 
int main(int argc, char *argv[])
{
 
int a[500],n,l,i,j,u,v,k,N,g,h;
pair <int,int> vec[500];
cout<<"Vvedite kolichestvo elementov posledovatel'nosti:"<<endl;
cin>>n;
 
cout<<"Vvedite elementi posledovatel'nosti:"<<endl;
for (l=0;l<n;l++){
cin>>a[l];} //вводим последовательность
cout<<endl;
quick(a,n); //сортируем по неубыванию
 
k=0; i=0; j=n-1; u=0; v=0;
 
while (i<j){k++;
vec[k].first=a[i];
vec[k].second=a[j];
i++;j--;
if (a[i-1]==a[i]) {u++;}
if (a[j]==a[j+1]) {v++;}}
if (u>=v){j=j-v-1;} else {i=i+u+1;}
 
for (l=1;l<=k;l++){
cout<<vec[l].first<<" "<<vec[l].second<<endl;}
 
system("PAUSE");
return EXIT_SUCCESS;
}
Добавлено через 9 часов 32 минуты
подскажите.. там с U и V у меня проблемы.. не могу понять до конца как работает.. я так понял если в последовательности есть одинаковые элементы после сортировки он их перешагивает..
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 10:15     Прога не всегда работает правильно.. #2
opax, Если я правильно понял задачу, то алгоритм здесь очень простой:
Во-первых мы не сможем построить
максимальное множество, состоящее из попарно не сравнимых векторов v
если в начальном наборе чисел есть только одно или два значения. Например:
5 5 5 5 5 5
или
5 5 5 5 5 7
Если есть хотя бы три разных значения (и общее число элементов в начальном наборе чисел больше 3), то делаем так:
- сортируем начальную последовательность (пусть эта последовательность задана массивом a[n])
- далее делаем так: vec[0].first=a[0]; vec[0].second=a[n-2]; vec[1].first=a[n-1]; vec[1].second=a[1];
- после этого раскладываем элементы массива a[] с индексами от 2 до n-3 включительно, в любом порядке.
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
17.01.2011, 10:28  [ТС]     Прога не всегда работает правильно.. #3
я просто хотел понять как мне свой код поправить чтобы выводил правильно когда у меня есть более 4 или 5 повторяющихся элементов в последовательности.. к примеру послед. из 10 элементов и элементы 1 2 3 4 1 1 2 3 9 2 он выводит (1 9) (1 4) (1 3) (2 3) (2 2) но по задаче 2 3 и 2 2 сравнимы.. 2=2 а 2<3 ну или 3>2 и с единицами также..

когда 1 2 3 4 5 6 7 8 9 10 он выводит 1 10,2 9 ,3 8 и т.д всё верно.. там они все несравнимы между собой..

если v[k]=(a,a[j])
то пусть количество оставшихся в массиве A элементов справа
от а[i-1], равных a[i-1], есть u, т.е. a=a[i+1]=...=a[i+u],
а количество оставшихся в массиве A элементов слева от а[j+1],
равных a[j+1], есть v, т.е.
a[j]=a[j-1]=...=a[j-v].

вот при повторяющихся элементах.. но понять не могу почему не работает..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 10:45     Прога не всегда работает правильно.. #4
opax, Кажется я понял что Вам нужно.
если взять любые два вектора и у них будет совпадать хотя бы одно значение, то они всегда будут сравнимы.
Цитата Сообщение от opax Посмотреть сообщение
(1 9) (1 4) (1 3) (2 3) (2 2) но по задаче 2 3 и 2 2 сравнимы
Здесь получаются сравнимы не только (2 3) и (2 2), но и:
(1 9) и (1 4) и (1 3)
а также (1 3) (2 3)
Цитата Сообщение от opax Посмотреть сообщение
и с единицами также..
наверное это Вы и имели ввиду.
Т.е. получается что вектора нужно формировать только из неповторяющихся значений.
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
17.01.2011, 10:49  [ТС]     Прога не всегда работает правильно.. #5
да,именно.. например (1 10) (2 9) (3 8) (4 7) (5 6)
но при этом если у меня в последовательности будут повторяться значения мне нужно через них прыгать чтобы не получались одинаковые.. тоесть 1 1 1 1 2 2 3 3 4 4 должен вывести (1 4) (2 3)

2 больше 1 а 3 меньше 4 а следовательно не сравнимы...

называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 10:59     Прога не всегда работает правильно.. #6
Цитата Сообщение от opax Посмотреть сообщение
тоесть 1 1 1 1 2 2 3 3 4 4 должен вывести (1 4) (2 3)
Не совсем, если по максимуму, то должен вывести:
(1 4) (4 1) (2 3) (3 2)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.01.2011, 11:28     Прога не всегда работает правильно..
Еще ссылки по теме:

Не работает прога из учебника C++
C++ прога вычисляет не правильно
C++ Программа не всегда работает правильно
не работает прога на VS 2010 C++
C++ не работает прога

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
17.01.2011, 11:28  [ТС]     Прога не всегда работает правильно.. #7
да,точно..
Yandex
Объявления
17.01.2011, 11:28     Прога не всегда работает правильно..
Ответ Создать тему
Опции темы

Текущее время: 17:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru