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

Откуда: loopback
Сообщений: 41808
Привет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
25 апр 19, 14:15    [21871665]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Я так понимаю не просто найти, а максимально быстро?

ИМХО что-то типа двоичного поиска: первый сравнить со средним, если первый больше среднего, то берем первую половину, иначе вторую и т.д.

Это если нет повторов, если есть повторы то только последовательный перебор.
25 апр 19, 14:29    [21871677]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
mayton
Привет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.

по сути, если массив сдвинут,
Находим значение медианы отрезка массива (на первой итерации всего массива) и проверяем, если её на левом отрезке если начало 1 отрезка меньше значения медианы, значит решение находится в правой части, повторяем это на отрезке в котором находится решение, пока не найдем точку в которой отрезки будет упорядочены. индекс в этой точке будет значением на сколько сместили.
25 апр 19, 14:35    [21871694]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Медиана - это o(n).
25 апр 19, 14:52    [21871732]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
mayton,

медиана это центр массива и сложность будет логарифмическая O(logn) у данного метода, а не линейная O(n), так как каждый раз мы уменьшаем диапазон поиска в в 2 раза, обычный бинарный поиск.
25 апр 19, 15:05    [21871750]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
А сорян. Я думал что имеется в виду медиана как в Фотошопном эффекте median.
25 апр 19, 15:07    [21871754]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Код-бы надо. Для пущей убедительности.
25 апр 19, 15:11    [21871760]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

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

Во вторых, как можно сравнивать массивы, если дан только один массив - отсортированный?
25 апр 19, 15:29    [21871781]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
7,8,9,10,1,2,3,4,5,6
25 апр 19, 15:33    [21871785]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Так сколько дано массивов?

Представленный массив - не отсортированый.
Его нет в перечне - "дано".
25 апр 19, 15:37    [21871787]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
static void Main(string[] args)
{
	var arr = Enumerable.Range(0, 40).ToArray();
	int shift = 11;
	var shiftArr = arr.Skip(arr.Length - shift).Concat(arr.Take(arr.Length - shift)).ToArray();
	Console.WriteLine(string.Join(",", shiftArr));
	Console.WriteLine(Find(shiftArr, 0, shiftArr.Length - 1));
	Console.ReadKey();
}
static int Find(int[] arr, int start, int end)
{
	var mid = start + ((end - start) / 2);
	if (end - start < 2) return mid +1;
	return arr[start] > arr[mid]
		? Find(arr, start, mid)
		: Find(arr, mid, end);
}}
25 апр 19, 15:41    [21871793]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Roman Mejtes, зацикливается:
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));
25 апр 19, 15:46    [21871799]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Roman Mejtes, спасибо.
25 апр 19, 15:52    [21871804]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Dima T, у меня вроде нет. Дотнета нету. Переписал в REPL.
scala> val arr = Array[Int](7,8,9,10,1,2,3,4,5,6)
arr: Array[Int] = Array(7, 8, 9, 10, 1, 2, 3, 4, 5, 6)

scala>

scala> def find(arr : Array[Int], start : Int, end : Int) : Int = {
     | var mid = start + ((end - start) / 2);
     |
     | if (end - start < 2)
     |                 return mid +1;
     | if (arr(start) > arr(mid))
     | find(arr, start, mid)
     |         else
     | find(arr, mid, end)
     | }
find: (arr: Array[Int], start: Int, end: Int)Int

scala> find(arr, 0, 9)
res0: Int = 4


Я изначально думал что надо циклический итератор ввести...
25 апр 19, 15:54    [21871806]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Можно ли изменить формулировку задачи?

Например,

Имеется N последовательных чисел от 1 до N.
Эти числа помещены в массив N чисел.

С этим массивом провели циклическую сдвижку на k элементов.
Получилось, что теперь первым числом в массиве будет число N-k+1,
а последним числом в массиве будет число N-k.

Теперь,
имея только новый массив после сдвига на k элементов, как можно определить это число k.
25 апр 19, 15:58    [21871816]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
Dima T
Roman Mejtes, зацикливается:
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

у меня не зацикливается
25 апр 19, 16:03    [21871824]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Roman Mejtes
Dima T
Roman Mejtes, зацикливается:
		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

у меня не зацикливается

Извиняюсь, не зацикливается. Это похоже студия у меня затупила, решил что зациклилось.
25 апр 19, 16:06    [21871828]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Некорректно для перевёрнутой сортировки.

val arr = Array[Int](3,2,1,15,14,13,12,11,10,9,8,7,6,5,4)

scala> find(arr, 0, 15 - 1)
res3: Int = 8


Мда... за кадром остался вопрос о направлении.
25 апр 19, 16:08    [21871831]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
mayton
Некорректно для перевёрнутой сортировки.

Больше на меньше замени.

mayton
Мда... за кадром остался вопрос о направлении.

И о повторах
int[] arr = { 1,1,1,2,1,1,1,1,1,1 };
25 апр 19, 16:12    [21871836]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Интересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

   | if (arr(start) == arr(mid))


Ну и при этом асимптоматику не сломать.
25 апр 19, 16:20    [21871845]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Зачем циклы, если задача поставлена так, как описано в 21871816.

Тогда задача решается с помощью одной формулы!
25 апр 19, 16:22    [21871851]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
mayton
Интересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

   | if (arr(start) == arr(mid))


Ну и при этом асимптоматику не сломать.

Эта проверка не особо замедлит. Рекурсивный вызов намного тяжелее.
25 апр 19, 16:30    [21871857]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10606
Столько всего написали для простейшей задачи.
Число шагов сдвига соответствует первому найденному элементу, который меньше последнего.
Обычный бинарный поиск с корректировкой на равенства.
25 апр 19, 16:37    [21871862]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
На таком массиве неправильно сработает
1,2,3
25 апр 19, 16:38    [21871863]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 10606
Dima T, правильно.
нулевой элемент будет возвращен, 0 шагов.
25 апр 19, 16:44    [21871870]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Для длин массивов 0,1,2 задача лишена смысла. Нет возможности понять где прошёл сдвиг.
25 апр 19, 16:57    [21871886]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
mayton
Для длин массивов 0,1,2 задача лишена смысла. Нет возможности понять где прошёл сдвиг.

Пусть будет 4 элемента {1,2,3,4}, тоже неверно считает. Я про случай когда сдвиг на 0 или количество элементов.
25 апр 19, 17:00    [21871891]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Лучше начать с маргинальных кейсов. Для 3х элементов.

