№ | Слайд | Текст |
1 |
 |
«Методические требования к подготовке школьников, участвующих винтеллектуальных турнирах по информатике». Часть 2. (Анализ результатов заочного этапа XVI турнира им. М.В. Ломоносова). |
2 |
 |
Секции9 класс, 10-11 классы. |
3 |
 |
Задача 1 (9 класс)Среди перечисленных устройств, укажите те, которые предназначены для долговременного хранения данных: оперативная память, RAID-массив, роутер, CD-RW. |
4 |
 |
Задача 1 (9 класс)Среди перечисленных устройств, укажите те, которые предназначены для долговременного хранения данных: оперативная память, RAID-массив, роутер, CD-RW. RAID — redundant array of independent disks — избыточный массив независимых дисков Ответ: 24 |
5 |
 |
Задача 2 (9 класс)Расставьте следующие числа в порядке возрастания: A = 120,113, B = 21,37, C = F,4A16, D = 1111,01112. |
6 |
 |
Задача 2 (9 класс)A = 120,113, B = 21,37, C = F,4A16, D = 1111,01112. Целые части равны: 1203 = 9 + 2?3 = 15, 217 = 2?7 + 1 = 15, F16 = 15, 11112 = 23 + 22 + 21 + 20 = 15. |
7 |
 |
Задача 2 (9 класс)A = 120,113, B = 21,37, C = F,4A16, D = 1111,01112. Дробные части: 0,113 = 1/3 + 1/9 = 4/9, 0,37 = 3/7, 0,4A16 = 4/16 + 10/64 = 26/64 = 13/32, 0,01112 = 1/4 + 1/8 + 1/16 = 7/16. |
8 |
 |
Задача 2 (9 класс)A = 120,113, B = 21,37, C = F,4A16, D = 1111,01112. Дробные части: 0,113 = 1/3 + 1/9 = 4/9, 0,37 = 3/7, 0,4A16 = 4/16 + 10/64 = 26/64 = 13/32, 0,01112 = 1/4 + 1/8 + 1/16 = 7/16. Ответ: CBDA |
9 |
 |
Задача 3 (9 класс)Шестеро друзей купили билеты на места 1 – 6 одного и того же ряда. Сколько существует вариантов их рассадки, если Оля не хочет сидеть на месте №1, Маша и Витя непременно хотят сидеть рядом, а остальным все равно? |
10 |
 |
Задача 3 (9 класс)Число размещений n человек на n местах равно Pn = n! = n ? (n-1) ? (n-2) ? … ? 2 ? 1. |
11 |
 |
Задача 3 (9 класс)6 мест: _ _ _ _ _ _ |
12 |
 |
Задача 3 (9 класс)6 мест: _ _ _ _ _ _ Посадим Машу и Витю: М В _ _ _ _ _ М В _ _ _ … _ _ _ _ М В |
13 |
 |
Задача 3 (9 класс)6 мест: _ _ _ _ _ _ Посадим Машу и Витю: М В _ _ _ _ _ М В _ _ _ … _ _ _ _ М В или В М _ _ _ _ _ В М _ _ _ … _ _ _ _ В М, всего 10 вариантов. |
14 |
 |
Задача 3 (9 класс)Случай 1. Место №1 занято: М В _ _ _ _ или В М _ _ _ _ . Остальным, включая Олю, все равно. |
15 |
 |
Задача 3 (9 класс)Случай 1. Место №1 занято: М В _ _ _ _ или В М _ _ _ _ . Остальным, включая Олю, все равно. Вариантов рассадки 4-х человек на 4 места: 4! = 4 ? 3 ? 2 ? 1 = 24, всего для шести человек: 2 ? 24 = 48 вариантов. |
16 |
 |
Задача 3 (9 класс)Случай 2. Место №1 свободно: _ М В _ _ _ … _ _ _ _ М В или _ В М _ _ _ … _ _ _ _ В М (8 вариантов). |
17 |
 |
Задача 3 (9 класс)Случай 2. Место №1 свободно: _ М В _ _ _ … _ _ _ _ М В или _ В М _ _ _ … _ _ _ _ В М (8 вариантов). Для Оли остается только 3 варианта. |
18 |
 |
