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

Вывести на экран пары чисел с наименьшей разностью - C++

Восстановить пароль Регистрация
 
MrSq
0 / 0 / 0
Регистрация: 24.02.2014
Сообщений: 14
14.10.2016, 12:00     Вывести на экран пары чисел с наименьшей разностью #1
Вход:
- программа, получает рандомные числа от 0 <= 100;

Выход:
- программа, сначала, должна вывести найменьшее абсолютное значение разности соседних чисел в масиве. После этого программа должна вывести пары чисел найменшей разности

Пример 1
Вход: 5, 4, 7, 1, 9, 13
Выход:
2
7 9

Пример 2
Вход: 8, 4, 7, 1, 9, 13, 11, 75, 21
Выход:
2
7 9
9 11
11 13

ВНИМАНИЕ!
1) Программа не должна использовать встроеные алгоритмы сортирования!!!
2) Программа должна работать в сложности O(n log n) !!!

Help!!!

Добавлено через 4 минуты
Цитата Сообщение от MrSq Посмотреть сообщение
ВНИМАНИЕ!
1) Программа не должна использовать встроеные алгоритмы сортирования!!!
2) Программа должна работать в сложности O(n log n) !!!
Самое основное это условие
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.10.2016, 12:00     Вывести на экран пары чисел с наименьшей разностью
Посмотрите здесь:

C++ Найти в каждой строке текста слова наименьшей длины и вывести на экран
C++ Вывести вместо каждой пары соседних чисел, разность которых меньше заданного числа Е, их среднеарифметическое
Ввести 10 действительных чисел, вывести число с наименьшей дробной частью C++
C++ В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D"
Вывести максимальный с каждой пары двух соседних елементов масива.Здесь выводит только с первой пары! C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stzer
38 / 59 / 17
Регистрация: 26.10.2013
Сообщений: 172
Завершенные тесты: 2
14.10.2016, 15:28     Вывести на экран пары чисел с наименьшей разностью #2
Не совсем понятны примеры. Почему в первом ответ не 1 с числами 4 и 5?
Во втором есть 8 и 7.

В условии сказано "соседних чисел в массиве". Соседние - это числа, индексы у которых различются на 1.
MrSq
0 / 0 / 0
Регистрация: 24.02.2014
Сообщений: 14
14.10.2016, 16:13  [ТС]     Вывести на экран пары чисел с наименьшей разностью #3
Видимо:
9 - 7 = 2
11 - 9 = 2
и т.д

Тоесть второй елемент минус первый и + наверное нужно проверять если второй елемент больше первого тогда отнимаем, если меньше то смотрим дальше.
stzer
38 / 59 / 17
Регистрация: 26.10.2013
Сообщений: 172
Завершенные тесты: 2
14.10.2016, 16:24     Вывести на экран пары чисел с наименьшей разностью #4
8, 4, 7, 1, 9, 13, 11, 75, 21

11 - 13 = -2
MrSq
0 / 0 / 0
Регистрация: 24.02.2014
Сообщений: 14
14.10.2016, 16:43  [ТС]     Вывести на экран пары чисел с наименьшей разностью #5
надо проверять видимо, вот такая вот задача. Не лучшим образом описанная
Цитата Сообщение от MrSq Посмотреть сообщение
если второй елемент больше первого тогда отнимаем, если меньше то смотрим дальше.
Добавлено через 2 минуты
Если сначала отсортировать данный масив, каким-то алгоритмом со сложностю n log n, данные будуть отсортированные тогда такой проблемы не будет

Добавлено через 3 минуты
А проблема будет другая, нужно будет находить числа найменьшей разности не линейным путем.
Ибо алгоритм будет со сложностью O(n), очень долго.
Invader0x7F
Helper C/C++
 Аватар для Invader0x7F
264 / 141 / 56
Регистрация: 22.09.2016
Сообщений: 478
Завершенные тесты: 4
14.10.2016, 18:00     Вывести на экран пары чисел с наименьшей разностью #6
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
77
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream> 
 
typedef struct Pair
{
    int min_i;
    int min_n;
    int diff;
} PAIR;
 
using namespace std;
 
int main()
{
    const int N = 10;
 
    std::srand((unsigned)std::time(NULL));
    
    int A[N] = { 0 }; PAIR pairs[N * N] = { { 0 } };
    for (int index = 0; index < N; index++)
    {
        A[index] = std::rand() % (N - 1) + 1;
        std::cout << A[index] << " ";
    }
 
    std::cout << endl;
 
    int min_diff = 0, min_i = -1, min_n = -1;
    for (int index = 0; index < N - 1; index++)
    {
        if ((std::abs(A[index] - A[index + 1]) < min_diff) || (min_i == -1))
        {
            min_i = index;
            min_diff = abs(A[index] - A[index + 1]);
        }
    }
 
    std::cout << A[min_i] << " " << A[min_i + 1] << endl << endl;
 
    int n = 0;
    for (int r = 0; r < 2 * N * log(N) - 1; r++)
    {
        min_n = min_i = -1; min_diff = 0;
        for (int index = 0; index < N; index++)
            for (int nindex = index + 1; nindex < N; nindex++)
            {
                if ((std::abs(A[index] - A[nindex]) < min_diff) || 
                    ((min_i == -1) && (min_n == -1)))
                {
                    bool exists = false;
                    for (int v = n - 1; v >= 0 && exists == false; v--)
                        if (pairs[v].min_i == index && pairs[v].min_n == nindex)
                            exists = true;
 
                    if (exists == false)
                    {
                        min_i = index; min_n = nindex;
                        min_diff = abs(A[index] - A[nindex]);
                    }
                }
            }
 
        if (min_i > -1 && min_n > -1)
        {
            pairs[n].min_i = min_i;
            pairs[n].min_n = min_n;
            pairs[n++].diff = std::abs(A[min_i] - A[min_n]);
        }
    }
 
    for (int z = 0; z < n; z++)
        std::cout << A[pairs[z].min_i] << " " << A[pairs[z].min_n] << " diff = " << pairs[z].diff << endl;
 
    std::cin.get();
}
Миниатюры
Вывести на экран пары чисел с наименьшей разностью  
Invader0x7F
Helper C/C++
 Аватар для Invader0x7F
264 / 141 / 56
Регистрация: 22.09.2016
Сообщений: 478
Завершенные тесты: 4
14.10.2016, 18:07     Вывести на экран пары чисел с наименьшей разностью #7
Пример 2
Вход: 8, 4, 7, 1, 9, 13, 11, 75, 21
Выход:
2
7 9
9 11
11 13
Кроме указанных в примере, программа должна выводить также и другие варианты.

2) Программа должна работать в сложности O(n log n) !!!
Данная программа будет иметь сложность не O(n log2(n)), а O(n log2(n^2)) = O(2 * n * log2(N)).
И будет "вырождаться" в O(N^2), в зависимости от набора данных.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.10.2016, 18:28     Вывести на экран пары чисел с наименьшей разностью
Еще ссылки по теме:

C++ Можно ли разбить последовательность на пары так, чтобы произведение чисел любой пары было одинаковым?
C++ Вывести на экран таблицу чисел
C++ Вывести на экран квадраты чисел от 10 до 20

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

Или воспользуйтесь поиском по форуму:
MrSq
0 / 0 / 0
Регистрация: 24.02.2014
Сообщений: 14
15.10.2016, 18:28  [ТС]     Вывести на экран пары чисел с наименьшей разностью #8
Спасибо вам, но жаль мне врядли это подойдет, потому что в худшем случае программа должна работать в сложности n log n

Добавлено через 2 минуты
Чисел может быть больше и они могут быть рандомом по убыванию в масиве, то есть от найбольшего до найменьшего, это и будет худший случай.
Yandex
Объявления
15.10.2016, 18:28     Вывести на экран пары чисел с наименьшей разностью
Ответ Создать тему
Опции темы

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