1,2,3 -> 0 (no shift)
1,3,2 -> 0 (cyclic right shif of desc. order integers)
2,3,1 -> 2 (cyclic right shif of asc. order integers)
2,1,3 -> 2 (cyclic left shif of asc. order integers)
3,1,2 -> 1 (cyclic right shift)
3,2,1 -> 0 (no shift (descended order integers)


Я не уверен что кейсы корректы. Прошу просмотреть глазами кому не лень.
25 апр 19, 17:04    [21871896]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
mayton
Для длин массивов 0,1,2 задача лишена смысла. Нет возможности понять где прошёл сдвиг.


Для длин массивово 0,1 - понятно
Но для длины массива 2 - смысл есть. Был сдвиг, не было сдвига
25 апр 19, 17:06    [21871897]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
Мне кажется слово "отсортированный" для нормальных людей по default обозначает "отсортированный по возрастанию"

Все прочее - типа отсортирован, но не понятно как, нужно было бы отдельно оговаривать в условиях задачи. Т.к. на практике, такие извращения крайне редко встречаются.

IMHO
25 апр 19, 17:08    [21871899]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
100% согласен. И вижу что условия - неплолные. И в части дубликатов тоже.
25 апр 19, 17:11    [21871905]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
На самом деле всё намного проще.
Смотрим обратную задачу.

Рассмотрим вариант, когда количество чисел в массиве чётное. Допустим 16.
И все они расположены по возрастанию слева направо.

Следовательно 1-ый элемент массива 1, а 9-ый элемент (следующий за половиной массива !!!) массива 9.

Сдвинули массив вправо на 3 числа, тогда 1-ый элемент - 14, а 9-ый элемент - 6.
Разница 9-6=3.
Следовательно, надо сдвигать на 3 влево, чтобы получить отсортированный массив.

Сдвинули массив исходный на 12 чисел вправо. Тогда 1-ый элемент 5, а 9-ый элемент - 13.
Разница 9-13=-4.
Следовательно, надо сдвигать вправо на 4, чтобы получить отсортированный массив.

Аналогично можно построить формулы для массива нечётной длины.

Думаю, что не будет проблемы, если массив будет убывать.
25 апр 19, 20:04    [21872026]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov,

Я по чистой случайности привёл прогрессию.
В реальности там - случайные числа, монотонные, с произвольным шагом.
25 апр 19, 21:15    [21872062]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Gennadiy Usov,
Я по чистой случайности привёл прогрессию.
В реальности там - случайные числа, монотонные, с произвольным шагом.
А теперь,
"по чистой случайности",
покажите те произвольные данные, которые есть
(можно около 16 чисел),
(не обязательно подряд),
сколько при этом массивов,
и что с массивами надо делать.
26 апр 19, 07:24    [21872163]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Gennadiy Usov
покажите те произвольные данные, которые есть

Например такие
19,22,26,1,3,6,7,9,11,14

Gennadiy Usov
сколько при этом массивов,
и что с массивами надо делать.

Массив один, делать все тоже
mayton
Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
26 апр 19, 08:03    [21872192]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Dima T
Gennadiy Usov
покажите те произвольные данные, которые есть
Например такие
19,22,26,1,3,6,7,9,11,14
Gennadiy Usov
сколько при этом массивов,и что с массивами надо делать.
Массив один, делать все тоже
mayton
Дан отсортированный массив целых размером N. После сортировки он - циклически сдвинут на M шагов. Найти насколько он сдвинут.
Вы (и mayton, и тот, кто дал задачу) себе противоречите:
дан не отсортированный массив,
дан массив, который когда-то был отсортированным, и был циклически сдвинут на М шагов.

Это две разные вещи!
26 апр 19, 08:41    [21872203]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Gennadiy Usov
Dima T
пропущено...
Например такие
19,22,26,1,3,6,7,9,11,14
пропущено...
Массив один, делать все тоже пропущено...
Вы (и mayton, и тот, кто дал задачу) себе противоречите:
дан не отсортированный массив,
дан массив, который когда-то был отсортированным, и был циклически сдвинут на М шагов.

Это две разные вещи!

Не надо к словам придираться. Есть немного тавтологии в постановке задачи, но противоречий нет.

Исходный массив
1,3,6,7,9,11,14,19,22,26

был сдвинут на 3 шага
26 апр 19, 08:48    [21872204]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Dima T
Gennadiy Usov
покажите те произвольные данные, которые есть
Например такие
19,22,26,1,3,6,7,9,11,14
Dima T
Не надо к словам придираться. Есть немного тавтологии в постановке задачи, но противоречий нет.
Исходный массив
1,3,6,7,9,11,14,19,22,26
был сдвинут на 3 шага
Теперь появился ещё исходный массив.

А где строгость постановки задачи?

А насчет тавтологии - лучше аккуратно это слово использовать.

А то в вики записано:
"В отличие от плеоназма, тавтология не оправдана ни с логической, ни с эмоциональной точек зрения, повторение идёт без какой-либо цели, от безграмотности."
26 апр 19, 09:23    [21872238]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1755
Gennadiy Usov,

Ну, понятно же, что дан Буратино, у которого в кармане когда-то было 2 яблока, но затем некто ...
26 апр 19, 09:58    [21872271]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
Dima T
пропущено...
Например такие
19,22,26,1,3,6,7,9,11,14
пропущено...
Массив один, делать все тоже пропущено...
Вы (и mayton, и тот, кто дал задачу) себе противоречите:
дан не отсортированный массив,
дан массив, который когда-то был отсортированным, и был циклически сдвинут на М шагов.

Это две разные вещи!

А как-бы вы переписали данное условие задачи?
26 апр 19, 10:16    [21872300]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
А как-бы вы переписали данное условие задачи?
Я уже пробовал сформулировать задачу по-новому21871816,
но все побежали делать коды по задаче и не обратили внимание на это сообщение.
Правда, данное сообщение было для последовательных чисел.
Попробую сформулировать условие задачи для произвольных чисел.

Имеется N различных (?) целых (?) чисел, которые размещены в массиве длиной N.
Причём, эти числа отсортированы в этом массиве.

С этим массивом провели циклическую сдвижку элементов на величину М.
Получилось, что теперь первым числом в новом массиве будет (N-М+1)-е число из первого массива,
а последним числом в новом массиве будет (N-М)-е число из первого массива.

Теперь,
имея новый массив после сдвига первого массива на М элементов, необходимо определить это число М.

Как то так.
26 апр 19, 12:57    [21872547]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Мне кажется, что это не задача, а полузадача.

Предположим нашли число М, и что дальше?
Для чего нужно это число М?

Любая задача подразумевает собой то, что она позволяет решить следующую задачу.

Так что будет являться продолжением этой задачи?
26 апр 19, 13:01    [21872552]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
Gennadiy Usov
Мне кажется, что это не задача, а полузадача.

Предположим нашли число М, и что дальше?
Для чего нужно это число М?

Любая задача подразумевает собой то, что она позволяет решить следующую задачу.

Так что будет являться продолжением этой задачи?

Есть файл фиксированной длинны, в него записывается запись, циклически, как только файл заканчивается запись начинается с нуля
Мы хотим получить все записи начиная с самой первой, без сортировки, так как сортировка это как правило O(nlogn), получается, мы за log(n) получаем сортированную последовательность и точку, до которой нужно прочитать
26 апр 19, 13:14    [21872586]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Roman Mejtes
Gennadiy Usov
Мне кажется, что это не задача, а полузадача.

Предположим нашли число М, и что дальше?
Для чего нужно это число М?

Любая задача подразумевает собой то, что она позволяет решить следующую задачу.

Так что будет являться продолжением этой задачи?

Есть файл фиксированной длинны, в него записывается запись, циклически, как только файл заканчивается запись начинается с нуля
Мы хотим получить все записи начиная с самой первой, без сортировки, так как сортировка это как правило O(nlogn), получается, мы за log(n) получаем сортированную последовательность и точку, до которой нужно прочитать

100% в точку. Я-бы лучше не придумал.
26 апр 19, 13:25    [21872597]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
Разберём всё по порядку.
Roman Mejtes
Есть файл фиксированной длинны, в него записывается запись, циклически, как только файл заканчивается запись начинается с нуля
Здесь файл наполнился, следующая запись будет с нуля, следовательно, "затирает" какую-то старую запись.
Roman Mejtes
Мы хотим получить все записи начиная с самой первой, без сортировки, так как сортировка это как правило O(nlogn), получается, мы за log(n) получаем сортированную последовательность и точку, до которой нужно прочитать
Файл заполнился, как было сказано ранее.
Можно считать информацию из файла с нуля. И это получится.

Так при чём здесь сортировка и задача топика?

Или надо считать запись где-то из середины файла?
26 апр 19, 13:31    [21872607]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov, вся беда в том что ты никогда не программировал. Эта задача для математика - лишена смысла.

Для программиста она важна с точки зрения хозяйственного распоряжения ресурсами.
Где ресурсы = дисковые или память или прочие носители информации.
26 апр 19, 13:51    [21872647]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1755
Gennadiy Usov
Разберём всё по порядку.
Roman Mejtes
Есть файл фиксированной длинны, в него записывается запись, циклически, как только файл заканчивается запись начинается с нуля
Здесь файл наполнился, следующая запись будет с нуля, следовательно, "затирает" какую-то старую запись.
Roman Mejtes
Мы хотим получить все записи начиная с самой первой, без сортировки, так как сортировка это как правило O(nlogn), получается, мы за log(n) получаем сортированную последовательность и точку, до которой нужно прочитать
Файл заполнился, как было сказано ранее.
Можно считать информацию из файла с нуля. И это получится.

Так при чём здесь сортировка и задача топика?

Или надо считать запись где-то из середины файла?


Программа ведет журнал событий в файле по циклу (из-за ограниченного размера флешки),
например, это электронный вахтер, или электронный инспектор ГИБДД.
Вдруг вырубается питание, и ей надо продолжить работу после перезагрузки.
26 апр 19, 14:37    [21872717]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1693
mayton
Gennadiy Usov, вся беда в том что ты никогда не программировал. Эта задача для математика - лишена смысла.
Если в какой-то науке нет места математике, то в этой науке нет смысла. Это так - ответка.

В то же время в следующих сообщениях нет ни слова о сортировке. А это - тема топика.
mayton
Для программиста она важна с точки зрения хозяйственного распоряжения ресурсами.
Где ресурсы = дисковые или память или прочие носители информации.
Aleksandr Sharahov
Программа ведет журнал событий в файле по циклу (из-за ограниченного размера флешки),
например, это электронный вахтер, или электронный инспектор ГИБДД.
Вдруг вырубается питание, и ей надо продолжить работу после перезагрузки.
26 апр 19, 15:14    [21872754]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Gennadiy Usov
В то же время в следующих сообщениях нет ни слова о сортировке. А это - тема топика.

Эти сообщения как раз по теме топика. Если нет понимания как они связаны, то это говорит о незнании азов программирования. Азы тут никто не будет объяснять, для этого есть книги.
26 апр 19, 15:28    [21872770]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Gennadiy Usov
mayton
Gennadiy Usov, вся беда в том что ты никогда не программировал. Эта задача для математика - лишена смысла.
Если в какой-то науке нет места математике, то в этой науке нет смысла. Это так - ответка.

В то же время в следующих сообщениях нет ни слова о сортировке. А это - тема топика.
mayton
Для программиста она важна с точки зрения хозяйственного распоряжения ресурсами.
Где ресурсы = дисковые или память или прочие носители информации.
Aleksandr Sharahov
Программа ведет журнал событий в файле по циклу (из-за ограниченного размера флешки),
например, это электронный вахтер, или электронный инспектор ГИБДД.
Вдруг вырубается питание, и ей надо продолжить работу после перезагрузки.

Журнал событий обычно содержит метку времени. Timestamp. Или счечик транзакций (по аналогии с DBMS WAL)

Например:
2019-01-02 17:33:01.110 [ALERT] User John Dou Entered 
2019-01-02 17:33:01.123 [INFO] Transaction 9875923 begin


Тоесть он всегда отсортирован по ворзрастанию метки времени. Но беря в расчет повторное использование
группы файлов WAL или LOG в этой непрерывной последовательности будет некий скачок. Это как раз
и есть условия нашей задачи. Только лог файл удалён из контекста обсуждения. А метка времени
заменена на целое число.
26 апр 19, 15:41    [21872781]     Ответить | Цитировать Сообщить модератору
 Re: Четверговая задачка на поиск  [new]
Gennadiy Usov
Member

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

Хотите сказать, что при "скачке" часть последних записей "становятся первыми"?
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]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Программирование Ответить