Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
25 / 25 / 5
Регистрация: 21.11.2013
Сообщений: 208
1

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

17.12.2013, 20:44. Просмотров 1967. Ответов 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), или подсказать идею решения, если у меня уж в корне неправильно
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.12.2013, 20:44
Ответы с готовыми решениями:

Количество различных рациональных чисел которые можно получить роставляя скобки
Обозначим i-е простое число как Рi (Р1=2, Р2=3, Р3=5 и т.д.). Для данного числа n рассмотрим...

Определить количество всех различных 3-х значных чисел, которые можно составить из цифр данного числа
Дано 3-х значное число, определить количество всех различных 3-х значных чисел, которые можно...

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

Найти всевозможные комбинации чисел, которые можно получить из одного числа
Здравствуйте , собственно суть задачи: Надо написать программу которая находит все возможные...

3
18 / 1 / 0
Регистрация: 26.09.2013
Сообщений: 59
18.12.2013, 04:23 2
т.е. она у тебя еще и рекурсивная...

хоть убей - не понял, в чем суть задачи? я понимаю, что тебе "надо", но зачем? алгоритм не понятен
0
25 / 25 / 5
Регистрация: 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;
}
0
Max_17
03.07.2014, 20:06 4
Если я не ошибаюсь, задача решается проще. Количество чисел определяется количеством слогаемых типа A, т. к. остальные будут равны B, т. е. от 0 до C, С + 1. Это конечно если А не равно В. Осталось доказать, что нельзя представить одно и тоже число 2 разными слагаемыми в таком же общем количестве двумя и более способами. Это сделать просто: если мы меняем сумму мы фактически только лишь уменьшаем количество слагаемых какого-либо типа, добавляя другого. Если меньшего слагаемого будет больше, чем было до, то сумма уменьшится и наоборот. Значит способов ровно С + 1, если только А не равно В.
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.07.2014, 20:06

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

Найти количество целых положительных чисел от 200 до 9000, которые делятся ровно из чисел 16,18,15
5. Найти количество целых положительных чисел от 200 до 9000, которые делятся ровно из чисел...

Найдите все числа от 1 до n, которые можно получить суммой различных степеней тройки
Помогите пожалуйста) Найдите все числа от 1 до n, которые можно получить суммой различных ...

Найти количество слов, которые можно составить из пяти различных букв
Чему равна сумма полинимиальных коэффициентов, если есть 5 различных символов и длина не должна...

Определить количество различных чисел, которое можно составить из цифр данного числа
Вводится трёхзначное число. Определить количество различных чисел, которое можно составить из цифр...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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