Четверговая задачка на поиск / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговая задачка на поиск

55 сообщений из 55, показаны все 3 страниц

все

Четверговая задачка на поиск

#39806268

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

...

Рейтинг:

0 / 0

25.04.2019, 14:15

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806274

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Я так понимаю не просто найти, а максимально быстро?

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

Это если нет повторов, если есть повторы то только последовательный перебор.

...

Рейтинг:

0 / 0

25.04.2019, 14:29

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806284

Roman Mejtes

Участник

Откуда: г. Пермь

Сообщения: 4 264

Рейтинг: 0 / 0

maytonПривет. Услышал задачу от коллеги который проводит технические собесы. Заинтересовало.

Дан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
по сути, если массив сдвинут,
Находим значение медианы отрезка массива (на первой итерации всего массива) и проверяем, если её на левом отрезке если начало 1 отрезка меньше значения медианы, значит решение находится в правой части, повторяем это на отрезке в котором находится решение, пока не найдем точку в которой отрезки будет упорядочены. индекс в этой точке будет значением на сколько сместили.

...

Рейтинг:

0 / 0

25.04.2019, 14:35

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806303

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Медиана - это o(n).

...

Рейтинг:

0 / 0

25.04.2019, 14:52

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806313

Roman Mejtes

Участник

Откуда: г. Пермь

Сообщения: 4 264

Рейтинг: 0 / 0

mayton,

медиана это центр массива и сложность будет логарифмическая O(logn) у данного метода, а не линейная O(n), так как каждый раз мы уменьшаем диапазон поиска в в 2 раза, обычный бинарный поиск.

...

Рейтинг:

0 / 0

25.04.2019, 15:05

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806315

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

А сорян. Я думал что имеется в виду медиана как в Фотошопном эффекте median.

...

Рейтинг:

0 / 0

25.04.2019, 15:07

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806318

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Код-бы надо. Для пущей убедительности.

...

Рейтинг:

0 / 0

25.04.2019, 15:11

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806334

Gennadiy Usov

Гость

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

Во вторых, как можно сравнивать массивы, если дан только один массив - отсортированный?

...

Рейтинг:

0 / 0

25.04.2019, 15:29

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806338

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Код: sql

7,8,9,10,1,2,3,4,5,6

...

Рейтинг:

0 / 0

25.04.2019, 15:33

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806340

Gennadiy Usov

Гость

Так сколько дано массивов?

Представленный массив - не отсортированый.
Его нет в перечне - "дано".

...

Рейтинг:

0 / 0

25.04.2019, 15:37

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806345

Roman Mejtes

Участник

Откуда: г. Пермь

Сообщения: 4 264

Рейтинг: 0 / 0

Код: c#

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

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);
}}

...

Рейтинг:

0 / 0

25.04.2019, 15:41

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806350

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Roman Mejtes, зацикливается:

Код: c#

1.
2.

		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

...

Рейтинг:

0 / 0

25.04.2019, 15:46

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806354

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Roman Mejtes, спасибо.

...

Рейтинг:

0 / 0

25.04.2019, 15:52

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806356

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, у меня вроде нет. Дотнета нету. Переписал в REPL.

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

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

Я изначально думал что надо циклический итератор ввести...

...

Рейтинг:

0 / 0

25.04.2019, 15:54

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806360

Gennadiy Usov

Гость

Можно ли изменить формулировку задачи?

Например,

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

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

Теперь,
имея только новый массив после сдвига на k элементов, как можно определить это число k.

...

Рейтинг:

0 / 0

25.04.2019, 15:58

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806365

Roman Mejtes

Участник

Откуда: г. Пермь

Сообщения: 4 264

Рейтинг: 0 / 0

Dima TRoman Mejtes, зацикливается:

Код: c#

1.
2.

		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

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

...

Рейтинг:

0 / 0

25.04.2019, 16:03

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806368

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Roman MejtesDima TRoman Mejtes, зацикливается:

Код: c#

1.
2.

		int[] arr = { 7,8,9,10,1,2,3,4,5,6 };
		Console.WriteLine(Find(arr, 0, arr.Length - 1));

у меня не зацикливается
Извиняюсь, не зацикливается. Это похоже студия у меня затупила, решил что зациклилось.

...

Рейтинг:

0 / 0

25.04.2019, 16:06

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806370

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Некорректно для перевёрнутой сортировки.

Код: sql

1.
2.
3.
4.

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

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

...

Рейтинг:

0 / 0

25.04.2019, 16:08

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806374

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonНекорректно для перевёрнутой сортировки.
Больше на меньше замени.

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

Код: c#

int[] arr = { 1,1,1,2,1,1,1,1,1,1 };

...

Рейтинг:

0 / 0

25.04.2019, 16:12

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806380

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Интересно .. можно ли бросить какой-то ассерт или эксцепшен если этот предикат
дал равенство?

Код: sql

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

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

...

Рейтинг:

0 / 0

25.04.2019, 16:20

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806383

Gennadiy Usov

Гость

Зачем циклы, если задача поставлена так, как описано в 21871816 .

Тогда задача решается с помощью одной формулы!

...

Рейтинг:

0 / 0

25.04.2019, 16:22

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806387

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

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

Код: sql

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

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

...

Рейтинг:

0 / 0

25.04.2019, 16:30

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806390

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Столько всего написали для простейшей задачи.
Число шагов сдвига соответствует первому найденному элементу, который меньше последнего.
Обычный бинарный поиск с корректировкой на равенства.

...

Рейтинг:

0 / 0

25.04.2019, 16:37

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806391

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

На таком массиве неправильно сработает

Код: c#

1,2,3

...

Рейтинг:

0 / 0

25.04.2019, 16:38

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806394

Соколинский Борис

Участник

Откуда: Москва

Сообщения: 13 304

Рейтинг: 0 / 0

Dima T, правильно.
нулевой элемент будет возвращен, 0 шагов.

...

Рейтинг:

0 / 0

25.04.2019, 16:44

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806401

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Для длин массивов 0,1,2 задача лишена смысла. Нет возможности понять где прошёл сдвиг.

...

Рейтинг:

0 / 0

25.04.2019, 16:57

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806406

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonДля длин массивов 0,1,2 задача лишена смысла. Нет возможности понять где прошёл сдвиг.
Пусть будет 4 элемента {1,2,3,4}, тоже неверно считает. Я про случай когда сдвиг на 0 или количество элементов.

...

Рейтинг:

0 / 0

25.04.2019, 17:00

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806411

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Лучше начать с маргинальных кейсов. Для 3х элементов.

Код: sql

1.
2.
3.
4.
5.
6.

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)

Я не уверен что кейсы корректы. Прошу просмотреть глазами кому не лень.

...

Рейтинг:

0 / 0

25.04.2019, 17:04

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806412

Leonid Kudryavtsev

Участник

Сообщения: 9 300

Рейтинг: 0 / 0

maytonДля длин массивов 0,1,2 задача лишена смысла. Нет возможности понять где прошёл сдвиг.

Для длин массивово 0,1 - понятно
Но для длины массива 2 - смысл есть. Был сдвиг, не было сдвига

...

Рейтинг:

0 / 0

25.04.2019, 17:06

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806414

Leonid Kudryavtsev

Участник

Сообщения: 9 300

Рейтинг: 0 / 0

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

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

IMHO

...

Рейтинг:

0 / 0

25.04.2019, 17:08

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806420

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

100% согласен. И вижу что условия - неплолные. И в части дубликатов тоже.

...

Рейтинг:

0 / 0

25.04.2019, 17:11

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806499

Gennadiy Usov

Гость

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

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

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

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

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

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

Думаю, что не будет проблемы, если массив будет убывать.

...

Рейтинг:

0 / 0

