Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.01.2011, 15:10
Новичок

Отправить личное сообщение для opax Посмотреть профиль Найти все сообщения от opax
 
Регистрация: 15.01.2011
Сообщений: 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;
конец_если
конец_если
конец_пока

код с++:
#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;

while (i<j){
k=k+1;
vec[k].first=a[i];
vec[k].second=a[j];
i++;j--;
cout<<"58"<<endl;
if ((vec[k].first==a[i])&&(vec[k].second==a[j])){
cout<<"60"<<endl;
while (a[i]==a[i+1]){
cout<<"62"<<endl;
u++;
while (a[j+1]==a[j]){
cout<<"64"<<endl;
v++;
if (u>=v){
cout<<"66"<<endl;
j=j-v-1;}
else{cout<<"68"<<endl;
i=i+u+1;}
}}}}
for(i=1;i<=k;i++){
cout<<vec[i].first<<" "<<vec[i].second<<endl;}



system("PAUSE");
return EXIT_SUCCESS;
}
  #2  
Старый 15.01.2011, 19:58
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Проверено в MS Visual Studio 2005, MS Visual Studio 6.0 и Borland 6 C++ Builder.
Во всех трех случаях обычные действия по настройке проектов приводят к желаемому результату.
  #3  
Старый 19.01.2011, 03:32
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Код:
--- main.cpp    2011-01-19 02:40:07.785000104 +0300
+++ main.cpp    2011-01-19 02:40:10.684000107 +0300
@@ -33,9 +33,9 @@
     qs(items, 0, count - 1);
 }
 
-int main(int argc, char *argv[])
+int main(void)
  {
-    int a[500], n, l, i, j, u, v, k, N, g, h;
+    int a[500], n, l, i, j, u, v, k;
     pair <int, int> vec[500];
     cout << "Vvedite kolichestvo elementov posledovatel'nosti:" << endl;
     cin >> n;
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра