kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

Готовимся к ЕГЭ по информатике

Нажмите, чтобы узнать подробности

Задания для подготовки к ЕГЭ по информатике. Материалы полезны учащимся и учителям.

Просмотр содержимого документа
«Готовимся к ЕГЭ по информатике»

Поиск оптимального маршрута по таблице

1. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 


A

B

C

D

E

F

A


4





B

4


6

3

6


C


6



4


D


3



2


E


6

4

2


5

F





5


 

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

Решение.

Варианты маршрутов:

 

A-B-C-E-F. Длина маршрута 4 + 6 + 4 + 5 = 19

 

A-B-D-E-F. Длина маршрута 4 + 3 + 2 + 5 = 14

 

A-B-E-F. Длина маршрута 4 + 6 + 5 = 15

 

Видно, что кратчайший путь равен 14.

2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


2

4

8


16

B

2



3



C

4



3



D

8

3

3


5

3

E




5


5

F

16



3

5


 

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

Решение.

Заметим, что в Е можно попасть только из D и F, следовательно, в маршруте также обязательно должен присутствовать пункт D. Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—E—F, его длина равна 15 км. Теперь, начиная с начала маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, A—B—D больше расстояния A—D, то заменяем участок маршрута A—B—D на A—D. Попробовав произвести все такие замены, получим, что маршрут A—B—D—E—F — самый короткий из тех, что удовлетворяют условию задачи.

Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.

 

Ответ: 15.

3. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

G

A


2


6




B

2


5

3




C


5


1



8

D

6

3

1


9

7


E




9



5

F




7



7

G



8


5

7


 

Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.

Решение.

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

 

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

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

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

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

Из пункта E можно попасть в пункт G.

Из пункта F можно попасть в пункт G.

 

A−B−C−D−E−G. Длина маршрута 22.

 

A−B−C−D−F−G. Длина маршрута 22.

 

A−B−C−G. Длина маршрута 15.

 

A−B−D−E−G. Длина маршрута 19.

 

A−B−D−F−G. Длина маршрута 19.

 

A−D−F−G. Длина маршрута 20.

 

A−D−E−G. Длина маршрута 20.

 

A−B−D−С−G. Длина маршрута 14.

 

Кратчайший путь равен 14.

 

Ответ: 14.

4. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

G

A


2


6




B

2


5

2




C


5


4



8

D

6

2

4


2

7


E




2



5

F




7



7

G



8


5

7


 

Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.

Решение.

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

 

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

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

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

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

Из пункта E можно попасть в пункт G.

Из пункта F можно попасть в пункт G.

 

A−B−C−D−E−G. Длина маршрута 18.

 

A−B−C−D−F−G. Длина маршрута 25.

 

A−B−C−G. Длина маршрута 15.

 

A−B−D−E−G. Длина маршрута 11.

 

A−B−D−F−G. Длина маршрута 18.

 

A−D−F−G. Длина маршрута 20.

 

A−D−E−G. Длина маршрута 13.

 

Кратчайший путь равен 11.

 

Ответ: 11.

5. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


2

4

8


16

B

2



3



C

4



3



D

8

3

3


5

3

E




5


5

F

16



3

5


 

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Решение.

Найдём все варианты маршрутов, удовлетворяющих условию и выберем самый короткий.

 

A−D−E−F. Длина маршрута 18.

 

A−C−D−E−F. Длина маршрута 17.

 

Кратчайший путь равен 17.

 

Ответ: 17.

6. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


2

4

8


16

B

2



3



C

4



3



D

8

3

3


2

3

E




2


5

F

16



3

5


 

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Решение.

Найдём все варианты маршрутов, удовлетворяющих условию и выберем самый короткий.

 

A−C−D−E−F. Длина маршрута 14.

 

A−D−E−F. Длина маршрута 15.

 

Кратчайший путь равен 14.

 

Ответ: 14.

7. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


3

4

4


16

B

3



5



C

4



2



D

4

5

2


6

10

E




6


3

F

16



10

3


 

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

Решение.

Найдём все маршруты, удовлетворяющие условию, посчитаем расстояние и выберем кратчайшее.

 

A-B-D-F 18

A-B-D-E-F 17

A-C-D-F 16

A-C-D-E-F 15

A-D-F 14

A-D-E-F 13

A-F 16

 

Кратчайшим является A-D-E-F с длиной 13.

8. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

G

A


2



6



B

2


10

9

3



C


10





6

D


9





9

E

6

3




5

14

F





5


7

G



6

9

14

7


 

 

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

Решение.

Рассмотрим все возможные маршруты. Кратчайшим окажется A-B-E-F-G длиной 17

9. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

G

A


8



6



B

8


2

9

3



C


2





5

D


9





9

E

6

3




5

10

F





5


7

G



5

9

10

7


 

 

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

Решение.

Рассмотрим все возможные пути из А в G. Кратчайшим является A-B-C-G длиной 15.

10. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


2

4

8


16

B

2



3



C

4



3



D

8

3

3


2

5

E




2