Задача 3 (9 класс)Случай 2. Место №1 свободно: _ М В _ _ _ … _ _ _ _ М В или _ В М _ _ _ … _ _ _ _ В М (8 вариантов). Для Оли остается только 3 варианта. Остается 3 человека на 3 места, для них 3! = 6 способов рассадки. Всего в случае 2: 8 ? 3 ? 6 = 144 способа. |
19 |
 |
Задача 3 (9 класс)Случай 2. Место №1 свободно: _ М В _ _ _ … _ _ _ _ М В или _ В М _ _ _ … _ _ _ _ В М (8 вариантов). Для Оли остается только 3 варианта. Остается 3 человека на 3 места, для них 3! = 6 способов рассадки. Всего в случае 2: 8 ? 3 ? 6 = 144 способа. Ответ: 48 + 144 = 192. |
20 |
 |
Задача 4 (9 класс)Вася сказал: «Если книга художественная и с картинками, то она интересная». Маша: «Если книга интересная, то она художественная и с картинками» Валера: «Если книга неинтересная, то она без картинок или нехудожественная». Мила: «Если книга без картинок или нехудожественная, то она неинтересная». Игнат: «Если книга неинтересная, то она нехудожественная и без картинок». Какие из перенумерованных высказываний логически эквивалентны Васиному? |
21 |
 |
Задача 4 (9 класс)A – книга художественная, B – книга с картинками, C – книга интересная. |
22 |
 |
Задача 4 (9 класс)A – книга художественная, B – книга с картинками, C – книга интересная. Вася : «Если книга художественная и с картинками, то она интересная» A ? B ? C |
23 |
 |
Задача 4 (9 класс)A – книга художественная, B – книга с картинками, C – книга интересная. Маша: «Если книга интересная, то она художественная и с картинками» C ? A ? B |
24 |
 |
Задача 4 (9 класс)A – книга художественная, B – книга с картинками, C – книга интересная. Валера: «Если книга неинтересная, то она без картинок или нехудожественная» (?C ? ?B) ? ? A |
25 |
 |
Задача 4 (9 класс)A – книга художественная, B – книга с картинками, C – книга интересная. Мила: «Если книга без картинок или нехудожественная, то она неинтересная» (?B ? ?A) ? ?C |
26 |
 |
Задача 4 (9 класс)A – книга художественная, B – книга с картинками, C – книга интересная. Игнат: «Если книга неинтересная, то она нехудожественная и без картинок» ?C ? (?A ? ?B) |
27 |
 |
Задача 4 (9 класс)Вася: A ? B ? C (прямое утверждение), Маша: C ? A ? B (обратное), Мила: (?B ? ?A) ? ?C (противоположное), Валера: ?C ? (?B ? ? A) (противоположное к обратному), Игнат: ?C ? (?A ? ?B). |
28 |
 |
Задача 4 (9 класс)X Y X ? Y 0 0 1 0 1 1 1 0 0 1 1 1 X ? Y = 1 ? X = 1 и Y = 0. |
29 |
 |
Задача 4 (9 класс)Вася: A ? B ? C (прямое утверждение), Маша: C ? A ? B (обратное). A = B = 1, C = 0, |
30 |
 |
Задача 4 (9 класс)Вася: A ? B ? C (прямое утверждение), Маша: C ? A ? B (обратное). A = B = 1, C = 0, Вася: 1 ? 0 = 0, Маша: 0 ? 1 = 1, утверждения не эквивалентны. |
31 |
 |
Задача 4 (9 класс)Вася: A ? B ? C (прямое утверждение), Мила: (?B ? ?A) ? ?C (противоположное). A = B = 0, C = 1, |
32 |
 |
Задача 4 (9 класс)Вася: A ? B ? C (прямое утверждение), Мила: (?B ? ?A) ? ?C (противоположное). A = B = 0, C = 1, Вася: 0 ? 1 = 1, Мила: 1 ? 0 = 0, утверждения не эквивалентны. |
33 |
 |
Задача 4 (9 класс)Вася: A ? B ? C, Игнат: ?C ? (?A ? ?B). A = 1, B = C = 0, Вася: 0 ? 0 = 1, Игнат: 1 ? 0 = 0, утверждения не эквивалентны. |
34 |
 |
Задача 4 (9 класс)Вася: A ? B ? C, Валера: ?C ? (?B ? ? A). A ? B ? C = 0 ? A = B = 1, C = 0, ?C ? (?B ? ? A) ? ?C = 1, ?B ? ? A = 0 |
35 |
 |
Задача 4 (9 класс)Вася: A ? B ? C, Валера: ?C ? (?B ? ? A). A ? B ? C = 0 ? A = B = 1, C = 0, ?C ? (?B ? ? A) ? ?C = 1, ?B ? ? A = 0 ? ? C = 0, ?B = ? A = 0 ? C = 0, A = B = 1. Эквивалентные утверждения. |
36 |
 |
Задача 5 (9 класс)Флэш-накопитель отформатирован под файловую систему FAT32. Размер кластера -- 4 килобайта. На устройстве созданы две папки. В папке «Документы» записано 9 файлов, размеры которых равны 1000 байтов, 17 Кб, 40 Кб, 70 Кб, 160 Кб, 280 Кб, 326 Кб, 4 Мб и 5 Мб. |
37 |
 |
Задача 5 (9 класс)файл 1000 байтов: 1 кластер = 4 Кб, |
38 |
 |
Задача 5 (9 класс)файл 1000 байтов: 1 кластер = 4 Кб, 17 Кб: 5 кластеров = 20 Кб, |
39 |
 |
Задача 5 (9 класс)файл 1000 байтов: 1 кластер = 4 Кб, 17 Кб: 5 кластеров = 20 Кб, 40 Кб: 40 Кб, 70 Кб: 72 Кб, 160 Кб: 160 Кб, 280 Кб: 280 Кб, 326 Кб: 328 Кб, 4 Мб: 4 Мб, 5 Мб: 5 Мб, всего: 10120 Кб. |
40 |
 |
Задача 5 (9 класс)В папке «Результаты эксперимента» записаны 100 файлов по 150 Кб каждый. |
41 |
 |
Задача 5 (9 класс)В папке «Результаты эксперимента» записаны 100 файлов по 150 Кб каждый. 1 файл 150 Кб: 38 кластеров = 152 Кб, 100 файлов: 15200 Кб. |
42 |
 |
Задача 5 (9 класс)Содержимое папки «Результаты эксперимента» заархивировали, не удаляя исходные файлы. Архиватор уменьшил суммарный размер на 20%. |
43 |
 |
Задача 5 (9 класс)Содержимое папки «Результаты эксперимента» заархивировали, не удаляя исходные файлы. Архиватор уменьшил суммарный размер на 20%. Данные в исходных 100 файлах: 100 х 150 Кб = 15000 Кб, размер архива: 0,8 х 15000 Кб = 12000 Кб, всего в папке 101 файл размером 27200 Кб. Итого на устройстве: 10120 + 27200 = 37320 Кб. |
44 |
 |
Задача 6 (9 класс)Шестеро друзей-студентов устроили шахматный турнир между собой. Их звали: Антон, Владимир, Евгений, Игорь, Константин и Николай. Известно, что среди друзей были: химик, физик, математик, историк, экономист и философ. |
45 |
 |
Задача 6 (9 класс)Хим. Физ. Мат. Ист. Экон. Фил. Антон Владимир Евгений Игорь Константин Николай |
46 |
 |
Задача 6 (9 класс)В первом туре Евгений выиграл у химика, Антон – у физика, а Константин – у историка. Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? ? Владимир Евгений ? ? ? Игорь Константин ? ? ? Николай |
47 |
 |
Задача 6 (9 класс)Во втором туре Владимир выиграл у физика. В третьем и четвертом турах историк не участвовал в турнире по болезни, в связи с этим Владимир и Николай не играли. Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? ? Владимир ? ? Евгений ? ? ? Игорь Константин ? ? ? Николай ? |
48 |
 |
Задача 6 (9 класс)Значит, историк – это Игорь. Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? ? Владимир ? ? Евгений ? ? ? Игорь ? ? ? + ? ? Константин ? ? ? Николай ? |
49 |
 |
Задача 6 (9 класс)В четвертом туре Антон выиграл у экономиста. В финал турнира вышли Евгений и Антон. После завершения игр философ, занявший последнее место, воскликнул: «Главное не победа, а участие!». Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? ? ? ? Владимир ? ? Евгений ? ? ? ? Игорь ? ? ? + ? ? Константин ? ? ? Николай ? |
50 |
 |
