В мире информатики и математики: Факультатив

пятница, 23 декабря 2016 г.

Факультатив_11 класс

1. Найти сумму чисел X=110111₂ и Y=135₈. Ответ запишите в двоичной системе счисления.

2. Дан фрагмент таблицы истинности выражения F:

x1	x2	x3	x4	x5	x6	F
0	1	0	1	1	1	1
1	0	1	0	1	1	0
0	1	0	1	1	0	1

Каким выражением может быть F?

1) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6

2) ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ ¬x6

3) x1 ∧ x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ x6

4) ¬x1 ∧ ¬x2 ∧ x3 ∧ x4 ∧ x5 ∧ x6

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

	П1	П2	П3	П4	П5	П6	П7
П1		57		20		25
П2	57		22	42	8		21
П3		22			23		8
П4	20	42				7	33
П5		8	23
П6	25			7			9
П7		21	8	33		9

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

4. Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы:

Символ «?» (вопросительный знак) означает ровно один произвольный символ.

Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

Определите, какое из указанных имён файлов НЕ удовлетворяет маске: ?ell*.??

1) yell.ow

2) fellow.rа

3) tell_me.tu

4) bell.lab

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 1011; В – 100; Г – 111; Д – 1010. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.

Каким из указанных способов это можно сделать?

1) это невозможно

2) для буквы Б – 10

3) для буквы В – 00

4) для буквы Г – 11

6. На экране есть два окна, в каждом из которых записано по числу. Исполнитель СУММАТОР имеет только две команды, которым присвоены номера:

1. Запиши сумму чисел в первое окно

2. Запиши сумму чисел во второе окно

Выполняя команду номер 1, СУММАТОР складывает числа в двух окнах и записывает результат в первое окно, а выполняя команду номер 2, заменяет этой суммой число во втором окне. Напишите программу, содержащую не более 5 команд, которая из пары чисел 1 и 2 получает пару чисел 13 и 4. Укажите лишь номера команд.

Например, программа 21211 – это программа:

Запиши сумму чисел во второе окно

Запиши сумму чисел в первое окно

Запиши сумму чисел во второе окно

Запиши сумму чисел в первое окно

которая преобразует пару чисел 1 и 0 в пару чисел 8 и 3.

7. На предприятии работают 100 человек. Каждый из них владеет как минимум одним иностранным языком (английским, немецким или французским). На следующей диаграмме отражено количество человек, владеющих каждым из языков.

Вторая диаграмма отражает количество человек, знающих только один язык, только два языка или все три иностранных языка.

Определить количество человек, владеющих только английским языком, если говорят на английском и немецком, но не знают французского 2 человека.

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

Бейсик	Паскаль
DIM N, S AS INTEGER N = 24 S = 0 WHILE N <= 28 S = S + 20 N = N + 2 WEND PRINTS	var n, s: integer; begin n := 24; s := 0; while n <= 28 do begin s := s + 20; n := n + 2 end; write(s) end.
Си	Алгоритмический язык
#include <stdio.h> void main() { int n, s; n = 24; s = 0; while (n <= 28) { s = s + 20; n = n + 2; } printf("%d", s); }	алг нач цел n, s n := 24 s := 0 нц пока n <= 28 s := s + 20 n := n + 2 кц вывод s кон

9. Производится четырёхканальная (квадро) звукозапись с частотой дискретизации 48 кГц и 32-битным разрешением. Запись длится 2 минуты, её результаты записываются в файл, сжатие данных не производится. Какая из приведённых ниже величин наиболее близка к размеру полученного файла?

1) 15 Мбайт

2) 27 Мбайт

3) 42 Мбайт

4) 88 Мбайт

10. Все 4-буквенные слова, составленные из букв В, И, Р, Т, записаны в алфавитном порядке.

Вот начало списка:

1. ВВВВ

2. ВВВИ

3. ВВВР

4. ВВВТ

5. ВВИВ

……

Запишите слово, которое стоит на 249-м месте от начала списка.

11. Последовательность чисел Фибоначчи задается рекуррентным соотношением:

F(1) = 1

F(2) = 1

F(n) = F(n–2) + F(n–1), при n >2, где n – натуральное число.

Чему равно восьмое число в последовательности Фибоначчи?

В ответе запишите только натуральное число.

12. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети.

IP-адрес узла: 208.64.195.128

Маска: 255.255.224.0

