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

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

02.08.2011, 21:11. Показов 4994. Ответов 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
 Аватар для HighPredator
6045 / 2160 / 753
Регистрация: 10.12.2010
Сообщений: 6,005
Записей в блоге: 3
02.08.2011, 21:35
В силу того что я не знаком с типом map, я не понял, что вы имели ввиду в строчках
C++
1
2
3
4
5
if (!pc[a])
pc[a] = f(a); 
if (!pc[b])
   pc[b] = f(b);
pc[n] = pc[a] + pc[b];
Проблема может быть в недрах этого типа. Вот вам рабочий вариант:
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
#include<windows.h>
#include<conio.h>
#include<iostream>
 
int n,p,q,x,y;
 
int A(int i)
{
    int temp;
    if(i<1) temp=1;
    else
    {
        temp=A(i/p-x)+A(i/q-y);
    }
    return temp;
}
 
 
void main(void)
{   
    n=12;
    p=2;
    q=3;
    x=1;
    y=0;
    std::cout<<A(n)<<"\n";
    getch();
}
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 21:40  [ТС]
Predator_2004, ваш вариант не пройдет по тайм-лимиту еще на большем колличестве тестов, там N до 10^13. Мой вариант прекрасно работает на моих тестах, я даже не могу найти пример на котором он будет работать неправильно.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
02.08.2011, 21:59
Цитата Сообщение от iama Посмотреть сообщение
Помогите, люди добрые!
А чем помочь-то?
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 22:03  [ТС]
Evg,
Цитата Сообщение от iama Посмотреть сообщение
Или хоть контрпример подскажите...
При котором мое решение в ограничения не впишется. Я просто даже не могу подобрать такие данные, чтобы программа работала больше секунды, причем тестирующий сервер мощнее моего компа.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
02.08.2011, 22:07
Цитата Сообщение от iama Посмотреть сообщение
При котором мое решение в ограничения не впишется. Я просто даже не могу подобрать такие данные, чтобы программа работала больше секунды, причем тестирующий сервер мощнее моего компа
Тут скорее математик нужен, чтобы подобрал такие значения, чтобы цепочка вычисления рекурсии оказалась длинной. Если смотреть решение "в лоб", то у тебя сделано оптимальным способом. Может прикол в том, что данная последовательность математически упрощается? А то как-то не тянет оно на олимпиадную
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 22:09  [ТС]
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
#include <stdio.h>
#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
    {
        if (pc.count(n / p - x) <= 0)
            pc[n / p - x] = f(n / p - x);
 
        if (pc.count(n / q - y) <= 0)
            pc[n / q - y] = f(n / q - y);
 
        en:
        return pc[n / p - x] + pc[n / q - y];
    }
}
 
int main()
{
    long long n;
 
    scanf("%I64d %I64d %I64d %I64d %I64d", &n, &p, &q, &x, &y);
 
    printf("%I64d\n", f(n));
 
    return 0;
}
Те же тесты не проходят. Причем вызовов функции будет не больше чем 2*log2(n). Ничего не понимаю.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
02.08.2011, 22:13
Цитата Сообщение от Predator_2004 Посмотреть сообщение
В силу того что я не знаком с типом map, я не понял, что вы имели ввиду в строчках
Он по сути дэла в map'е кэширует уже вычисленные значения последовательности, чтобы второй раз их не считать (ибо это рекурсивно и требует времени)

Добавлено через 2 минуты
Цитата Сообщение от iama Посмотреть сообщение
Те же тесты не проходят. Причем вызовов функции будет не больше чем 2*log2(n). Ничего не понимаю
А отличие только в том, что ты используешь count?

Добавлено через 34 секунды
Кстати, первый вариант куда более читаемый. Во втором ты сэкономил на двух переменных и код превратил в кишку
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 22:17  [ТС]
Цитата Сообщение от Evg Посмотреть сообщение
Кстати, первый вариант куда более читаемый. Во втором ты сэкономил на двух переменных и код превратил в кишку
Я просто не нашел в документации поведения operator[] при отсутствии входящего элемента.

Даже придумать не могу, какой контейнер может больше оптимизировать работу программы. Математически упростить алгоритм никак нельзя. На том же сайте люди сдают за 0,5сек и 5мб памяти, причем на gcpp, как?..
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30
02.08.2011, 22:20
Ну хз. Я не алгоритмист

