Вы можете поддержать наш проект и автора курса?
Ответ: 3
Группа заданий B
В1. Если в некоторой системе счисления десятичное число 47 записывается в виде 52, то чему равно основание этой системы?
Решение. Пусть основание равно р. Тогда (52)р = (5р + 2)10 = (47)10. Решая уравнение 5р + 2 = 47, получаем р = 9.
Ответ: 9
В2. Найти число решений уравнения (число различных комбинаций значений логических переменных), сами значения можно не находить:
.
Решение. Выражение представляет произведение двух условий, поэтому будет равно 1 (истине) тогда и только тогда, когда оба множителя равны 1. Следовательно, t = 1 и выражение в скобках должно быть равно 1. Так как выражение в скобках представляет собой сумму двух слагаемых, то для его равенства 1 необходимо, чтобы хотя бы одно из слагаемых было равно 1. Первое слагаемое равно 0 при любом значении x, так как t = 1. Второе слагаемое равнои может равняться 1 лишь тогда, когда y = 0 и z = 1. Итак, будет всего два различных решения уравнения, а именно, (x, y, z, t) = (0, 0, 1, 1), (1, 0, 1, 1). Замечание: можно было бы найти количество всех комбинаций переменных, равное 16 и отнять от него число решений уравнения с правой частью равной нулю (сравните эти два подхода по сложности).
Ответ: 2.
В3. Дан исполнитель Вычислитель с единственной командой вида: Удвоить(а) — сложить целое число a с самим собой и заменить значение числа a этой полученной суммой. Запишите наиболее короткую программу исполнителя для получения из a = 2 и b = 3 значений a = 64, b = 96.
Решение. Представим искомые числа в виде:
64 = 2(2(2(2(2(2))))) = Удвоить(Удвоить(Удвоить(Удвоить(Удвоить(а))))),
96 = 2(2(2(2(2(3))))) = Удвоить(Удвоить(Удвоить(Удвоить(Удвоить(b))))).
Тело алгоритма можно составить следующим образом:
нц для i от 1 до 5 Удвоить(a) Удвоить(b) кц
Возможны и другие варианты, например:
нц пока (iОтвет:алг В3(арг цел a,b, рез цел a,b) нач ввод(a,b) нц для i от 1 до 5 Удвоить(a) Удвоить(b) кц вывод( значения a и b равны: ,a,b) кон
B4. Некто А — отличник, у Б — пятерка или пропуск занятия, у В — четверка или тройка, у Г — возможны все оценки и даже пропуск занятий, у Д — пропуск или тройка. Какая оценка у каждого из них, если один отсутствовал на занятии, а все остальные получили различные оценки?
Решение. Составим и заполним таблицу всех разрешенных ситуации (таблицу возможностей):
| А | Б | В | Г | Д | |
| + | + | — | + | — | |
| — | — | + | + | — | |
| — | — | + | + | + | |
| — | — | — | + | — | |
| — | + | — | + | + |
Из этой таблицы видно, что А получил 5, поэтому, Б мог только пропустить занятие, Д — оценка 3, В — оценка 4, Г — оценка 2.
Ответ: А — 5, Б — пропуск, Д — 3, В — 4, Г — 2.
В5. После того, как пользователь интернет по телефонному каналу подключения скачивает (с помощью модема, работающего непрерывно со скоростью 16384 бит/сек) каждый раз более 16 Мегабайт, непрерывное подключение к сети прерывается из-за технических ограничений провайдера. Сколько сек. непрерывно может работать в сети пользователь?
Решение. Объем непрерывной скачиваемой за раз информации равен 227 бит. Скорость модема равна 214 бит/сек. Время работы равно 213 сек.
Ответ: 213 сек. или около 2,5 часа.
В6. Какое число будет стоять на 9-ом месте в образованной по одному правилу последовательности битовых сигналов (в каждом следующем битовом сигнале на одну десятичную цифру больше):
001, 001010, 001010011, 001010011100, ….
Решение. Так как в каждом новом сигнале число десятичных цифр увеличивается на единицу, то каждая тройка битов кодирует одну десятичную цифру. Переведем тройки битов в десятичную систему и получим последовательность сообщений: 1, 12, 123, 1234 и т. д.
Ответ: 123456789
В7. Файл с именем f и с наиболее распространенным расширением Word скачивается по протоколу передачи файлов с сервера интернет-узла с доменом второго уровня gsa в коммерческих сетях США. Запишите полностью URL скачиваемого файла, если он не использует других доменов (уровней), кроме как упомянутых в условии.
Решение. Наиболее распространённое расширение в редакторе Word — doc. Протокол передачи (пересылки) файлов — ftp (File Transport Protocol), домен (первого уровня) коммерческих сетей США — com. Так как это интернет-узел, то должен присутствовать в полном имени ресурса и домен www. Итак, полное имя ресурса — ftp://www.gsa.com/f.doc.
Ответ: ftp://www.gsa.com/f.doc.
В8. Для поиска в интернет материалов о событиях первенства России с участием команды Спартак или команды Динамо были сформулированы 4 запроса:
- первенство России (Спартак | Динамо);
- первенство России (СпартакДинамо);
- первенство России (Спартак | Динамо);
- первенство России | Спартак| Динамо.
Расположить поисковые запросы по убыванию количества интернет — страниц, которые будут найдены по этим запросам. Какой из запросов наиболее адекватен целям поискового запроса? Какую семантическую неточность можете указать во всех запросах?
Решение. Так каксоответствует и, а | — или, то запрос 1) найдёт все ресурсы с информацией о первенстве России, в которых упоминаются слова Спартак или Динамо. Сюда войдут, например, и события с упоминанием футболистов по имени Спартак (если такие найдутся). Запрос 2) найдёт все ресурсы с информацией о первенстве России, в которых упоминаются команды Спартак и Динамо. Запрос 3) найдёт все ресурсы с информацией о первенстве России, а также о команде Спартак или команде Динамо. Запрос 4) найдёт все ресурсы с информацией или о первенстве России, или о команде Спартак (о всех Спартаках), или о команде Динамо (о всех Динамо). Если расположить эти запросы по убыванию страниц, то получим: 4), 1), 3), 2). Наиболее адекватный целям поиска запрос — 3). Во всех запросах не указан вид соревнований (футбол или хоккей, например).
Ответ: ранжированный по убыванию количества найденных страниц ряд запросов имеет вид — 4), 1), 3), 2), а наиболее адекватный поставленным целям запрос — 3). Семантическая неточность — не указан вид соревнований.
Группа заданий C
С1. Требовалось написать алгоритм (программу) подсчета всех натуральных чисел n, кратных 7 и заключенных строго между натуральными числами a и b. Входная информация вводится с клавиатуры, а на выходе должно быть получено сообщение, например, вида искомое число равно 12 (если есть 12 таких кратных чисел) или искомое число равно 0 (если нет кратных чисел). Некто, в спешке, написал следующий алгоритм (следующую программу):
ШАЯ:
алг С1(арг цел a, b, рез цел n)нач цел c вывод(введите a, b:) ввод(a,b) n:=0 если (a=b) и (mod(а,7)=0) то n:=n+1 иначе нц для c от a до b если (mod(с,7)=0) то n:=n+1 все кц все вывод(искомое число равно ,n)кон
Паскаль:
var a, b, c, n: integer;begin write(‘введите a, b:’); read(a,b); n:=0; if (a=b) and (a mod 7=0) then n:=n+1 else for c:=a to b do if (с mod 7=0) then n:=n+1; write(‘искомое число равно ‘,n);end.
Бейсик:
dim a, b, c, n as integer print ‘введите a, b:’ input a,b n = 0 if (a = b) and (a MOD 7=0) then n = n + 1 else for c = a to b if (с MOD 7 = 0) then n = n + 1 end if next c end if print искомое число равно , nend.
Для такой программы последовательно выполните три задания:
- Укажите наборвходных чисел a, b, для которогопрограмма работает неправильно.
- Укажите любойвариант доработки программы (удаления, добавления, изменения команд),чтобы не было случаев её неправильной работы.
- Укажитевариант доработки программы без использования логических операций (and, or, not).
Решение.
- Программа небудет работать для всех тестов, удовлетворяющих условию b
- Приводимвариант доработки программы, чтобы не было случаев её неправильной работы.
ШАЯ:
алг С1(арг цел a, b, рез цел n)нач цел c вывод(введите a, b:) ввод(a,b) n:=0 если (a=b) и (mod(а,7)=0) то n:=n+1 иначе если (a?b) то если (ab) то c:=a a:=b b:=a все нц для c от a до b если (mod(с,7)=0) то n:=n+1 все кц все все вывод(искомое число равно , n)кон
Паскаль:
var a, b, c, n: integer;begin write(‘введите a, b:’); read(a,b); n:=0; if (a=b) and (a mod 7=0) then n:=n+1 else if (ab) then begin if (ab) then begin c:=a; a:=b; b:=a end; for c:=a to b do if (с mod 7=0) then n:=n+1 end; write(‘искомое число равно ‘,n);end.
Бейсик:
dim a, b, c, n as integer print введите a, b: input a,b n = 0 if (a = b) and (a MOD 7=0) then n = n + 1 else if (ab) then if (ab) then c = a: a = b: b = a for c = a to b if (с MOD 7 = 0) then n = n + 1 end if next c end if end if end if print искомое число равно , nend.
- Вариантдоработки программы без использования логических операций (and, or, not) можнополучить из предыдущих вариантов, если заменить условие (например, наБейсике; для остальных версий — аналогично):
if (a = b) and (a MOD 7=0) then :
на условие вида
if (a = b) then if (a MOD 7=0) then : .
С2. Для заданного числового массива (ряда чисел) составить алгоритм нахождения m — максимума среди элементов массива, находящихся на нечетных местах (то есть среди x1, x3, x5 и т. д.) и k — минимума среди элементов массива, находящихся на четных местах (то есть среди x2, x4, x6 и т. д.).
Решение. Алгоритм запишем на языках ШАЯ, Паскаль, Бейсик.
ШАЯ:
алг С2(арг цел n, таб х[1:n], рез цел m,k) нач цел i ввод(n) нц для i от 1 до n ввод(x[i]) кц i:=1 k:=x[2] m:=x[1] нц пока (iПаскаль:var n, k, m: integer; x: array[1..100] of integer; begin readln(n); for i:=1 to n do read(x[i]); i:=1; k:=x[2]; m:=x[1]; while (iБейсик:dim k, n, i, x(100) as integer input n for i = 1 to n input x(i) next i i = 1 k = x(2) m = x(1) while (in) if (mx(i+1)) then k = x(i+1) end if i = i + 2 wend if (n MOD 2 = 1) then if (mx(n)) then m = x(n) end if end if printk=,m,m=,m end.
С3. Два игрока играют в игру со следующими правилами: имея достаточный запас монет (диаметром d см), каждый из них кладет по очереди одну монету на стол размером а и b (см). Проигрывает тот игрок, которому некуда класть очередную монету. Монета должна опираться своей полной площадью на стол (не допускается свисание монеты). Можно перемещать монету, соблюдая это условие. Описать стратегию выигрышной игры (как начинать и как ходить игроку для выигрыша).
Решение. Определим, сколько монет поместится максимально (без свисания) на столе. По стороне длины a это количество равно n=int(a/d), а по стороне b — равно m=int(b/d). Общее количество монет равно k=nm. Все зависит от четности (нечетности) этого числа. Если k — нечетно, то выигрывает всегда тот, кто ходит первым, а если k — четно, то он проигрывает всегда. Стратегия хода проста: каждый раз к монете второго игрока (после его хода) нужно приставлять по длине или ширине стола свою монету в этом ряду или начинать новый ряд (если предыдущий ряд уже заполнен).
С4. Составить алгоритм удаления из заданного текста a всех символов, расположенных на нечетных местах другого заданного текста b.
Решение. Алгоритм (ШАЯ, Паскаль, Бейсик) запишется следующим образом.
ШАЯ:
алг C4(арг лит a, b, рез лит a)дано | текст a и текст bнадо | из текста a удалить все символы, входящие в текст b и расположенные | на нечетных позициях текста bнач | начало алгоритма цел i, | количество символов текста a j, | количество символов текста b d, | длина текста b m | длина текста аввод(a,b) | ввод исходных текстовm:=длина(a) | переменной m присваиваится длина ad:=длина(b) | переменной d присваиваится длина bi:=1 | начальный номер символа aнц пока (iПрограмма на Паскале (не комментируем и записываем компактно): var d, m, i, j: integer; a, b: string;begin readln(a,b); m:=length(a); d:=length(b); i:=1; while (iПрограмма на Бейсике (не комментируем и записываем компактно): dim d, m, i, j as integer a, b as string input a, b m = length(a) d = length(b) i = 1 while (im) j = 1 while (jd + 1) if (a(i) = b(j)) then for k = i to m — 1: a(k) = a(k + 1): next k: m = m — 1 end if j = j + 2 wend i = i + 1 wend print(результирующий текст:, a) end.
Минимум теоретических сведений по школьной информатике Информатика — это междисциплинарная,методологическая наука об информационных процессах, о моделях, об алгоритмахи алгоритмизации, о программах и программировании, об исполнителях алгоритмови различных исполняющих системах, об их использовании в обществе, в природе,в познании. Информация — это некоторая упорядоченнаяпоследовательность сообщений, отражающих, передающих, увеличивающих нашизнания. Приведём основные соотношения между единицамиизмерения сообщений: 1 бит (binary digit -двоичная единица) = 0 или 1, 1 байт = 8 битов, 1 килобайт (1Кб) = 213бит, 1 мегабайт (1Мб) = 223бит, 1 гигабайт (1Гб) = 233бит, Мера информации — критерий оценки количестваинформации, разнообразия и определенности в информационной системе. Пусть известны Nсостояний системы S (Nопытов с различными, равновозможными, последовательными состояниями системы).Если каждое состояние системы закодировать двоичными кодами, то мераразнообразия состояний системы (мера количества информации) задаётся формулойР. Хартли: H=log2N (бит). Код — правило соответствия набора знаков одногомножества Х знакам другого множества Y. Если каждому символу Х при кодировании соответствует отдельный знак Y, то это кодирование. Если для каждого символа из Yнайдется по некоторому правилу однозначно его прообраз в X, то это правило называется декодированием. При представлении сообщений в ЭВМ все символыкодируются байтами. Сообщение, котороемы хотим передать адресату, назовём открытымсообщением. Зашифрованное сообщение может быть построено наддругим алфавитом. Назовём его закрытым сообщением. Процесспреобразования открытого сообщения в закрытое сообщение и есть шифрование. Любая система счисления — это система кодирования числовыхвеличин (количеств), позволяющая выполнять операции кодирования идекодирования, то есть по любой количественной величине однозначно находитьего кодовое представление и по любой кодовой записи — восстанавливатьсоответствующую ей числовую величину. Все системы счисления строятся по общемупринципу: определяется величина р — основаниесистемы, а любое число х записывается в видекомбинации степеней веса р от 0-ой до n-ой степениследующим образом: (x)10=xnpn+xn-1pn-1+…+x1p1+x0p0. Сложение в двоичной системе счисленияосуществляется по правилам: 0 + 0 = 0, 0 + 1 = 1, 1 + 0= 1, 1 + 1 = 210 = 102 (единица идет в старшийразряд). Таблица вычитания в двоичной системе счисленияимеет вид: 0 — 0 = 0, 1 — 0 = 1, 1 — 1= 0, 0 — 1 = 10 — 1 = 1 (единицу забираем у старшего разряда). Таблица умножения в двоичной системе счисленияимеет вид:, , , . Таблица деления в двоичной системе счисленияимеет вид: 0 : 0 = не определено, 1 :0 = не определено, 0 : 1 = 0, 1 : 1 = 1. Обратным кодом числа в системе с основанием р называется число в этой системе, получаемое заменойцифры, символа в каждом разряде числа на его дополнение до максимальной цифрыв системе (то есть до р-1). Дополнительный код =обратный код + единица в младшем разряде. Высказывание — некоторое повествовательноеутверждение, про которое можно однозначно сказать (сразу посмотрев нанего), истинно оно или ложно. Эти два значения всевозможныхвысказываний обозначаются истина и ложь,true и fаlse или 1 и 0. Переменная,значениями которой могут быть лишь значения 1 или 0называется логической переменной или булевой переменной. Множествологических переменныхсопределенными над ним операциями: x — отрицания или инверсии,-логического сложения или дизъюнкции,-логического умножения или конъюнкции называется алгебройпредикатов (и высказываний), если эти операции удовлетворяют следующимаксиомам:
.
, .
, .
, .
, .
, .
,.
|