25.04.2019, 20:04

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806518

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov,

Я по чистой случайности привёл прогрессию.
В реальности там - случайные числа, монотонные, с произвольным шагом.

...

Рейтинг:

0 / 0

25.04.2019, 21:15

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806559

Gennadiy Usov

Гость

maytonGennadiy Usov,
Я по чистой случайности привёл прогрессию.
В реальности там - случайные числа, монотонные, с произвольным шагом.А теперь,
"по чистой случайности",
покажите те произвольные данные, которые есть
(можно около 16 чисел),
(не обязательно подряд),
сколько при этом массивов,
и что с массивами надо делать.

...

Рейтинг:

0 / 0

26.04.2019, 07:24

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806564

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Gennadiy Usovпокажите те произвольные данные, которые есть
Например такие

Код: sql

19,22,26,1,3,6,7,9,11,14

...

Рейтинг:

0 / 0

26.04.2019, 08:03

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806570

Gennadiy Usov

Гость

Dima TGennadiy Usovпокажите те произвольные данные, которые есть Например такие

Код: sql

19,22,26,1,3,6,7,9,11,14

Gennadiy Usovсколько при этом массивов,и что с массивами надо делать.Массив один, делать все тоже mayton Дан отсортированный массив целых размером N. После сортировки он - циклически сдвинут на M шагов. Найти насколько он сдвинут. Вы (и mayton, и тот, кто дал задачу) себе противоречите:
дан не отсортированный массив,
дан массив, который когда-то был отсортированным, и был циклически сдвинут на М шагов.

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

...

Рейтинг:

0 / 0

26.04.2019, 08:41

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806571

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Gennadiy UsovDima Tпропущено...
Например такие

Код: sql

19,22,26,1,3,6,7,9,11,14

пропущено...
Массив один, делать все тоже пропущено...
Вы (и mayton, и тот, кто дал задачу) себе противоречите:
дан не отсортированный массив,
дан массив, который когда-то был отсортированным, и был циклически сдвинут на М шагов.

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

Исходный массив

Код: sql

1,3,6,7,9,11,14,19,22,26

был сдвинут на 3 шага

...

Рейтинг:

0 / 0

26.04.2019, 08:48

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806582

Gennadiy Usov

Гость

Dima TGennadiy Usovпокажите те произвольные данные, которые есть Например такие

Код: sql

19,22,26,1,3,6,7,9,11,14

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

Код: sql

1,3,6,7,9,11,14,19,22,26

был сдвинут на 3 шагаТеперь появился ещё исходный массив.

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

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

А то в вики записано:
"В отличие от плеоназма, тавтология не оправдана ни с логической, ни с эмоциональной точек зрения, повторение идёт без какой-либо цели, от безграмотности."

...

Рейтинг:

0 / 0

26.04.2019, 09:23

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806591

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Gennadiy Usov,

Ну, понятно же, что дан Буратино, у которого в кармане когда-то было 2 яблока, но затем некто ...

...

Рейтинг:

0 / 0

26.04.2019, 09:58

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806602

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy UsovDima Tпропущено...
Например такие

Код: sql

19,22,26,1,3,6,7,9,11,14

пропущено...
Массив один, делать все тоже пропущено...
Вы (и mayton, и тот, кто дал задачу) себе противоречите:
дан не отсортированный массив,
дан массив, который когда-то был отсортированным, и был циклически сдвинут на М шагов.

Это две разные вещи!
А как-бы вы переписали данное условие задачи?

...

Рейтинг:

0 / 0

26.04.2019, 10:16

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806743

Gennadiy Usov

Гость

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

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

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

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

Как то так.

...

Рейтинг:

0 / 0

26.04.2019, 12:57

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806746

Gennadiy Usov

Гость

Мне кажется, что это не задача, а полузадача.

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

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

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

...

Рейтинг:

0 / 0

26.04.2019, 13:01

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806764

Roman Mejtes

