Уникальные пары с равной суммой в C

Question

Уникальные пары с равной суммой в C

Реализация GCC ELF Linux

main.c:

#include 

int not_extern_int = 1;
extern int extern_int;

void main() {
    printf("%d\n", not_extern_int);
    printf("%d\n", extern_int);
}

Скомпилировать и декомпилировать:

gcc -c main.c
readelf -s main.o

Выход содержит:

Num:    Value          Size Type    Bind   Vis      Ndx Name
 9: 0000000000000000     4 OBJECT  GLOBAL DEFAULT    3 not_extern_int
12: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND extern_int

В главе System V ABI Update ELF spec главу «Таблица символов» объясняется:

SHN_UNDEF Этот индекс таблицы разделов означает, что символ не определен. Когда редактор ссылок объединяет этот объектный файл с другим, который определяет указанный символ, ссылки этого файла на символ будут связаны с фактическим определением.

, который в основном является поведением, которое дает стандарт C to extern.

С этого момента задача компоновщика заключается в создании окончательной программы, но информация extern уже извлечена из исходного кода в объектный файл.

Проверено на GCC 4.8.

0

c algorithm time-complexity

задан Mark Benningfield 20 March 2019 в 14:37

1 ответ

Другие вопросы по тегам:

c algorithm time-complexity

Похожие вопросы:

score 0 · Answer 1

C-код для расчета всех сумм и хранения сумм с индексами внутри массива структур. Затем мы сортируем структуры и печатаем смежные элементы структуры с одинаковой суммой.

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <errno.h>
#include <assert.h>

// for debugging
#define debug(...)  ((void)0) // printf(__VA_ARGS__)

// two indexes and a sum
struct is_s {
    // one index inside the array
    size_t i;
    // the other index also inside the array
    size_t j;
    // no idea, must be random
    int sum;
};

// used for qsoring the struct is_s
static int is_qsort_compare_sum(const void *a0, const void *b0) {
    const struct is_s * const a = a0;
    const struct is_s * const b = b0;
    return a->sum - b->sum;
}

int unique_pairs(const size_t len, const int arr[len]) {
    if (len <= 1) return 0;
    // The number of unsorted combinations must be n!/(2!*(n-2)!)
    const size_t islen = len * (len - 1) / 2; // @MOehm
    debug("%zu\n", islen);

    struct is_s * const is = malloc(islen * sizeof(*is));
    if (is == NULL) {
        return -ENOMEM;
    }

    size_t isidx = 0;
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = i + 1; j < len; ++j) {
            assert(isidx < islen); // just for safety
            struct is_s * const p = &is[isidx++];
            p->i = i;
            p->j = j;
            p->sum = arr[i] + arr[j];
            debug("[%zu]=[%zu]=%d [%zu]=%d %d\n", isidx, p->i, arr[p->i], p->j, arr[p->j], p->sum);
        }
    }

    qsort(is, islen, sizeof(*is), is_qsort_compare_sum);

    for (size_t i = 0; i < islen - 1; ++i) {
        debug("([%zu]=%d,[%zu]=%d)%d = ([%zu]=%d,[%zu]=%d)%d\n", 
            is[i].i, arr[is[i].i], is[i].j, arr[is[i].j], is[i].sum,
            is[i+1].i, arr[is[i+1].i], is[i+1].j, arr[is[i+1].j], is[i+1].sum
        );
        if (is[i].sum == is[i + 1].sum) {
            printf("(%d,%d),(%d,%d) = %d\n",
                arr[is[i].i], arr[is[i].j],
                arr[is[i+1].i], arr[is[i+1].j], is[i].sum);
        }
    }

    free(is);

    return 0;
}

int main(void) {
    const int arr[] = {6,4,12,10,22,54,32,42,21,11};
    return unique_pairs(sizeof(arr)/sizeof(*arr), arr);
}

Результат, который я получаю:

(6,10),(4,12) = 16
(10,22),(21,11) = 32
(12,21),(22,11) = 33
(22,21),(32,11) = 43
(32,21),(42,11) = 53
(12,42),(22,32) = 54
(10,54),(22,42) = 64

Поскольку я задаюсь вопросом, правильно ли это, как заметил @Bathsheba, я думаю, что худший случай - O (n * n).