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

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

Восстановить пароль Регистрация
 
 
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
09.06.2014, 22:56     Объединить 2 массива в один, в котором все числа идут по убыванию #1
Привет всем. Мне нужно объединить 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;
        }
    }
}
Скажите, этот код подходит? Если да, то как изменить его, чтоб числа в массиве С шли по убыванию?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2014, 22:56     Объединить 2 массива в один, в котором все числа идут по убыванию
Посмотрите здесь:

За один просмотр символов строки найти все самые длинные слова, символы в которых идут в строгом возрастании кодов C++
объединить три 2-мерных массива в один 3-мерный массив C++
C++ Получить новый массив, в котором сначала идут положительные числа, затем нулевые, затем отрицательные исходного
Объединить элементы 2-х массивов в один массив, содержащий все различные числа C++
C++ Как объединить два массива в один?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tchikh
50 / 70 / 11
Регистрация: 23.01.2013
Сообщений: 253
09.06.2014, 23:11     Объединить 2 массива в один, в котором все числа идут по убыванию #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;
        }
    }
}
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 00:45  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #3
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
50 / 70 / 11
Регистрация: 23.01.2013
Сообщений: 253
10.06.2014, 00:47     Объединить 2 массива в один, в котором все числа идут по убыванию #4
Массивы a и b необязательно сортировать, они уже отсортированы по условию
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 02:58  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #5
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
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
10.06.2014, 04:34     Объединить 2 массива в один, в котором все числа идут по убыванию #6
у вас условие в 10й строке равносильно
C++
1
while((A + (B < n) + m) != 0)
т.к. приоритет операции "+" выше, чем "<".
Расставьте скобки:
C++
1
while((A + B) < (n + m))
Trwsdf
Заблокирован
10.06.2014, 11:28     Объединить 2 массива в один, в котором все числа идут по убыванию #7
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
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 13:27  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #8
Вот я исправил, как сказал 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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
10.06.2014, 15:29     Объединить 2 массива в один, в котором все числа идут по убыванию #9
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Все та же ошибка.
Какая?
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 15:56  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #10
alsav22, HEAP CORRUPTION DETECTED

Добавлено через 1 минуту
alsav22, Правильно выводит массив С и одновременно выводит эту ошибку.
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
10.06.2014, 16:11     Объединить 2 массива в один, в котором все числа идут по убыванию #11
Опять скобки, только в 39й строке) условие равносильно
C++
1
for(d = 0; ((d < n) + m) != 0;d++)
Добавлено через 54 секунды
в результате выход за границы массива
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
10.06.2014, 16:12     Объединить 2 массива в один, в котором все числа идут по убыванию #12
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
alsav22, HEAP CORRUPTION DETECTED
Проблема в этом спецификаторе:
C++
1
"%lld"
Закоментируйте вызов функции и проверьте. Среда какая?
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 16:21  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #13
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
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
10.06.2014, 16:23     Объединить 2 массива в один, в котором все числа идут по убыванию #14
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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
10.06.2014, 16:24     Объединить 2 массива в один, в котором все числа идут по убыванию #15
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
MVC Professional 2010.
...
Цитата Сообщение от alsav22 Посмотреть сообщение
Проблема в этом спецификаторе: "%lld"
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 16:28  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #16
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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
10.06.2014, 16:34     Объединить 2 массива в один, в котором все числа идут по убыванию #17
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
Так мне нужно long long, так как
И? Я вам написал причину ошибка. Вопросы по поводу scanf() и того, что вам нужно, задавайте на форуме Си, здесь С++.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 16:36  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #18
alsav22, Спасибо. Вы очень добры.
alsav22
10.06.2014, 16:42
  #19

Не по теме:

Цитата Сообщение от Sh@dow777 Посмотреть сообщение
alsav22, Спасибо. Вы очень добры.
Приходите ещё...

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2014, 16:57     Объединить 2 массива в один, в котором все числа идут по убыванию
Еще ссылки по теме:

Объединить два упорядоченных по неубыванию массива в один C++
C++ Объединить два упорядоченных массива в один
Два двумерных массива объединить в один двумерный C++

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

Или воспользуйтесь поиском по форуму:
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
10.06.2014, 16:57  [ТС]     Объединить 2 массива в один, в котором все числа идут по убыванию #20
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;
}
Yandex
Объявления
10.06.2014, 16:57     Объединить 2 массива в один, в котором все числа идут по убыванию
Ответ Создать тему
Опции темы

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