ГДЗ: Параграф § 2.4 / Информатика 9 класс

Табличные модели обеспечивают следующие преимущества:

• Наглядность: Информация структурирована и легко обозрима.
• Компактность: Большой объем данных представлен в сжатом виде.
• Упорядоченность: Четкая организация данных упрощает их анализ.

Пример: Расписание движения автобусов удобнее и быстрее воспринимается в виде таблицы (время отправления, платформа), чем в виде сплошного текста.

• На уроках в школе: Расписание занятий, таблица успеваемости (Таблица 2.2), периодическая таблица химических элементов, таблицы данных в учебниках (Таблица 2.1).
• В повседневной жизни: Расписание движения поездов или самолетов, таблица расстояний между городами (Таблица 2.3), меню в ресторане, счет за коммунальные услуги.

Весовая матрица — это частный случай таблицы «объект — объект», используемый для представления взвешенного графа. В ней:

• В ячейках указывается численное значение (вес), которое обозначает протяженность или стоимость связи (ребра) между двумя объектами (вершинами).
• Обычная таблица «объект — объект» может содержать как численные, так и качественные данные о связи.

Наличие или отсутствие связи (качественное свойство) между объектами в таблице «объект — объект» часто представляется с помощью бинарных значений:

• 1 (или другой символ) — связь существует (например, есть граница, дорога).
• 0 (или пустая ячейка) — связь отсутствует.

Таблицы типа «объект — объект» особенно удобны для:

• Решения логических задач, где требуется установить однозначное соответствие между элементами нескольких классов.
• Моделирования взаимосвязей (например, расстояние между городами, успеваемость учеников по предметам).
• Представления графов (весовые матрицы).

Необходимо построить таблицу «Имя — Фамилия» и таблицу «Имя — Место» для установления соответствий.

• Имена: Валерий, Николай, Михаил, Игорь.
• Фамилии: Симаков, Чигрин, Зимин, Копылов.
• Места: 1, 2, 3, 4.

1. Устанавливаем соответствие Место/Имя и Место/Фамилия:

• Место 1: Копылов (Фамилия).
• Место 2: Валерий (Имя), но на самом деле второе место занял Михаил. Из этого следует, что предсказание о Валерии неверно.
• Место 3: Чигрин (Фамилия), но на самом деле третье место занял Николай. Из этого следует, что предсказание о Чигрине неверно.
• Место 4: Эдуард (Имя).
• На самом деле второе место занял Михаил.
• На самом деле третье место занял Николай.

2. Определяем Места:

• Место 2: Михаил.
• Место 3: Николай.
• Оставшиеся места: Место 1 и Место 4.
• Оставшиеся имена: Валерий, Игорь.

3. Определяем Фамилии:

• Чигрин и Блинов (видимо, опечатка, должно быть Зимин или Симаков) не вошли в четверку лидеров. Игнорируем «Блинов» как опечатку, так как в списке фамилий его нет, а Чигрин есть в списке фамилий. Однако в условии сказано, что «Чигрин и Блинов не попал в четвёрку сильнейших». Это противоречит тому, что Чигрин занял третье место по предсказанию. Будем полагать, что в последнем предложении допущена опечатка и оно относится к общей информации (не к истинному положению).

• Используем истинные данные: Копылов занял 1-е место, Михаил — 2-е, Николай — 3-е.
• Фамилии, занявшие места: Копылов (1-е), Чигрин (3-е по предсказанию, но 3-е занял Николай), Блинов/Зимин/Симаков.

4. Принимаем только непротиворечивые факты:

• Место 1: Копылов (Фамилия).
• Место 2: Михаил (Имя).
• Место 3: Николай (Имя).
• Место 4: Игорь или Валерий.
• Оставшаяся фамилия: Симаков, Зимин, Чигрин (исключая Копылова).

5. Сопоставляем имена и фамилии:

• Предположим, что фамилии Чигрин и Зимин не попали в четвёрку лидеров, тогда:
• Фамилии в четверке: Копылов (1-е), Симаков (оставшаяся), Зимин, Чигрин.
• Если Копылов — 1-е место, то 2-е, 3-е, 4-е места заняли Симаков, Зимин, Чигрин (в каком-то порядке).
• Тогда утверждение «Чигрин... не попал в четверку сильнейших» означает, что Чигрин не в четверке.
• Фамилии в четверке: Копылов (1-е), Симаков, Зимин.
• Имена в четверке: Михаил (2-е), Николай (3-е), Валерий, Игорь.

6. Окончательное сопоставление:

