Сложная арифметика (Си)

[Gon]

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

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

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

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

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;

	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;
}

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

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

[BaronTreep]

Есть типы побольше чем int

unsigned long int - 4 байт, > 4 миллиардов
long double - 10 байт

[Gon]

Да есть. Использовал unsigned long int, да он будет работать если значение К=7(получается: 307487848), но если увеличить значение К до, например, 14, то получается значение: 2620816, неможет же быть что при увеличении К количество возможных путей зайца уменьшается.

По поводу double, я не смог переделать программу, чтоб работало с этим типом Проблемы с массивом. Было бы хорошо если бы вы подсказали что нужно поправить.

[Gon]

Переделал программу, с использованием длинной арифметики.
Если камуто потом надо будет.

#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;
}