|
|
Другие темы раздела | |
C++ Вычислите значения полиномов Лагерра Ln(x):
https://www.cyberforum.ru/ cpp-beginners/ thread1244223.html Ln(x)=\begin{cases}1 & \text{ if } n=0 \\ -x + 1 & \text{ if } n=1 \\ x^2-4x+2 & \text{ if } n=2 \\ -x^3+9x^2-18x+6 & \text{ if } n=3 \\ x^4-16x^3+72x^2-96x+24 & \text{ if } n=4 \end{cases} x = 0.5. Помогите пожалуйста!! |
Cохранение очень большого массива в текстовый файл C++ Помогите пожалуйста. Мне требуется сохранить карту в своей игре в текстовый файл. Класс карты: class cMap { public: cRegion regions; }; class cRegion { public: |
C++ Написать функцию, которая сортирует переданный ей динамический массив "быстрой" сортировкой
https://www.cyberforum.ru/ cpp-beginners/ thread1244219.html #include <iostream> #include <vector> using namespace std; void qSort( vector <int> &A,int nStart, int nEnd) { int L,R,c,X; if (nStart>=nEnd) return; L=nStart; R=nEnd; X=A; while (L<=R) |
C++ Как вывести фигуру в окне?
https://www.cyberforum.ru/ cpp-beginners/ thread1244215.html Всем доброго дня. Я знаком с C++ довольно поверхностно, но на уровне консольного приложения знаю, возможно, все. Начал изучать DirectX по книгам Горнакова С.Г., для пущего реализма поставил VC++6.0 и DX9 под WinXP - все, как у него. И все же постоянно приходится адаптировать код, чтобы избавиться от ошибок. До сего момента справлялся, однако теперь в тупике. Следующий код... |
Класс "Множество" и операции над ним C++ Не хватает опыта понять ошибку Здравствуйте! Никак не получается тот же результат хотя проверял несколько раз вот само задание: #include <iostream> using namespace std; const int MaxSize = 100; class Set{ int len; char members; int find(char ch); |
C++ Определить, какие вершины достижимы из заданной вершины S
https://www.cyberforum.ru/ cpp-beginners/ thread1244197.html Подскажите алгоритм для этой задачи, пожалуйста. Достижимые вершины Имя входного файла: graph.in Имя выходного файла: graph.out Ограничение по времени: 2 секунды Ограничение по памяти: 64 мегабайта Задан неориентированный граф, нужно определить, какие вершины достижимы |
C++ Как правильно очищать вектор указателей Привет Всем! Есть вопрос по вектору указателей, как правильно очищать память при таком случае очищение происходит существенно медленнее чем инициализация, но память очищается: #include <vector> void creat(std::vector<int*> &p) { for (int i(0); i<5000000; i++) { https://www.cyberforum.ru/ cpp-beginners/ thread1244154.html |
Защита 2д онлайн игры от взломов C++ Здравствуйте, вообщем, я пытаюсь написать 2д рпг онлайн игру, которую в будущем хотелось бы переделать под андроид и выпустить в маркет, но речь не об этом. На данный момент игра реализована как обычная 2д рпг. Позже переделаю её под клиент, который будет общаться с сервером и все необходимые данные будут заноситься сервером в БД. Больше всего беспокоюсь по поводу защиты. В принципе, уже... |
C++ Подключение библиотеки Glaux.lib и ошибка компиляции
https://www.cyberforum.ru/ cpp-beginners/ thread1244127.html Здравствуйте, У меня возникла проблема - надо подключить библиотеку GLAux (OpenGL-ая). Скачал от нее .h и .lib, подключил .h через #include, в свойствах проекта добавил Glaux.lib в дополнительные зависимости. При компиляции выдает ошибку LNK1104 : не удается открыть файл "Glaux.lib". Помогите советом, как ее правильно подключить. У меня VS C++ 2010 Express. Заранее спасибо) |
C++ Работает ли Борланд C++ 6 с Windows 7 Извиняюсь за "глупый" вопрос. Несколько лет работал с С++ В6 менялись компы, менялись ОС, но всё время установка С++ получалась не с "первого раза" (что терпимо), и иногда в процессе работы - "падала" (что тоже терпимо)... В последнее время перестала запоминать текущие установки Desktop-ы (точнее брекпоинты, что тоже терпимо) Потом был годичный перерыв в работе за время которого произошло... https://www.cyberforum.ru/ cpp-beginners/ thread1244102.html |
Не могу открыть WMware через VS, не видит wmx файл C++ Добрый день, в visual studio 2012 пишу консольное приложение, которое должно открывать виртуальную машину. Столкнулся с такой проблемой, что не находит *.wmx файл(файл конфигураций). Пишет вот что: Usage: C:\Users\212\documents\visual studio 2012\Projects\powerOn\x64\Debug\powerOn.exe <vmxpath> where vmxpath is an absolute path to the .vmx file for the virtual machine. Для продолжения нажмите... |
C++ Вычислительная часть на С++ и графика на Python Здравтсвуйте. Возник вопрос - можно ли использовать Python (pygame) в программе на c+. То есть вся вычеслительная часть на С++, а графика на Python. https://www.cyberforum.ru/ cpp-beginners/ thread1244030.html |
18.08.2014, 22:57 | 0 | ||||||||||||||||||||||||||||||
Объяснить линейный поиск в массиве и сортировка массива - C++ - Ответ 653011618.08.2014, 22:57. Показов 5540. Ответов 3
Метки (Все метки)
Сообщение было отмечено Antosha как решение
Решение
Линейный поиск - берём наш массив и перебираем всё элементы с 1 по последний, сравнивая с искомым значением.
"Пузырьковая" сортировка. Идея метода состоит в следующем: шаг сортировки заключается в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. Для реализации расположим массив сверху вниз, от нулевого элемента - к последнему. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию. Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию. Пример кода.
Основные принципы метода. Среднее число сравнений и обменов имеют квадратичный порядок роста, отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся. Рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла. Таким образом первый шаг оптимизации заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу. Процесс оптимизации можно продолжить, запоминая не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседних элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i. Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя "легкий" пузырек снизу поднимется наверх за один проход, "тяжелые" пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов. Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".
Сортировка выбором Идея данного метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Сейчас, мы с вами попробуем построить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1). На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже. Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] является упорядоченной. Таким образом, на шаге (n-1) вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Рассмотрим пример, реализующий данный метод:
Основные принципы метода 1. Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки возрастает относительно количества элементов. 2. Алгоритм не использует дополнительной памяти: все операции происходят "на месте". Давайте, определим, насколько устойчив данный метод? Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них. Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a. Таким образом, входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя не очень оптимально. Однако, такую сортировку можно использовать для массивов имеющих небольшие размеры. Добавлено через 1 минуту Сортировка вставками. Сортировка простыми вставками в чем-то похожа на методы изложенные в предыдущих разделах урока. Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность. Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы. Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется. Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда найден элемент, меньший x или достигнуто начало последовательности. Реализация метода
Принципы метода Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Однако, алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить из в одно, поставив в начало массива специальный "сторожевой элемент". Он должен быть заведомо меньше всех остальных элементов массива. Тогда при j=0 будет заведомо верно a[0] <=x. Цикл остановится на нулевом элементе, что и было целью условия j>=0. Таким образом, сортировка будет происходить правильным образом, а во внутреннем цикле станет на одно сравнение меньше. Однако, отсортированный массив будет не полон, так как из него исчезло первое число. Для окончания сортировки это число следует вернуть назад, а затем вставить в отсортированную последовательность a[1]...a[n].
Вернуться к обсуждению: Объяснить линейный поиск в массиве и сортировка массива C++
2
|
18.08.2014, 22:57 | |
Готовые ответы и решения:
3
Сортировка, линейный и бинарный поиск в массиве Линейный поиск в массиве Линейный поиск в массиве Линейный поиск в массиве |
18.08.2014, 22:57 | |
18.08.2014, 22:57 | |
Помогаю со студенческими работами здесь
0
Линейный поиск в массиве Линейный поиск в массиве структуры Линейный поиск в массиве и списке Линейный Поиск в массиве со случайными числами |