Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.52/23: Рейтинг темы: голосов - 23, средняя оценка - 4.52
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297

Бесконечная последовательность

02.08.2011, 21:11. Показов 5034. Ответов 50
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задача

Моё решение на плюсах
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <map>
 
using namespace std;
 
long long p, q, x, y;
map <long long, long long> pc;
 
long long f(long long n)
{
    if (n < 1)
        return 1;
    else
    {
        long long a = n / p - x, b = n / q - y;
 
        if (!pc[a])
            pc[a] = f(a);
 
        if (!pc[b])
            pc[b] = f(b);
 
        pc[n] = pc[a] + pc[b];
 
        return pc[n];
    }
}
 
int main()
{
    long long n;
 
    cin >> n >> p >> q >> x >> y;
 
    cout << f(n) << endl;
 
    return 0;
}


Есть подозрения, что при каком-то наборе данных алгоритм зацикливается (но не должно же - чем глубже рекурсия, тем меньший элемент последовательности ищется, вроде всегда так), пробовал крайние значения - работает в доли секунды.

Помогите, люди добрые!

Или хоть контрпример подскажите...
1
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
02.08.2011, 21:11
Ответы с готовыми решениями:

Бесконечная последовательность
Добрый день! начала изучать новую тему, прочитала кучу разного материала, но на практике ничего не получается, так как нет достойного...

Бесконечная последовательность десятичных цифр
Бесконечная последовательность десятичных цифр содержит запись последовательных целых чисел: 123456789101112... Определить какая цифра...

Бесконечная последовательность рациональных чисел v0, v1 , . образована по следующему закону :
Описание задачи необходимо вставлять в текстовом виде Бесконечная последовательность рациональных чисел v0, v1 , ... образована по...

50
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.08.2011, 00:42  [ТС]
Студворк — интернет-сервис помощи студентам
Спасибо за участие и внимание, о результатах отпишу завтра
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
03.08.2011, 00:42
Или то же самое, только более однообразно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long f(long long n)
{
    long long res = 1;
    if (n > 0 && !(res = pc[n]))
    {
        long long a = n / p - x, b = n / q - y, fa = 1, fb = 1;
        
        if (a > 0 && !(fa = pc[a]))
            fa = pc[a] = f(a);
 
        if (b > 0 && !(fb = pc[b]))
            fb = pc[b] = f(b);
 
        res = pc[n] = fa + fb;
 
    }
    return res;
}
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.08.2011, 09:48  [ТС]
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Чтобы избавиться от "запора" по времени, надо статический массив организовать и туда сохранять вычисленные значения.
Делал это как массив pair <long long, long long>, тот же результат
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Два рекурсивных вызова за раз - это многократное повторение одних и тех же вычислений. Вспомните последовательность Фибоначчи и как там избавляются от рекурсии.
Второй будет вычисляться только если он отличен от первого, по моему - оптимально. Можете оценить сложность моей реализации? Мне кажется, там что-то сравнимое с линейной сложностью.

grizlik78, и такой вариант тоже пробовал очень странно вышло - прироста в производительности - ноль, в то время как обьем используемой памяти вырос в полтора раза (ну это-то понятно, для каждого вызова хранить лишние 128 бит, оно и выходит)
Цитата Сообщение от BAIZOR Посмотреть сообщение
У меня осталась единственная идея, это сделать так как вы делали, НО исползьвать вместо мэпы свою структуру которая будет работать точно также только не будет сортировать себя.
И она будет работать быстрей, чем за логарифм от своего размера? И что же это за структура?
Цитата Сообщение от grizlik78 Посмотреть сообщение
Или то же самое, только более однообразно.
Увы, результат тот же

Добавлено через 22 минуты
Цитата Сообщение от iama Посмотреть сообщение
Делал это как массив pair <long long, long long>, тот же результат
Переделал еще как long long ar [2][1000000], по памяти - 1мб, со временем - та же фигня
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
03.08.2011, 11:30
Цитата Сообщение от iama Посмотреть сообщение
Увы, результат тот же
Да я почти не сомневался. Там экономится в основном поиск, а потери производительности где если и могут быть, так это при вставке. Но, блин, 2 секунды... Это как же так надо было мап реализовать?

Цитата Сообщение от iama Посмотреть сообщение
очень странно вышло - прироста в производительности - ноль, в то время как обьем используемой памяти вырос в полтора раза (ну это-то понятно, для каждого вызова хранить лишние 128 бит, оно и выходит)
А это интересно. Сколько было и сколько стало? По размеру косвенно можно попытаться оценить глубину рекурсии. Хотя и не просто это.
1
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
03.08.2011, 11:58
Вместо map попробуй использовать хеш-таблицу.
1
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.08.2011, 12:46  [ТС]
Цитата Сообщение от grizlik78 Посмотреть сообщение
Это как же так надо было мап реализовать?
У меня тот же вопрос. Ладно, GNU C++ 3.4, там еще что угодно могло быть, но VC++ 2008... Там уж точно он должен быть нормально реализован.
Цитата Сообщение от grizlik78 Посмотреть сообщение
А это интересно. Сколько было и сколько стало? По размеру косвенно можно попытаться оценить глубину рекурсии. Хотя и не просто это.
Я на разных тестах выводин размер map'a/vector'a/массива - больше 10 000 пар никогда не было. Такое чувство, что большая часть памяти идет не на структуру, а на стек для рекурсии
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Вместо map попробуй использовать хеш-таблицу
Можете скинуть ссылку на пример подобной реализации? unordered_map не подходит, т. к. в VC++ 2008, насколько я знаю, он еще не поддерживается

Добавлено через 3 минуты
Нашел! буду пробовать

Добавлено через 7 минут
Вариант с hash_map'ом даже не компилирует (на тестирующем сервере)

Добавлено через 15 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
 
long long p, q, x, y, arl;
long long ar [2][1000000];
 
long long f(long long n)
{
    if (n < 1)
        return 1;
    else
    {
        long long a = n / p - x, b = n / q - y, ax, bx;
 
        for (int i = 0; i < arl; i++)
            if (ar[0][i] == n)
                return ar[1][i];
 
        if (a < 1)
        {
            ax = 1;
            goto ax_found;
        }
 
        for (int i = 0; i < arl; i++)
            if (ar[0][i] == a)
            {
                ax = ar[1][i];
                goto ax_found;
            }
 
        ax = f(a);
        ar[0][arl] = a;
        ar[1][arl] = ax;
        arl++;
 
        ax_found:
 
        if (b < 1)
        {
            bx = 1;
            goto bx_found;
        }
 
        for (int i = 0; i < arl; i++)
            if (ar[0][i] == b)
            {
                bx = ar[1][i];
                goto bx_found;
            }
 
        bx = f(b);
        ar[0][arl] = b;
        ar[1][arl] = bx;
        arl++;
 
        bx_found:
 
        ar[0][arl] = n;
        ar[1][arl] = ax + bx;
        arl++;
 
        return ax + bx;
    }
}
 
int main()
{
    long long n;
 
    arl = 0;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%I64d %I64d %I64d %I64d %I64d", &n, &p, &q, &x, &y);
    printf("%I64d %I64d\n", arl, f(n));
 
    return 0;
}
Версия с статическим массивом, тут же вывожу и колличество заполненых элементов массива, при
Code
1
1000000000000000000 2 3 1 0
работает меньше чем полсекунды
0
Эксперт С++
 Аватар для Хохол
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
03.08.2011, 12:52
Хешмапу и руками несложно написать, только врядли она поможет.
0
 Аватар для iama
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 на секунду.


Цитата Сообщение от iama Посмотреть сообщение
И она будет работать быстрей, чем за логарифм от своего размера? И что же это за структура?
Сейчас напишу, через пару минут покаже код

Добавлено через 25 минут
Я дико ошибался, в моей структуре доступ к элементу будет вообще за О(N) где N - размер структуру, мэпа лучше.

Очень интересная задача! Пока не знаю как к ней подойти, но я еще подумаю, и если что получится то обязательно Вам отпишу!

Добавлено через 1 минуту
Ах да, там я видел писали про хешы, так вот, не забивайте себе голову, тут в хешах нету смысла.
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.08.2011, 13:32  [ТС]
Цитата Сообщение от BAIZOR Посмотреть сообщение
Ах да, там я видел писали про хешы, так вот, не забивайте себе голову, тут в хешах нету смысла.
Они могли бы дать меньшую сложность поиска и вставки элемента в структуре, но тут проблема, очевидно, не в этом.
0
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
03.08.2011, 13:34
Цитата Сообщение от iama Посмотреть сообщение
Они могли бы дать меньшую сложность поиска и вставки элемента в структуре
каким образом? мэпа дает уже за логорифм.
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
03.08.2011, 13:37
Написал тут генератор x и y.
При вот таких значениях
10000000000000 2 2 287955 1013083
мой вариант работает около 7 секунд, при этом совершается более 5 млн. вызовов функции f.
И думаю это не предел
1
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.08.2011, 13:43  [ТС]
BAIZOR, вот тут есть. Поиск по ключу явно был бы быстрее.

grizlik78, огромное спасибо. Буду оптимизировать
0
Эксперт С++
 Аватар для Хохол
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
Цитата Сообщение от iama Посмотреть сообщение
BAIZOR, вот тут есть. Поиск по ключу явно был бы быстрее.
Мєпа также исчит по ключу, но суть в хешах что бы сравнить объекты которые по сути очень тяжело сравнить, допустим 1 строку текста сравнить с другой, тупо переберать буквы и сравнивать - глупо, для этого хеши что бы посчитать хеш этой строки 1 раз (за О(N) N - длина строки), потом подсчитать второй, и можна сравнивать их за O(1), покачто выгода не проглядываеться, тогда представтьве что вам надо сравнить строку А со строками А0 - Аn. Сразу экономия большая.

А в вашей задаче использовать хеш мэп, это всеравно что использовать мэп, только еще будут затраты на само преобразование в мэп, а оно громоздкое. Там сложная формула в которой много делений, делений по модулю, делений на простое числое (которое еще надо будет вывести) умножение на что-то, и вот только тогда вы получите уникальный хеш код элеменьта, НО зачем вам получять хеш код и так уникального элемента?
В этом просто нету смысла, вы будете только тратить время на получение хэш кода.
0
Эксперт С++
 Аватар для Хохол
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
03.08.2011, 13:53
Причем вызовов функции
будет не больше чем 2*log2(n)
Думаю вы уже поняли что оценка неверна.
Я пока с телефона и помочь особо не могу, только критиковать
1
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
03.08.2011, 13:53
Цитата Сообщение от Хохол Посмотреть сообщение
Чушь же. Нигде так не делают, всегда от сервера время зависит.
то есть вы хотите сказать что если сервер перегружен залитыми на него решениями, и он не буде туспевать проверять все сразу, то он всем выдаст time limite поскольку они не впишуться во время?
Или если на одном сервере стоит процессор более мощьный чем на другом, то на мощьном сервере решение пройдет, а на слабом нет?
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
03.08.2011, 13:55
Цитата Сообщение от BAIZOR Посмотреть сообщение
то есть вы хотите сказать что если если сервер перегружен залитыми на него решениями, и он не буде туспевать проверять все сразу, то он всем выдаст time limite поскольку они не впишуться во время?
Если внимательно посмотреть, то на всех таких серверах тестовые задания выстраиваются в очередь.
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
Цитата Сообщение от grizlik78 Посмотреть сообщение
Если внимательно посмотреть, то на всех таких серверах тестовые задания выстраиваются в очередь.
Тогда получиться что если есть скажем 2 разных контестных сервера (Codeforces и TopCoder).
И скажем, на ТопКодере мощьнее ихний процессор, и вдруг попались одинаковые задачи.
То на ТопКодере она может пройти, а на Кодфорсесе нет?

Добавлено через 58 секунд
Цитата Сообщение от Хохол Посмотреть сообщение
Сервер по-очереди проверяет решения. И хватит гнать на хешмапу, она классная, прочитайте сначала литературу.
я не гоню на нее, она действительно классная, но не в этой задаче.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
03.08.2011, 13:58
Помогаю со студенческими работами здесь

Бесконечная сфера и бесконечная плоскость
Даже не знаю в какой степени это геометрический вопрос, но пересекает ли бесконечная плоскость бесконечную сферу?

Бесконечная рекурсия
есть 2 функции который должны возвращать 0 или 1 в зависимости от элементов массивов PA и element. Известно что значения этих функций при...

Бесконечная загрузка ОС
Всем доброго времени суток! Иногда сталкиваюсь с проблемой бесконечной загрузки ОС. Проблема появляется не систематически, может пару...

Бесконечная загрузка
бесконечно грузит, потом перезагружает компьютер и опять так же.До этого пытался поставит 10 винду выдало ошибку и теперь даже если ставишь...

Бесконечная игра
Я где-то читал что раньше была игра переносная (как тамогочи только не томагочи а летать на корабле там надо было) и программа у этой игры...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru