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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
#1

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

17.12.2013, 20:44. Просмотров 1291. Ответов 3
Метки нет (Все метки)

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++
Обозначим i-е простое число как Рi (Р1=2, Р2=3, Р3=5 и т.д.). Для данного числа n рассмотрим выражение: Р1 / Р2 / Р3 / ... / Рn. Напишите...

Найти сколько различных трехзначных чисел можно получить из заданного числа n путем вычеркивания цифр - C++
Задача: найти сколько различных трехзначных чисел можно получить из заданного числа n путем вычеркивания цифр? Я придумал такое: ...

Найти числа, изменяя которые по заданному правилу можно в итоге получить ноль - C++
1.Игрок А объявляет двузначное число от 01 до 99. Игрок В меняет местами его цифры и прибавляет полученное число к сумме его цифр....

В строке найти количество слов, которые содержат ровно три буквы «А» - C++
Дана строка, состоящая из русских слов, набранных заглавными буквами и разделенных пробелами (одним или несколькими). Найти количество...

Найти все числа, которые можно представить в виде суммы квадратов двух натуральных чисел - C++
Дано натуральное число N. Среди чисел 1,2,...,N найти все те, которые можно представить в виде суммы квадратов двух натуральных чисел....

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

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

хоть убей - не понял, в чем суть задачи? я понимаю, что тебе "надо", но зачем? алгоритм не понятен
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
18.12.2013, 19:25  [ТС] #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 #4
Если я не ошибаюсь, задача решается проще. Количество чисел определяется количеством слогаемых типа A, т. к. остальные будут равны B, т. е. от 0 до C, С + 1. Это конечно если А не равно В. Осталось доказать, что нельзя представить одно и тоже число 2 разными слагаемыми в таком же общем количестве двумя и более способами. Это сделать просто: если мы меняем сумму мы фактически только лишь уменьшаем количество слагаемых какого-либо типа, добавляя другого. Если меньшего слагаемого будет больше, чем было до, то сумма уменьшится и наоборот. Значит способов ровно С + 1, если только А не равно В.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2014, 20:06
Привет! Вот еще темы с ответами:

Дана последовательность чисел. Найти количество различных чисел в этой последовательности - C++
Дана последовательность чисел. Найти количество различных чисел в этой последовательности Дана последовательность чисел. Найти...

Нужно найти числа которые являются произведением K различных простых множителей , k<7 - C++
Помогите пожалуйста решить задачу:Нужно найти числа которые являются произведением K различных простых множителей , k&lt;7 .Или хотя бы...

Найти количество различных чисел - C++
Найти количество различных чисел среди элементов данного массива. Рекомендации: Отсортировать числа, а затем посчитать количество...

Дана строка, состоящая из русских слов. Найти количество слов, которые содержат ровно три буквы «А» - C++
Дана строка, состоящая из русских слов, набранных заглавными буквами и разделенных пробелами (одним или несколькими). Найти количество...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.07.2014, 20:06
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru