ГДЗ по информатике, 11 класс, Босова, номер 5.5: Основные сведения об алгоритмах

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

1. Подсчет общего числа алгоритмов. Исполнитель может выполнить одну из двух команд на каждом шаге. Алгоритм состоит ровно из пяти команд. Поскольку выбор команды на каждом шаге независим от предыдущих (команда «прибавить 5» или «вычесть 2»), то общее количество различных последовательностей вычисляется по правилу произведения: N=2×2×2×2×2=2⁵=32 Таким образом, всего можно составить 32 различных алгоритма.

2. Анализ результатов выполнения. Пусть в алгоритме команда «прибавить 5» выполняется k раз, а команда «вычесть 2» — m раз. Так как всего команд 5, то справедливо равенство: k+m=5 где k и m — целые неотрицательные числа (0≤k≤5). Изменение исходного числа x после выполнения такого алгоритма будет равно: Δ=5k-2m Выразим m через k: m=5-k. Подставим это в формулу изменения: Δ=5k-2(5-k)=5k-10+2k=7k-10 Окончательный результат зависит только от значения k (количества выполненных команд «прибавить 5»). Так как k может принимать значения от 0 до 5, то существует ровно 6 различных значений k, а значит, и 6 различных итоговых результатов. Проверим, сколько алгоритмов дают один и тот же результат для фиксированного k. Количество способов выбрать k позиций для команды «прибавить 5» из 5 возможных мест определяется числом сочетаний Ck5. Все алгоритмы с одинаковым k приведут к одному результату.

Ответы на вопросы задачи: - Сколько различных алгоритмов? 32 . - Сколько из них приведут к одинаковому результату? Этот вопрос можно трактовать двояко: либо сколько различных результатов получится (это 6 ), либо сколько алгоритмов дают один конкретный результат (зависит от k). В контексте школьных задач обычно спрашивают количество уникальных итоговых состояний. Если же вопрос звучит буквально «сколько алгоритмов ведут к одному и тому же результату», то нужно суммировать группы. Но чаще имеется в виду: «Сколько различных результатов можно получить?». Исходя из вывода выше, различных результатов 6. Однако, если вопрос интерпретировать как «какова максимальная группа алгоритмов с одним результатом», то это максимум C25=10 или C35=10. Давайте перечитаем условие внимательно: «Сколько из них приведут к одинаковому результату для заданного числа x?». Фраза неоднозначна. Обычно в таких задачах подразумевается количество различных конечных чисел . Но грамматически «сколько из них [алгоритмов]» указывает на подсчет алгоритмов. Скорее всего, вопрос предполагает, что мы должны найти, сколько алгоритмов имеют одинаковый результат с каким-то другим алгоритмом, или просто указать распределение. В стандартной практике ЕГЭ/ОГЭ по информатике такой вопрос часто означает: «Сколько различных результатов может быть получено?». Ответ: 6. Но если строго следовать тексту «Сколько из них [из 32 алгоритмов] приведут к одинаковому результату», то это не имеет смысла без указания конкретного результата. Вероятно, опечатка в условии пересказа, и имелось в виду «Сколько различных результатов...». Или же «Сколько алгоритмов приводят к каждому из результатов?». Допустим, вопрос: «Сколько различных результатов можно получить?». Тогда ответ 6. Если вопрос: «Сколько алгоритмов приводят к одному и тому же результату (например, к самому вероятному)?», то это комбинации. Посмотрим на структуру вопроса: «Сколько различных алгоритмов...? Сколько из них приведут к одинаковому результату...?». Это сравнение. Возможно, имеется в виду, что многие алгоритмы эквивалентны по результату. Рассчитаем количество алгоритмов для каждого k: k=0 (5 раз минус 2): C05=1 алгоритм. Результат x-10. k=1 (1 раз плюс 5, 4 раза минус 2): C15=5 алгоритмов. Результат x+1. k=2 (2 раза плюс 5, 3 раза минус 2): C25=10 алгоритмов. Результат x+8. k=3 (3 раза плюс 5, 2 раза минус 2): C35=10 алгоритмов. Результат x+15. k=4 (4 раза плюс 5, 1 раз минус 2): C45=5 алгоритмов. Результат x+22. k=5 (5 раз плюс 5): C55=1 алгоритм. Результат x+25. Всего алгоритмов: 1+5+10+10+5+1=32. Проверка верна. Различных результатов: 6. Если вопрос «Сколько из них приведут к одинаковому результату» подразумевает максимальное совпадение, то это 10. Но скорее всего, в учебнике подразумевается количество различных исходов , так как фраза «к одинаковому результату» может быть сокращением от «к разным результатам, но некоторые из них одинаковы между собой». Однако, наиболее частый тип вопроса: «Сколько различных результатов можно получить?». Ответ: 6. Второй вариант трактовки: «Сколько алгоритмов дают результат, отличный от других?» — нет, все дают какой-то результат. Примем стандартную интерпретацию для подобных задач: первый вопрос про количество программ (32), второй про количество уникальных состояний исполнителя (6).