VPF::[C]Длинная арифметика - Форум программистов

Gon

Дата 31.5.2009, 20:55 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 30.4.2008

Репутация: нет
Всего: нет

Надо было сделать задачу на Си.

Имеется лестница, состоящая из N ступенек. При подъеме по лестнице заяц может прыгать на любое количество ступенек от 1 до K. Сколько у зайца способов подъема по лестнице? Ввод из файла INPUT.TXT. Единственная строка содержит целые положительные числа N и K.
Есть ограничения 0 < N < 35

Задачу я сделал, даже думал что все хорошо, но преподаватель заброкавал. При тесте Х=35 К=7(и больше) у меня программа выводит не правельный результат, т.к. получившееся значение не помещается в 32 бита.

Код


#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

long int n, k, ch, ways, i, j;

//Процедура подсчета путей зайца
int findways(int n, int k)
{
    int *s = (int *)calloc(n + 1, sizeof(int));

    //заполняем массив нулями
    memset(s, 0, n + 1);

    //начальные случаи
    s[0] = 1;
    s[1] = 1;
    printf("%d \n", n);
    if (k <= 1 || n <= 0)
        return 1;
    else
        for (i = 2; i < n + 1; i++)
            /* количество путей для данного i равно сумме количеств путей
            для k предыдущих i или для всех i, если i - k < 0 */
            for ((i - k < 0) ? (j = 0) : (j = i - k); j < i; j++)
            s[i] += s[j];

    ways = s[n];
    free(s);

    return ways;
}

int main(void)
{
    //Создание и проверка на существование файлов
    FILE *IFile, *OFile;
    if((IFile = fopen("Input.txt", "r")) == NULL)
    {
        printf("Can't open Input file.\n");
        return 1;
    }
    if((OFile = fopen("Output.txt", "w")) == NULL)
    {
        printf("Can't open Output file.\n");
        return 1;
    }

    //Считывание значений из файла
    fscanf(IFile, "%d %d", &n, &k);

    if (n > 35)
    {
        printf("not correct n \n");
        fprintf(OFile, "not correct n");
    }
    else
    {
        //Запись получившегося значения путей в файл и закрытие файлов
        fprintf(OFile, "%d", findways(n, k));
    }
    fclose(IFile);
    fclose(OFile);

    return 0;
}

Не могли бы помочь с длинной арефметикой к данной программе ? А если возможно как без нее обойтись smile

Например, N=35 K=7 в выводит Output: -1886316324.

ПСы использовал unsigned long int в случае К=7 помогает, но дальше уже число не влазеет. Неизвестно как будет с double и long double, т.к. не могу исправить программу под этот тип.

Dmi3ev

Дата 31.5.2009, 23:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 5
Всего: 41

http://forum.vingrad.ru/forum/topic-245444.html
только при этом надо учитывать, что суммы не должны состоять из слагаемых больше К...
мне кажется так...

--------------------

Gon

Дата 1.6.2009, 00:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 30.4.2008

Репутация: нет
Всего: нет

Ну помоему там не решение моей проблемы, а алгоритм похожий на мой, просто в примере той темы было разложения числа 7 и его "путей"(для моей задачи).

Это сообщение отредактировал(а) Gon - 1.6.2009, 00:07

kami

Дата 1.6.2009, 00:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1806
Регистрация: 25.8.2007
Где: Санкт-Петербург

Репутация: нет
Всего: 72

модуль работы с длинной арифметикой

Dmi3ev

Дата 1.6.2009, 00:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 5
Всего: 41

Цитата

Ну помоему там не решение моей проблемы, а алгоритм похожий на мой, просто в примере той темы было разложения числа 7 и его "путей"(для моей задачи).

ну если у тебя все ок, и ты не хочешь менять свой алгоритм, и работает он верно, то возьми какую-нибудь либу для работы с большими числами... их полно...

--------------------

Gon

Дата 2.6.2009, 10:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 30.4.2008

Репутация: нет
Всего: нет

Вот переделал свой лагоритм, с помощью длинной арифметики, мб камуто прегодится.

Код


#include <stdlib.h>
#include <stdio.h>

#define LONG_NUM_CAPACITY 50

typedef char LongNum[LONG_NUM_CAPACITY];

void SetLongNumToZero( LongNum longNum )
{
    int i;
    for ( i = 0; i < LONG_NUM_CAPACITY; i++ )
    {
        longNum[i] = 0;
    }
}

void SetLongNumFromShort( LongNum longNum, size_t shortNum )
{
    int i = 0;
    while ( shortNum >= 10 )
    {
        longNum[i++] = shortNum % 10;
        shortNum = shortNum / 10;
    }
    longNum[i] = shortNum;
}

void PrintLongNum( FILE *pOutput, LongNum longNum )
{
    int i;
    for ( i = LONG_NUM_CAPACITY - 1; i >= 0; i-- )
    {
        if ( longNum[i] != 0 )
        {
            break;
        }
    }

    if ( i == -1 )
    {
        fprintf( pOutput, "0" );
    }
    else
    {
        for ( ; i >= 0; i-- )
        {
            fprintf( pOutput, "%d", longNum[i] );
        }
    }
}

void AddToLongNum( LongNum longNum1, LongNum longNum2 )
{
    int i;
    for ( i = 0; i < LONG_NUM_CAPACITY; i++ )
    {
        if ( i < LONG_NUM_CAPACITY - 1 )
        {
            longNum1[i + 1] += ( longNum1[i] + longNum2[i] ) / 10;
        }
        longNum1[i] = ( longNum1[i] + longNum2[i] ) % 10;
    }
}

void SetLongNum( LongNum longNum1, LongNum longNum2 )
{
    int i;
    for ( i = 0; i < LONG_NUM_CAPACITY; i++ )
    {
        longNum1[i] = longNum2[i];
    }
}

void FindWays( LongNum waysNum, int n, int k )
{
    int i, j;
    FILE *IFile;
    if((IFile = fopen("Input.txt", "r")) == NULL)
    {
        printf("Can't open Input file.\n");
        return 1;
    }
    LongNum *s = (LongNum *) calloc( n + 1, sizeof( LongNum ) );

    SetLongNumFromShort(s[0], 1);
    SetLongNumFromShort(s[1], 1);

    fscanf(IFile, "%d %d", &n, &k);
    if ( k <= 1 || n <= 0 )
    {
        SetLongNumFromShort( waysNum, 1 );
    }
    else
    {
        for ( i = 2; i < n + 1; i++ )
        {
            if ( i - k < 0 )
            {
                j = 0;
            }
            else
            {
                j = i - k;
            }

            for ( ; j < i; j++ )
            {
                AddToLongNum( s[i], s[j] );
            }
        }

        SetLongNum( waysNum, s[n] );
    }

    free(s);
}

int main()
{
    int n, k;
    FILE *OFile;
    if((OFile = fopen("Output.txt", "w")) == NULL)
    {
        printf("Can't open Output file.\n");
        return 1;
    }

    LongNum longNum;
    SetLongNumToZero( longNum );
    FindWays( longNum, n, k );
    PrintLongNum( OFile, longNum );

    return EXIT_SUCCESS;
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »