Форум программистов, компьютерный форум CyberForum.ru

динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
trebor
1 / 1 / 0
Регистрация: 05.01.2011
Сообщений: 25
05.01.2011, 16:56     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #1
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
#include <stdio.h>
 
int rekursia(int K,int N);
 
int main()  {
    int K,N;
    long n;
    /*(freopen("input.txt","r",stdin); /*перенаправление потоков для  
    freopen("output.txt","w",stdout);*/ /*работы с файлами
    scanf("%d %d",&K,&N);
    n=rekursia(K,N);
    printf("%d\n",n);
    
 
 
}
 
int rekursia(int K,int N)  { /* собственно сама функция
    if (N<0) 
        return 0;
    if(N==0)
        return 1;
    if(N==1) 
        return 1;
    return 2*rekursia(K,N-1)-rekursia(K,N-K-1);
}

Текст задачи:

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.

Входные данные

В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Собственно сама алгоритм: F(K,N)=2*F(K,N-1)-F(K,N-K-1).

Помогите, пожалуйста, с длинной арифметикой, желательно, чтобы использовался целочисленный массив.(потому как при больших K и N ответ не влазит ни в какой тип данных).

Премного благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2011, 16:56     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику).
Посмотрите здесь:

C++ Задача на длинную арифметику
C++ Динамическое программирование
C++ [C++] Реализовать длинную арифметику ASM вставками
C++ Реализовать длинную арифметику
Как доделать длинную целочисленную арифметику? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 17:53     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #2
Код прошел все тесты:
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
#include <stdio.h>
 
void rekursia(int y, int K,int N, int **mas);
 
int main()  {
        int K,N, **mas, i, j;
        freopen("input.txt","r",stdin); 
        freopen("output.txt","w",stdout);
        scanf("%d %d",&K,&N);
        mas=new int*[N+1];
        for(i=0; i<N+1; i++)
        {
            mas[i]=new int[100];
            for(j=0; j<100; j++)
                mas[i][j]=0;
        }       
        mas[0][0]=1;
        rekursia(1, K, N, mas);
        int fl=1;
        for(i=99; i>=0; i--)
        {
            if(!fl)
                printf("%d", mas[N][i]);
            if(fl && mas[N][i])
            {
                fl=0;
                printf("%d", mas[N][i]);
            }
        }
        return 0; 
}
 
void rekursia(int y, int K,int N, int **mas)  {
    if(y==N+1)
        return;
    int i=0;
    if(y-K>=0)
        i=y-K;
    for(; i<y; i++)
        for(int j=0; j<100; j++)
            mas[y][j]+=mas[i][j];
    for(i=0; i<99; i++)
        if(mas[y][i]>9)
        {
            mas[y][i+1]+=mas[y][i]/10;
            mas[y][i]%=10;
        }
    rekursia(y+1, K, N, mas);
}
trebor
1 / 1 / 0
Регистрация: 05.01.2011
Сообщений: 25
05.01.2011, 18:08  [ТС]     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #3
Спасибо большое, будем разбираться.

Добавлено через 3 минуты
Если кто способен написать попроще, и есть время, не стесняйтесьИнтересны все версии))

Странно, вроде компилится, но когда загружается приложение .exe, выходит ошибка: Debug error!
Извините, если что, я еще совсем новичок.
Это похоже что-то с Visual Studio, код компилится, спасибо ещё
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 18:14     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #4
trebor, Вы куда сдаете задачу?
trebor
1 / 1 / 0
Регистрация: 05.01.2011
Сообщений: 25
05.01.2011, 18:22  [ТС]     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #5
на ********.
просто в visual studio тормоза какие-то..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 18:32     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #6
Сдать задачу получилось вроде?

Добавлено через 3 минуты
trebor, Напишите любой код который у вас без ошибок работает.
trebor
1 / 1 / 0
Регистрация: 05.01.2011
Сообщений: 25
05.01.2011, 18:35  [ТС]     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #7
Да, получилось, только мне еще интересно было бы разобрать код, а так как я новичок...

Насчёт второго пункта, не совсем понял, но тот код, который в начале топика, работает на малых числах, порядка 30*30.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 18:42     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #8
trebor, Сейчас я напишу комментарии для своего кода.
Насчет второго пункта (
Странно, вроде компилится, но когда загружается приложение .exe, выходит ошибка: Debug error!
): скорее всего у Вас в проекте не было файла input.txt или он был но не с подходящими данными.
trebor
1 / 1 / 0
Регистрация: 05.01.2011
Сообщений: 25
05.01.2011, 18:47  [ТС]     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #9
ну конечно же, да...., мне стыдно((спасибо, файлы файлы с данными...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2011, 18:55     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику).
Еще ссылки по теме:

Динамическое программирование: самая длинная строго возрастающая подпоследовательность C++
C++ Переделать в длинную арифметику
C++ Задача на длинную арифметику

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2011, 18:55     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). #10
Я немного не так сделал, не по этому алгоритму:
Цитата Сообщение от trebor Посмотреть сообщение
F(K,N)=2*F(K,N-1)-F(K,N-K-1).
я сделал так:
F(K,N)=F(K, N-1)+F(K, N-2)+...+F(K, N-K).

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
#include <stdio.h>
 
void rekursia(int y, int K,int N, int **mas);// в функцию передаем номер текущей ступени y, K, N, двумерный массив для хранения значений F(K,N)
 
int main()  {
        int K,N, **mas, i, j;
        freopen("input.txt","r",stdin); 
        freopen("output.txt","w",stdout);
        scanf("%d %d",&K,&N);
                mas=new int*[N+1];// создаем двумерный массив размером (N+1)*100 - каждая строка это значение F(K,N), сто элементов типа int в каждой строке, чтобы хватило для большого числа
                for(i=0; i<N+1; i++)
                {
                        mas[i]=new int[100];
                        for(j=0; j<100; j++)
                                mas[i][j]=0;
                }               
                mas[0][0]=1;// в нулевой строке 1 - нулевая строка это земля (даже не первая ступень)
        rekursia(1, K, N, mas);// вызываем рек.функцию в параметрах передаем, что текущая рассматриваемая ступенька - первая, а также передаем значения K,M, и адрес mas[][]
                int fl=1;
                for(i=99; i>=0; i--)
                {
                        if(!fl)
                                printf("%d", mas[N][i]);
                        if(fl && mas[N][i])
                        {
                                fl=0;
                                printf("%d", mas[N][i]);
                        }
                }
                return 0; 
}
 
void rekursia(int y, int K,int N, int **mas)  {
        if(y==N+1)// если текущая рассматриваемая ступенька имеет номер N+1, то прекращаем рекурсию
                return;
        int i=0;// в этой строке и двух ниже определяем значение i (c учетом сколько ступенек от земли)
        if(y-K>=0)
                i=y-K;
        for(; i<y; i++)// в этом цикле делаем: F(K,N)=F(K, N-1)+F(K, N-2)+...+F(K, N-K).
                for(int j=0; j<100; j++)
                        mas[y][j]+=mas[i][j];
        for(i=0; i<99; i++)// в этом цикле в строке с только что расчитанным F(K,N) делаем так что в каждом элементе число не более 9 (напоминаю, что всего элементов для хранения F(K,N) сто).
                if(mas[y][i]>9)
                {
                        mas[y][i+1]+=mas[y][i]/10;
                        mas[y][i]%=10;
                }
        rekursia(y+1, K, N, mas);// вызываем рек. функцию для следующей ступеньки.
}
Yandex
Объявления
05.01.2011, 18:55     динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику).
Ответ Создать тему
Опции темы

Текущее время: 12:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru