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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Aндерсон_256
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 16
#1

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

23.04.2014, 17:38. Просмотров 216. Ответов 0
Метки нет (Все метки)

Не могу никак одолеть следующую задачу:
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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++? - C++
Как работать с длинной арифметикой в C++? Может есть какие-нибудь функции предназначенные именно для этого?

Не могу справиться с if! - C++
Вот код: #include &lt;iostream.h&gt; #include &lt;stdio.h&gt; int main() { using namespace std; string name; cout &lt;&lt; &quot;Type name: ...

Не могу справиться с функцией с++ istringstream - C++
В общем, изначальный код был таков: #include &quot;stdafx.h&quot; #include&lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;sstream&gt; #include...

Не могу справиться с задачей на BorlC++ - C++
Дерево Пифагора – такая вещь, когда все начинается с квадрата, который на одной из сторон имеет равнобедренный прямоугольный треугольник....

не могу справиться с программами (они несложные) - C++
Парни, от меня в универе требуют к четвергу написать проги на C++, я написала около 9, осталось только 3.. помогите пожалуйста :-[ ...

не могу справиться задачкой в С++. У кого светлая голова напишите пожалуйста - C++
Задан массив, состоящий из 10 элементов. Из положительных элементов извлечь квадратный корень, отрицательные возвести в квадрат, нулевые...

Не могу справиться с задачей: "по какому предмету у студента с заданным номером в журнале лучшая оценка по итогам сессии?"! - C++
Задача выглядит так: &quot;по какому предмету у студента с заданным номером в журнале лучшая оценка по итогам сессии?&quot; То есть дан список...

Можно ли адресной арифметикой перебрать массив массивов по первому индексу во вложенном цикле, а во внешнем по второму? - C++
Можно ли адресной арифметикой перебрать массив массивов по первому индексу во вложенном цикле, а во внешнем по второму?

Как получить доступ к элементам массива работая с ним как с указателем и адресной арифметикой - C++
int array = { {1,2,3}, {1,2},{1,2,3,4}, {1,2,3,4},{1,2,},}; for(int i = 0; i &lt; 25; i++) printf(&quot;%d &quot;, array); ...

Помогите справиться с задачей!! - C++
Начал изучать С++ и попалась задача, не подскажите как ее сделать? Задача 2.29 Для действительных чисел х и а составить функцию...

Как справиться с задачей! - C++
Попались примеры сложные помогите решить

Помогите справиться с лабой по массивам) - C++
Задан массив из k чисел. Определить количество инверсий в массиве (т. е. таких пар элементов, в которых большее число находится слева от...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru