Решение проверка условий Фано):
1) Для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;
2) Проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);
3) Проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111.
«прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);
«обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;
4) Проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111.
«прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);
«обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;
5) Проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111.
«прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит;
ответ: 4
Решение дерево):
1) Построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):
однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);
3) Теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом
4) Видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано
5) Хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):
видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв
6) В заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится
ответ: 4
Решение проверка условий Фано):
1) Для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;
2) Проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);
3) Проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111.
«прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);
«обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;
4) Проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111.
«прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);
«обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;
5) Проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111.
«прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит;
ответ: 4
Решение дерево):
1) Построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):
однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);
3) Теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом
4) Видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано
5) Хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца):
видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв
6) В заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится
ответ: 4
#include <iomanip>
using namespace std;
int main() {
int n,k;
cout<<"n = "; cin>>n;
int a[n];
srand(time(NULL));
for (int i=0; i<n; i++) {
a[i]=rand()%25; cout<<a[i]<<" ";
}
cout<<endl;
cout<<"k = "; cin>>k;
for (int i=0; i<n-1; i++)
for (int j=i+1; j<n; j++)
if (a[j]>a[i]) swap(a[i],a[j]);
for (int i=0; i<k; i++) cout<<a[i]<<" ";
cout<<endl;
system("pause");
return 0;
}