В
Все
М
Математика
О
ОБЖ
У
Українська мова
Д
Другие предметы
Х
Химия
М
Музыка
Н
Немецкий язык
Б
Беларуская мова
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
Р
Русский язык
У
Українська література
Ф
Французский язык
П
Психология
А
Алгебра
О
Обществознание
М
МХК
В
Видео-ответы
Г
География
П
Право
Г
Геометрия
А
Английский язык
И
Информатика
Қ
Қазақ тiлi
Л
Литература
И
История
Кисик123
Кисик123
12.04.2020 16:13 •  Информатика

Составить трассировочную таблицу для следующих программ. Определить, что будет напечатано в результате выполнения программ:


Составить трассировочную таблицу для следующих программ. Определить, что будет напечатано в результа
Составить трассировочную таблицу для следующих программ. Определить, что будет напечатано в результа
Составить трассировочную таблицу для следующих программ. Определить, что будет напечатано в результа
Составить трассировочную таблицу для следующих программ. Определить, что будет напечатано в результа

Показать ответ
Ответ:
ladhice
ladhice
28.06.2022 01:20

72 Кб

Объяснение:

1) Определим сколькими битами кодируется отдельный символ, т.е. найдем информационный вес символа.

По формуле  N = 2^{i}, где N - мощность алфавита, i - информационный вес символа алфавита.

512 = 2^{i}\\2^{9} = 2^{i}\\

i = 9 (бит)

2) Информационный объем или количество информации находят по формуле I = K*i, где K - количество символов, i - информационный вес символов.

K = 16*16*256 (симв.) - умножили количество символов на количество строк и получаем количество символов на одной странице, тогда чтобы найти количество символов в книге нужно домножить на количество страниц.

I = 16*16*256*9 = 2^{4}*2^{4}*2^{8}*9 = 2^{16}*9 (бит)

3) Переведем биты в килобайты, Кб.

1 байт = 8 бит

1 Кб = 1024 байт

1 Кб = 1024 байт = 1024*8 бит = 2^{10}*2^{3} = 2^{13} (бит)

Тогда для перевода нужно I =  2^{16}*9 разделить на 2^{13}:

\frac{2^{16}*9}{2^{13}} = \frac{2^{3}*9}{1} = 8*9 = 72 (Кб)

0,0(0 оценок)
Ответ:
сварочка2000
сварочка2000
19.03.2021 16:15
Можно поступить следующим образом: создаем multimap. Читаем слова из словаря, для каждого слова находим все супрефиксы, вставляем их в multimap в качестве ключа, значение можно ставить любое (например, (int) 1). После этого в цикле читаем слова-образцы и выводим значение count от каждого слова-образца. 

Программа будет иметь примерно такую структуру:
multimap<string, ...> subprefixes
input n
n times:
    input s
    for j = 0..size of s:
        if s[..j] is subprefix of s:
            subprefixes.insert(pair<string, ...>(s[..j], ...))
input m
m times:
    input s
    print subprefixes.count(s)

Остался вопрос, как определять, является ли s[..j] супрефиксом.  Конечно, можно это делать наивно: пройти циклом для всех возможных длин подстрок j и проверить, правда ли, что s[0] = s[s.size() - j - 1], s[1] = s[s.size() - j]...

Как можно ускорить всё это?
1) Выберем какое-нибудь достаточно большое (по сравнению с кодами символов) простое число x, например, x = 1009. Вычислим для строки s все хеши по формуле h_n(s)=s_0+s_1x+s_2x^2+\dots+s_{n-1}x^{n-1} для n = 1..len s (это делается за линейное время относительно len s, если предпросчитать все степени x от нулевой до 50)
Теперь если у строки s длины k есть супрефикс длины j, то обязательно h_j(s)x^{k-j}=h_{k}(s)-h_{k-j-1}(s) – проверить это быстрее, чем ходить циклом.
2) Необязательно хранить в multimap-е подстроки, это дорого и по времени и по памяти. Можно хранить хеши.
3) Можно вместо одного multimap-а создать 50 multimap-ов, в каждом хранить только супрефиксы одной длины.

Получаем примерно такое:
pow = new long long[51]
pow[0] = 1
for i = 1..50:
    pow[i] = x * pow[i - 1]
suprefixes = new multimap<long long, ...>[51]
input n
n times:
    input s
    h = hashes(s)
    k = len s
    for j = 1..k:
         if h[j] * pow[k - j] == h[k] - h[k - j - 1]:
              suprefixes[j].insert(pair(h[j], ...))
input m
m times:
    input s
    print puprefixes[len s].count(hash(s))

В принципе, для такого решения multimap не нужен, достаточно иметь map, и хранить для каждого ключа количество вхождений. Это можно делать и для multimap.
0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота