2 / 2 / 0
Регистрация: 14.02.2013
Сообщений: 145
1

Подсчитать количество возможных вариантов формирования взрывоопасной стопки

19.12.2015, 17:15. Показов 4113. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа A — особо опасные и типа B — неопасные. Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку (один над другим) для захоронения. Стопка является взрывоопасной, если в ней подряд идут более чем два контейнера с отходами типа A.

Требуется написать программу, которая подсчитывает количество возможных вариантов формирования взрывоопасной стопки для заданного числа контейнеров N.
Нашел в интернете это:
F(i,0) = F(i-1,0)+F(i-1,1)
F(i,1) = F(i-1,0)
F(0,0) = 1
F(0,1) = 0

Ответ = 2^N-F(N,0)-F(N,1)
Но что-то не понимаю.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.12.2015, 17:15
Ответы с готовыми решениями:

Вывести количество безопасных вариантов формирования стопки из N контейнеров
При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A),...

Подсчет количества возможных вариантов формирования массива по условию
Всем привет! Нужна помощь. Вот задание: На одном из секретных заводов осуществляется обработка...

Сколько существует всех возможных вариантов формирования подгрупп?
Группу из 16 студентов должны разбить на подгруппы для работы в разных компьютерных классах....

Количество возможных вариантов и ребус
Прошу помощи 1)Перед фермером стоит задача: купить на 100 рублей 100 голов скота. Стоимость быка...

4
2 / 2 / 0
Регистрация: 14.02.2013
Сообщений: 145
23.12.2015, 12:57  [ТС] 2
Если начать считать самому видятся числа Фибоначчи для N=3 k=5 для N=4 k=8 для N=5 k=13
0
Mental handicap
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
23.12.2015, 17:59 3
Двоичное представление чисел.
B — это 0
A — это 1
0
2 / 2 / 0
Регистрация: 14.02.2013
Сообщений: 145
28.12.2015, 11:32  [ТС] 4
F(i,0) = F(i-1,0)+F(i-1,1)
F(i,1) = F(i-1,0)
F(0,0) = 1
F(0,1) = 0
Ну а это как тогда понимать что за параметры такие у функции.
0
Платежеспособный зверь
8915 / 4345 / 1639
Регистрация: 28.10.2009
Сообщений: 11,541
28.12.2015, 11:56 5
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Это классическая задача на динамическое программирование. Я помню, лет 15 назад она была на региональной олимпиаде школьников.
Вот некоторые соображения, умному достаточно, а дуракам нет смысла браться за эту задачу.


Будем искать число опасных стопок для произвольного N. Сложность в том, что стопки сами по себе разные. Разобьем их на 4 класса:
Тип 1 - опасные, содержат три или более контейнера A подряд.
Тип 2 - не опасны, но наверху лежат два контейнера А.
Тип 3 - не опасны, но наверху лежат один контейнер А (а под ним, если есть, B).
Тип 4 - не опасны, с контейнером B наверху.

Теперь перейдем к стопкам размером N + 1. Каждая стопка из рассмотренных ранее классов породит 2 стопки, причем несложные логические рассуждения (возьмите карандаш) показывают, что:
из стопки 1-го класса получится 2 стопки 1-го класса;
из стопки 2-го класса получится по стопке 1-го и 4-го класса;
из стопки 3-го класса получится по стопке 2-го и 4-го класса;
из стопки 4-го класса получится по стопке 3-го и 4-го класса;

Теперь о граничных (вообще-то, для итеративных схем лучше говорить "о начальных") условиях. Их можно написать как для N = 1 (по одной стопке типа 3 и 4), так и для N = 0 (одна стопка типа 4 - собственно, стопок нет вообще). Заметим, что нам достаточно знать количества стопок высоты на единицу меньшей текущей. После этого решение становится совсем простым.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.12.2015, 11:56
Помогаю со студенческими работами здесь

Рассчитать количество возможных вариантов комбинаций
Здравствуйте, вот никак не могу додуматься как решать такую интересную задачку. Допустим есть...

Количество возможных вариантов комбинаций множества из N элементов
Как определить количество возможных вариантов комбинаций множества N элементов (порядок расстановки...

Как посчитать общее количество возможных вариантов игр?
Всем привет! Помогите решить такую задачу. Есть 15 футбольных матчей, в которых бывает 3 исхода -...

Определить количество всех возможных вариантов обувания 80 ног
Добрый день. Дана такая задача (текста задания нету, пересказываю словесно): у сороконожки 40...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru