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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Замена оператора % http://www.cyberforum.ru/cpp-beginners/thread1849959.html
Привет всем форумчанам! Впервые тут, так как только начал учиться программировать. Подскажите, кто знает - как заменить оператор %? то есть, есть ли другие способы деления с модулем, не используя оператор %? Заранее спасибо всем за ответ.
C++ Только 1.5 месяца знаком с С++, а уже такое задают П.5.18.Правил Запрещено размещать задания и решения в виде картинок и других файлов с их текстом. П.5.16.Правил Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос - одна тема. Напишите пожалуйста программы, чтобы я разобрался во всём этом на С++ http://www.cyberforum.ru/cpp-beginners/thread1849932.html
Из указанной области матрицы выбрать значения элементов, сумма которых будет максимальной C++
Задать матрицу размерности m * n (m, n> 2). Начиная с левого нижнего угла матрицы и двигаясь только вправо и вверх, достичь ее правого верхнего угла и выбрать при этом такие значения элементов, сумма которых будет максимальной. Вывести выбранные элементы.
Подсчет символов в строке C++
Помогите, пожалуйста, написать программу на языке C++, которая будет подсчитывать количество введенных слов, которые заканчиваются на букву f или F Желательно БЕЗ использования массивов и указателей Сама попыталась накидать это: (типа сначала пробелы заменяются на новые строки, потом считаются), но корректно оно не работает #include<iostream> #include<stdio.h> #include<clocale> int...
C++ Найти сумму таких чисел в диапазоне [a; b], которые при возведении в квадрат превышают b http://www.cyberforum.ru/cpp-beginners/thread1849888.html
Всем привет,надо составить блоксхему к этому заданию. Вводятся числа a и b. Найти сумму таких чисел в диапазоне , которые при возведении в квадрат превышают b. тема занятия цикл for.
C++ Исправить ошибку времени выполнения Всем привет вот уже больше 2-х часов вожусь с простой задачей на динамическую память. Непосредственно весь код #include <iostream> #include <conio.h> #include <math.h> #include <algorithm> #include <ctime> #include <vector> подробнее

Показать сообщение отдельно
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2898 / 1434 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
14.11.2016, 12:34     Отсортировать 8 чисел только 16 сравнениями
Цитата Сообщение от 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 обратно в последовательность. И порядок этот диктуется так называемыми Числами Якобсталя.
 
Текущее время: 03:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru