Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.62
Eudesan
0 / 0 / 0
Регистрация: 25.08.2013
Сообщений: 5
#1

Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом - C++

29.08.2013, 13:50. Просмотров 3856. Ответов 16
Метки нет (Все метки)

Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.В данной задаче нельзя использовать циклы и массивы.

Сложность в том, что не могу даже продумать алгоритм решения. Думал, может попробовать перебирать двоичные числа от ("b-единиц"+"a-нулей") до нуля. тогда в них надо пересчитывать количество нулей и единиц, а те, которые удовлетворят условию проверить на отсутствие двух нулей рядом... но что-то мне моя задумка не очень нравится
В общем буду благодарен за совет по алгоритму или рабочий код
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2013, 13:50
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом (C++):

Количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом - C++
http://informatics.mccme.ru/mod/statements/view.php?id=654#1 #include <iostream> using namespace std; int main() { int n; ...

Программа генерации последовательностей нулей и единиц - C++
помогите пожалуйста написать программу генерации m-последовательностей 0 и 1, удовлетворяющих обоим требованиям: 1) никакие 3 единицы не...

Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) - C++
Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида...

Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX ) - C++
Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида...

Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. - C++
Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. Запись натурального...

Подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом - Pascal
(Ссылка на сторонний ресурс удалена) Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие...

16
SatanaXIII
Супер-модератор
Эксперт С++
5689 / 2744 / 258
Регистрация: 01.11.2011
Сообщений: 6,699
Завершенные тесты: 1
29.08.2013, 14:26 #2
Все должно свестись к какой-нибудь формуле комбинаторики. Типа количество сочетаний из чего-нибудь по чему-нибудь. И скорее всего формула сведется к просчету факториала, который и надо будет оформить в виде рекурсии.
2
Somebody
2798 / 1609 / 149
Регистрация: 03.12.2007
Сообщений: 4,204
Завершенные тесты: 3
29.08.2013, 16:31 #3
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если все единицы:
f(0, b) = 1
Если один ноль, остальные единицы:
f(1, b) = b + 1
Если больше одного нуля и нет единиц:
f(>1, 0) = 0
Иначе либо последняя цифра - ноль, тогда предпоследняя - единица; либо последняя - единица.
f(a, b) = f(a - 1, b - 1) + f(a, b - 1)
Вроде так.
3
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
29.08.2013, 16:58 #4
Цитата Сообщение от Eudesan Посмотреть сообщение
Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.В данной задаче нельзя использовать циклы и массивы.

Сложность в том, что не могу даже продумать алгоритм решения. Думал, может попробовать перебирать двоичные числа от ("b-единиц"+"a-нулей") до нуля. тогда в них надо пересчитывать количество нулей и единиц, а те, которые удовлетворят условию проверить на отсутствие двух нулей рядом... но что-то мне моя задумка не очень нравится
В общем буду благодарен за совет по алгоритму или рабочий код
Так а зачем что-то перебирать?
C++
1
2
3
4
5
6
7
if (abs(a-b)==1) 
  c=1;
else
  if (a==b)
    c=2;
  else
    c=0;
UPD невнимательно прочитал, единицы ж могут рядом стоять Но все равно тут все к формуле в принципе сведется. Рекурсии по идее не будет.
1
Eudesan
0 / 0 / 0
Регистрация: 25.08.2013
Сообщений: 5
29.08.2013, 20:16  [ТС] #5
Цитата Сообщение от Somebody Посмотреть сообщение
Иначе либо последняя цифра - ноль, тогда предпоследняя - единица; либо последняя - единица.
f(a, b) = f(a - 1, b - 1) + f(a, b - 1)
а можно тут подробнее объяснить?
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6955 / 3238 / 322
Регистрация: 04.12.2011
Сообщений: 8,934
Записей в блоге: 5
30.08.2013, 03:31 #6
Мне вот что в голову пришло. Пусть есть a и b, нулей и единиц соответственно. Размер записи: n = a + b.
Подсчитаем максимально возможное количество нулей Z в записи n.
Максимальное количество нулей равно Z = n/2 если не учитывать записи с ведущим нулём. Деление - нацело.
Вероятно записи с ведущим нулём учитывать не стоит, но как бы мы не решили, Z у нас получится и это значит, что количество единиц в "разреженной" записи минимум E= n-Z.
В такой записи представлено одно единственно возможное число, так как перестановка любой 1-цы возможна лишь на место другой 1-цы (они меняются местами) и нового числа не получается.
В случае если n>b>E у нас получается p = b - E = b+Z-n = Z -a единиц сверх E требуемых для построения "разреженного" каркаса. И их размещение в Z нулевых позициях не учитывая повторений, вроде как:
http://www.cyberforum.ru/cgi-bin/latex.cgi?A = C_z ^p
1
Somebody
2798 / 1609 / 149
Регистрация: 03.12.2007
Сообщений: 4,204
Завершенные тесты: 3
30.08.2013, 12:01 #7
IGPIGP, если в этом "каркасе" заменить несколько нулей на единицы, то уже появляется возможность заменить какие-то единицы на нули.
1010 -> 1101
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6955 / 3238 / 322
Регистрация: 04.12.2011
Сообщений: 8,934
Записей в блоге: 5
30.08.2013, 13:42 #8
Цитата Сообщение от Somebody Посмотреть сообщение
IGPIGP, если в этом "каркасе" заменить несколько нулей на единицы, то уже появляется возможность заменить какие-то единицы на нули.
1010 -> 1101
Да. Сыровато получилось.
Особенно самая последняя формула.
Тем не менее, именно каркас для четных чисел и есть пока главная ценность представленной идеи. Плохо, что к чистой рекурсии, он приводит только для чисел c длиной вида 2^n
Смотрите, только в четном числе каркас однозначен. Например в записи:
10101010
нельзя сдвинуть ни одну единицу. Но тогда для числа:
11111101 a=1, b=7 на этом каркасе (10101010)
получаем вопрос: сколько можно построить чисел из 7-4=3 единиц (избытка над каркасом) на 4-х нулях (свободных нулях каркаса)
И для чисел длина которых 2^n , можно делить пока есть свободные единицы.
Для нечётных всё сложнее. Пока удалось додуматься, что для записи длиной n = 2k+1 можно построить k+1 каркасов. То есть не один:
для 3 -> 2
101
110
для 5 -> 3
10101
10110
11010
для 7 -> 4
...
Далее еще видно, что каждый каркас нечётного, можно получить из каркаса предыдущего чётного, приписав в конце 1 или записав 1 рядом с существующей (с любой стороны но один раз)). Отсюда и k+1. Пока не вижу как построить рекурсивную цепь рассуждений. Четность и нечётность может быть встречена, на каждом шаге, при снижении длины записи, в любой последовательности.
Ещё интересно, что некоторые каркасы (нечётных n), похоже, не могут дать новых чисел ни при каких условиях, но пока не продумывается.
Может и непродуктивно это всё.
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,559
Записей в блоге: 1
30.08.2013, 15:04 #9
Последовательность из a нулей и b единиц f(a,b) может начинаться либо с 1f(a,b-1), либо 01f(a-1,b-1), т.е. аналогично примеру Somebody. Зачем еще что-то придумывать - рекурсия получена...
2
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6955 / 3238 / 322
Регистрация: 04.12.2011
Сообщений: 8,934
Записей в блоге: 5
30.08.2013, 15:24 #10
zer0mail, согласен. Вероятно так, только и получится. Просто пытался порассуждать о том, как бы можно снизить число рекурсивных вызовов.
Не особо успешно.
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,559
Записей в блоге: 1
30.08.2013, 15:59 #11
f(a,b)=Cab+1, а биномиальные быстрее всего считать через треугольник Паскаля, хотя для малых индексов годится и рекурсия.
0
salam
174 / 155 / 17
Регистрация: 10.07.2012
Сообщений: 762
30.08.2013, 19:55 #12
от автора очевидно требуют переборчиком рекурсивно подсчитать. Но видимо задачу можно решить динамикой.
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,559
Записей в блоге: 1
30.08.2013, 20:21 #13
Цитата Сообщение от salam Посмотреть сообщение
от автора очевидно требуют переборчиком рекурсивно подсчитать. Но видимо задачу можно решить динамикой.
Так в чем проблема - написать <10 строк кода по готовой формуле?
0
salam
174 / 155 / 17
Регистрация: 10.07.2012
Сообщений: 762
31.08.2013, 06:39 #14
Цитата Сообщение от zer0mail Посмотреть сообщение
Так в чем проблема - написать <10 строк кода по готовой формуле?
Проблема в том, что нет никакой готовой формулы. Автор должен учиться писать перебор.
0
zer0mail
2447 / 2081 / 205
Регистрация: 03.07.2012
Сообщений: 7,559
Записей в блоге: 1
31.08.2013, 11:50 #15
Вы че это: "нет готовой формулы", "чего-нибудь", "скорее всего"
C++
1
2
3
4
5
6
7
8
int fun(int a,int b) {
    if (a> b+1) return 0;
    if (a==0 || b==0) return 1;
    return fun(a,b-1)+fun(a-1,b-1);
}
main()
...
cout<<(a+b?fun(a,b):0);
В чем тут сложность - не понимаю
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.08.2013, 11:50
Привет! Вот еще темы с ответами:

Сколько существует перестановок из n элементов, в которых 2 элемента не стоят рядом - Дискретная математика
Сколько существует перестановок из n элементов, в которых 2 элемента не стоят рядом.

Определите количество N-разрядных натуральных чисел, у которых никакие 2 рядом стоящие цифры не равны - Алгебра
Доброго всем времени суток! Прошу меня простить, если я неверно выбрал раздел. Просто пошлите меня, куда нужно :) Теперь по теме....

Выясните, стоят ли в матрице два нуля рядом по горизонтали или вертикали - Turbo Pascal
Помогите решить Двумерный массив n на n заполнен 0,1 и 2. Выясните, стоят ли в нем два нуля рядом по горизонтали или вертикали

сколько существует N-битовых строк,содержащих A нулей и К единиц,если - Логика и множества
сколько существует N-битовых строк,содержащих A нулей и К единиц,если: N=10,A=4,K=6


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

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

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