Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
1

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

30.11.2012, 01:22. Просмотров 1768. Ответов 10
Метки нет (Все метки)

Даны числа a и b. Определите, сколько существует последовательностей из
a нулей и b единиц, в которых никакие два нуля не стоят рядом.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.11.2012, 01:22
Ответы с готовыми решениями:

Задача на рекурсию
Помогите решить след. задачу: Вот мой вариант, но здесь не сохраняется порядок: void Func()...

Задача на рекурсию
Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них....

Задача на рекурсию
const n=...; type vector = array of real; Описать рекурсивную функцию max (x) для определения...

Задача на рекурсию
Нашел одну задачу, она по моему на рекурсию, но не могу реализовать это. Сколько существует...

10
256 / 46 / 4
Регистрация: 24.11.2012
Сообщений: 466
30.11.2012, 01:28 2
ну по крайней мере сразу с уверенностью можно сказать, что если b - a > 1, то ни одной.
0
Эксперт С++
4703 / 2528 / 753
Регистрация: 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
1
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
30.11.2012, 19:04  [ТС] 4
Спасибо большое, но есть одно не понятное, почему когда программа компилируется, и пытаешься ввести значения, то программа прекращается и выкидывает из неё?
0
Эксперт С++
4703 / 2528 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
01.12.2012, 00:03 5
Цитата Сообщение от gigas Посмотреть сообщение
Спасибо большое, но есть одно не понятное, почему когда программа компилируется, и пытаешься ввести значения, то программа прекращается и выкидывает из неё?
Тогда у меня вопросы:
Программа компилируется?
Какие значения вводите, когда программа прекращается и выкидывает из неё?
1
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)!)

А рекурсию используй для вычисления факториала
1
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
01.12.2012, 13:25  [ТС] 7
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Тогда у меня вопросы:
Программа компилируется?
Какие значения вводите, когда программа прекращается и выкидывает из неё?
она компилируется! запускаешь программу и пытаясь хоть что то ввести она прекращается
0
1306 / 968 / 267
Регистрация: 17.05.2012
Сообщений: 2,687
01.12.2012, 13:29 8
Цитата Сообщение от gigas Посмотреть сообщение
она компилируется! запускаешь программу и пытаясь хоть что то ввести она прекращается
пропишите в конце System("Pause");
0
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
а можно понять смысл работы программы?
0
BumerangSP
01.12.2012, 15:04
  #10
 Комментарий модератора 
gigas, не нужно дублировать тему для того, чтобы уточнить, что Вам нужно " с компилятором dev-c++"
1
7 / 1 / 1
Регистрация: 30.11.2012
Сообщений: 91
01.12.2012, 15:21  [ТС] 11
Ребят спасибо всем большое, я разобрался)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.12.2012, 15:21

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

Задача на рекурсию
Помогите пожалуйста. Есть задача: Дана последовательность a с элементами из множества {0,1}....

Задача на рекурсию
Доброго времени суток. Прошу помощи в решении поставленной задачи Описать функцию Max1 (x),...

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

Задача на рекурсию
посажена картошка: 30 рядков по 20 лунок в каждом. 1. Смоделировать картофельное поле, зная, что...


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

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

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