Задача 6 (9 класс)Антон – математик, а Николай – физик. Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? + ? ? ? Владимир ? ? ? Евгений ? ? ? ? ? Игорь ? ? ? + ? ? Константин ? ? ? ? Николай ? + ? ? ? ? |
51 |
 |
Задача 6 (9 класс)Евгений – экономист. Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? + ? ? ? Владимир ? ? ? ? Евгений ? ? ? ? + ? Игорь ? ? ? + ? ? Константин ? ? ? ? ? Николай ? + ? ? ? ? |
52 |
 |
Задача 6 (9 класс)Владимир – химик, Константин – философ. Ответ: ВНАИЕК Хим. Физ. Мат. Ист. Экон. Фил. Антон ? ? + ? ? ? Владимир + ? ? ? ? ? Евгений ? ? ? ? + ? Игорь ? ? ? + ? ? Константин ? ? ? ? ? + Николай ? + ? ? ? ? |
53 |
 |
Задача 7 (9 класс)В системе счисления с основанием p выполнено равенство: B0B + AAC = CB1. Буквы A, B, и C обозначают цифры от 1 до 9 (но возможно, что p > 10), разным буквам соответствуют разные цифры. Найдите максимально возможное основание p и восстановите это равенство в числах. В ответ запишите число ABC. |
54 |
 |
Задача 7 (9 класс)B0B + AAC = CB1, B + C = 1p или B + C = 11p |
55 |
 |
Задача 7 (9 класс)B0B + AAC = CB1, B + C = 1p или B + C = 11p B = 0 или C = 0 невозможно |
56 |
 |
Задача 7 (9 класс)B0B + AAC = CB1, B + C = 11p = (p + 1)10 0 + A + 1 = bp или 0 + A + 1 = 1bp |
57 |
 |
Задача 7 (9 класс)B0B + AAC = CB1, B + C = p + 1 0 + A + 1 = bp или 0 + A + 1 = 1bp тогда B = 0 – невозможно |
58 |
 |
Задача 7 (9 класс)Система уравнений: B + C = p + 1, A + 1 = B, B + A = C. |
59 |
 |
Задача 7 (9 класс)Система уравнений: B + C = p + 1, A + 1 = B, – подставим в третье ур-е: B + A = C. 2A + 1 = C |
60 |
 |
Задача 7 (9 класс)Система уравнений: B + C = p + 1, A + 1 = B, – подставим в третье ур-е: B + A = C. 2A + 1 = C Далее B и C подставим в первое уравнение и находим: A + 1 + 2A + 1 = p + 1, A = (p – 1)/3. |
61 |
 |
Задача 7 (9 класс)Решение: A = (p – 1) / 3, B = (p + 2) / 3, C = (2p + 1) / 3. (2p + 1) / 3 ? 9 ? p ? 13. При p = 13 получаем A = 4, B = 5, C = 9. |
62 |
 |
Задача 1 (10-11 классы)В ячейке D6 число 25, найти A1. |
63 |
 |
Задача 1 (10-11 классы)Пусть в ячейке A1 число x. Тогда B3 = 2 + 2x, B6 = 7 + 2x, C6 = B6 + 2x = 7 + 4x, D6 = C6 + 2x = 7 + 6x = 25, x = 3 |
64 |
 |
Задача 2 (10-11 классы)Найдите наименьшие возможные основания x и y систем счисления, для которых выполнено равенство 22x + 33y = 65x–y. |
65 |
 |
Задача 2 (10-11 классы)Найдите наименьшие возможные основания x и y систем счисления, для которых выполнено равенство 22x + 33y = 65x–y. 2x + 2 + 3y + 3 = 6(x – y) + 5 2x + 3y + 5 = 6x – 6y + 5, 4x = 9y, y = 4x/9. |
66 |
 |
Задача 2 (10-11 классы)Найдите наименьшие возможные основания x и y систем счисления, для которых выполнено равенство 22x + 33y = 65x–y. 2x + 2 + 3y + 3 = 6(x – y) + 5 2x + 3y + 5 = 6x – 6y + 5, 4x = 9y, y = 4x/9. При x = 9 y = 4, но x – y = 5, цифр 6 и 5 не бывает. При x = 18 y = 8 – ответ. |
67 |
 |
