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

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

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

Отсортировать 8 чисел только 16 сравнениями - C++

14.11.2016, 01:14. Просмотров 400. Ответов 15
Метки нет (Все метки)

Как отсортировать 8 чисел только 16 сравнениями?? Может у кого есть идеи?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.11.2016, 01:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Отсортировать 8 чисел только 16 сравнениями (C++):

Как доказать, что невозможно отсортировать 8 чисел менее чем 16 сравнениями? - C++
Как доказать, что невозможно отсортировать 8 чисел менее чем 16 сравнениями?

Отсортировать только простые числа в массиве - C++
Я написала код поиска простых чисел, их сортировки. Но мне нужно чтобы сортировались и выводились на экран не только простые числа, но и...

Отсортировать по возрастанию только четные элементы массива - C++
№1: Отсортировать по возрастанию только четные элементы массива. У меня массив сам выводится, но сортироваться не хочет, помогите...

Отсортировать текст и вывести только согласные буквы - C++
После введения с клавиатуры произвольного текста отсортировать его и выдать на екран строками по алфавиту только согласные буквы кириллицы...

Отсортировать по возрастанию только положительные элементы массива - C++
Отсортировать по возрастанию только положительные элементы массива. Как объяснил преподаватель так чтобы положительные отсортировались а...

Отсортировать только положительные элементы масива по росту - C++
Как єто сделать?

15
afront
913 / 867 / 329
Регистрация: 29.02.2016
Сообщений: 2,783
14.11.2016, 10:33 #2
обычна сортировка выбором для случая когда нужно все переставить сделает именно столько сравнений.
если начальное расположение цифр будет иным и какие то цифры стоят на "своем" месте - сравнений будет меньше

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
#include <iostream>
using namespace std;
int main()
{
    int n =8;
    int a[8] = {8,7,6,5,4,3,2,1};
    
    int count =0;
    for(int i = 0; i < n; ++i){ 
        int pos = i; 
        int tmp = a[i];
        for(int j = i + 1; j < n; ++j)
           if (a[j] < tmp){
               pos = j; 
               tmp = a[j]; 
               count++;
           }
        a[pos] = a[i]; 
        a[i] = tmp;
    }
    cout << "count = " << count << endl;
    system("pause");
    return 0;
}
0
GbaLog-
Любитель чаепитий
2900 / 1357 / 333
Регистрация: 24.08.2014
Сообщений: 4,799
Записей в блоге: 1
Завершенные тесты: 2
14.11.2016, 10:37 #3
afront, А почему вы прибавляете count, только если условие дало true?
Ведь сравнение есть, независимо от того, истину оно дало, или ложь.
0
afront
913 / 867 / 329
Регистрация: 29.02.2016
Сообщений: 2,783
14.11.2016, 11:16 #4
GbaLog-, да, я не прав, посчитал перестановки
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3899 / 2136 / 548
Регистрация: 18.10.2014
Сообщений: 3,749
14.11.2016, 12:34 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от bellaps Посмотреть сообщение
Как отсортировать 8 чисел только 16 сравнениями??
Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью. Обычный merge sort отсортирует за 17 сравнений и это будет намного практичнее.

А за 16 сравнений это делается так:

1. Сначала сортируем элементы в парах, на что понадобится 4 сравнения

[b1][a1] [b2][a2] [b3][a3] [b4][a4]

Теперь у нас b1 < a1, b2 < a2 и т.д.

2. Теперь полностью упорядочиваем между собой пары по возрастанию старших элементов пар a. На это потребуется 5 сравнений

[b1][a1] [b2][a2] [b3][a3] [b4][a4]

То есть пусть теперь у нас a1 < a2 < a3 < a4 и в то же время b1 < a1, b2 < a2 и т.д.

3. Теперь мысленно извлекаем элементы b из последовательности

[a1][a2][a3][a4]

и вставляем их по одному обратно в правильные места в такой очередности: b1, b3, b2, b4.

3.1. b1 уже находился на своем месте, поэтому мы вставляем его обратно без сравнения вообще

[b1][a1][a2][a3][a4]

3.2. b3 (который меньше a3) должен попасть куда-то до a3. На бинарный поиск места для вставки среди 3 элементов надо 2 сравнения.

Тут могут получиться разные варианты:

[b3][b1][a1][a2][a3][a4]
[b1][b3][a1][a2][a3][a4]
[b1][a1][b3][a2][a3][a4]
[b1][a1][a2][b3][a3][a4]

3.3. b2 (который меньше a2) должен попасть куда-то до a2. Обратите внимание, что область поиска в любом случае - 3 или 2 элемента. На бинарный поиск места для вставки надо 2 сравнения.

Количество возможных исходов тут вырастает и я их "рисовать" не буду.

3.4. b4 (который меньше a4) должен попасть куда-то до a4. Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения.

Все. Итого 4+5+2+2+3 = 16 сравнений.

Уменьшение количества сравнений возникает за счет хитрого выбора порядка вставки элементов b обратно в последовательность. И порядок этот диктуется так называемыми Числами Якобсталя.
2
Evg
Эксперт CАвтор FAQ
17954 / 6185 / 414
Регистрация: 30.03.2009
Сообщений: 16,974
Записей в блоге: 27
14.11.2016, 12:46 #6
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ну алгоритм тут довольно хитрый (описан у Кнута) и с не очень большой практической ценностью
Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3899 / 2136 / 548
Регистрация: 18.10.2014
Сообщений: 3,749
14.11.2016, 12:51 #7
Цитата Сообщение от Evg Посмотреть сообщение
Есть подозрение, что подобные алгоритмы разрабатывают для реализации в железе, а не в софте
Трудно сказать... При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше. 8 элементов - 19 компараторов минимум.
0
zer0mail
2344 / 1974 / 193
Регистрация: 03.07.2012
Сообщений: 7,095
Записей в блоге: 1
14.11.2016, 16:27 #8
Интересно, можно ли отсортировавать:
элементов сравнений
5......................7
6.....................10
7.....................13
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3899 / 2136 / 548
Регистрация: 18.10.2014
Сообщений: 3,749
14.11.2016, 19:12 #9
Цитата Сообщение от zer0mail Посмотреть сообщение
Интересно, можно ли отсортировавать:
элементов сравнений
5......................7
6.....................10
7.....................13
Да, можно.
0
zer0mail
2344 / 1974 / 193
Регистрация: 03.07.2012
Сообщений: 7,095
Записей в блоге: 1
14.11.2016, 19:22 #10
Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима..
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3899 / 2136 / 548
Регистрация: 18.10.2014
Сообщений: 3,749
14.11.2016, 19:31 #11
Цитата Сообщение от zer0mail Посмотреть сообщение
Теория информации определяет нижнюю границу (в правом столбике). Но нижняя граница не всегда достижима..
Таблица справа в

https://en.wikipedia.org/wiki/Compar...to_sort_a_list

содержит известные результаты. Расхождение с теоретической нижней границей начинается с 12 элементов, но периодически возвращается на границу.
1
Evg
Эксперт CАвтор FAQ
17954 / 6185 / 414
Регистрация: 30.03.2009
Сообщений: 16,974
Записей в блоге: 27
14.11.2016, 19:46 #12
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
При упоминании железа на ум сразу приходят сети сортировки. Но в сетях сортировки порядок сравнений жестко прошит заранее и из-за этого сравнений (компараторов) получается больше
В железных алгоритмах (например, в микросхеме), насколько я понимаю, наиболее критичным является количество тактов. Типа того, что 4 сравнения можно выполнять параллельно (одновременно)
0
bellaps
0 / 0 / 0
Регистрация: 28.10.2016
Сообщений: 7
14.11.2016, 20:05  [ТС] #13
TheCalligrapher, "Тут просто делается бинарный поиск места для вставки среди 6 элементов, на который надо 3 сравнения."
Я не совсем поняла, как это достижимо?
Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3899 / 2136 / 548
Регистрация: 18.10.2014
Сообщений: 3,749
14.11.2016, 20:37 #14
Цитата Сообщение от bellaps Посмотреть сообщение
Если, например, у меня ряд [b1] [b2] [a1] [a2] [b3] [a3] [a4], то с чем именно мне сравнивать b4,чтобы получилось за 3 срнвнения?
b4 заведомо меньше, чем a4. То есть вам надо вставить b4 слева от a4. Это запросто делается бинарным поиском за 3 сравнения. Например, в вашем варианте, начнем со сравнения с a2

Код
b4 < a2  =>  b4 < b2  =>  b4 < b1  - вставляем слева от b1
                      =>  b4 > b1  - вставляем слева от b2
         =>  b4 > b2  =>  b4 < a1  - вставляем слева от a1
                      =>  b4 > a1  - вставляем слева от a2
b4 > a2  =>  b4 < b3               - вставляем слева от b3
         =>  b4 > b3  =>  b4 < a3  - вставляем слева от a3
                      =>  b4 > a3  - вставляем слева от a4
0
bellaps
0 / 0 / 0
Регистрация: 28.10.2016
Сообщений: 7
03.12.2016, 21:56  [ТС] #15
Добавлено через 1 минуту
TheCalligrapher, Добрый день! Снова всплыл вопрос. Но разве это не 5 сравнений? Ведь сравниваем а4 с 5 остальными элементами..

Добавлено через 6 минут
Добавлю, что задание раположить элементы в возрастающей последовательности,сравнивая и перестанавливая после сравнения. В visual basic. Типа:
If a>b then
x=a
a=b
b=x
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2016, 21:56
Привет! Вот еще темы с ответами:

Отсортировать по убыванию только элементы вектора, расположенные на чётных позициях - C++
1ая. Помогите решить. с++ не изучал, поступил на заочку, дали задание 2 дня на все это сессия, спасайте)))пожайлуйста Постановка задачи ...

Определить, что только одно из чисел А и В четное и каждое из чисел А,В,С кратно трем. - C++
Здравствуйте! Помогите пожалуйста написать программу реализующее задачу, которая является истинным, когда 1)только одно из чисел А и В...

Дан массив целых чисел. Верно ли, что он состоит только из простых чисел? - C++
Дан массив целых чисел. Верно ли, что он состоит только из простых чисел?

Ввести n положительных целых чисел. Найти количество чисел, записанных только четными цифрами - C++
Всем привет.Я делаю лабу по программированию,только начала знакомиться с++,с остальными заданиями мне было всё более-менее понятно.Но тут...


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

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

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