Форум программистов, компьютерный форум, киберфорум
Наши страницы
Информатика
Войти
Регистрация
Восстановить пароль
 
Doublench
1 / 1 / 3
Регистрация: 05.07.2013
Сообщений: 176
#1

Найдите количество различных программ - Информатика

13.07.2013, 23:19. Просмотров 801. Ответов 2
Метки нет (Все метки)

Программы исполнителя:
1. умножить число на 5;
2. прибавить к числу 1.
Программа для исполнителя записывается как строка из цифр 1 и 2.
Найдите количество различных программ, которые позволяют из числа 1 получить число 101.

Как такое решить ? Ведь получается уйма различных вариантов ? Как подсчитать ? Или я чего не понял ...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2013, 23:19
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найдите количество различных программ (Информатика):

Найдите количество всех различных наборов из четырех четных чисел
"Найдите количество всех различных наборов из четырех четных чисел (int...

Найдите количество различных вариантов раскраски сторон правильного пятиугольника
Найдите количество различных вариантов раскраски сторон правильного...

В массиве найдите количество серий из четверок подряд идущих попарно различных элементов
В массиве найдите количество серий из четверок подряд идущих попарно различных...

Найти количество выполняющихся на ПК программ и количество пользовательских программ
Найти количество выполняющихся на ПК программ и количество пользовательских...

Самоустановка различных программ
Здравствуйте! В системе устанавливаются самостоятельно различные программы,...

Загрузка и установка различных программ, а также их запуск
Здравствуйте, уважаемые. Подцепил самый настоящий рассадник всего, о чём только...

2
кот Бегемот
Платежеспособный зверь
8447 / 3886 / 1511
Регистрация: 28.10.2009
Сообщений: 10,062
14.07.2013, 23:32 #2
Цитата Сообщение от Doublench Посмотреть сообщение
Программы исполнителя:
1. умножить число на 5;
2. прибавить к числу 1.
Программа для исполнителя записывается как строка из цифр 1 и 2.
Найдите количество различных программ, которые позволяют из числа 1 получить число 101.

Как такое решить ? Ведь получается уйма различных вариантов ? Как подсчитать ? Или я чего не понял ...
Эта задача решается с помощью динамического программирования. Легче всего это понять с помощью таблицы.
Нарисуем таблицу, в которой будет 2 строки и 101 столбец. В принципе, можно обойтись и меньшим количеством столбцов, это станет ясно позднее. Отметим для себя несколько постулатов:
1. Число 1 нам дано, следовательно мы получили его единственным способом.
2. Число, не делящееся на 5 можно получить только из предыдущего числа прибавлением единицы.
3. Число, делящееся на 5 можно получить из предыдущего числа и из числа, которое в 5 раз меньше.

А теперь начнём рисовать таблицу, в которой вверху будут числа от 1 до 101, а в нижней строке - количество способов их получения. Итак, число 1 получено единственным способом (постулат 1):
--------------------------
1|2|3|4|5|6|7|8|9|10|
--------------------------
1|_|_|_|_|_|_|_|_|__|
--------------------------
Число 2 может быть получено только из числа 1, а 1 получен единственным способом, значит, число 2 тоже получено единственным способом.
Аналогично, число 3 можно получить только из числа 2, которое получено единственным способом, значит, число 3 тоже получено единственным способом.
Ну, и 4, разумеется, тоже. Итак:
--------------------------
1|2|3|4|5|6|7|8|9|10|
--------------------------
1|1|1|1|_|_|_|_|_|__|
--------------------------

А вот число 5 можно получить и из числа 4, и из числа 1 (умножением на 5), складываем способы 1+1=2
Согласно постулату 2, числа 6,7, 8,9 также получены двумя способами, а вот 10 получаем одним способом из числа 2 и двумя способами из числа 9 (поскольку оно само получено двумя способами), значит, всего 3 способа.
--------------------------
1|2|3|4|5|6|7|8|9|10|
--------------------------
1|1|1|1|2|2|2|2|2|3_|
--------------------------

Очевидно, что дальше таблица будет заполняться аналогично, изменение будет только для чисел, кратных 5, поэтому сокращённая таблица будет иметь вид:
----------------------------------------------------------------------------------------
1|5|10|15|20|25|30|35|40|45|50|55|60|65|70|75|80|85|90|95|100|101|
----------------------------------------------------------------------------------------
1|2|3_|4_|5_|7_|9_|11|13|15|18|21|24|27|30|34|38|42|46|50|55_|55_|
----------------------------------------------------------------------------------------
Чтобы стало яснее, приведу пример для числа 75: 75 можно получить из 15, умножением на 5 (4 способа) и из 74 прибавлением единицы, но 74,73,72,71 получаются из 70 тридцатью способами, значит, 75 получаем 4+30=34 способа
1
Doublench
1 / 1 / 3
Регистрация: 05.07.2013
Сообщений: 176
15.07.2013, 13:48  [ТС] #3
спасибо. гениально.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.07.2013, 13:48
Привет! Вот еще темы с решениями:

Установка непонятных программ и появление различных вкладок
День добрый! Компьютер заметно начал притормаживать и ссылки в браузерах...

Разработка программ с чтением и записью файлов различных типов
Изменить программу (программа написана ниже), организовав чтение исходных...

Самопроизвольная установка различных программ и приложений от mail и Crossbrowser
Доброго времени суток! Прошу помощи знающих! Проблема в следующем: На...

Как защитит клавиатуру и мышь от блокировке, различных программ?
Как защитит клавиатуру и мышь от блокировке, различных программ? В одном...


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

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

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