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

Внести единую упорядоченность в последовательность - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Neonik
1 / 1 / 0
Регистрация: 04.11.2011
Сообщений: 22
30.11.2011, 17:27     Внести единую упорядоченность в последовательность #1
Дано действительные числа c1, . . . cp, d1 . . .dq(c1≤ c2. . . ≤cp , d1≤ d2. . . ≤dq), внести единую упорядоченность в c1, . . . cp, d1 . . .dq, получив f1,f2, . . . fp+q , такие что f1 ≤f2≤ . . . ≤fp+q. Число сравнений не должно превышать p + q.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Сыроежка
Заблокирован
01.12.2011, 20:52     Внести единую упорядоченность в последовательность #2
Сначала я думал, что можно взять за основу стандартный алгоритм std::set_union, но оказывается он работает несколько иначе, чем вам требуется.

Поэтому придется писать свой алгоритм, который оформим в виде функции с именем ordered_union

C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned int ordered_union( int a[], unsigned int n, int b[], unsigned int m, int c[] )
{
   unsigned i = 0, j = 0, k = 0;
 
   while ( ( i != n ) || ( j != m ) )
   {
      while ( ( i != n ) && ( j == m || a[i] <= b[j ] ) ) c[k++] = a[i++];
      while ( ( j != m ) && ( i == n || b[j] < a[i] ) ) c[k++] = b[j++];
   }
 
   return ( k );
}
Эта функция принимает три массива: два исходных вместе с их размерностями и результирующий массив. Возвращает она индекс в результирующем массиве ( c[] ) после записи в результирующий массив первых двух массивов ( a[] и b[] )

Пример работы программы

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
#include   <iostream>
 
 
int main()
{
   int a[3] = { 1, 1, 5 };
   int b[5] = { 1, 3, 5, 5, 7 };
   int c[8];
 
   std:;cout << "a[] = ";
   for ( unsigned int i = 0; i < 3; i++ ) std::cout << a[i] << ' ';
   std::cout << std::endl;
 
   std:;cout << "b[] = ";
   for ( unsigned int i = 0; i < 5; i++ ) std::cout << b[i] << ' ';
   std::cout << std::endl;
 
   ordered_union( a, 3, b, 5, c );
 
   std:;cout << "c[] = ";
   for ( unsigned int i = 0; i < 8; i++ ) std::cout << c[i] << ' ';
   std::cout << std::endl;
 
   return ( 0 );
}
gooseim
Эксперт C++
500 / 404 / 35
Регистрация: 23.09.2010
Сообщений: 1,139
01.12.2011, 20:57     Внести единую упорядоченность в последовательность #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm> 
#include <iterator>
 
int main()
{
   int a[3] = { 1, 1, 5 };
   int b[5] = { 1, 3, 5, 5, 7 };
   int c[8];
   
   std::copy(a, a + 3, c);
   std::copy(b, b + 5, c + 3);
   std::sort(c, c + 8);
   
   std::copy(c, c + 8, std::ostream_iterator<int>(std::cout, " "));
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.12.2011, 21:00     Внести единую упорядоченность в последовательность #4
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
#include<stdio.h>
void Sort(int *a, int na, int *b, int nb, int *c)
{
   int i, j, k;
   i = j = k = 0;
   while (i < na && j < nb)
      if (a[i] < b[j])
         c[k++] = a[i++];
      else c[k++] = b[j++];
   if (i < na)
      for(j = i; j < na; j++)
         c[k++] = a[j];
   else
      for(i = j; i < nb; i++)
         c[k++] = b[i];
}
 
void Print(int *a, int n)
{
   int i;
   for(i = 0; i < n; i++)
      printf("%d ", a[i]);
   putchar('\n');
}
 
int main()
{
   int a[3] = { 1, 1, 5 };
   int b[5] = { 1, 3, 5, 5, 7 };
   int c[8];
   Print(a, 3);
   Print(b, 5);
   Sort(a, 3, b, 5, c);
   Print(c, 8);
   return 0;
}
Сыроежка
Заблокирован
01.12.2011, 21:26     Внести единую упорядоченность в последовательность #5
gooseim,

Я не думаю, что он проходили стандартные алгоритмы. Пока что тема про операторы цикла и операторы ветвления.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.12.2011, 21:30     Внести единую упорядоченность в последовательность #6
gooseim, спасибо за ваш вариант. Многим интересно посмотреть решение задачи на Си и на С++ (с использованием STL), разве что сложность алгоритма не будет удовлетворять заявленным ТС ограничениям
Сыроежка
Заблокирован
02.12.2011, 00:01     Внести единую упорядоченность в последовательность #7
Цитата Сообщение от Thinker Посмотреть сообщение
gooseim, спасибо за ваш вариант. Многим интересно посмотреть решение задачи на Си и на С++ (с использованием STL), разве что сложность алгоритма не будет удовлетворять заявленным ТС ограничениям


Если вас интересует, как это делается в С++ с использованием STL, то это делается не так, как указал gooseim, а в одну строчку. Пример gooseim - это пример того, как не следует делать.

А решается эта задача с помощью алгоритма std::merge

C++
1
std::merge( a, a + 3, b, b + 5, c );
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2011, 08:53     Внести единую упорядоченность в последовательность
Еще ссылки по теме:

В одномерном массиве: проверить на упорядоченность, отсортировать C++
C++ Удалить и вставить элементы, не нарушая упорядоченность массива
C++ По отдельности всё работает, собираю в единую программу - бунт

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 08:53     Внести единую упорядоченность в последовательность #8
Цитата Сообщение от Сыроежка Посмотреть сообщение
Если вас интересует, как это делается в С++...

Не по теме:

меня это совсем не интересует, просто написал в противовес вашему сообщению, не более того

Yandex
Объявления
02.12.2011, 08:53     Внести единую упорядоченность в последовательность
Ответ Создать тему
Опции темы

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