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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
17.12.2013, 20:44     Найти количество различных чисел, которые можно получить из числа ровно за C команд #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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), или подсказать идею решения, если у меня уж в корне неправильно
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2013, 20:44     Найти количество различных чисел, которые можно получить из числа ровно за C команд
Посмотрите здесь:

Дана последовательность чисел. Найти количество различных чисел в этой последовательности C++
Дана последовательность чисел. Найти количество различных чисел в этой последовательности C++
Найти количество различных чисел C++
Количество различных рациональных чисел которые можно получить роставляя скобки C++
C++ В строке найти количество слов, которые содержат ровно три буквы «А»
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vitecd
18 / 1 / 0
Регистрация: 26.09.2013
Сообщений: 59
18.12.2013, 04:23     Найти количество различных чисел, которые можно получить из числа ровно за C команд #2
т.е. она у тебя еще и рекурсивная...

хоть убей - не понял, в чем суть задачи? я понимаю, что тебе "надо", но зачем? алгоритм не понятен
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
18.12.2013, 19:25  [ТС]     Найти количество различных чисел, которые можно получить из числа ровно за C команд #3
Я вчера затупил. Очень
Задача-елементарщина
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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;
}
Max_17
Сообщений: n/a
03.07.2014, 20:06     Найти количество различных чисел, которые можно получить из числа ровно за C команд #4
Если я не ошибаюсь, задача решается проще. Количество чисел определяется количеством слогаемых типа A, т. к. остальные будут равны B, т. е. от 0 до C, С + 1. Это конечно если А не равно В. Осталось доказать, что нельзя представить одно и тоже число 2 разными слагаемыми в таком же общем количестве двумя и более способами. Это сделать просто: если мы меняем сумму мы фактически только лишь уменьшаем количество слагаемых какого-либо типа, добавляя другого. Если меньшего слагаемого будет больше, чем было до, то сумма уменьшится и наоборот. Значит способов ровно С + 1, если только А не равно В.
Yandex
Объявления
03.07.2014, 20:06     Найти количество различных чисел, которые можно получить из числа ровно за C команд
Ответ Создать тему
Опции темы

Текущее время: 11:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru