Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
Хорошо, в файле все записи "отсортированы временем".
Случился "скачок", номера записей сдвинулись.

Хотите сказать, что при "скачке" часть последних записей "становятся первыми"?
26 апр 19, 16:32    [21872843]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Записи - стационарны. Они не двигаются никуда. Просто новые записи переписывают старые.
Вот и получается такой "пилообразный" импульс на всём протяжении истории журнала.

Но после перезагрузки базы. Или приложения мы теряем сведения о том моменте или о том
месте где писали раньше.

Найти это место - суть данной задачи.
26 апр 19, 16:43    [21872853]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
no56892
Member

Откуда:
Сообщений: 588
mayton,
В постановке:
автор
Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.

Если принять за изначальный массив А, а после сдвига - массив В, то
задача имеет бесконечное множество сдвигов M массива А в результате которого получится массив В => определить на сколько сдвинули в данной постановке не возможно.

Уточнить бы у товарища, кот задает такие вопросы, чему равно М, если массив после сдвига (B) выглядит так:
{1,2} ?

Может быть А = {2,1} и М = 1, или все-таки A={2,1} и М= 1000000000000000000000000000000000000001 ?
10 май 19, 14:28    [21882128]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Чему равен арксинус 1/2 ? Может быть 30 градусам. Может быть бесконечному множеству углов.

Но обычно интересен более практический нежели общий ответ.
10 май 19, 16:21    [21882154]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
fkthat
Member

Откуда:
Сообщений: 1163
Найти самое большое число - в какой позиции оно будет находится, на столько он и сдвинут. Сложность O(n).

Было:          1,2,3,4,5
сдвинули на 2: 4,5,1,2,3


Пятерка как раз во второй позиции.
11 май 19, 15:36    [21882496]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
Все форумы / Программирование Ответить