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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
MrSq
0 / 0 / 0
Регистрация: 24.02.2014
Сообщений: 14
#1

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

14.10.2016, 12:00. Просмотров 239. Ответов 7
Метки нет (Все метки)

Вход:
- программа, получает рандомные числа от 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) !!!
Самое основное это условие
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.10.2016, 12:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вывести на экран пары чисел с наименьшей разностью (C++):

Написать алгоритм вывода на экран пар с наименьшей разностью - C++
Всем доброго времени суток. Помогите мне пожалуйста с алгоритмом! Никак не могу написать :wall: Создавал ранее на форуме тему....

Найти в каждой строке текста слова наименьшей длины и вывести на экран - C++
Здравствуйте! Подскажите, пожалуйста, как исправить код, чтобы программа находила в каждой строке текста слова наименьшей длины и...

Ввести 10 действительных чисел, вывести число с наименьшей дробной частью - C++
/*16.Ввести 10 действительных чисел, вывести число с наименьшей дробной частью.*/ #include &lt;stdio.h&gt; #include &quot;StdAfx.h&quot; #include...

Написать программу, которая находит и выводит на экран пары дружественных чисел - C++
Кто знает как решить задачу на С++, при помощи вложенных циклов? Написать программу, которая находит и выводит на экран пары дружественных ...

Вывести максимальный с каждой пары двух соседних елементов масива.Здесь выводит только с первой пары! - C++
//--------------------------------------------------------------------------- #include &lt;vcl.h&gt; #pragma hdrstop #include&lt;conio.h&gt; ...

Можно ли разбить последовательность на пары так, чтобы произведение чисел любой пары было одинаковым? - C++
Помогите написать код задачи на с++ Дана последовательность целых чисел. Выяснить, можно разбить ее на пары таким образом , чтобы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
stzer
94 / 70 / 21
Регистрация: 26.10.2013
Сообщений: 220
Завершенные тесты: 2
14.10.2016, 15:28 #2
Не совсем понятны примеры. Почему в первом ответ не 1 с числами 4 и 5?
Во втором есть 8 и 7.

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

Тоесть второй елемент минус первый и + наверное нужно проверять если второй елемент больше первого тогда отнимаем, если меньше то смотрим дальше.
0
stzer
94 / 70 / 21
Регистрация: 26.10.2013
Сообщений: 220
Завершенные тесты: 2
14.10.2016, 16:24 #4
8, 4, 7, 1, 9, 13, 11, 75, 21

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

Добавлено через 3 минуты
А проблема будет другая, нужно будет находить числа найменьшей разности не линейным путем.
Ибо алгоритм будет со сложностью O(n), очень долго.
0
Invader0x7F
Helper C/C++
281 / 158 / 61
Регистрация: 22.09.2016
Сообщений: 519
Завершенные тесты: 5
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();
}
1
Миниатюры
Вывести на экран пары чисел с наименьшей разностью  
Invader0x7F
Helper C/C++
281 / 158 / 61
Регистрация: 22.09.2016
Сообщений: 519
Завершенные тесты: 5
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), в зависимости от набора данных.
1
MrSq
0 / 0 / 0
Регистрация: 24.02.2014
Сообщений: 14
15.10.2016, 18:28  [ТС] #8
Спасибо вам, но жаль мне врядли это подойдет, потому что в худшем случае программа должна работать в сложности n log n

Добавлено через 2 минуты
Чисел может быть больше и они могут быть рандомом по убыванию в масиве, то есть от найбольшего до найменьшего, это и будет худший случай.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.10.2016, 18:28
Привет! Вот еще темы с ответами:

Вывести вместо каждой пары соседних чисел, разность которых меньше заданного числа Е, их среднеарифметическое - C++
решить ОДНУ из трех задач 1. дана убывающая последовательность чисел. вывести вместо каждой пары соседних чисел, разность которых...

В неубывающей последовательности целых чисел найти количество пар чисел с заданной разностью "D" - C++
Помогите пожалуйста оптимизировать алгоритм, тут приведен простой перебор и на большом тесте программа работает очень долго. По заданию...

Вывести на экран номер последнего честного числа в массиве, если четных чисел нет – вывести сообщение - C++
Помогите написать код... очень надо для зачета!))) желательно на С++ дев... чтобы с описаниями)) Помогите бедному студенту... Задача. ...

Дан массив натуральных чисел А[m,n] и число а. Вывести этот массив на экран, вычислит количество элементов равных а и вывести их индексы - C++
Дан массив натуральных чисел А и часло а. Вывести этот массив на экран, обчислить количество элементов равных а и вывести их индексы. ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.10.2016, 18:28
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru