Объединить 2 массива в один, в котором все числа идут по убыванию

@Sh@dow777 · Регистрация: 10.12.2013

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

Привет всем. Мне нужно объединить 2 массива в один, в котором все числа идут по убыванию. Вот подробности задачи.

Текстовый файл merge.dat содержит четыре строки. В первой строке записано натуральное число N (1 ≤ N ≤ 100 000) — количество дуболомов в первой шеренге.

Вторая строка содержит N натуральных чисел, записанных через пробел. Числа идут в невозрастающем порядке. Каждое число лежит в диапазоне от 1 до 1 000 000 000.

В третьей строке записано натуральное число M (1 ≤ M ≤ 100 000) — количество дуболомов во второй шеренге.

Четвертая строка содержит M натуральных чисел, записанных через пробел. Числа идут в невозрастающем порядке. Каждое число лежит в диапазоне от 1 до 1 000 000 000.

Формат выходного файла merge.sol

Текстовый файл merge.sol должен содержать N+M чисел, идущих в невозрастающем порядке. Каждое число — это рост соответствующего дуболома из первой или из второй шеренги. Каждое число должно выводиться в отдельную строку.

У меня есть предположения, что раз числа идут в невозрастающем порядке, то 2 массива нужно сначала отсортировать по убыванию, а потом слить вместе процедурой слияния.
Я так понимаю, что для слияния нужно использовать этот код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T> void Merge(T const *const A, int const nA,
                             T const *const B, int const nB,
                             T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов,
  //  и массива B, содержащего nB элементов.
  //  Результат записать в массив C.
 
    int a(0), b(0); //Номера текущих элементов в массивах A и B
 
    while( a+b < nA+nB ) //Пока остались элементы в массивах
    {
        if( (b>=nB) || ( (a<nA) && (A[a]<=B[b]) ) )
        { //Копирую элемент из массива A
            C[a+b] = A[a];
            ++a;
        } else { //Копирую элемент из массива B
            C[a+b] = B[b];
            ++b;
        }
    }
}

Скажите, этот код подходит? Если да, то как изменить его, чтоб числа в массиве С шли по убыванию?

@Tchikh · 09.06.2014, 23:11

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T> void Merge(T const *const A, int const nA,
                             T const *const B, int const nB,
                             T *const C)
{ //Выполнить слияние массива A, содержащего nA элементов,
  //  и массива B, содержащего nB элементов.
  //  Результат записать в массив C.
 
    int a(0), b(0); //Номера текущих элементов в массивах A и B
 
    while( a+b < nA+nB ) //Пока остались элементы в массивах
    {
        if( (b>=nB) || ( (a<nA) && (A[a]>=B[b]) ) )
        { //Копирую элемент из массива A
            C[a+b] = A[a];
            ++a;
        } else { //Копирую элемент из массива B
            C[a+b] = B[b];
            ++b;
        }
    }
}

@Sh@dow777 · 10.06.2014, 00:45 **[ТС]**

Tchikh, Спасибо, сейчас попробую и отпишусь.

Добавлено через 1 час 29 минут
Tchikh, Я написал программу. Вот мой код.

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <conio.h>
 
long long int n, m;
int i, j, q, s, t, k, d;
 
