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

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

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

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

17.12.2013, 20:44. Просмотров 1276. Ответов 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++
C++ В строке найти количество слов, которые содержат ровно три буквы «А»
C++ Алгебра: Есть массив чисел и число f, надо определить, можно ли получить f, складывая любое количество чисел из массива
C++ В первую строку выходного файла выведите ровно N различных целых чисел
Найти количество различных цифр данного натурального числа C++
Найти сколько различных трехзначных чисел можно получить из заданного числа n путем вычеркивания цифр C++
Найти все числа, которые можно представить в виде суммы квадратов двух натуральных чисел C++
Найти числа, изменяя которые по заданному правилу можно в итоге получить ноль C++
C++ Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города
Нужно найти числа которые являются произведением K различных простых множителей , k<7 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 команд
Ответ Создать тему
Опции темы

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