8 (базовый уровень)
Тема: Кодирование данных, комбинаторика, системы счисления.
Что проверяется:
Знание основных понятий и методов, используемых при измерении количества информации.
2.2. Теоретические подходы к оценке количества информации. Единицы измерения количества информации. Алфавитный подход к оценке количества информации. Закон аддитивности информации. Формула Хартли. Информация и вероятность. Формула Шеннона
1.3. Понимание основных принципов дискретизации различных видов информации
Что нужно знать:
· В русском языке 33 буквы: 10 гласных букв (а, у, о, ы, и, э, я, ю, ё, е), 21 согласная буква (б, в, г, д, ж, з, й, к, л, м, н, п, р, с, т, ф, х, ц, ч, ш, щ) и два знака (ь, ъ).
· Алфавит английского языка по написанию совпадает с латинским алфавитом и состоит из 26 букв.
· принципы работы с числами, записанными в позиционных системах счисления
· если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение
N = n1 · n2 · … · nL
· если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL
· если в программе L вложенных циклов и внешний цикл выполняется n1 раз, следующий (вложенный) n2 раз и т.д., то команды самого внутреннего цикла будут выполняться N раз, где
N = n1 · n2 · … · nL.
Если n1 = n2 = … = nL = n, то N = nL.
· при увеличении n или L значение N сильно возрастает, что приводит к существенному увеличению времени выполнения программы.
· (В. Ялдыгин) при решении с помощью программы на языке Python удобно использовать функции из модуля itertools:
combinations – комбинации, например,
from itertools import combinations
cmb = list(combinations('ABC', 2))
print( cmb )
// Результат: [('A', 'B'), ('A', 'C'), ('B', 'C')]
permutations – перестановки, например,
from itertools import permutations
cmb = list(permutations('ABC'))
print( cmb )
// Результат: [('A', 'B', 'C'), ('A', 'C', 'B'),
// ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'),
// ('C', 'B', 'A')]
product – декартово произведение (все возможные слова заданной длины, составленные из данного алфавита), например:
from itertools import product
cmb = list(product('ABC',repeat=2))
print( cmb )
// Результат: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'),
// ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
Как видно из этих примеров, результат работы этих трёх функций – массив кортежей. В нём удобно работать с отдельными символами, но неудобно искать сочетания букв. Если нужно работать с сочетаниями букв, нужно «склеить» символы каждого кортежа в строки с помощью метода .join:
from itertools import product
cmb = product('ABC',repeat=2)
cmb = list( map( "".join, cmb ) )
print( cmb )
// Результат: ['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA',
// 'CB', 'CC']
или так:
from itertools import product
cmb = product('ABC',repeat=2)
for p in cmb:
s = "".join(p)
print( s )
// Результат: AA AB AC BA BB BC CA CB CC
· (А. Шпехт) Для перебора всех возможных вариантов в С++ удобно использовать функцию next_permutation(), которая генерирует следующую лексикографическую перестановку. Для использования функции необходимо подключить библиотеку <algorithm>. Функция переставляет диапазон [first, last) в следующую перестановку, причём набор всех перестановок упорядочен лексикографически. Возвращает true, если такая «следующая перестановка» существует, и генерирует её; в противном случае преобразует диапазон в лексикографически первую перестановку. Следующий фрагмент выведет «acb»:
#include <algorithm>
#include <string>
#include <iostream>
int main()
{
std::string s = "abc";
next_permutation(s.begin(), s.end());
std::cout << s;
}
Следующий код печатает все три перестановки строки «aba»:
#include <algorithm>
#include <string>
#include <iostream>
int main
{
std :: string s = "aba" ;
std :: sort( s.begin() , s.end() ) ;
do {
std :: cout << s << '\n' ;
} while ( std :: next_permutation( s.begin(), s.end() ) ) ;
}
Результат:
aab
aba
baa
Пусть требуется получить все возможные перестановки слова "ЕГЭ". Для выводя в консоль кириллических символов необходимо подключить локаль: setlocale(LC_ALL, "Russian");
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int main
{
setlocale(LC_ALL, "Russian");
string s = "ЕГЭ";
sort( s.begin(), s.end() );
do {
cout << s << '\n' ;
} while ( next_permutation( s.begin(), s.end() ) ) ;
}
Результат:
ГЕЭ
ГЭЕ
ЕГЭ
ЕЭГ
ЭГЕ
ЭЕГ