2

F

16



5

2


 

 

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

Решение.

Рассмотрим все возможные маршруты из А в F, удовлетворяющие условию. Кратчайшим является A-B-D-F длиной 10.

11. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


7

4

8


16

B

7



3



C

4



3



D

8

3

3


2

3

E




2


5

F

16



3

5


 

 

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

Решение.

Рассмотрим все возможные пути. Кратчайшим окажется путь A-C-D-F длиной 10.

12. Между населенными пунктами ABCDEF построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


6

10


3

14

B

6





7

C

10



2

5

3

D



2


4


E

3


5

4



F

14

7

3




 

 

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

Решение.

Варианты маршрутов:

 

A-B-F. Длина маршрута 6 + 7 = 13

A-C-F. Длина маршрута 10 + 3 = 13

A-E-C-F. Длина маршрута 3 + 5 + 3 = 11

A-F. Длина маршрута 14

 

Видно, что кратчайший путь равен 11.

 

Ответ: 11.

13. Между населенными пунктами ABCDEF построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 


A

B

C

D

E

F

A


4

7

11


16

B

4



6

5


C

7





9

D

11

6



3


E


5


3


4

F

16


9


4


 

 

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

Решение.

Варианты маршрутов:

 

A-B-D-E-F. Длина маршрута 4 + 6 + 3 + 4 = 17

A-B-E-F. Длина маршрута 4 + 5 + 4 = 13

A-C-F. Длина маршрута 7 + 9 = 16

A-F. Длина маршрута 16

 

Видно, что кратчайший путь равен 13.

 

Ответ: 13.

14. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 


A

B

C

D

E

F

A



3




B



9


4


C

3

9


3

8


D



3


2


E


4

8

2


7

F





7


 

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

Решение.

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

 

В пункт F можно попасть только из пункта Е.

В пункт Е можно попасть из пунктов С, В и D.

В пункты В и D можно попасть только из пункта С.

В пункт С можно попасть только из пункта А.

 

A-C-E-F. Длина маршрута 3 + 8 + 7 = 18.

 

A-С-D-E-F. Длина маршрута 3 + 3 + 2 + 7 = 15.

 

A-С-B-E-F. Длина маршрута 3 + 9 + 4 + 7 = 23.

 

Видно, что кратчайший путь равен 15.




Получите в подарок сайт учителя

Предмет: Информатика

Категория: Тесты

Целевая аудитория: 11 класс

Скачать
Готовимся к ЕГЭ по информатике

Автор: Фазулзянова Леисан Хамитовна

Дата: 28.09.2019

Номер свидетельства: 521223

Похожие файлы

object(ArrayObject)#850 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(137) "Рабочая программа индивидуального курса «Готовимся к ЕГЭ по информатике» "
    ["seo_title"] => string(77) "rabochaia-proghramma-individual-nogho-kursa-gotovimsia-k-iege-po-informatikie"
    ["file_id"] => string(6) "152550"
    ["category_seo"] => string(11) "informatika"
    ["subcategory_seo"] => string(12) "planirovanie"
    ["date"] => string(10) "1420877524"
  }
}
object(ArrayObject)#872 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(19) "Решение  С1"
    ["seo_title"] => string(14) "rieshieniie-s1"
    ["file_id"] => string(6) "264859"
    ["category_seo"] => string(10) "matematika"
    ["subcategory_seo"] => string(11) "presentacii"
    ["date"] => string(10) "1449775254"
  }
}
object(ArrayObject)#850 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(96) "Использование ИКТ на уроках Человек.Общество.Право. "
    ["seo_title"] => string(59) "ispol-zovaniie-ikt-na-urokakh-chieloviek-obshchiestvo-pravo"
    ["file_id"] => string(6) "133274"
    ["category_seo"] => string(16) "obschestvoznanie"
    ["subcategory_seo"] => string(12) "meropriyatia"
    ["date"] => string(10) "1416490090"
  }
}
object(ArrayObject)#872 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(111) "Информационная карта инновационного педагогического опыта "
    ["seo_title"] => string(67) "informatsionnaia-karta-innovatsionnogho-piedaghoghichieskogho-opyta"
    ["file_id"] => string(6) "175714"
    ["category_seo"] => string(13) "vsemUchitelam"
    ["subcategory_seo"] => string(7) "prochee"
    ["date"] => string(10) "1424293732"
  }
}
object(ArrayObject)#850 (1) {
  ["storage":"ArrayObject":private] => array(6) {
    ["title"] => string(126) "«Использование информационных технологий на уроках химии и физики» "
    ["seo_title"] => string(72) "ispol-zovaniie-informatsionnykh-tiekhnologhii-na-urokakh-khimii-i-fiziki"
    ["file_id"] => string(6) "203882"
    ["category_seo"] => string(6) "himiya"
    ["subcategory_seo"] => string(7) "prochee"
    ["date"] => string(10) "1429552908"
  }
}

Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

Удобный поиск материалов для учителей

Ваш личный кабинет
Проверка свидетельства