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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
#1

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

17.01.2011, 09:33. Просмотров 584. Ответов 6
Метки нет (Все метки)

Задача: Построить максимальное множество, состоящее из попарно не сравнимых векторов 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 у меня проблемы.. не могу понять до конца как работает.. я так понял если в последовательности есть одинаковые элементы после сортировки он их перешагивает..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.01.2011, 09:33     Прога не всегда работает правильно..
Посмотрите здесь:

Программа не всегда работает правильно - C++
Всем добрый вечер. Реализовал программу, подсчитывающую корень уравнения методом касательных(Ньютона). В качестве примера использовал...

прога не правильно работает - C++
У меня ошибка в while но не знаю как исправить:( #include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;clocale&gt; #include &lt;iomanip&gt; ...

прога вычисляет не правильно - C++
Задание к работе Пользовательский класс должен содержать необходимые элементы-данные, метод установки их начальных значений: Void...

Прога на Си, все правильно вроде, но выскакивает - C++
Проверьте, пожалуйста, вроде задержку сделала, но выскакивает почему-то не считает результат... #include &lt;vcl.h&gt; #include &lt;conio.h&gt; ...

не работает прога - C++
#include &lt;cstdlib&gt; #include &lt;stdio.h&gt; #include &lt;iostream.h&gt; #include &lt;math.h&gt; #include &lt;stdlib.h&gt; #include &lt;conio.h&gt; //#define...

Не работает прога - C++
#include &lt;iostream&gt; using namespace std; int main() {//Начало int x,y; cout&lt;&lt;&quot;Vvedite chislo &quot;; cin&gt;&gt;x; switch(x) { case...

не работает прога - C++
прога работает она запускается,появляется окно,но сразу же отключается.. Дана матрица состоящая из N,M вещественных элементов. 1.Найти...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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
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++
4669 / 2495 / 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
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++
4669 / 2495 / 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++
#include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; #include &lt;stdlib.h&gt; float f1(float); float f2(float); float...

Не работает прога из учебника - C++
Нашла очень хороший учебник в инете: то, что нужно, мало воды, много примеров. Как только захотела запустить прогу и посмотреть, как она...

Прога работает неправильно - C++
Например вводим 123 45 new_str_ed=new_str_cop; ch=getchar();//здесь почему то просит ввести символы if (ch==32)//во входном потоке...

не работает прога на VS 2010 - C++
#include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;math.h&gt; #include &lt;curses.h&gt; #include &lt;stdlib.h&gt; FILE *file; char *fname...

почему не работает прога? - C++
#include &lt;iostream&gt; #include &lt;iomanip&gt; using namespace std; void mean (const int, int); void median (const int, int); void...


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

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

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