2011-gre-cs-practice-book.pdf/Q30 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
Urmat A (обсуждение | вклад) |
||
| (не показано 8 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q30-08c765 == | == Вопрос: Q30-08c765 == | ||
Дан ориентированный граф: | Дан ориентированный граф: | ||
| − | [ | + | <graph> |
| + | digraph G{ | ||
| + | rankdir=LR; | ||
| + | edge [color=blue]; | ||
| + | 10 -> 5 | ||
| + | 10 -> 20 | ||
| + | 5 -> 13 | ||
| + | 5 -> 17 | ||
| + | 17 -> 13 | ||
| + | 20 -> 17 | ||
| + | 20 -> 30 | ||
| + | 13 -> 14 | ||
| + | 14 -> 7 | ||
| + | 17-> 7 | ||
| + | 7 -> 30 | ||
| + | } | ||
| + | </graph> | ||
| − | Что из перечисленного является топологической сортировкой вершин графа[https://habr.com/ru/companies/otus/articles/499138/]? | + | Что из перечисленного является [https://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D0%BF%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 топологической сортировкой вершин графа] ([https://habr.com/ru/companies/otus/articles/499138/])? |
=== Ответы === | === Ответы === | ||
| − | + | * 5, 7, 10, 13, 14, 17, 20, 30 | |
| − | + | * 10, 5, 13, 14, 7, 30, 17, 20 | |
| − | + | * 10, 5, 13, 17, 20, 14, 7, 30 | |
| − | + | * 10, 5, 20, 13, 17, 30, 14, 7 | |
| − | + | * Правильный ответ: 10, 20, 5, 17, 13, 14, 7, 30 | |
=== Объяснение === | === Объяснение === | ||
| Строка 19: | Строка 34: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|29|30}} | {{cstest-source|2011-gre-cs-practice-book.pdf|29|30}} | ||
| − | Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30. Далее можно пойти либо в 7, либо в 20. Но из 20 можно попасть 7, значит эта вершина стоит раньше. Тогда идем выбираем 7. Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот. Пойдём так дальше до 13. Получили 13-14-7-30. | + | * Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30. |
| + | * Далее можно пойти либо в 7, либо в 20. | ||
| + | * Но из 20 можно попасть 7, значит эта вершина стоит раньше. | ||
| + | * Тогда идем выбираем 7. | ||
| + | * Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот. | ||
| + | * Пойдём так дальше до 13. Получили 13-14-7-30. | ||
| + | * Из 13 опять вилка — либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30. | ||
| + | * Далее очевидный выбор между 10 и 20. | ||
| + | * Получили 10-20-5-17-13-14-7-30. | ||
| − | {{question-ok | + | [[Участник:StasFomin|StasFomin]]: Все-таки можно размышлять проще. |
| − | + | * Начало однозначно 10, конец 30 — таких вариантов два. | |
| + | * Но в варианте «10, 5, 13, 17, 20, 14, 7, 30» явное нарушение «20→17». | ||
| + | |||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 19:20, 19 декабря 2024 (UTC)}} | ||
| + | |||
| + | [[Категория:Алгоритмы на графах]] | ||
Текущая версия на 22:28, 21 декабря 2024
Вопрос: Q30-08c765
Дан ориентированный граф:
Что из перечисленного является топологической сортировкой вершин графа ([1])?
Ответы
- 5, 7, 10, 13, 14, 17, 20, 30
- 10, 5, 13, 14, 7, 30, 17, 20
- 10, 5, 13, 17, 20, 14, 7, 30
- 10, 5, 20, 13, 17, 30, 14, 7
- Правильный ответ: 10, 20, 5, 17, 13, 14, 7, 30
Объяснение
Исходники — вопрос 30 на 29 странице книги «2011-gre-cs-practice-book.pdf»
- Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30.
- Далее можно пойти либо в 7, либо в 20.
- Но из 20 можно попасть 7, значит эта вершина стоит раньше.
- Тогда идем выбираем 7.
- Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот.
- Пойдём так дальше до 13. Получили 13-14-7-30.
- Из 13 опять вилка — либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30.
- Далее очевидный выбор между 10 и 20.
- Получили 10-20-5-17-13-14-7-30.
StasFomin: Все-таки можно размышлять проще.
- Начало однозначно 10, конец 30 — таких вариантов два.
- Но в варианте «10, 5, 13, 17, 20, 14, 7, 30» явное нарушение «20→17».