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