ГДЗ Информатика 6 класс Семёнов, номер 80

№

Дерево команд Удвоителя

Найди все возможные варианты чисел, которые могут быть отображены на экране Удвоителя после выполнения им не больше 5 команд из начального положения «1». Для решения построй дерево перебора вариантов. Пользуясь построенным деревом, найди все числа второго десятка, которые нельзя получить на экране Удвоителя не больше чем за 5 команд.

Решение

По системе команд Удвоителя из любого числа x есть две ветви: прибавь даёт , а умножь на даёт . Корень дерева — начальное число . Строим пять уровней команд. Первое разветвление даёт два одинаковых числа , потому что и .

Полное дерево пяти команд с названиями ветвей:


├─ + → 
│  ├─ + → 
│  │  ├─ + → 
│  │  │  ├─ + → 
│  │  │  │  ├─ + → 
│  │  │  │  └─ × → 
│  │  │  └─ × → 
│  │  │     ├─ + → 
│  │  │     └─ × → 
│  │  └─ × → 
│  │     ├─ + → 
│  │     │  ├─ + → 
│  │     │  └─ × → 
│  │     └─ × → 
│  │        ├─ + → 
│  │        └─ × → 
│  └─ × → 
│     ├─ + → 
│     │  ├─ + → 
│     │  │  ├─ + → 
│     │  │  └─ × → 
│     │  └─ × → 
│     │     ├─ + → 
│     │     └─ × → 
│     └─ × → 
│        ├─ + → 
│        │  ├─ + → 
│        │  └─ × → 
│        └─ × → 
│           ├─ + → 
│           └─ × → 
└─ × → 
   ├─ + → 
   │  ├─ + → 
   │  │  ├─ + → 
   │  │  │  ├─ + → 
   │  │  │  └─ × → 
   │  │  └─ × → 
   │  │     ├─ + → 
   │  │     └─ × → 
   │  └─ × → 
   │     ├─ + → 
   │     │  ├─ + → 
   │     │  └─ × → 
   │     └─ × → 
   │        ├─ + → 
   │        └─ × → 
   └─ × → 
      ├─ + → 
      │  ├─ + → 
      │  │  ├─ + → 
      │  │  └─ × → 
      │  └─ × → 
      │     ├─ + → 
      │     └─ × → 
      └─ × → 
         ├─ + → 
         │  ├─ + → 
         │  └─ × → 
         └─ × → 
            ├─ + → 
            └─ × →

На каждом следующем уровне от каждого элемента снова проведены эти две ветви. Например, из получаем и , из — и . Одинаковые числа на одном уровне имеют одинаковые продолжения, поэтому в таблице записываем их один раз, не теряя возможных результатов.

Число выполненных команд	Различные числа на этом уровне дерева


	,
	, , ,
	, , , , , , ,
	, , , , , , , , , , , , , ,

«Не больше пяти» означает, что берём результаты всех уровней от нулевого до пятого. Получаем числа –, –, , , .

Во втором десятке находятся числа от до . Из них встречаются , , , , , , , . Числа и отсутствуют на всех рассмотренных уровнях. Поскольку каждый вариант команды включён в дерево, получить их за пять или меньше команд нельзя.

Ответ

✓ dzmen.ru

Возможные числа: , , , , , , , , , , , , , , , , , , , .

Числа второго десятка, которые нельзя получить не больше чем за команд: и .

Помогло?

Номер 80 ГДЗ Информатика 6 класс, Семёнов 2022, страница 49