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

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

02.08.2011, 21:11. Показов 5276. Ответов 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
2383 / 1667 / 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
2383 / 1667 / 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
2383 / 1667 / 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
2383 / 1667 / 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
Ответ Создать тему
Новые блоги и статьи
FSharp: interface of module
DevAlt 16.05.2026
Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .
Хитросплетение родственных связей пантеона греческих богов.
russiannick 14.05.2026
Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов
alhaos 12.05.2026
По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .
Debian 13: Установка Lazarus QT5
ВитГо 09.05.2026
Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .
Нейросеть на алгоритме "эстафета хвоста" как перспектива.
Hrethgir 06.05.2026
На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .
Асинхронный приём данных из COM-порта
Argus19 01.05.2026
Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .
попытка написать игровой сервер на C++
pyirrlicht 29.04.2026
попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .
Контроль уникальности выбранного документа-основания при изменении реквизита
Maks 28.04.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru