Top.Mail.Ru
Ответы

Информатика 8 класс срочно

Ваня недавно открыл для себя азбуку Морзе, где каждую букву можно представить в виде двух сигналов длинного (тире) и короткого (точка). Но его беспокоит, что без использования разделителя между отдельными буквами одно и то же сообщение можно расшифровать несколькими способами, поэтому Ваня начал размышлять, как можно усовершенствовать данную систему кодировки букв. Ваня узнал, что для однозначной расшифровки сообщения нужно, чтобы ни одна последовательность точек и тире для одной буквы не была началом другой последовательности для другой буквы. Вооружившись этой идеей и подсчитав, сколько раз каждый символ встречается в тексте, Ваня задумался: как придумать такие кодовые слова для символов, чтобы закодировать текст с минимальным количеством точек и тире? В таблице показано, сколько букв в тексте насчитал Ваня. Помогите ему придумать для каждой буквы такую последовательность точек и тире, чтобы их суммарное количество, необходимое для кодирования текста, было минимальным. Обратите внимание: Ваня хочет, чтобы в дальнейшем данный текст можно было однозначно расшифровать

По дате
По рейтингу
Аватар пользователя
Ученик

я ее в 6 решаю

Аватар пользователя
Ученик

Помогу Ване!

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

| Буква | Количество точек | Количество тире |
| --- | --- | --- |
| a | 5 | 1 |
| b | 3 | 3 |
| c | 2 | 4 |
| д | 4 | 2 |
| e | 3 | 3 |
| f | 2 | 4 |
| ... | ... | ... |

Далее, мы можем использовать алгоритм greedy для поиска минимального количества точек и тире для кодировки текста. Алгоритм сводится к следующему:

1. Сортируем буквы в порядке убывания количества точек.
2. Выбираем первую букву, которая еще не была использована.
3. Выбираем для нее минимальную последовательность точек и тире, не начиная с какой-либо другой буквы.
4. Удаляем выбранную букву из таблицы.
5. Повторяем шаги 2-4, пока не будет использована вся таблица.

Ответ:

1. a: -.-. (2 точки и 1 тире)
2. d: -.. (1 точка и 2 тиры)
3. e: .-.-.- (3 точки и 1 тире)
4. b: ... (3 точки)
5. f: ..-.- (2 точки и 2 тиры)
6. ...

Ваня может использовать эти кодовые слова для кодировки текста с минимальным количеством точек и тире.

Аватар пользователя
Ученик

всего 8 букв от а до г и от о до р

Аватар пользователя
Ученик

У меня это на олимпиаде по информатике в 6 классе, а не в 8🤯

Аватар пользователя
Ученик

у меня в 7 эта задача была,лол

Аватар пользователя
Ученик

Это конечно не ответ, но меня смущает, что эта задачка была у меня на олимпиаде в 6 классе.

Аватар пользователя
Ученик

А у меня в 5 классе тоже эта задача...ЭТО ТИПО НОРМАЛЬНО?



Видео по теме