void sort1(int a[], long long int n, int t, int i, int j){
 
    for(i = 0; i < n;i++){
        for(j = 0;j < n - 1;j++){
            if(a[j] < a[j + 1]){
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}
void sort2(int b[], long long int m, int k, int q, int s){
 
    for(q = 0;q < m;q++){
        for(s = 0;s < m - 1;s++){
            if(b[s] < b[s + 1]){
                k = b[s];
                b[s] = b[s + 1];
                b[s + 1] = k;
            }
        }
    }
}
void merge(int a[], int b[], int c[], long long int n, long long int m){
    int A(0), B(0);
 
    while(A + B < n + m)
    {
        if( (B >= m) || ( (A < n) && (a[A] >= b[B]) ) )
        {
            c[A + B] = a[A];
            ++A;
        } else
        {
            c[A + B] = b[B];
            ++B;
        }
    }
}
int main()
{
    scanf("%lld", &n);
    int *a = new int[n];
 
    for(i = 0; i < n;i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &m);
    int *b = new int[m];
 
    for(q = 0;q < m;q++)
        scanf("%lld", &b[q]);
    int *c = new int[n + m];
 
    sort1(a, n, t, i, j);
    sort2(b, m, k, q, s);
    merge(a, b, c, n, m);
 
    for(d = 0; d < n + m;d++)
        printf("%lld\n", c[d]);
    delete[]a;
    delete[]b;
    delete[]c;
 
    getch();
 
    return 0;
}

Но у меня выбивает ошибку "HEAP CORRUPTION DETECTED". В чем проблема?

@Tchikh · 10.06.2014, 00:47

Массивы a и b необязательно сортировать, они уже отсортированы по условию

@Sh@dow777 · 10.06.2014, 02:58 **[ТС]**

Tchikh, Хорошо, я уберу сортировку. Но думаю, что эта ошибка возникает в процессе слияния. Хотя слитый массив выводит так, как надо. И одновременно выводит ошибку.

Добавлено через 5 минут
Tchikh, Вот код без сортировки.

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
#include <stdio.h>
#include <conio.h>
 
long long int n, m;
int i, q, d;
 
void merge(int a[], int b[], int c[], long long int n, long long int m){
    int A(0), B(0);
 
    while(A + B < n + m)
    {
        if( (B >= m) || ( (A < n) && (a[A] >= b[B]) ) )
        {
            c[A + B] = a[A];
            ++A;
        } else
        {
            c[A + B] = b[B];
            ++B;
        }
    }
}
int main()
{
    scanf("%lld", &n);
    int *a = new int[n];
 
    for(i = 0; i < n;i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &m);
    int *b = new int[m];
 
    for(q = 0;q < m;q++)
        scanf("%lld", &b[q]);
    int *c = new int[n + m];
 
    merge(a, b, c, n, m);
 
    for(d = 0; d < n + m;d++)
        printf("%lld\n", c[d]);
    delete[]a;
    delete[]b;
    delete[]c;
 
    getch();
 
    return 0;
}

Все тоже самое.

Добавлено через 17 минут
Вопрос еще в силе. Кто нибудь скажите, в чем причина моей ошибки?

Добавлено через 1 час 41 минуту
Кто нибудь скажет, где у меня проблема? В гугле нахожу эту ошибку, но там она никак не связана с процедурой слияния. Скажите, что мне нужно исправить?

@Max Dark · 10.06.2014, 04:34

у вас условие в 10й строке равносильно

C++
1
while((A + (B < n) + m) != 0)

т.к. приоритет операции "+" выше, чем "<".
Расставьте скобки:

C++
1
while((A + B) < (n + m))

@Trwsdf · 10.06.2014, 11:28

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  std::ifstream init("C:\\merge.dat", ios_base::in);
    if (!init.fail()) {
        std::multiset<int> result;
        int size;
        init>>size;
        for (int i = 0, elem; i < size; i++)result.insert((init >> elem, elem));
        init>>size;
        for (int i = 0, elem; i < size; i++)result.insert((init >> elem, elem));
        std::ofstream out("C:\\merge.sol", ios_base::out);
        if (!out.fail()) {
            std::for_each(result.rbegin(), result.rend(), [&out](const int& a) {
                out << a << "\r\n";
            });
        };
    };

@Sh@dow777 · 10.06.2014, 13:27 **[ТС]**

Вот я исправил, как сказал Cra3y,

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
#include <stdio.h>
#include <conio.h>
 
long long int n, m;
int i, q, d;
 
void merge(int a[], int b[], int c[], long long int n, long long int m){
    int A(0), B(0);
 
    while((A + B) < (n + m))
    {
        if( (B >= m) || ( (A < n) && (a[A] >= b[B]) ) )
        {
            c[A + B] = a[A];
            ++A;
        } else
        {
            c[A + B] = b[B];
            ++B;
        }
    }
}
int main()
{
    scanf("%lld", &n);
    int *a = new int[n];
 
    for(i = 0; i < n;i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &m);
    int *b = new int[m];
 
    for(q = 0;q < m;q++)
        scanf("%lld", &b[q]);
    int *c = new int[n + m];
 
    merge(a, b, c, n, m);
 
    for(d = 0; d < n + m;d++)
        printf("%lld\n", c[d]);
    delete[]a;
    delete[]b;
    delete[]c;
 
    getch();
 
    return 0;
}

Все та же ошибка. Я спросил у препода про ошибку. Он тоже не знает. Я в шоке

alsav22 · 10.06.2014, 15:29

Сообщение от Sh@dow777

Все та же ошибка.

Какая?

@Sh@dow777 · 10.06.2014, 15:56 **[ТС]**

alsav22, HEAP CORRUPTION DETECTED

Добавлено через 1 минуту
alsav22, Правильно выводит массив С и одновременно выводит эту ошибку.

@Max Dark · 10.06.2014, 16:11

Опять скобки, только в 39й строке) условие равносильно

C++
1
for(d = 0; ((d < n) + m) != 0;d++)

Добавлено через 54 секунды
в результате выход за границы массива

alsav22 · 10.06.2014, 16:12

Сообщение от Sh@dow777

alsav22, HEAP CORRUPTION DETECTED

Проблема в этом спецификаторе:

C++
1
"%lld"

Закоментируйте вызов функции и проверьте. Среда какая?

@Sh@dow777 · 10.06.2014, 16:21 **[ТС]**

alsav22, MVC Professional 2010.

Добавлено через 2 минуты
Cra3y,

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
#include <stdio.h>
#include <conio.h>
 
long long int n, m;
int i, q, d;
 
void merge(int a[], int b[], int c[], long long int n, long long int m){
    int A(0), B(0);
 
    while((A + B) < (n + m))
    {
        if( (B >= m) || ( (A < n) && (a[A] >= b[B]) ) )
        {
            c[A + B] = a[A];
            ++A;
        } else
        {
            c[A + B] = b[B];
            ++B;
        }
    }
}
int main()
{
    scanf("%lld", &n);
    int *a = new int[n];
 
    for(i = 0; i < n;i++)
        scanf("%lld", &a[i]);
    scanf("%lld", &m);
    int *b = new int[m];
 
    for(q = 0;q < m;q++)
        scanf("%lld", &b[q]);
    int *c = new int[n + m];
 
    merge(a, b, c, n, m);
 
    for(d = 0; d < (n + m);d++)
        printf("%lld\n", c[d]);
    delete[]a;
    delete[]b;
    delete[]c;
 
    getch();
 
    return 0;
}

Все тоже самое.

@Max Dark · 10.06.2014, 16:23

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
#include <iostream>
#include <cstdint>
 
void merge(const uint64_t *a, const uint64_t *b, uint64_t *c, size_t n, size_t m){
    size_t A(0), B(0);
 
    while((A + B) < (n + m)) {
        if( (B >= m) ||
            ( (A < n) && (a[A] >= b[B]) ) )
        {
            c[A + B] = a[A];
            ++A;
        }
        else {
            c[A + B] = b[B];
            ++B;
        }
    }
}
void enter(std::istream &in, uint64_t *a, size_t sz) {
    for(size_t i = 0; i< sz; ++i)
        in>>a[i];
}
void output(std::ostream &out, uint64_t *a, size_t sz) {
    for(size_t i = 0; i< sz; ++i)
        out<<a[i]<<std::endl;
}
int main() {
    size_t n, m;
 
    std::cin>>n;
    uint64_t *a = new uint64_t[n];
    enter(std::cin, a, n);
 
    std::cin>>m;
    uint64_t *b = new uint64_t[m];
    enter(std::cin, b, m);
    
    uint64_t *c = new uint64_t[n + m];
 
    merge(a, b, c, n, m);
 
    output(std::cout, c, n + m);
    
    delete []a;
    delete []b;
    delete []c;
 
    return 0;
}

alsav22 · 10.06.2014, 16:24

Сообщение от Sh@dow777

MVC Professional 2010.

...

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

Проблема в этом спецификаторе: "%lld"

@Sh@dow777 · 10.06.2014, 16:28 **[ТС]**

alsav22, Так мне нужно long long, так как

Сообщение от Sh@dow777

M (1 ≤ M ≤ 100 000)

Сообщение от Sh@dow777

N (1 ≤ N ≤ 100 000)

Сообщение от Sh@dow777

Каждое число лежит в диапазоне от 1 до 1 000 000 000.

alsav22 · 10.06.2014, 16:34

Сообщение от Sh@dow777

Так мне нужно long long, так как

И? Я вам написал причину ошибка. Вопросы по поводу scanf() и того, что вам нужно, задавайте на форуме Си, здесь С++.

@Sh@dow777 · 10.06.2014, 16:36 **[ТС]**

alsav22, Спасибо. Вы очень добры.

alsav22 · 10.06.2014, 16:42

Не по теме:

Сообщение от Sh@dow777

alsav22, Спасибо. Вы очень добры.

Приходите ещё...:)

@Sh@dow777 · 10.06.2014, 16:57 **[ТС]**

alsav22, Хорошо. Вот моя другая программа. Тоже связана с сортировкой слиянием. Она была написана на Си, но для ВАС я переделал ее для С++. Та же ошибка.

Сообщение от Sh@dow777

HEAP CORRUPTION DETECTED

Что скажете?

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
60
61
62
63
#include <iostream>
#include <conio.h>
using namespace std;
 
void Merge(int *A, int first, int last)
{
    int middle, start, final, j;
    int *mas=new int[last];
    middle = (first + last) / 2;
    start = first;
    final = middle + 1;
    for (j = first; j <= last; j++)
    {
        if ((start <= middle) && ((final>last) || (A[start]<A[final])))
        {
            mas[j] = A[start];
            start++;
        }
        else
        {
            mas[j] = A[final];
            final++;
        }
    }
    for (j = first; j <= last; j++)
    {
        A[j] = mas[j];
    }
    delete[]mas;
}
void MergeSort(int *A, int first, int last)
{
    if (first<last)
    {
        MergeSort(A, first, (first + last) / 2);
        MergeSort(A, (first + last) / 2 + 1, last);
        Merge(A, first, last);
    }
}
int main()
{
    int i, n;
    
    cin >> n;
    int *A = new int[n];
 
    for (i = 0; i < n; i++)
    {
        cin >> A[i];
    }
 
    MergeSort(A, 1, n);
     
    for (i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    delete[]A;
    
    getch();
 
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@Tchikh 52 / 72 / 20 Регистрация: 23.01.2013 Сообщений: 273
	10.06.2014, 00:47
	Массивы a и b необязательно сортировать, они уже отсортированы по условию 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	10.06.2014, 15:56 [ТС]
	alsav22, HEAP CORRUPTION DETECTED Добавлено через 1 минуту alsav22, Правильно выводит массив С и одновременно выводит эту ошибку. 0

@Sh@dow777 17 / 17 / 6 Регистрация: 10.12.2013 Сообщений: 740
	10.06.2014, 16:36 [ТС]
	alsav22, Спасибо. Вы очень добры. 0