Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.71/21: Рейтинг темы: голосов - 21, средняя оценка - 4.71
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85

Разница множеств с использованием qsort

11.12.2020, 18:22. Показов 4717. Ответов 25

Студворк — интернет-сервис помощи студентам
Даны два массива чисел А и В. Требуется найти все такие значения элементов массива А, которых нет среди элементов массива В. В задаче необходимо использовать функцию qsort.
Сигнатура:
В первой строке записано целое число N (1<=N<=10^5) - количество элементов массива А. Во второй строке через пробел записаны N целых чисел, каждое из которых не превосходит по абсолютной величине 10^9 - элементы массива А. В следующих двух строках в аналогичном формате записаны элементы массива В. В первой строке нужно вывести одно целое число - количество значений, удовлетворяющих описанному условию. Во второй строке нужно вывести все такие значения в порядке возрастания.
У меня в голову приходит только код без qsort. Работать-то работает, да только без нужной функции. Естественно, на одном из тестов в системе программа валится. Подскажите, пожалуйста, как впихнуть сюда qsort:
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
#include<stdio.h>
int main()
{
    int N;
    int A[100001] = {0}; 
    scanf("%d", &N);
    for (int i = 0, k; i < N; i++)
    {
        scanf("%d", &k);
        A[k] = 1;
    }
    scanf("%d", &N);  
    for (int i = 0, k; i < N; i++)
    {
        scanf("%d", &k);
        A[k] = 0;  
    }
    N = 0;
    for (int i = 0; i <= 100000; i++)
        N += A[i];
    printf("%d\n", N);
    for (int i = 0; i <= 100000; i++)
        if (A[i]) printf("%d ", i);
 
    puts("");
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.12.2020, 18:22
Ответы с готовыми решениями:

Сортировка массива структур с использованием qsort
Народ прошу помощи, нужно отсортировать массив структур с помощью функции qsort() typedef struct word { int count; char...

Разница двух множеств (коллекций) LinkedList
Подскажите, пожалуйста как найти разницу двух linkedlist. У меня есть одна коллекция &quot;a&quot;, и есть другая коллекция...

2 Combobox-а, пересечение и разница двух множеств
Есть 3 комбобокса, нужно удалить те элементы в ComboBox1 которые есть в ComboBox2, элементы которые остались в ComboBox1 записать в...

25
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85
12.12.2020, 20:54  [ТС]
Студворк — интернет-сервис помощи студентам
analogov net, все равно спасибо буду думать дальше
0
 Аватар для analogov net
2532 / 1130 / 495
Регистрация: 17.11.2018
Сообщений: 2,840
13.12.2020, 01:13
Лучший ответ Сообщение было отмечено A_Hatake как решение

Решение

Цитата Сообщение от A_Hatake Посмотреть сообщение
буду думать дальше
Давай, я тоже попробую. Но не обещаю... Что-то бестолковка не фурычит совсем...

Добавлено через 2 часа 6 минут
A_Hatake, можешь кинуть сюда немного разных хитрых наборов входных данных? Потестить хочу...

Добавлено через 2 часа 9 минут
A_Hatake, короче, сам попробуй потестировать. Я ушёл в туман...
Кликните здесь для просмотра всего текста
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
#define N 100000
int cmp( const void *a, const void *b )
{
    return *( int * ) a - *( int * ) b;
}
void fillArray( int *ar, int *n )
{
    scanf( "%d", n );
    for( int i = 0; i < *n; i++ )
        scanf( "%d", &ar[i] );
    qsort( ar, *n, sizeof( int ), cmp );
}
int main()
{
    int A[N], B[N], i, j, k, n, m;
 
    fillArray( A, &n );
    fillArray( B, &m );
 
    i = j = k = 0;
    if( A[i] < B[j] )
        A[k++] = A[i++];
    while( i < n && j < m )
    {
        if( A[i] < B[j] && A[i] != A[i - 1] )
            A[k++] = A[i++];
        else if( B[j] < A[i] )
            j++;
        else
            i++;
    }
 
    for( ; i < n; i++ )
        if( A[i] != A[i - 1] )
            A[k++] = A[i];
 
    printf( "%d\n", k );
    for( i = 0; i < k; i++ )
        printf( "%d ", A[i] );
 
    return 0;
}
1
2493 / 1157 / 709
Регистрация: 25.04.2016
Сообщений: 3,339
13.12.2020, 06:40
Цитата Сообщение от A_Hatake Посмотреть сообщение
все хорошо, только повторяющиеся элементы выводить и считать не нужно. Как это сделать?
Цитата Сообщение от A_Hatake Посмотреть сообщение
А при тестировании приведенной программы вывод такой:
4
2 6 8 8
Ну так добавьте проверку на вхождение проверяемого значения еще и в unique:
C
1
2
3
4
int size = 0;   // число уникальных
for (int i = 0; i < n; i++)     // находим уникальные
    if ( !search_value(b, m, a[i]) && !search_value(unique, size, a[i]) )
        unique[size++] = a[i];
Смысл такой:
Если a[i] не входит в массив b[m], а так же не входит в массив unique[size], добавить a[i] в unique и увеличить его размер на 1.

Вы бы за секунду с этим управились, если бы понимали как работает алгоритм.

Добавлено через 2 часа 41 минуту
По сути, весь алгоритм программы сводится к удавокоду:
Python
1
2
3
4
5
6
7
a = [int(i) for i in input().split()]       # Заполняем список a[] с клавиатуры
b = [int(i) for i in input().split()]       # Заполняем список b[] с клавиатуры
unique = {i for i in a if i not in b}       # Формируем множество уникальных
uSize = len(unique)                         # Узнаем количество уникальных
print(f'\n{uSize}')                         # Выводим число уникальных и
if (uSize > 0):                             # отсортированные элементы unique,
    print( *sorted(unique) )                #   если таковые имеются
1
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85
13.12.2020, 13:21  [ТС]
analogov net, stake-k26, спасибо!!! Все получилось
0
2493 / 1157 / 709
Регистрация: 25.04.2016
Сообщений: 3,339
15.12.2020, 09:11
Кстати, если вы сортируете исходные массивы A и B, то в unique оказываются сразу отсортированные значения, а значит, вместо линейного поиска, можно смело использовать бинарный. из того же stdlib например:
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
75
76
#include <stdio.h>
#include <stdlib.h>
 
const size_t nsize = sizeof(int);
 
int cmp (const void * one, const void * two) {
    return *(int *)one - *(int *)two;
}
 
void get_error (int error_code, const char message[]) {
    fputs(message, stderr);
    exit(error_code);
}
 
int get_elements (int a[], int size) {
    for (int i = 0; i < size; i++)
        if (scanf("%d", &a[i]) != 1)
            return 0;
    qsort(a, size, nsize, cmp);
    return 1;
}
 
int main (void) {
    int n, m;
    if (scanf("%d", &n) != 1 || n < 1)          // размер массива a
        get_error(1, "Wrong size of array!");
 
    int *a = (int *) calloc(n, nsize);          // создаем массив
    if (a == NULL)
        get_error(2, "Can't allocate memory!");
 
    if ( !get_elements(a, n) ) {                // считываем элементы массива
        free(a);
        get_error(3, "Can't read the data!");
    }
 
    if (scanf("%d", &m) != 1 || m < 1) {        // размер массива b
        free(a);
        get_error(1, "Wrong size of array!");
    }
    int *b = (int *) calloc(m, nsize);          // создаем массив
    if (b == NULL) {
        free(a);
        get_error(2, "Can't allocate memory!");
    }
    if ( !get_elements(b, m) ) {                // считываем элементы массива
        free(a);
        free(b);
        get_error(3, "Can't read the data!");
    }
 
    int *unique = (int *) calloc(n, nsize);     // массив уникальных
    if (unique == NULL) {
        free(a);
        free(b);
        get_error(2, "Can't allocate memory!");
    }
 
    int i, size = 0;                            // число уникальных
    for (i = 0; i < n; i++)                     // находим уникальные
        if( !bsearch(&a[i], b, m, nsize, cmp) &&
            !bsearch(&a[i], unique, size, nsize, cmp) )
                unique[size++] = a[i];
 
    printf("%d\n", size);                       // выводим результат на экран
    if (size > 0) {
        for (i = 0; i < size; i++)
            printf("%d ", unique[i]);
        puts("");
    }
 
    free(a);                                    // освобождаем память и выходим
    free(b);
    free(unique);
    return 0;
}
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38223 / 21155 / 4314
Регистрация: 12.02.2012
Сообщений: 34,765
Записей в блоге: 14
15.12.2020, 12:42
Цитата Сообщение от A_Hatake Посмотреть сообщение
одскажите, пожалуйста, как впихнуть сюда qsort:
- нужно отсортировать исходный массив, а для поиска элементов использовать двоичный поиск
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
15.12.2020, 12:42

Программирование с использованием множеств.
Дано 30 целых чисел от 1 до 20. Подсчитать, сколько среди них чисел, делящихся на 3.

задачу по С++ с использованием множеств
Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать...

Задача с использованием множеств
При решении задачи обязательно использовать множества

использованием множеств и строк
Дана строка символов, состоящая из произвольного текста на английском языке, слова разделены пробелами. Вывести на экран порядковый номер...

Программирование с использованием множеств
Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Вывести...


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

Или воспользуйтесь поиском по форуму:
26
Ответ Создать тему
Новые блоги и статьи
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .
[EasyBuilder Pro] Памятка по разработке для панелей Weintek
ФедосеевПавел 26.08.2026
Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
Запись в регистр сведений независимо от заполненности табличной части
Maks 25.08.2026
Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?
Мастера простых решений
DevAlt 23.08.2026
В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru