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

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

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

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

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

Программа не всегда работает правильно - 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++
прога работает она запускается,появляется окно,но сразу же отключается.. Дана матрица состоящая из N,M вещественных элементов. 1.Найти...

6
valeriikozlov
Эксперт С++
4670 / 2496 / 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 включительно, в любом порядке.
1
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].

вот при повторяющихся элементах.. но понять не могу почему не работает..
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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 Посмотреть сообщение
и с единицами также..
наверное это Вы и имели ввиду.
Т.е. получается что вектора нужно формировать только из неповторяющихся значений.
0
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 а следовательно не сравнимы...

называются сравнимыми, если а<=а' и в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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)
1
opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
17.01.2011, 11:28  [ТС] #7
да,точно..
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.01.2011, 11:28
Привет! Вот еще темы с ответами:

Не работает прога - 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++
#include &lt;iostream&gt; #include &lt;iomanip&gt; using namespace std; void mean (const int, int); void median (const int, int); void...

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

не работает прога на 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...


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

Или воспользуйтесь поиском по форуму:
7
Yandex
Объявления
17.01.2011, 11:28
Ответ Создать тему
Опции темы

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