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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Числа Фибоначчи http://www.cyberforum.ru/cpp-beginners/thread1155358.html
Числа Фибоначчи {u}_{0},{u}_{1},{u}_{2},... определяются следующим образом: {u}_{0}=0,{u}_{1}=1,{u}_{n}={u}_{n-1}+{u}_{n-2} (n=2,3,...). Составить программу вычисления {u}_{n} для данного неотъемлемого целого n, которая будет включать рекурсивную функцию, которая основана на использовании соотношения {u}_{n}={u}_{n-1}+{u}_{n-2}
C++ Банкомат. В чем ошибка? Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Автор: Фёдор Меньшиков, ВГПУ. Реальный текст программы. ATM may contain notes of four kinds: 50, 100, 500 and 1000 rubles. Amount of notes of each kind at any moment is a non-negative integer number. 0 means that there are no notes of this kind. The lack of some notes may be filled with notes of smaller cost.... http://www.cyberforum.ru/cpp-beginners/thread1155356.html
C++ Программа переноса слов по слогам исправить ошибки
#include <stdio.h> #include <conio.h> #include <stdlib.h> #include <string.h> const maxrule=4;//êîë-âî ïðàâèë ïåðåíîñà...ìîæåòå äîïèñàòü ñâîè... ô-öèÿ äîëæíà ïðèíèìàòü ñëîâî è âîçâðàùàòü ïîçèöèþ äå ìîíà ïåðåíåñòè. int gl(char lit) { int i,res=0; char *glasn="óåûàîýÿèþ¸"; //char *glasn="eyuioav"; for (i=0;i<strlen(glasn);i++)
C++ Составить программу для вычисления среднего объема шаров
Решите пожалуйста=* Составить программу для вычисления Z=\frac{{V}_{1}+{V}_{2}+{V}_{3}}{3} где - {V}_{1},{V}_{2},{V}_{3} - объемы шаров с радиусами {r}_{1},{r}_{2},{r}_{3}, Вычисление объема шара по формуле V=\frac{4}{3}\pi {R}^{2} оформить при помощи функции.
C++ Трабл с решением задания, условные операторы http://www.cyberforum.ru/cpp-beginners/thread1155349.html
Здраствуйте, возникла определенная проблема при решении задания. Полагаю, не суть, что за задание, проблема вот в чем: В приведенном ниже алгоритме: #include <stdio.h> #include <conio.h> #include <math.h> int main() { float x, y;
C++ Проверить, високосный ли год, и вычислить сколько членов семьи родились в високосные годы Пожалуйста напишите код буду благодарна * Используя функцию year проверки ли год високосным, вычислить, сколько членов вашей семьи родились в високосные годы. Параметром функции является номер года, результат логического типа. / / Функция определяет ли год високосным bool year (unsigned int x) { if (x% 4) return false; else return true; подробнее

Показать сообщение отдельно
Aндерсон_256
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 16
23.04.2014, 17:38     Не могу справиться с длинной арифметикой
Не могу никак одолеть следующую задачу:
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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];
        }
    }
Буду весьма признателен человеку, указавшему мой промах.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru