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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Neonik
1 / 1 / 0
Регистрация: 04.11.2011
Сообщений: 22
#1

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

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

Внести единую упорядоченность в последовательность - C++
Такая вот задача: Дано действительные числа {c}_{1}, \: ..., \: {c}_{p}, \: {d}_{1}, \: ... \: {d}_{q} \: ({c}_{1} \leq {c}_{2} \: ......

Создать файл и внести в него последовательность символов. - C++
Создать файл и внести в него последовательность символов. Вывести из этого файла в результирующий файл символы в обратной...

По отдельности всё работает, собираю в единую программу - бунт - C++
Доброго всем здравия. Написал несколько маленьких программ, все работает, собираю в единую не работает. Компилятор указывает на...

Проверить массив на упорядоченность - C++
В одномерном массиве, состоящем из и целых элементов, вычислить: 1) К максимальных элементов массива; 2) Проверить массив на...

Упорядоченность букв по алфавиту(русских) - C++
Дана строка букв русского алфавита. определить, упорядочены ли буквы по алфавиту

Упорядоченность элементов строки изменить на обратную - C++
Найти в матрице первую строку, все элементы (числа) которой упорядочены по убыванию. Изменить упорядоченность элементов этой строки на...

7
Сыроежка
Заблокирован
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 );
}
0
gooseim
Эксперт С++
508 / 412 / 37
Регистрация: 23.09.2010
Сообщений: 1,159
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, " "));
}
0
Thinker
Эксперт С++
4227 / 2201 / 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;
}
0
Сыроежка
Заблокирован
01.12.2011, 21:26 #5
gooseim,

Я не думаю, что он проходили стандартные алгоритмы. Пока что тема про операторы цикла и операторы ветвления.
0
Thinker
Эксперт С++
4227 / 2201 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.12.2011, 21:30 #6
gooseim, спасибо за ваш вариант. Многим интересно посмотреть решение задачи на Си и на С++ (с использованием STL), разве что сложность алгоритма не будет удовлетворять заявленным ТС ограничениям
0
Сыроежка
Заблокирован
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 );
0
Thinker
Эксперт С++
4227 / 2201 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 08:53 #8
Цитата Сообщение от Сыроежка Посмотреть сообщение
Если вас интересует, как это делается в С++...

Не по теме:

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

1
02.12.2011, 08:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2011, 08:53
Привет! Вот еще темы с ответами:

В одномерном массиве: проверить на упорядоченность, отсортировать - C++
1. В одномерном массиве, состоящем из n вещественных элементов: Проверить на упорядоченность отрицательные элементы; Отсортировать...

Проверка строчных букв на упорядоченность по алфавиту - C++
Доброго времени суток! Помогите с программой пожалуйста. Отблагодарю не только словами. Программу надо написать на языке Си иди С++,...

Простой список в виде массива.Как работать с элементами списка-массива через единую функцию - C++
Добрый день!Подсобите,как реализовать Простой список,но не через шаблоны или создание указателей,а как бы в виде массива.(Ну,или ваш...

Удалить строку из двумерного массива и проверить упорядоченность в С - C++
Дан двумерный массив и нужно удалить упорядоченную строку с минимальным номером. Вопрос такой: как удалить строку из двумерного массива в С...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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