Задача 3 (10-11 классы)Одна и та же цепочка символов является словом алфавита из 8 букв и словом алфавита из 64 букв. Во сколько раз информационный объем этого слова в первом случае меньше, чем во втором? |
68 |
 |
Задача 3 (10-11 классы)Пусть в цепочке n символов. Сколько таких цепочек? В 8-букв. алфавите: 8n = 23n, в 64-букв. алфавите: 64n = 26n. |
69 |
 |
Задача 3 (10-11 классы)Пусть в цепочке n символов. Сколько таких цепочек? В 8-букв. алфавите: 8n = 23n, в 64-букв. алфавите: 64n = 26n. Информационный объем: log2(кол-во цепочек). Ответ: 6n / 3n = 2. |
70 |
 |
Задача 4 (10-11 классы)Логические выражения F(x, y, z) и G(x, y, z) имеют указанные таблицы истинности. Сколько единиц в таблице истинности выражения H(x, y, z) = F( G(z, y, x), ?x, y?z ) ? x y z F G 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 |
71 |
 |
Задача 4 (10-11 классы)x y z F G G(z,y,x) 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 |
72 |
 |
Задача 4 (10-11 классы)x y z F G G(z,y,x) ?x y?z 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 |
73 |
 |
Задача 4 (10-11 классы)H(x, y, z) = F( g(z, y, x), ?x, y?z ), 6 единиц. x y z F G G(z,y,x) ?x y?z H 0 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 |
74 |
 |
Задача 5 (10-11 классы)c := a d := b нц для i := 1 до 3 a := a + b b := b – a кц вывод a + b + c + d Что будет выведено на экран? |
75 |
 |
Задача 5 (10-11 классы)C := a d := b нц для i := 1 до 3 i a b c d a := a + b до цикла x y x y b := b – a 1 x + y – x кц 2 y – x – y вывод a + b + c + d 3 – x – y a + b + c + d = – x – y + x + y = 0. |
76 |
 |
Задача 6 (10-11 классы)Дана блок-схема программы, которая работает с массивом целых чисел A[1:10]. Элементы массива равны 5, 4, 8, 6, 1, 10, 8, 9, 7, 6. Укажите наименьшее целое число, при вводе которого программа остановится, и результат работы при этом будет максимальный. |
77 |
 |
Задача 6 (10-11 классы)Элементы массива A[1:10] равны: 5, 4, 8, 6, 1, 10, 8, 9, 7, 6. |
78 |
 |
Задача 6 (10-11 классы)Основная часть – это цикл. i – счетчик итераций, k – рабочая переменная. |
79 |
 |
Задача 6 (10-11 классы)Основная часть – это цикл. i – счетчик итераций, k – рабочая переменная. Действие в цикле: k := A[k]. Выход из цикла: k вернется к исходному значению. |
80 |
 |
Задача 6 (10-11 классы)Основная часть – это цикл. i – счетчик итераций, k – рабочая переменная. Действие в цикле: k := A[k]. Выход из цикла: k вернется к исходному значению. Результат: число итераций. |
81 |
 |
Задача 6 (10-11 классы)Элементы массива A: i 1 2 3 4 5 6 7 8 9 10 A[i] 5, 4, 8, 6, 1, 10, 8, 9, 7, 6. k := A[k] – как изменяется значение k? |
82 |
 |
Задача 6 (10-11 классы)Элементы массива A: i 1 2 3 4 5 6 7 8 9 10 A[i] 5, 4, 8, 6, 1, 10, 8, 9, 7, 6. k := A[k] |
83 |
 |
Задача 6 (10-11 классы)Элементы массива A: i 1 2 3 4 5 6 7 8 9 10 A[i] 5, 4, 8, 6, 1, 10, 8, 9, 7, 6. k := A[k] |
84 |
 |
Задача 6 (10-11 классы)Элементы массива A: i 1 2 3 4 5 6 7 8 9 10 A[i] 5, 4, 8, 6, 1, 10, 8, 9, 7, 6. k := A[k] |
85 |
 |
Задача 6 (10-11 классы)Укажите наименьшее целое число, при вводе которого программа остановится, и результат работы при этом будет максимальный. |
86 |
 |
Задача 6 (10-11 классы)n = 1 – результат 2, n = 2 – зацикливание, … … … … n = 7, 8, 9 – результат 3 (максимальный), наименьшее n с результатом 3 равно 7. Ответ: 7. |
87 |
 |
Задача 7 (10-11 классы)mod(m, n) – остаток от деления m на n Что будет в результате работы, если введено число 20? Ввод N k := 0 нц для i := 1 до N нц для j := 1 до N если mod(i, 2) = mod(j, 3) то k := k + 1 все кц кц вывод k |
88 |
 |
Двойной цикл перебирает все пары чисел (i, j), i, j = 1 … 20 исравнивает остатки mod(i, 2) и mod(j, 3). |
89 |
 |
Двойной цикл перебирает все пары чисел (i, j), i, j = 1 … 20 исравнивает остатки mod(i, 2) и mod(j, 3). mod(i, 2) = 0, таких i 10 штук. Нужны j, которые делятся на 3: 3, 6, 9, 12, 15, 18 – 6 штук для каждого i, а всего 60 пар чисел. |
90 |
 |
Двойной цикл перебирает все пары чисел (i, j), i, j = 1 … 20 исравнивает остатки mod(i, 2) и mod(j, 3). mod(i, 2) = 0, таких i 10 штук. Нужны j, которые делятся на 3: 3, 6, 9, 12, 15, 18 – 6 штук для каждого i, а всего 60 пар чисел. 2) mod(i, 2) = 1, таких i тоже 10 штук. Нужны j с mod(j, 3) = 1: 1, 4, 7, 10, 13, 16, 19 – 7 штук для каждого i, а всего 70 пар чисел. Итого 130 . |
91 |
 |
Задача 8 (10-11 классы)A := 0 b := N m := T [1, N] res := N нц пока b > 1 s := 0 нц для i := 1 до b s := s + T [i, i + a] кц Если m < s то m := s res := a + 1 все a := a + 1 b := b – 1 кц вывод res -------------------------------------------- N = 5, таблица T задана, укажите результат работы. |
92 |
 |
Задача 8 (10-11 классы)a = 0, b = 5, s = 5 A := 0 b := N m := T [1, N] res := N нц пока b > 1 s := 0 нц для i := 1 до b s := s + T [i, i + a] кц ……….. T = T = T = T = T = 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 |
93 |
 |
Задача 8 (10-11 классы)a = 0, b = 5, s = 5 a = 1, b = 4, ……….. Если m < s то m := s res := a + 1 все a := a + 1 b := b – 1 кц вывод res T = T = T = T = T = 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 |
94 |
 |
Задача 8 (10-11 классы)a = 0, b = 5, s = 5 a = 1, b = 4, s = 8 A := 0 b := N m := T [1, N] res := N нц пока b > 1 s := 0 нц для i := 1 до b s := s + T [i, i + a] кц ……….. T = T = T = T = T = 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 |
95 |
 |
Задача 8 (10-11 классы)a = 0, b = 5, s = 5 a = 1, b = 4, s = 8 a = 2, b = 3, A := 0 b := N m := T [1, N] res := N нц пока b > 1 s := 0 нц для i := 1 до b s := s + T [i, i + a] кц ……….. T = T = T = T = T = 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 |
96 |
 |
Задача 8 (10-11 классы)a = 0, b = 5, s = 5 a = 1, b = 4, s = 8 a = 2, b = 3, s = 9 a = 3, b = 2, s = 8 A := 0 b := N m := T [1, N] res := N нц пока b > 1 s := 0 нц для i := 1 до b s := s + T [i, i + a] кц ……….. T = T = T = T = T = 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 |
97 |
 |
Задача 8 (10-11 классы)a = 0, b = 5, s = 5 a = 1, b = 4, s = 8 a = 2, b = 3, s = 9 a = 3, b = 2, s = 8 Результат работы = 3. ……….. Если m < s то m := s res := a + 1 все a := a + 1 b := b – 1 кц вывод res T = T = T = T = T = 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 |
98 |
 |
Задача 9 (10-11 классы)БИТ_И(x, y) -- операция «побитовое И». К каждой паре соответствующих двоичных разрядов x и y применяется логическое И. Пример: x = 110100012 y = 010110012 Бит_и(x, y) = 010100012 = 8110 |
99 |
 |
