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

Не могу справиться с длинной арифметикой - C++

Восстановить пароль Регистрация
 
Aндерсон_256
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 16
23.04.2014, 17:38     Не могу справиться с длинной арифметикой #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 – общее число ступенек лестницы.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.

Понятно, что задача требует применения динамического программирования и длинной арифметики. С первым я справился, со вторым никак не выходит, из сил выбился, но ошибку свою отыскать никак не могу. Код задачи с ДП,но без ДА:

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
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout ("output.txt");
    int k,n;
    fin>> k >> n;
 
    long long*ar=new long long[n+1];
    ar[0]=ar[1]=1;
    for(int i=2;i<k;i++)
    {
        ar[i]=0;
        for(int y=i;y>=0;--y)
        {
            ar[i]+=ar[y];
        }
    }
    for(int i=k;i<=n;i++)
    {
        ar[i]=0;
        for(int y=k;y>0;--y)
        {
            ar[i]+=ar[i-y];
        }
    }
        fout << ar[n];
 
 
 
}
Вот код программы с ДП и ДА, которая сбивается при больших значениях, и в ответе получается многоциферная ахинея со знаками минус:

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
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout ("output.txt");
    int k,n;
    fin >> k >> n;
    int**ar;
    ar=new int*[n+1];
    int arry[2];
    arry[0]=2;
    arry[1]=1;
    ar[0]=ar[1]=arry;
 
    for(int i=2;i<k;i++)
    {
        int siz=ar[i-1][0]+1;
        ar[i]=new int[siz];
        ar[i][0]= siz;
        for(int q =1;q<siz;q++)
        {
            ar[i][q]=0;
        }
 
        for(int y=i-1;y>=0;y--)
        {
            for(int z=1;z<ar[i][0]-1;z++)
        {
            ar[i][z]+=ar[y][z];
 
            ar[i][z+1]+=(ar[i][z]/10);
 
            ar[i][z]%=10;
 
        }
 
           }
             if(ar[i][siz-1]==0)
           {
 
               ar[i][0]-=1;
        }
    }
     for(int i=k;i<=n;i++)
    {
        int siz=ar[i-1][0]+1;
        ar[i]=new int[siz];
        ar[i][0]= siz;
        for(int q =1;q<siz;q++)
        {
            ar[i][q]=0;
        }
        for(int y=k;y>0;--y)
        {
           for(int z=1;z<ar[i][0]-1;z++)
           {
               ar[i][z]+=ar[i-y][z];
               ar[i][z+1]+=(ar[i][z]/10);
               ar[i][z]%=10;
           }
        }
        if(ar[i][siz-1]==0)
        {
            ar[i][0]-=1;
        }
    }
        for(int y=ar[n][0]-1;y>=1;y--)
        {
            fout << ar[n][y];
        }
    }
Буду весьма признателен человеку, указавшему мой промах.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2014, 17:38     Не могу справиться с длинной арифметикой
Посмотрите здесь:

C++ Не могу справиться с задачей на BorlC++
Не могу справиться с одномерным массивом:) C++
C++ Не могу справиться с простой программкой
C++ не могу справиться с программами (они несложные)
Не могу справиться с if! C++
C++ Не могу справиться с двумерным массивом
C++ Не могу справиться с функцией с++ istringstream

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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