С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
#1

Сортировка списка - C++

12.04.2014, 04:55. Просмотров 535. Ответов 17
Метки нет (Все метки)

Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые числа, <= 10^6
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2014, 04:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка списка (C++):

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка - C++
Здравствуйте! Возникла проблема с программой. Тема: &quot;Сортировка двусвязного списка путем исключения элемента с минимальным значением и...

Сортировка списка - C++
Здравствуйте, не совсем понимаю как должна быть реализована сортировка вставками в деке. Что имеется на данный момент: class List...

Сортировка списка - C++
Здравствуйте!!! Прошу помочь мне написать алгоритм сортировки односвязного списка. Задание такое: необходимо из элементов трёх списков...

Сортировка списка - C++
помогите сделать сортировку по возрасту, а то ничего не выходит #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; struct...

Сортировка списка - C++
Помогите пожалуйста, нужна сортировка методом вставок односвязанного кольцевого списка, не пойму как делать. Со списками ток начал...

Сортировка списка - C++
Получается, что пользователь вносит книги в библиотеку, записывая имя писателя, название, год издания и тд... После чего он может...

17
IrineK
12.04.2014, 07:34
  #2

Не по теме:

Цитата Сообщение от freewrestler Посмотреть сообщение
Городов до 10^8
Это для императора галактики?
На земле столько городов нет: http://www.statisticbrain.com/total-number-of-cities-in-the-world/

0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 07:35  [ТС] #3
Условие задачи таково
0
IrineK
Заблокирован
12.04.2014, 07:39 #4
freewrestler,
Разъясните, у вас городов 10^8 и у каждого города - свои села
или
у вас город один и у него 10^8 сел?
0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 07:48  [ТС] #5
Есть один город. А затем села - у каждого собственное название и определенное расстояние от этого города. Нам дано количество сел N( 1 <= N <= 10^8), а также даны названия этих сел и расстояние для каждого села до города. Нужно вывести список сел в порядке удаленности. К примеру:

Входные данные:
3
Дыбенко 35
Каменномостский 13
Утриш 18

Выходные данные:
Каменномостский 13
Утриш 18
Дыбенко 35

Добавлено через 4 минуты
Нужно сделать структурами, создать функцию сортировки, а после ввода данных вызвать эту функцию. Но к сожалению реализовать не могу..
0
IrineK
Заблокирован
12.04.2014, 07:51 #6
Количество намекает на то, что нужно создавать стек, а затем вставлять следующий пункт, используя бинарный поиск.
0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 07:52  [ТС] #7
а ну тогда совсем молчу ))
0
IrineK
Заблокирован
12.04.2014, 08:02 #8
Если будете сортировать как обычно - это долго.

Добавлено через 10 минут
Цитата Сообщение от freewrestler Посмотреть сообщение
ну тогда совсем молчу
Если можно пользоваться STL, то не так уж страшно.

Если в задании указано, что нужно написать все самому - тогда немного страшнее.
0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:04  [ТС] #9
STL-ом пользоваться думаю можно, а об обязательстве решения самому не сказано)
0
dzrkot
zzzZZZ...
523 / 353 / 54
Регистрация: 11.09.2013
Сообщений: 2,036
12.04.2014, 08:16 #10
sort();
0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:17  [ТС] #11
sort - Timelimit exceeded =))
0
IrineK
Заблокирован
12.04.2014, 08:44 #12
Сортировки дают кво операций ~ N2
Если у вас N = 108, то N2 = 1016
Комп способен на порядка 107 в секунду.
Значит, вам нужно 109 секунд = 32 года.

Добавлено через 10 минут
Кво операций при бинарном поиске по N элементам 1 + log2N
Искать будем по списку, т.е. среднее кво операций будет вполовину меньше.
Нужно расставить N элементов, т.е. общее кво операций
N(1 + log2N) / 2

При N = 108 М = 1 + 8*log210 = 1 + 8*3,3 = 28 операций
Поскольку, список нарастает от 1 до N, среднее кво операций равно половине этой величины, т.е. 14 операций на одну вставку.
Для N вставок: 14 * 108 операций
Комп справится за 140 с.
0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:45  [ТС] #13
а 140 секунд это разве мало?)
0
IrineK
Заблокирован
12.04.2014, 08:47 #14
Все познается в сравнении.
Если мысленно представить 32 года и 140 секунд, то ответ очевиден.
0
freewrestler
3 / 3 / 0
Регистрация: 10.11.2011
Сообщений: 126
12.04.2014, 08:47  [ТС] #15
С этим полностью согласен)
0
12.04.2014, 08:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2014, 08:47
Привет! Вот еще темы с ответами:

Сортировка списка - C++
Всем привет) Нужно реализовать сортировку списка, линейного однонаправленного. Написал, но что-то как-то не правильно... void...

Сортировка списка - C++
Народ нужна помощь :) Элементы списка представлены следующим образом: class Node { public: char *name; Node *next; ...

Сортировка списка - C++
Приветствую всех! Есть небольшая проблема: не могу понять, как создать сортировку в алфавитном порядке. Вот код: void SortList() { ...

Сортировка списка - C++
Люди помогите плиз я уже не могу!! надо сортировать список!!! Останьные недоработки тоже можете указать. Вот код Жду ответов) ...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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