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

ReSQL.ru

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

Гость

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

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

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

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

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

25 сообщений из 55, страница 2 из 3

все

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

#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

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

25 сообщений из 55, страница 2 из 3

все

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

Цитировать

Написать

Автор*:

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

Тема*:

Сообщение

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

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

Автор:

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

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

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

Вложение:

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

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

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

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

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

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

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

start [/forum/topic.php?fid=16&msg=39806559&tid=1339946]:	0ms
get settings:	11ms
get forum list:	14ms
check forum access:	4ms
check topic access:	4ms
track hit:	169ms
get topic data:	12ms
get forum data:	3ms
get page messages:	63ms
get tp. blocked users:	2ms
others:	236ms

total:	518ms