|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
||||||
Бесконечная последовательность02.08.2011, 21:11. Показов 5565. Ответов 50
Метки нет (Все метки)
Задача
Моё решение на плюсах
Есть подозрения, что при каком-то наборе данных алгоритм зацикливается (но не должно же - чем глубже рекурсия, тем меньший элемент последовательности ищется, вроде всегда так), пробовал крайние значения - работает в доли секунды. Помогите, люди добрые! Или хоть контрпример подскажите...
1
|
||||||
| 02.08.2011, 21:11 | |
|
Ответы с готовыми решениями:
50
Бесконечная последовательность Бесконечная последовательность десятичных цифр Бесконечная последовательность рациональных чисел v0, v1 , . образована по следующему закону : |
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
| 03.08.2011, 00:42 [ТС] | |
|
0
|
|
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
||||||
| 03.08.2011, 00:42 | ||||||
|
Или то же самое, только более однообразно.
0
|
||||||
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
||||||
| 03.08.2011, 09:48 [ТС] | ||||||
|
grizlik78, и такой вариант тоже пробовал очень странно вышло - прироста в производительности - ноль, в то время как обьем используемой памяти вырос в полтора раза (ну это-то понятно, для каждого вызова хранить лишние 128 бит, оно и выходит)Добавлено через 22 минуты
0
|
||||||
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
|||
| 03.08.2011, 11:30 | |||
|
1
|
|||
|
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
|
|
| 03.08.2011, 11:58 | |
|
Вместо map попробуй использовать хеш-таблицу.
1
|
|
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
||||||||||||||
| 03.08.2011, 12:46 [ТС] | ||||||||||||||
unordered_map не подходит, т. к. в VC++ 2008, насколько я знаю, он еще не поддерживаетсяДобавлено через 3 минуты Нашел! буду пробовать Добавлено через 7 минут Вариант с hash_map'ом даже не компилирует (на тестирующем сервере) Добавлено через 15 минут
0
|
||||||||||||||
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
|
| 03.08.2011, 12:52 | |
|
Хешмапу и руками несложно написать, только врядли она поможет.
0
|
|
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
| 03.08.2011, 12:54 [ТС] | |
|
Хохол, а что поможет? Должно же все проходить, у меня на моем компе при тех ограничениях за 100мс проходит
0
|
|
|
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
|
||
| 03.08.2011, 13:27 | ||
|
iama, дело не в компах, на тестовом сервере проверяют тоже не по времени, иначе было б не честно, и от загрузки сервера зависелоб решение задач(по времени) подсчтитываеться кол-во итераций процессора, и переводиться во время, смутно помню что это около 10^6 на секунду.
Добавлено через 25 минут Я дико ошибался, в моей структуре доступ к элементу будет вообще за О(N) где N - размер структуру, мэпа лучше. Очень интересная задача! Пока не знаю как к ней подойти, но я еще подумаю, и если что получится то обязательно Вам отпишу! ![]() Добавлено через 1 минуту Ах да, там я видел писали про хешы, так вот, не забивайте себе голову, тут в хешах нету смысла.
0
|
||
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
||
| 03.08.2011, 13:32 [ТС] | ||
|
0
|
||
|
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
|
|
| 03.08.2011, 13:34 | |
|
0
|
|
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
|
| 03.08.2011, 13:37 | |
|
Написал тут генератор x и y.
При вот таких значениях 10000000000000 2 2 287955 1013083 мой вариант работает около 7 секунд, при этом совершается более 5 млн. вызовов функции f. И думаю это не предел
1
|
|
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
||
| 03.08.2011, 13:46 | ||
1
|
||
|
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
|
||
| 03.08.2011, 13:51 | ||
|
А в вашей задаче использовать хеш мэп, это всеравно что использовать мэп, только еще будут затраты на само преобразование в мэп, а оно громоздкое. Там сложная формула в которой много делений, делений по модулю, делений на простое числое (которое еще надо будет вывести) умножение на что-то, и вот только тогда вы получите уникальный хеш код элеменьта, НО зачем вам получять хеш код и так уникального элемента? В этом просто нету смысла, вы будете только тратить время на получение хэш кода.
0
|
||
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
||
| 03.08.2011, 13:53 | ||
Я пока с телефона и помочь особо не могу, только критиковать
1
|
||
|
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
|
||
| 03.08.2011, 13:53 | ||
|
Или если на одном сервере стоит процессор более мощьный чем на другом, то на мощьном сервере решение пройдет, а на слабом нет?
0
|
||
|
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
|
||
| 03.08.2011, 13:55 | ||
|
1
|
||
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
|
| 03.08.2011, 13:57 | |
|
Сервер по-очереди проверяет решения. И хватит гнать на хешмапу, она классная, прочитайте сначала литературу.
1
|
|
|
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
|
|||
| 03.08.2011, 13:58 | |||
|
И скажем, на ТопКодере мощьнее ихний процессор, и вдруг попались одинаковые задачи. То на ТопКодере она может пройти, а на Кодфорсесе нет? Добавлено через 58 секунд
0
|
|||
| 03.08.2011, 13:58 | |
|
Бесконечная сфера и бесконечная плоскость Бесконечная рекурсия Бесконечная загрузка ОС Бесконечная загрузка Бесконечная игра Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
|
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#.
Название изменил на ColorStep.
Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
|
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами:
- ВидТО (СправочникСсылка. ВидыТО);
- ВидГСМ. . .
|
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала.
Ниже прикреплён. . .
|
|
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F
Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU.
Опрашиваются регистры. . .
|
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка:
Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
|
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо
Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
|
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман.
Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
|