Меню

Поиск графа соответствующего таблице



Поиск графа соответствующего таблице

  • Главная
  • ЕГЭ
    • Вопросы и ответы
    • Перевод баллов
    • Соответствие заданий
  • Ваши задания
  • Учебники
    • Программирование
      • Типы данных Pascal
      • Математические функции
    • Основы логики
      • Логические операции
      • Приоритет операций
      • Законы логики
    • Системы счисления
      • О системах счисления
      • Перевод чисел
      • Таблица триад и тетрад
  • Видеоуроки
    • Досрочный-2016
    • Демо-2016
    • Досрочный-2015
    • Алгебра логики
  • Онлайн-тесты
    • Вариант 1
    • Вариант 2
    • Вариант 3
    • Вариант 4
    • Вариант 5
    • Вариант 6
    • Вариант 7
    • Вариант 8
    • Вариант 9
    • Вариант 10
  • Программы
    • Степени двойки
    • IP, маска и адрес сети
    • Решатор 5
    • Решатор 13
  • Словарь
  • 1 Системы счисления
  • 2 Таблицы истинности
  • 3 Поиск кратчайшего пути
  • 4 Базы данных
    Файловая система
  • 5 Кодирование информации
  • 6 Анализ алгоритмов
  • 7 Электронные таблицы
  • 8 Программирование: циклы
  • 9 Объем информации
    Передача информации
  • 10 Комбинаторика
  • 11 Рекурсивные алгоритмы
  • 12 Сети, адресация
  • 13 Количество информации
  • 14 Алгоритмы с исполнителем
  • 15 Поиск путей в графе
  • 16 Системы счисления
  • 17 Запросы для поисковых систем
  • 18 Логические выражения
    Отрезки, множества, функции
  • 19 Программирование: массивы
  • 20 Программирование: циклы
  • 21 Программирование: подпрограммы
  • 22 Перебор вариантов
  • 23 Системы логических уравнений
  • 24 Программирование: поиск ошибки в программе
  • 25 Программирование: обработка массивов
  • 26 Теория игр
  • 27 Программирование: разработка программы

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

П1 П2 П3 П4 П5 П6 П7
П1 45 10
П2 45 40 55
П3 15 60
П4 10 40 20 35
П5 15 55
П6 55 60 20 55 45
П7 35 45

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите. какова длина дороги из пункта В в пункт Е. В ответе запишите целое число — так, как оно указано в таблице.

Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.

В решении задания есть видеоразбор

Чтобы найти расстояние между пунктами В и Е необходимо определить, какой пункт таблицы соответствует пункту В карты, а какой — пункту Е карты.

Обратите внимание на граф. Пункт В — единственный, из которого выходит пять дорог. По таблице видно, что это П6. То есть П6 таблицы — это пункт В на графе.

Теперь посмотрим на пункт Е в графе. Он единственный, из которого выходит четыре дороги. По таблице видно, что пунктом В графа может быть только П4.

Таким образом, мы должны определить расстояние между П6 и П4 в таблице, что очень легко сделать:

П1 П2 П3 П4 П5 П6 П7
П1 45 10
П2 45 40 55
П3 15 60
П4 10 40 20 35
П5 15 55
П6 55 60 20 55 45
П7 35 45

Ответ: 20

Видеоразбор задания:

Источник

Простейшие задачи на графы

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?

Заметим, что количество путей в город Е является суммой путей в города Ж, Г и Д. Количество путей в город Ж — сумма путей в города Г и Б. Таким образом получаем:

Заметим, что в пункты Б и В можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Заметим, что количество путей в город Ж является суммой путей в города Д, Г и Е. Количество путей в город Г — сумма путей в город В, Б и Е. Таким образом получаем:

Читайте также:  Сортировка и индексирование таблиц

Заметим, что в пункты Б, В и Е можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

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

Найдём все варианты маршрутов из A в E и выберем самый короткий.

Из пункта A можно попасть в пункты B, D.

Из пункта B можно попасть в пункты C, D.

Из пункта C можно попасть в пункты D, E.

A—B—C—E: длина маршрута 7 км.

A—D—B—C—E: длина маршрута 9 км.

A—D—C—E: длина маршрута 6 км.

Самый короткий путь: A—D—C—E. Длина маршрута 6 км.

Геральт спешит выручить Цири из плена Кагыра. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Геральта до Цири (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Найдём все варианты маршрутов из И в М и выберем самый короткий.

Из пункта И можно попасть в пункты А, Б, Г, М.

Из пункта Г можно попасть в пункты И, М.

Из пункта В можно попасть в пункты А, Б.

Из пункта Б можно попасть в пункты В, И, М.

И—А—В—Б—М: длина маршрута 7 км.

И—Б—М: длина маршрута 4 км.

И—Г—М: длина маршрута 7 км.

И—М: длина маршрута 8 км.

Самый короткий путь: И—Б—М. Длина маршрута 4 км. Самый короткий участок этого пути равен 1 км.

На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.

Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

Заметим, что наиболее удалены друг от друга пункты A и D. Найдём все варианты маршрутов из A в D и выберем самый короткий.

A—B—D: длина маршрута 13 км.

A—C—D: длина маршрута 15 км.

A—B—C—D: длина маршрута 23 км.

A—C—B—D: длина маршрута 17 км.

Заметим, что кратчайшее расстояние между пунктами A и D равняется 13.

Источник

Поиск и подстановка по нескольким условиям

Постановка задачи

Если вы продвинутый пользователь Microsoft Excel, то должны быть знакомы с функцией поиска и подстановки ВПР или VLOOKUP (если еще нет, то сначала почитайте эту статью, чтобы им стать). Для тех, кто понимает, рекламировать ее не нужно 🙂 — без нее не обходится ни один сложный расчет в Excel. Есть, однако, одна проблема: эта функция умеет искать данные только по совпадению одного параметра. А если у нас их несколько?

Предположим, что у нас есть база данных по ценам товаров за разные месяцы:

vlookup-2cols1.png

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

Способ 1. Дополнительный столбец с ключом поиска

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

Добавим рядом с нашей таблицей еще один столбец, где склеим название товара и месяц в единое целое с помощью оператора сцепки (&), чтобы получить уникальный столбец-ключ для поиска:

vlookup-2cols2.png

Теперь можно использовать знакомую функцию ВПР (VLOOKUP) для поиска склеенной пары НектаринЯнварь из ячеек H3 и J3 в созданном ключевом столбце:

vlookup-2cols3.png

Плюсы : Простой способ, знакомая функция, работает с любыми данными.

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

Читайте также:  Момент свинчивания нкт 73 гкш 1500 таблица

Способ 2. Функция СУММЕСЛИМН

Если нужно найти именно число (в нашем случае цена как раз число), то вместо ВПР можно использовать функцию СУММЕСЛИМН (SUMIFS) , появившуюся начиная с Excel 2007. По идее, эта функция выбирает и суммирует числовые значения по нескольким (до 127!) условиям. Но если в нашем списке нет повторяющихся товаров внутри одного месяца, то она просто выведет значение цены для заданного товара и месяца:

vlookup-2cols4.png

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

Минусы : Работает только с числовыми данными на выходе, не применима для поиска текста, не работает в старых версиях Excel (2003 и ранее).

Способ 3. Формула массива

О том, как спользовать связку функций ИНДЕКС (INDEX) и ПОИСКПОЗ (MATCH) в качестве более мощной альтернативы ВПР я уже подробно описывал (с видео). В нашем же случае, можно применить их для поиска по нескольким столбцам в виде формулы массива. Для этого:

  1. Выделите пустую зеленую ячейку, где должен быть результат.
  2. Введите в строке формул в нее следующую формулу:

vlookup-2cols6.png

  • Нажмите в конце не Enter, а сочетание Ctrl+Shift+Enter, чтобы ввести формулу не как обычную, а как формулу массива.
  • Как это на самом деле работает:

    Функция ИНДЕКС выдает из диапазона цен C2:C161 содержимое N-ой ячейки по порядку. При этом порядковый номер нужной ячейки нам находит функция ПОИСКПОЗ. Она ищет связку названия товара и месяца (НектаринЯнварь) по очереди во всех ячейках склеенного из двух столбцов диапазона A2:A161&B2:B161 и выдает порядковый номер ячейки, где нашла точное совпадение. По сути, это первый способ, но ключевой столбец создается виртуально прямо внутри формулы, а не в ячейках листа.

    Плюсы : Не нужен отдельный столбец, работает и с числами и с текстом.

    Минусы : Ощутимо тормозит на больших таблицах (как и все формулы массива, впрочем), особенно если указывать диапазоны «с запасом» или сразу целые столбцы (т.е. вместо A2:A161 вводить A:A и т.д.) Многим непривычны формулы массива в принципе (тогда вам сюда).

    Источник

    Поиск графа соответствующего таблице

    На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

    П1 П2 П3 П4 П5 П6 П7
    П1 45 10
    П2 45 40 55
    П3 15 60
    П4 10 40 20 35
    П5 15 55
    П6 55 60 20 55 45
    П7 35 45

    Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

    Пункт В − единственный пункт с пятью дорогами, значит, ему соответствует П6, а пункт Е − единственный с четырьмя дорогами, значит, ему соответствует П4.

    Длина дороги из П6 в П4 равна 20.

    На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

    Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

    Пункт Г − единственный пункт с тремя дорогами, значит, ему соответствует П2, а пункт Е − единственный с четырьмя дорогами, значит, ему соответствует П4.

    Длина дороги из П2 в П4 равна 40.

    На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

    Читайте также:  Таблица с машинными швами

    Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

    Пункт В − единственный пункт с пятью дорогами, значит, ему соответствует П6, а пункт Г − единственный с тремя дорогами, значит, ему соответствует П2.

    Длина дороги из П6 в П2 равна 55.

    На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

    Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Д. В ответе запишите целое число.

    Есть только один пункт, из которого ведёт 5 дорог — это В, а в таблице — П6.

    Из А ведёт две дороги и одна из них в В. В таблице такому соответствует П5.

    Из Б ведёт 3 дороги, причём есть дороги в А и в В, в таблице под такое подходит только П3.

    Из Д три дороги, две из которых в Б и в В, в таблице только один пункт такому соответствует — П7.

    Таким образом, Б — это П3, а Д — П7. Длина дороги между П3 и П7 — 8.

    На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

    Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Д. В ответе запишите целое число.

    Есть только один пункт, из которого ведёт 5 дорог — это В, а в таблице — П6.

    Из А ведёт две дороги и одна из них в В. В таблице такому соответствует П5.

    Из Б ведёт 3 дороги, причём есть дороги в А и в В, в таблице под такое подходит только П3.

    Из Д три дороги, две из которых в Б и в В, в таблице только один пункт такому соответствует — П7.

    Таким образом, Б — это П3, а Д — П7. Длина дороги между П3 и П7 — 11.

    Источник

    Демоверсия егэ по информатике 2020. Задание 3

    На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

    решение 3 задания демоверсии 2020 разбор 3 задания демоверсии 2020

    Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

    Определите, какова протяжённость дороги из пункта Д в пункт Е.
    В ответе запишите целое число – так, как оно указано в таблице.

    • Выберем на граве вершины с уникальным количеством ребер: это вершина А1 ребро и вершина Д5 ребер. Найдем и обозначим их в таблице:

    Так как вершина А соединяется только с вершиной Б, то обозначим вершину Б тоже:

    Вершина Б соединяется с четырьмя вершинами, у которых разное количество ребер: А(1), В(2), Д(5) и Г(3). Раз количество ребер разное, то по таблице определим все эти вершины:

    Теперь для поиска протяженности пути от пункта Д в пункт Е достаточно найти вершину Е. По графу видим, что у нее 2 ребра. Из оставшихся столбцов и строк таблицы, находим строку с двумя значениями:

  • Таким образом, вершине Д соответствует строка/столбец 4, а вершине, Е — 1. На пересечении их в таблице стоит число 9 .
  • Источник

    Adblock
    detector