При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса сети и запишите в нужном порядке соответствующие им буквы без использования точек.

A	B	C	D	E	F	G	H
0	64	128	192	195	208	224	255

Пример. Пусть искомый IP-адрес: 192.168.128.0, и дана таблица:

A	B	C	D	E	F	G	H
128	168	255	8	127	0	17	192

В этом случае правильный ответ будет записан в виде: HBAF.

13. В марафонском забеге участвуют 87 человек. Специальное устройство регистрирует прохождение каждым участником некоторой промежуточной отметки, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого участника. Каков информационный объем сообщения, записанного устройством, если данную промежуточную отметку миновали только 64 из 87 вышедших на старт участников? (Ответ дайте в байтах.)

14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (111, 27)
преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл
  ПОКА условие
    последовательность команд
  КОНЕЦ ПОКА
выполняется, пока условие истинно.

В конструкции

  ЕСЛИ условие
    ТО команда1
    ИНАЧЕ команда2
  КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Ниже приведена программа для исполнителя Редактор.

НАЧАЛО

ПОКА нашлось (722) ИЛИ нашлось (557)

  ЕСЛИ нашлось (722)
    ТО заменить (722, 57)
    ИНАЧЕ заменить (557, 72)
  КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

На вход этой программе подается строка, состоящая из 55 цифр; последняя цифра в строке — цифра 7, а остальные цифры — пятёрки. Какая строка получится в результате применения программы к этой строке? В ответе запишите полученную строку.

15. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город Т?

16. Запишите число 128 в пятеричной системе счисления. В ответе укажите только цифры, основание системы счисления писать не нужно.

17. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в тысячах)
Мороз \| Солнце	3300
Солнце	2000
Мороз & Солнце	200

Какое количество страниц (в тысячах) будет найдено по запросу Мороз? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

18. Для какого из приведённых чисел X истинно логическое условие: ¬((X кратно 5) $\text{[math]}$ (X кратно 25))?

1) 37

2) 59

3) 65

4) 125

19. В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, в котором значения элементов массива сначала задаются, а затем меняются.

for i : = 0 to 10 do
A[i] : = i;
for i : = 0 to 5 do begin
A[10-i] : = A[9-i];
A[i] : = A[i+1];
end;

Чему будут равны элементы этого массива?

1) 0 1 2 3 4 5 6 7 8 9 10

2) 0 1 2 3 4 5 6 7 8 9 9

3) 1 2 3 4 5 5 5 6 7 8 9

4) 1 2 3 4 5 6 5 4 3 2 1

20. Ниже на четырёх языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 13, а потом 5.

Бейсик	Паскаль
DIM X, A, B, C AS INTEGER INPUT X A = 0: B = 10 WHILE X > 0 C = X MOD 10 A = A + C IF C < B THEN B = C X = X \ 10 WEND PRINT A PRINT B	var x, a, b, c: integer; begin readln(x); a := 0; b := 10; while x>0 do begin c := x mod 10; a := a+c; if c < b then b := c; x := x div 10; end; writeln(a); write(b); end.
Си	Алгоритмический
#include <stdio.h> void main() { int x, a, b, c; scanf("%d", &x); a = 0; b = 10; while (x>0) { c = x%10; a = a+c; if (c<b) b = c; x = x/10; } printf("%d\n%d", a, b); }	алг нач цел x, a, b, c ввод x a := 0; b := 10 нц пока x>0 c := mod(x,10) a := a+c если c<b то b := c все x := div(x,10) кц вывод a, нс, b кон

21. При каком наименьшем значении входной переменной k программа выдаёт тот же ответ, что и при входном значении k = 64? Для Вашего удобства программа приведена на пяти языках программирования.

Бейсик	Python
DIM K, I AS LONG INPUT K I = 12 WHILE I > 0 AND F(I) >= K I = I - 1 WEND PRINT I FUNCTION F(N) F = N * N - 20 END FUNCTION	def f(n): return n * n - 20 k = int(input()) i = 12 while i > 0 and f(i) >= k: i = i - 1 print(i)
Алгоритмический язык	Паскаль
алг нач цел i, k ввод k i := 12 нц пока i > 0 и f(i) >= k i := i - 1 кц вывод i кон алг цел f(цел n) нач знач := n * n - 20 кон	var k, i : longint; function f(n: longint) : longint; begin f := n * n - 20 end; begin readln(k); i := 12; while (i>0) and (f(i) >= k) do i := i-1; writeln(i) end.
Си
#include <stdio.h> long f(long n) { return n * n - 20; } int main() { long k, i; scanf("%ld", &k); i = 12; while (i > 0 && f(i) >= k) i––; printf("%ld", i); return 0; }