• Место 1 (Копылов): Должен быть Валерий или Игорь.
• Место 2 (Михаил): Должен быть Симаков или Зимин.
• Место 3 (Николай): Должен быть Симаков или Зимин.
• Место 4: Оставшееся имя и фамилия.

Ответ (по логике задачи):

• Первое место: Игорь Копылов.
• Второе место: Михаил Симаков.
• Третье место: Николай Зимин.
• Четвертое место: Валерий Чигрин (если исключить противоречие в условии) или оставшийся вариант, что не позволяет однозначно решить задачу.
• Придерживаясь логики, что 1-е место занял Копылов, 2-е — Михаил, 3-е — Николай:

Имя/Фамилия:

• Николай Зимин (3-е место)
• Михаил Симаков (2-е место)
• Игорь Копылов (1-е место)
• Валерий Чигрин (4-е место)

Необходимо построить две таблицы «Город — Имя (Муж)» и «Город — Имя (Жена)» и заполнить их по условиям.

• Города: Норильск, Москва, Ростов, Пятигорск.
• Мужья: Антон, Борис, Давид, Григорий.
• Жены: Ольга, Мария, Светлана, Екатерина.

1. Заполняем известные данные:

• Мария живет в Москве.
• Светлана живет в Ростове.
• Григорий и Светлана не живут в одном городе. Так как Светлана в Ростове, то Григорий не в Ростове.

2. Определяем пары:

• Дано 8 имен, но 4 пары. Значит, имена: Мария, Светлана, Екатерина, Ольга (Жены), и Антон, Борис, Григорий, Давид (Мужья).
• Из условия: Мария, Светлана, Екатерина, Антон живут в Норильске, Борис и Ольга — супруги, Григорий и Светлана не живут в одном городе.
• Пара 1: Борис и Ольга (живут в одном городе).
• Мария живет в Москве.
• Светлана живет в Ростове.
• Антон, Мария, Светлана, Екатерина живут в Норильске? Противоречие с пунктами 2 и 3. Условие «Мария, Светлана, Екатерина, Антон живут в Норильске» означает, что эти четыре человека НЕ живут в Норильске, если следовать логике задачи из учебника, где перечисляются имена, а потом дается условие. Принимаем как опечатку и используем только однозначные факты.

3. Используем однозначные факты:

• Жена в Москве: Мария.
• Жена в Ростове: Светлана.
• Муж в Ростове: Не Григорий.

4. Сопоставляем пары по оставшимся именам и городам:

• Оставшиеся жены: Ольга, Екатерина.
• Оставшиеся мужья: Антон, Давид, Григорий.
• Оставшиеся города: Норильск, Пятигорск.

Ответ (по логике задачи):

• Ростов: Давид и Светлана. (Так как Светлана в Ростове, а Григорий не в Ростове).
• Москва: Григорий и Мария. (Мария в Москве, а Григорий не в Ростове).
• Норильск: Антон и Екатерина.
• Пятигорск: Борис и Ольга.

Начальное положение: \((1, 2)\). Выигрышная позиция (W) — \( x + y \geq 17 \).

1. Возможные ходы из (1, 2):

• \( (1 \cdot 3, 2) = (3, 2) \)
• \( (1 + 2, 2) = (3, 2) \)
• \( (1, 2 \cdot 3) = (1, 6) \)
• \( (1, 2 + 2) = (1, 4) \)

Все ходы первого игрока ведут в позиции, где \( x + y < 17 \).

2. Анализ выигрышных/проигрышных позиций:

• Проигрышные позиции (P): Позиции, из которых все возможные ходы ведут в W-позиции (победа для следующего игрока), и сумма \( x + y < 17 \).
• Выигрышные позиции (W): Позиции, из которых существует хотя бы один ход, ведущий в P-позицию (победа для текущего игрока), или сумма \( x + y \geq 17 \).

Путем анализа обратным ходом (начиная с W-позиций):

• Максимальная P-позиция: \( x + y = 16 \). Например, \((8, 8)\), \((16, 0)\), \((0, 16)\), \((5, 11)\).
• Из \((3, 2)\): Все ходы ведут в W-позиции для Второго игрока. Например, \((3 \cdot 3, 2) = (9, 2)\), \((3, 2 \cdot 3) = (3, 6)\).

Ответ:

• Выигрывает ли второй игрок? Если начальная позиция \((1, 2)\) является W-позицией для первого игрока, то он побеждает. Если \((1, 2)\) является P-позицией, то побеждает второй игрок. Построение дерева показывает, что \((1, 2)\) — это W-позиция для первого игрока. Первый игрок побеждает. (Условие задачи в учебнике (стр. 130) часто предполагает, что \((1, 2)\) — это проигрышная позиция для первого, но в данной игре это W-позиция).
• Первый выигрышный ход: Для победы первый игрок должен сделать ход в P-позицию для второго. Из \((1, 2)\) нет хода в P-позицию для второго. Первый игрок побеждает, если он может сделать ход, который гарантирует ему победу.
• Для победы первый игрок должен сделать ход в позицию, из которой второй игрок НЕ сможет попасть в \( x + y \geq 17 \).
• Ход \((1, 4)\) или \((3, 2)\) не позволяет второму игроку победить сразу.
• Выигрышная стратегия: \((1, 2) \rightarrow (1, 6)\) (прибавили 4). Нет, такого хода нет. \((1, 2) \rightarrow (1, 4)\) (прибавили 2), или \((1, 2) \rightarrow (3, 2)\) (прибавили 2), или \((1, 2) \rightarrow (3, 2)\) (умножили на 3), или \((1, 2) \rightarrow (1, 6)\) (умножили на 3).
• Позиция \((1, 6)\) дает \(1+6=7\). Ходы второго игрока: \((3, 6)\), \((1, 18)\). Ход \((1, 18)\) — победа для второго. Значит, ход \((1, 6)\) — P-позиция.
• Правильный выигрышный ход: Первый игрок делает ход \((1, 2) \rightarrow (3, 2)\).
• \( 3 + 2 = 5 \). Из \((3, 2)\) ходы: \((9, 2)\) (11), \((3, 6)\) (9), \((5, 2)\) (7), \((3, 4)\) (7). Все \( < 17 \).
• Второй игрок из \((3, 2)\) ходит в \((9, 2)\) (11). Ходы первого: \((27, 2)\) (29 — победа).
• Первый игрок выигрывает. Первый выигрышный ход: \((1, 2) \rightarrow (3, 2)\) (умножение на 3 или +2).

Кратчайший путь из A в E, который обязательно проходит через C, включает два отрезка: A до C и C до E.

1. Находим кратчайший путь A \(\rightarrow\) C:

• A \(\rightarrow\) C: \( 4 \)
• A \(\rightarrow\) B \(\rightarrow\) C: \( 1 + 2 = 3 \)
• A \(\rightarrow\) D \(\rightarrow\) C: \( 3 + 3 = 6 \)

Кратчайший путь A \(\rightarrow\) C: A \(\rightarrow\) B \(\rightarrow\) C с длиной \( 3 \).

2. Находим кратчайший путь C \(\rightarrow\) E:

• C \(\rightarrow\) E: \( 7 \)
• C \(\rightarrow\) D \(\rightarrow\) E: \( 3 + 2 = 5 \)
• C \(\rightarrow\) B \(\rightarrow\) E: \( 2 + 5 = 7 \)

Кратчайший путь C \(\rightarrow\) E: C \(\rightarrow\) D \(\rightarrow\) E с длиной \( 5 \).

3. Суммируем длины:

• Путь A \(\rightarrow\) C \(\rightarrow\) E: \( (A \rightarrow B \rightarrow C) + (C \rightarrow D \rightarrow E) = 3 + 5 = 8 \)

Ответ: Длина кратчайшего пути из A в E, проходящего через C, равна 8 (путь: A \(\rightarrow\) B \(\rightarrow\) C \(\rightarrow\) D \(\rightarrow\) E).

Необходимо найти минимальную стоимость перевозки из A в B, то есть кратчайший путь (минимальный вес) между этими пунктами для каждой из трех матриц.

• Компания 1 (Матрица 1):
• Прямой путь A \(\rightarrow\) B: \( 3 \).
• Другие пути: A \(\rightarrow\) D \(\rightarrow\) B: \( 1 + 4 = 5 \).
• Минимальная стоимость Компании 1: \( 3 \).
• Компания 2 (Матрица 2):
• Прямой путь A \(\rightarrow\) B: \( 3 \).
• Другие пути: A \(\rightarrow\) D \(\rightarrow\) B: \( 1 + 4 = 5 \).
• Минимальная стоимость Компании 2: \( 3 \).
• Компания 3 (Матрица 3):
• Прямой путь A \(\rightarrow\) B: \( 1 \).
• Другие пути: A \(\rightarrow\) E \(\rightarrow\) B: \( 4 + 2 = 6 \).
• Минимальная стоимость Компании 3: \( 1 \).

Ответ: Минимальную стоимость перевозки из A в B предлагает Компания 3 со стоимостью 1 у.е.