Участник

Откуда: г. Пермь

Сообщения: 4 264

Рейтинг: 0 / 0

Gennadiy UsovМне кажется, что это не задача, а полузадача.

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

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

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

...

Рейтинг:

0 / 0

26.04.2019, 13:14

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806771

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Roman MejtesGennadiy UsovМне кажется, что это не задача, а полузадача.

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

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

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

...

Рейтинг:

0 / 0

26.04.2019, 13:25

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806777

Gennadiy Usov

Гость

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

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

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

...

Рейтинг:

0 / 0

26.04.2019, 13:31

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806799

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov, вся беда в том что ты никогда не программировал. Эта задача для математика - лишена смысла.

Для программиста она важна с точки зрения хозяйственного распоряжения ресурсами.
Где ресурсы = дисковые или память или прочие носители информации.

...

Рейтинг:

0 / 0

26.04.2019, 13:51

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806834

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

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

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

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

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

...

Рейтинг:

0 / 0

26.04.2019, 14:37

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806857

Gennadiy Usov

Гость

maytonGennadiy Usov, вся беда в том что ты никогда не программировал. Эта задача для математика - лишена смысла.Если в какой-то науке нет места математике, то в этой науке нет смысла. Это так - ответка.

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

...

Рейтинг:

0 / 0

26.04.2019, 15:14

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806867

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Gennadiy UsovВ то же время в следующих сообщениях нет ни слова о сортировке. А это - тема топика.
Эти сообщения как раз по теме топика. Если нет понимания как они связаны, то это говорит о незнании азов программирования. Азы тут никто не будет объяснять, для этого есть книги.

...

Рейтинг:

0 / 0

26.04.2019, 15:28

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806873

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Например:

Код: sql

1.
2.

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 в этой непрерывной последовательности будет некий скачок. Это как раз
и есть условия нашей задачи. Только лог файл удалён из контекста обсуждения. А метка времени
заменена на целое число.

...

Рейтинг:

0 / 0

26.04.2019, 15:41

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806906

Gennadiy Usov

Гость

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

Хотите сказать, что при "скачке" часть последних записей "становятся первыми"?

...

Рейтинг:

0 / 0

26.04.2019, 16:32

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39806913

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

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

Найти это место - суть данной задачи.

...

Рейтинг:

0 / 0

26.04.2019, 16:43

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39811866

no56892

Участник

Сообщения: 588

Рейтинг: 0 / 0

mayton,
В постановке:
авторДан отсортированный массив целых размером N. После сортировки он - циклически
сдвинут на M шагов. Найти насколько он сдвинут.
Если принять за изначальный массив А, а после сдвига - массив В, то
задача имеет бесконечное множество сдвигов M массива А в результате которого получится массив В => определить на сколько сдвинули в данной постановке не возможно.

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

Может быть А = {2,1} и М = 1, или все-таки A={2,1} и М= 1000000000000000000000000000000000000001 ?

...

Рейтинг:

0 / 0

10.05.2019, 14:28

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39811885

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

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

Но обычно интересен более практический нежели общий ответ.

...

Рейтинг:

0 / 0

10.05.2019, 16:21

| Ответить | Цитировать | Написать

Четверговая задачка на поиск

#39812069

fkthat

Участник

Сообщения: 3 601

Рейтинг: 0 / 0

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

Код: sql

1.
2.

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

Пятерка как раз во второй позиции.

...

Рейтинг:

0 / 0

11.05.2019, 15:36

| Ответить | Цитировать | Написать

55 сообщений из 55, показаны все 3 страниц

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговая задачка на поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?all=1&fid=16&tid=1339946]:	0ms
get settings:	9ms
get forum list:	16ms
check forum access:	4ms
check topic access:	4ms
track hit:	277ms
get topic data:	14ms
get forum data:	3ms
get page messages:	75ms
get tp. blocked users:	2ms
others:	234ms

total:	638ms