22. У исполнителя Увеличитель две команды, которым присвоены номера:

1. прибавь 2,

2. умножь на 3.

Первая из них увеличивает число на экране на 2, вторая — умножает его на 3.

Программа для Увеличителя — это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 59?

Ответ обоснуйте.

23. Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
…
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
(x7 ∨ y7) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ..., x7, y1, y2, ..., y7, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

24. Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x — действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). Программист торопился и написал программу неправильно.

Бейсик	Паскаль
INPUT x IF x>=-3 THEN IF x<=9 THEN IF x>1 THEN PRINT "не принадлежит" ELSE PRINT "принадлежит" ENDIF ENDIF ENDIF END	var x: real; begin readln(x); if x>=-3 then if x<=9 then if x>1 then write('не принадлежит') else write('принадлежит') end.
Си	Алгоритмический язык
void main(void) { float x; scanf("%f",&x); if(x>=-3) if(x<=9) if(x>1) printf("не принадлежит"); else printf("принадлежит"); }	алг нач вещ x ввод x если x>=-3 то если x<=9 то если x>1 то вывод 'не принадлежит' иначе вывод 'принадлежит' все все все кон

Последовательно выполните следующее.

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 1, 5 и 9) принадлежат заштрихованным областям (B и D соответственно).

В столбцах условий укажите «Да», если условие выполнится; «Нет», если условие не выполнится; «—» (прочерк), если условие не будет проверяться; «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите «—» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет».

2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

Область	Условие 1 (x >= –3)	Условие 2 (x <= 9)	Условие 3 (x > 1)	Программа выведет	Область обрабатывается верно
A
B
C
D
E

25. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от -1000 до 1000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди положительных элементов массива, кратных 4. Если в исходном массиве нет элемента, значение которого положительно и делится на 4, то вывести сообщение «Не найдено».

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Бэйсик	Паскаль
N = 20 DIM A(N) AS INTEGER DIM I, J, MIN AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END	const N = 20; var a: array [1..N] of integer; i, j, min: integer; begin for i := 1 to N do readln(a[i]); ... end.
Си	Алгоритмический язык
#include <stdio.h> #define N 20 void main() { int a[N]; int i, j, min; for (i = 0; i < N; i++) scanf("%d", &a[i]); ... }	алг нач цел N = 20 целтаб a[1:N] цел i, j, min нц для i от 1 до N ввод a[i] кц ... кон
Естественный язык
Объявляем массив А из 20 элементов. Объявляем целочисленные переменные I, J, MIN. В цикле от 1 до 20 вводим элементы массива А с 1-го по 20-й.

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

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучуодин или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 40 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 39.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

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

2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.

3. Укажите значение S, при котором:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.

27. Последовательность натуральных чисел характеризуется числом Y – наибольшим числом, кратным 26 и являющимся произведением двух элементов последовательности с различными номерами.

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), находящую число Y для последовательности натуральных чисел, значение каждого элемента которой не превосходит 1000. Программа должна напечатать найденное число, если оно существует для заданной последовательности, или ноль в противном случае.

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Пример входных данных:

100

130

Пример выходных данных для приведённого выше примера входных данных: 13000

Разделы

пятница, 23 декабря 2016 г.

Факультатив_11 класс

Комментариев нет:

Отправить комментарий

7 класс

	П1	П2	П3	П4	П5	П6	П7
П1		57		20		25
П2	57		22	42	8		21
П3		22			23		8
П4	20	42				7	33
П5		8	23
П6	25			7			9
П7		21	8	33		9

	П1	П2	П3	П4	П5	П6	П7
П1		57		20		25
П2	57		22	42	8		21
П3		22			23		8
П4	20	42				7	33
П5		8	23
П6	25			7			9
П7		21	8	33		9

Разделы

пятница, 23 декабря 2016 г.

Факультатив_11 класс

Комментариев нет:

Отправить комментарий

пятница, 23 декабря 2016 г.

	П1	П2	П3	П4	П5	П6	П7
П1		57		20		25
П2	57		22	42	8		21
П3		22			23		8
П4	20	42				7	33
П5		8	23
П6	25			7			9
П7		21	8	33		9