Найти количество различных чисел, которые можно получить из числа ровно за C команд

@max_besheniy · Регистрация: 21.11.2013

Author24 — интернет-сервис помощи студентам

C++

#include <iostream>
using namespace std;
int c(int x, int y)
{
    if (x == y || y == 0) return 1;
    else if (y > x) return 0;
    else return c(x - 1, y - 1) + c(x - 1, y);
}
int main()
{
    int a,b,k;
    cin >>a>>b>>k;
    int s=0;
    for(int i=1;i<=k-1;i++)
    for(int j=1;j<=k-1;j++)
        if (j+i==k) s+=((c(i+j,i)+c(j+i,j)))/2;
    if (a==b) cout<<1<<endl;
    else
    cout<<s/k<<endl;
}

Есть задача следующего содержания
У исполнителя две команды:

1. прибавить A

2. прибавить B

Первая увеличивает число на экране на A, вторая - на B. Программа для этого исполнителя - это последовательность комманд. Изначально число на экране - 255. Сколько различных чисел можно получить из него с помощью программы, которая содержит ровно C комманд.
Входные данные:
Входной поток содержит три целых числа A, B, C (-1000 <= A, B <= 1000, 1 <= C <= 1000)

Выходные данные:
Выведите количество различных чисел, которые можно получить из числа 255 с помощью программы ровно из C команд.

Пример входного файла (input.txt):
3 -2 5
Пример выходного файла (output.txt):
6

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

Добавлено через 4 минуты
Желательно было бы подкинуть функцию с более скоростным вычисление с(n,m), или подсказать идею решения, если у меня уж в корне неправильно

@vitecd · 18.12.2013, 04:23

т.е. она у тебя еще и рекурсивная...

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

@max_besheniy · 18.12.2013, 19:25 **[ТС]**

Я вчера затупил. Очень
Задача-елементарщина

C++

#include <iostream>
using namespace std;
int main()
{
    int a,b,k;
    cin >>a>>b>>k;
    int s=0;
    for(int i=0;i<=k;i++)
    for(int j=0;j<=k;j++)
        if (i+j==k) s++;
    if (a==b) cout<<1<<endl;
else
    cout<<s<<endl;
}

03.07.2014, 20:06

Если я не ошибаюсь, задача решается проще. Количество чисел определяется количеством слогаемых типа A, т. к. остальные будут равны B, т. е. от 0 до C, С + 1. Это конечно если А не равно В. Осталось доказать, что нельзя представить одно и тоже число 2 разными слагаемыми в таком же общем количестве двумя и более способами. Это сделать просто: если мы меняем сумму мы фактически только лишь уменьшаем количество слагаемых какого-либо типа, добавляя другого. Если меньшего слагаемого будет больше, чем было до, то сумма уменьшится и наоборот. Значит способов ровно С + 1, если только А не равно В.

@vitecd 18 / 1 / 0 Регистрация: 26.09.2013 Сообщений: 59
	18.12.2013, 04:23	2
	т.е. она у тебя еще и рекурсивная... хоть убей - не понял, в чем суть задачи? я понимаю, что тебе "надо", но зачем? алгоритм не понятен 0

Max_17
	03.07.2014, 20:06	4
	Если я не ошибаюсь, задача решается проще. Количество чисел определяется количеством слогаемых типа A, т. к. остальные будут равны B, т. е. от 0 до C, С + 1. Это конечно если А не равно В. Осталось доказать, что нельзя представить одно и тоже число 2 разными слагаемыми в таком же общем количестве двумя и более способами. Это сделать просто: если мы меняем сумму мы фактически только лишь уменьшаем количество слагаемых какого-либо типа, добавляя другого. Если меньшего слагаемого будет больше, чем было до, то сумма уменьшится и наоборот. Значит способов ровно С + 1, если только А не равно В.