Задача 9 (10-11 классы)если s >= b то b := s res := A[i] все кц вывод res --------------------------------------------------- Массив A[1:N]: 1, 53, 129, 192, 15, 68, 7, 168, 82, 224. Массив M[1:8]: 1, 2, 4, 8, 16, 32, 64, 128. Результат работы программы? N := 10 b := –1 res := 0 нц для i := 1 до N s := 0 нц для j := 1 до 8 если БИТ_И( A[i], M[j] ) > 0 то s := s + 1 все кц |
100 |
 |
Задача 9 (10-11 классы)………… нц для j := 1 до 8 если БИТ_И( A[i], M[j] ) > 0 то s := s + 1 все кц ………… Что подсчитывает этот цикл? Элементы массива M – степени 2. 1 = 20 = 000000012, 2 = 21 = 000000102, 4 = 22 = 000001002, ……… 128 = 27 = 100000002. Чему равно БИТ_И(x, 2j)? |
101 |
 |
Задача 9 (10-11 классы)………… нц для j := 1 до 8 если БИТ_И( A[i], M[j] ) > 0 то s := s + 1 все кц ………… Что подсчитывает этот цикл? Элементы массива M – степени 2. 1 = 20 = 000000012, 2 = 21 = 000000102, 4 = 22 = 000001002, ……… 128 = 27 = 100000002. БИТ_И(x, 2j), пример: x = 1101*0012 2j = 000010002 Бит_и(x, 2j ) = 0000*0002 |
102 |
 |
Задача 9 (10-11 классы)………… нц для j := 1 до 8 если БИТ_И( A[i], M[j] ) > 0 то s := s + 1 все кц ………… Что подсчитывает этот цикл? БИТ_И(x, 2j) > 0 ? j-й бит числа x равен 1 |
103 |
 |
Задача 9 (10-11 классы)………… нц для j := 1 до 8 если БИТ_И( A[i], M[j] ) > 0 то s := s + 1 все кц ………… Что подсчитывает этот цикл? БИТ_И(x, 2j) > 0 ? j-й бит числа x равен 1 БИТ_И( A[i], M[j] ) > 0 ? j-й двоичный разряд числа A[i] равен 1 Цикл считает число единиц в двоичной записи A[i]. |
104 |
 |
Задача 9 (10-11 классы)N := 10 b := –1 res := 0 нц для i := 1 до N | s := число 1 в a[i] ……… если s >= b то b := s res := a[i] все кц вывод res B – максимальное число 1 в элементах массива A, res – элемент a[i], соответствующий b (последний такой, если их несколько). |
105 |
 |
Задача 9 (10-11 классы)Массив A: 1, 53, 129, 192, 15, 68, 7, 168, 82, 224. 1 = 20 = 000000012, 53 = 32 + 16 + 4 + 1 = 25 + 24 + 22 + 20 = 001101012, 129 = 128 + 1, 192 = 128 + 64, 15 = 8 + 4 + 2 + 1, 68 = 64 + 4, 7 = 4 + 2 + 1, 168 = 128 + 32 + 8, 82 = 64 + 16 + 2, 224 = 128 + 64 + 32. 4 двоичные 1 в числах 53 и 15. Ответ: 15. |
106 |
 |
Задача 10 (10-11 классы)алг ПОИСК(цел x, цел y) нач если x + y > 10 то вывод ?(?, x, ?, ?, y, ?)? иначе ПОИСК(x + 5, y – 2) ПОИСК(x + 1, y + 1) все кон Результат работы ПОИСК(2,1) (кол-во пар чисел на экране) ? |
107 |
 |
Задача 10 (10-11 классы)…….. Поиск(x + 5, y – 2) поиск(x + 1, y + 1) ……… Поиск(2,1) |
108 |
 |
Задача 10 (10-11 классы)…….. Поиск(x + 5, y – 2) поиск(x + 1, y + 1) ……… ПОИСК(2,1) ……………. Ответ: 12 |
109 |
 |
Спасибо за внимание |
«Методические требования к подготовке школьников, участвующих в интеллектуальных турнирах по информатике» |
http://900igr.net/prezentacija/informatika/metodicheskie-trebovanija-k-podgotovke-shkolnikov-uchastvujuschikh-v-intellektualnykh-turnirakh-po-informatike-81729.html