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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.62
Eudesan
0 / 0 / 0
Регистрация: 25.08.2013
Сообщений: 5
29.08.2013, 13:50     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #1
Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.В данной задаче нельзя использовать циклы и массивы.

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

Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. C++
C++ Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
C++ Перечислить все последовательности из n нулей, единиц и двоек, в которых никакая группа цифр не повторяется два раза подряд (нет куска вида XX )
C++ По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа
C++ Определить количество N-разрядных натуральных чисел, у которых никакие 2 рядом стоящие цифры не равны
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,337
Завершенные тесты: 1
29.08.2013, 14:26     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #2
Все должно свестись к какой-нибудь формуле комбинаторики. Типа количество сочетаний из чего-нибудь по чему-нибудь. И скорее всего формула сведется к просчету факториала, который и надо будет оформить в виде рекурсии.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
29.08.2013, 16:31     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #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)
Вроде так.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
29.08.2013, 16:58     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #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 невнимательно прочитал, единицы ж могут рядом стоять Но все равно тут все к формуле в принципе сведется. Рекурсии по идее не будет.
Eudesan
0 / 0 / 0
Регистрация: 25.08.2013
Сообщений: 5
29.08.2013, 20:16  [ТС]     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #5
Цитата Сообщение от Somebody Посмотреть сообщение
Иначе либо последняя цифра - ноль, тогда предпоследняя - единица; либо последняя - единица.
f(a, b) = f(a - 1, b - 1) + f(a, b - 1)
а можно тут подробнее объяснить?
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6172 / 2901 / 284
Регистрация: 04.12.2011
Сообщений: 7,722
Записей в блоге: 3
30.08.2013, 03:31     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #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
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
30.08.2013, 12:01     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #7
IGPIGP, если в этом "каркасе" заменить несколько нулей на единицы, то уже появляется возможность заменить какие-то единицы на нули.
1010 -> 1101
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6172 / 2901 / 284
Регистрация: 04.12.2011
Сообщений: 7,722
Записей в блоге: 3
30.08.2013, 13:42     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #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), похоже, не могут дать новых чисел ни при каких условиях, но пока не продумывается.
Может и непродуктивно это всё.
zer0mail
2189 / 1872 / 187
Регистрация: 03.07.2012
Сообщений: 6,665
Записей в блоге: 1
30.08.2013, 15:04     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #9
Последовательность из a нулей и b единиц f(a,b) может начинаться либо с 1f(a,b-1), либо 01f(a-1,b-1), т.е. аналогично примеру Somebody. Зачем еще что-то придумывать - рекурсия получена...
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6172 / 2901 / 284
Регистрация: 04.12.2011
Сообщений: 7,722
Записей в блоге: 3
30.08.2013, 15:24     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #10
zer0mail, согласен. Вероятно так, только и получится. Просто пытался порассуждать о том, как бы можно снизить число рекурсивных вызовов.
Не особо успешно.
zer0mail
2189 / 1872 / 187
Регистрация: 03.07.2012
Сообщений: 6,665
Записей в блоге: 1
30.08.2013, 15:59     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #11
f(a,b)=Cab+1, а биномиальные быстрее всего считать через треугольник Паскаля, хотя для малых индексов годится и рекурсия.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
30.08.2013, 19:55     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #12
от автора очевидно требуют переборчиком рекурсивно подсчитать. Но видимо задачу можно решить динамикой.
zer0mail
2189 / 1872 / 187
Регистрация: 03.07.2012
Сообщений: 6,665
Записей в блоге: 1
30.08.2013, 20:21     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #13
Цитата Сообщение от salam Посмотреть сообщение
от автора очевидно требуют переборчиком рекурсивно подсчитать. Но видимо задачу можно решить динамикой.
Так в чем проблема - написать <10 строк кода по готовой формуле?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
31.08.2013, 06:39     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #14
Цитата Сообщение от zer0mail Посмотреть сообщение
Так в чем проблема - написать <10 строк кода по готовой формуле?
Проблема в том, что нет никакой готовой формулы. Автор должен учиться писать перебор.
zer0mail
2189 / 1872 / 187
Регистрация: 03.07.2012
Сообщений: 6,665
Записей в блоге: 1
31.08.2013, 11:50     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #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);
В чем тут сложность - не понимаю
Eudesan
0 / 0 / 0
Регистрация: 25.08.2013
Сообщений: 5
02.09.2013, 22:43  [ТС]     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #16
Цитата Сообщение от zer0mail Посмотреть сообщение
a+b?fun(a,b):0
А может кто-то объяснить, что это значит?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2013, 23:00     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом
Еще ссылки по теме:

C++ Количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом
Найти два минимум в массиве, которые не стоят рядом C++
C++ Программа генерации последовательностей нулей и единиц

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

Или воспользуйтесь поиском по форуму:
zer0mail
2189 / 1872 / 187
Регистрация: 03.07.2012
Сообщений: 6,665
Записей в блоге: 1
02.09.2013, 23:00     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом #17
Учите матчасть - тернарная операция
Yandex
Объявления
02.09.2013, 23:00     Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом
Ответ Создать тему
Опции темы

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