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

@Neonik · Регистрация: 04.11.2011

Студворк — интернет-сервис помощи студентам

Дано действительные числа 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

Сначала я думал, что можно взять за основу стандартный алгоритм 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 · 01.12.2011, 20:57

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 · 01.12.2011, 21:00

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

gooseim,

Я не думаю, что он проходили стандартные алгоритмы.

Пока что тема про операторы цикла и операторы ветвления.

@Thinker · 01.12.2011, 21:30

gooseim, спасибо за ваш вариант. Многим интересно посмотреть решение задачи на Си и на С++ (с использованием STL), разве что сложность алгоритма не будет удовлетворять заявленным ТС ограничениям

@Сыроежка · 02.12.2011, 00:01

Сообщение от Thinker

gooseim, спасибо за ваш вариант. Многим интересно посмотреть решение задачи на Си и на С++ (с использованием STL), разве что сложность алгоритма не будет удовлетворять заявленным ТС ограничениям

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

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

C++
1
std::merge( a, a + 3, b, b + 5, c );

@Thinker · 02.12.2011, 08:53

Сообщение от Сыроежка

Если вас интересует, как это делается в С++...

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@Neonik 1 / 1 / 0 Регистрация: 04.11.2011 Сообщений: 22

	Внести единую упорядоченность в последовательность 30.11.2011, 17:27. Показов 2230. Ответов 7 Метки нет (Все метки) Дано действительные числа c1, . . . cp, d1 . . .dq(c1≤ c2. . . ≤cp , d1≤ d2. . . ≤dq), внести единую упорядоченность в c1, . . . cp, d1 . . .dq, получив f1,f2, . . . fp+q , такие что f1 ≤f2≤ . . . ≤fp+q. Число сравнений не должно превышать p + q. 1

@Сыроежка Заблокирован
	01.12.2011, 21:26
	gooseim, Я не думаю, что он проходили стандартные алгоритмы. Пока что тема про операторы цикла и операторы ветвления. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	01.12.2011, 21:30
	gooseim, спасибо за ваш вариант. Многим интересно посмотреть решение задачи на Си и на С++ (с использованием STL), разве что сложность алгоритма не будет удовлетворять заявленным ТС ограничениям 0