Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.16.15.149] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу.
Есть такая задача. Строится некий ряд Bn: b1 = 1, b2 = 2, а, начиная с 3его слагаемого правила такие: • идет наименьшее положительное число, которое еще не добавлялось в числовой ряд; • НОД (bn, b(n-1)) > 1 То есть начало ряда будет таким: 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15 и т.д. Пользователь вводит натуральное число до 3млрд (это количество запросов) и затем каждый запрос состоит из натурального числа b. И надо для всех заданных b найти номер этого числа в этом ряду. Например: 2 9 4 2 – будет 2 запроса 9 – пользователя интересует, под каким номером стоит число 9 (ответ будет 6) 4 – пользователя интересует, под каким номером стоит число 4 (ответ будет 3) У пользователя есть право запрашивать числа до 280 000 включительно! Например, он может захотеть узнать, под каким номером число 273 909 было включено в последовательность. Программу я написал, выдает корректные результаты, но работает для больших чисел чуть ли не по 15-25 минут. Ужас. Основная структура данных, которую использую (дин.одномерный массив): 0 1 2 4 6 3 9 в качестве значений выступает число, выражающее номер числа в ряду 0 1 2 3 4 5 6 в качестве индекса взято число, добавляемое в ряд самый первый элемент массива - фиктивный (не юзается). те элементы, которые не добавлены в ряд, имеют значение = 0. Приходится постоянно отслеживать первый элемент, у которого значение = 0 (кроме 1го элемента, который фиктивный). Как я понимаю, ведь здесь нет формулы, которая позволяет четко получить номер числа по значению. Например, пользователь хочет знать порядковый номер числа = 15 000 в ряду. 15 000 число было получено после добавления 14 999 числа и т.д. То есть в любом случае надо строить все цепочку чисел до нужного. Также этот массив разреженный (не сильно правда). Также, например, число 200 000 примерно по счету добавляется в ряд под № 400 000. Программа работает так: выясняю макс. число среди всех запросов от пользователя. До этого числа (читай, индекса) заполняю порядковыми номерами все элементы массива. После этого вывожу результат массив[число заданное пользователем]. А вопрос у меня такой: это нормально, что программа для «худшего» случая работает под 30минут? Мне, кажется, что, точно нет. Может здесь нужна совсем другая структура данных... P.S. Ограничение по памяти: где-то около 200 «метров». |
Сообщ.
#2
,
|
|
|
Цитата FasterHarder @ НОД (bn, b(n-1)) > 1 Можно это расшифровать? |
Сообщ.
#3
,
|
|
|
Цитата Mikle @ Число и предыдущее к нему не должны быть взаимно простыми. Можно это расшифровать? |
Сообщ.
#4
,
|
|
|
Неплохая задачка, немного подумать пришлось. Можно действительно просто все числа сгенерировать до максимально запрошенного пользователем, только делать надо это оптимально.
Это должно сработать быстро и легко уложиться в ограничения. |
Сообщ.
#5
,
|
|
|