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

задача на рекурсию в си++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
gigas
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
30.11.2012, 01:22     задача на рекурсию в си++ #1
Даны числа a и b. Определите, сколько существует последовательностей из
a нулей и b единиц, в которых никакие два нуля не стоят рядом.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.11.2012, 01:22     задача на рекурсию в си++
Посмотрите здесь:

C++ Задача на рекурсию
Задача на рекурсию C++
C++ Задача на рекурсию
Задача на рекурсию C++
C++ Задача на рекурсию
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
activnaya
 Аватар для activnaya
255 / 45 / 2
Регистрация: 24.11.2012
Сообщений: 466
30.11.2012, 01:28     задача на рекурсию в си++ #2
ну по крайней мере сразу с уверенностью можно сказать, что если b - a > 1, то ни одной.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.11.2012, 06:35     задача на рекурсию в си++ #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
#define N 51 
int t[N];
int rec(int a, int b, int l, int n)
{
    if(l>n)
        return 1;
    if(t[l-1]==0)
    {
        if(b==0)
            return 0;
        t[l]=1;
        return rec(a, b-1, l+1, n);
    }
    else
    {
        int tmp=0;
        if(a>0)
        {
            t[l]=0;
            tmp+=rec(a-1, b, l+1, n);
        }
        if(b>0)
        {
            t[l]=1;
            tmp+=rec(a, b-1, l+1, n);
        }
        return tmp;     
    }
}
int main(){
    int a, b;
    cin>>a>>b;
    t[0]=1;
    cout<<rec(a,b,1,a+b)<<endl;
    return 0;
 }
работает при a+b<=50
gigas
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
30.11.2012, 19:04  [ТС]     задача на рекурсию в си++ #4
Спасибо большое, но есть одно не понятное, почему когда программа компилируется, и пытаешься ввести значения, то программа прекращается и выкидывает из неё?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.12.2012, 00:03     задача на рекурсию в си++ #5
Цитата Сообщение от gigas Посмотреть сообщение
Спасибо большое, но есть одно не понятное, почему когда программа компилируется, и пытаешься ввести значения, то программа прекращается и выкидывает из неё?
Тогда у меня вопросы:
Программа компилируется?
Какие значения вводите, когда программа прекращается и выкидывает из неё?
dikanev
21 / 21 / 1
Регистрация: 28.05.2010
Сообщений: 67
01.12.2012, 01:15     задача на рекурсию в си++ #6
Чтобы нули не стояли рядом, нужно между ними расставить по единице. Если b < a-1, то единиц не хватит и сразу выводим 0. Иначе, остается b - a + 1 единица, которые мы можем произвольно раскидать по а+1 позициям. Пусть p[1], ..., p[a+1] - количество единиц в каждой позиции. Нас интересует число решений уравнения

p[1]+...+p[a+1] = b-a+1

где p целые неотрицательные числа. Такие решения называются композициями целого числа n = b-a+1 длиной k = a+1. Из комбинаторики известно, что число таких композиций равно числу сочетаний из n+k-1 = b+1 по k-1 = a и составляет, таким образом,

N = (b+1)!/(a!*(b-a+1)!)

А рекурсию используй для вычисления факториала
gigas
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
01.12.2012, 13:25  [ТС]     задача на рекурсию в си++ #7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Тогда у меня вопросы:
Программа компилируется?
Какие значения вводите, когда программа прекращается и выкидывает из неё?
она компилируется! запускаешь программу и пытаясь хоть что то ввести она прекращается
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
01.12.2012, 13:29     задача на рекурсию в си++ #8
Цитата Сообщение от gigas Посмотреть сообщение
она компилируется! запускаешь программу и пытаясь хоть что то ввести она прекращается
пропишите в конце System("Pause");
gigas
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
01.12.2012, 14:57  [ТС]     задача на рекурсию в си++ #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Тогда у меня вопросы:
Программа компилируется?
Какие значения вводите, когда программа прекращается и выкидывает из неё?
значения вводишь первое либо 1 либо 0, а второе значение больше 99 уже прерывается

Добавлено через 16 минут
Цитата Сообщение от dikanev Посмотреть сообщение
Чтобы нули не стояли рядом, нужно между ними расставить по единице. Если b < a-1, то единиц не хватит и сразу выводим 0. Иначе, остается b - a + 1 единица, которые мы можем произвольно раскидать по а+1 позициям. Пусть p[1], ..., p[a+1] - количество единиц в каждой позиции. Нас интересует число решений уравнения

p[1]+...+p[a+1] = b-a+1

где p целые неотрицательные числа. Такие решения называются композициями целого числа n = b-a+1 длиной k = a+1. Из комбинаторики известно, что число таких композиций равно числу сочетаний из n+k-1 = b+1 по k-1 = a и составляет, таким образом,

N = (b+1)!/(a!*(b-a+1)!)

А рекурсию используй для вычисления факториала
я в си++ новичок , поэтому изъясните пожалуйста попонятней!

Добавлено через 15 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
C++
1
2
3
4
5
#include <iostream>
using namespace std;
#define N 51 
....
 }
работает при a+b<=50
а можно понять смысл работы программы?
BumerangSP
01.12.2012, 15:04
  #10
 Комментарий модератора 
gigas, не нужно дублировать тему для того, чтобы уточнить, что Вам нужно " с компилятором dev-c++"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.12.2012, 15:21     задача на рекурсию в си++
Еще ссылки по теме:

Задача на рекурсию C++
Задача на рекурсию C++
Задача на рекурсию C++

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

Или воспользуйтесь поиском по форуму:
gigas
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
01.12.2012, 15:21  [ТС]     задача на рекурсию в си++ #11
Ребят спасибо всем большое, я разобрался)
Yandex
Объявления
01.12.2012, 15:21     задача на рекурсию в си++
Ответ Создать тему
Опции темы

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