Чтобы сравнить два твоих варианта - воткни печати во все ветки и сравни. Может [] работает не так, как ты ожидал, может count работает не так, может ещё что-то
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 22:22  [ТС]
Evg, да нет, тот вариант точно так же работает, потому и печально. И на том спасибо
0
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
02.08.2011, 23:17
Вам надо избавиться от Map.
Не оптимальный подход, одной действие с элементом мэпы делаеться за логорифм от его размера, так что - это плохо.

З.Ы. только что здал задачу на 46.7%

Добавлено через 2 минуты
Прошу извенить, в худшем тесте ответ был за 2.031 секунды, не прошла на 100% я поторопился с выводами.

Но ответы правильные.
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 23:24  [ТС]
BAIZOR, даже знаю что вы написали.
Что-то вроде
этого
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
#include <stdio.h>
#include <map>
 
using namespace std;
 
long long p, q, x, y;
 
long long f(long long n)
 {
    if (n < 1)
        return 1;
    else
        return f(n / p - x) + f(n / q - y);
 }
 
int main()
 {
    long long n;
 
    scanf("%I64d %I64d %I64d %I64d %I64d", &n, &p, &q, &x, &y);
    printf("%I64d\n", f(n));
 
    return 0;
 }


Не пройдет, например при таком тесте
Code
1
10000000000000 2 3 1 0
А вот для моего решения контрпример я так и не нашел...
0
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
02.08.2011, 23:27
именно, я уже это понял, тут смутно проглядываеться математика, надо подумать...
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
02.08.2011, 23:29  [ТС]
Цитата Сообщение от BAIZOR Посмотреть сообщение
Не оптимальный подход, одной действие с элементом мэпы делаеться за логорифм от его размера, так что - это плохо.
Обращений к функции - максимум 2*log2(n), в каждом обращении - пускай по 10 обращений к ассоциативному массиву. Даже меньше чем линейная сложность.

Что интересно, простая рекурсия без ничего проходит 3 и 4 тест, а вариант с map'ом - нет

Добавлено через 2 минуты
BAIZOR, на том сайте есть "Дистанционная летняя компьютерная школа", где выкладывают задания. Так вот эту задачу там выложили в разделе о рекурсии, без разбора. Формулу вы тут никак не выведете
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
02.08.2011, 23:57
iama, не проходит по времени или по ответам?
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
03.08.2011, 00:05  [ТС]
ValeryLaptev, по времени на 4 тестах
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
03.08.2011, 00:16
Еще одно соображение.
Чтобы избавиться от "запора" по времени, надо статический массив организовать и туда сохранять вычисленные значения.
А чтобы знать, что сохранять, надо поиграться индексами. Наверняка индекс левого и правого слагаемого где-то совпадает...

Два рекурсивных вызова за раз - это многократное повторение одних и тех же вычислений. Вспомните последовательность Фибоначчи и как там избавляются от рекурсии.
0
Эксперт С++
 Аватар для grizlik78
2382 / 1666 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
03.08.2011, 00:21
Можно попробовать "поэкономить на спичках"
Но что-то сомнительно, что что-то изменится. Но прям интересно даже
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
#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)
{
    long long res;
    if (n < 1)
        return 1;
    if (!(res = pc[n]))
    {
        long long a = n / p - x, b = n / q - y, fa = 1, fb = 1;
        if (a < 0)
            a = 0;
        if (b < 0)
            b = 0;
 
        if (a && !(fa = pc[a]))
            fa = pc[a] = f(a);
 
        if (b && !(fb = pc[b]))
            fb = pc[b] = f(b);
 
        res = pc[n] = fa + fb;
 
    }
    return res;
}
 
int main()
{
    long long n;
 
    cin >> n >> p >> q >> x >> y;
 
    pc[0] = 1;
    cout << f(n) << endl;
 
    return 0;
}
0
0 / 0 / 0
Регистрация: 30.10.2010
Сообщений: 68
03.08.2011, 00:41
iama, ничиго не проглядываеться, всю дорогу упераюсь в то что надо найти кол-во листьев на бинарном дереве, но именно это и делает рекурсия, и никак предсказать поведение рекурсии у меня не получаеться, к сожалению.

У меня осталась единственная идея, это сделать так как вы делали, НО исползьвать вместо мэпы свою структуру которая будет работать точно также только не будет сортировать себя.
И обязательно считывать и выводить scanf и printf -ами!

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
Влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru