Как в исполнителе Чертежник сделать алгоритм черчения нескольких квадратов?
Каким алгоритмом в системе КУМИР можно нарисовать несколько вложенных друг в друга квадратов, отстоящих на единицу друг от друга, если неизвестно сколько квадратов надо нарисовать?
2 ответа:
На этапе построения алгоритма не нужно знать сколько квадратов будет начерчено, надо только предусмотреть ввод количества повторений построения квадрата (переменная "колич") с выводом подсказки:
вывод "Количество="
ввод колич
В момент выполнения программы пользователь сам задаст нужное количество, а программа повторит цикл построения, отслеживая номер рисуемого квадрата в переменной "квадрат".
Получится такой алгоритм:
использовать Чертежник
алг
нач
цел колич,сторона,квадра<wbr />т
вывод "Количество="
ввод колич
сторона:=1
сместиться в точку(0, 0)
нц для квадрат от 1 до колич
опустить перо
сместиться на вектор(0,сторона)
сместиться на вектор(сторона,0)
сместиться на вектор(0,-сторона)
сместиться на вектор(-сторона,0)
поднять перо
сместиться на вектор(-1,-1)
сторона:=сторона+2
кц
кон
Количество квадратов можно ввести оператором ввода , а при построении алгоритма надо предусмотреть переменную для количества повторений (переменная "колич")
В программе цикл построения надо повторить столько раз сколько будет введено в переменную "колич", каждый раз смещая точку начала черчения на единицу по каждой оси и увеличивая сторону квадрата.
Перед вводом количества квадратов необходимо написать пользователю оператором вывод текст "Укажите количество квадратов"
Получится такая программа:
использовать Чертежник
алг
нач
цел колич, сторона
вывод "Укажите количество квадратов"
ввод колич
сторона:=1
сместиться в точку(0, 0)
нц колич раз
опустить перо
сместиться на вектор(0,сторона)
сместиться на вектор(сторона,0)
сместиться на вектор(0,-сторона)
сместиться на вектор(-сторона,0)
поднять перо
сместиться на вектор(-1,-1)
сторона:=сторона+2<wbr />
кц
кон
Читайте также
Строим двоичное дерево кодов динамически, по частоте появления каждого символа в сообщении (можно и по готовой таблице вероятностей появления символов).
Определим частоты появления символов
- Символ "Ш" встречается 4 раза
- Символ "Л" встречается 2 раза
- Символ "А" встречается 5 раз
- Символ " " встречается 6 раз
- Символ "С" встречается 6 раз
- Символ "П" встречается 1 раз
- Символ "О" встречается 3 раза
- Символ "Е" встречается 1 раз
- Символ "И" встречается 1 раз
- Символ "У" встречается 2 раз
- Символ "К" встречается 1 раз
каждый символ является конечным узлом дерева, а частота появления является весом этого узла.
составим список нераспределённых узлов по возрастанию весов.
- "П" (1)
- "Е" (1)
- "И" (1)
- "К" (1)
- "Л" (2)
- "У" (2)
- "О" (3)
- "Ш" (4)
- "А" (5)
- "_" (6)
- "С" (6)
объединяем узлы с минимальными весами в один родительский узел с суммарным весом
и помещаем его в список вместо этих узлов в соответствии с весом этого узла
в результате список нераспределённых узлов сокращается на 1 узел.
Эту операцию повторяем до тех пор пока не останется один корневой узел.
Узлы "П" и "Е" объединяем в узел 1
после первого шага список примет вид:
- "И" (1)
- "К" (1)
- 1 (2)
- "Л" (2)
- "У" (2)
- "О" (3)
- "Ш" (4)
- "А" (5)
- "_" (6)
- "С" (6)
после шага 10 останется один корневой узел с весом 32
строим кодовое дерево: узел с меньшим весом помещаем в левую ветвь, а с большим в правую.
При обходе дерева левое ребро добавляет к коду бит 0, а правое бит 1
получаем следующую таблицу кодов символов
- Код символа "С" равен 00
- Код символа " " равен 111
- Код символа "А" равен 110
- Код символа "Ш" равен 101
- Код символа "О" равен 010
- Код символа "У" равен 0111
- Код символа "Л" равен 0110
- Код символа "К" равен 10001
- Код символа "И" равен 10000
- Код символа "Е" равен 10011
- Код символа "П" равен 10010
Заметим , что получились префиксные коды: код любого символа не является началом кода другого символа, т.е. соблюдается условие Фано.
Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:
4*3+2*4+5*3+6*3+6*2+<wbr />1*5+3*3+1*5+1*5+2*4+1<wbr />*5=102 бит
Кодирование осуществляется по таблице кодов, заменой каждого символа его кодом
Кодированное сообщение имеет вид:
10101101101110011010<wbr />111011110010010111101<wbr />010000010011111100001<wbr />110001000110011011011<wbr />1000111101100010111
Чтобы раскодировать сообщение необходимо последовательно считать первый бит и пройти от корня соответствующее ребро дерева, далее следующий бит и так до тех пор до тех пор, пока узел не является листом (конечным узлом ветви), затем повторить эту операцию от корня снова, до тех пор, пока не кончится сообщение.
Фраза "ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ" имеет длину 32 байт или 256 бит в восьмибитном коде (например ASCII) или 512 бит в юникоде.
Это сообщение содержит 11 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(11)=4 бит
при равномерном кодировании длина текста равна 32*4=128 бит
Коэффициент сжатия по сравнению с равномерным кодированием равен 128/102=~1,25
Коэффициент сжатия по сравнению с кодом ASCII кодированием равен 256/102=~2,5
Коэффициент сжатия по сравнению с кодированием в юникоде равен 512/102=~5
Это похожая задача. Здесь после положительных элементов вставляется число 100, и всё записывается в новый массив.
Писать вам код не собираюсь, нужно и самой уметь что-то делать.
По блок-схеме смотрите очерёдность действий. У вас в условии будет не B[i]>=0, a B[i]=q. И вставлять вы будете не число 100, а букву u.
Задача элементарна.
Строим дерево Хаффмана по количеству повторений символов в сообщении
считаем сколь раз повторяется каждый символ:
"К" повторяется 3 раза
"О" повторяется 3 раза
"Р" повторяется 4 раза
"Л" повторяется 5 раз
"Е" повторяется 3 раза
"В" повторяется 3 раза
"А" повторяется 7 раз
" " повторяется 3 раза
"У" повторяется 2 раза
"П" повторяется 1 раз
"Д" повторяется 1 раз
"И" повторяется 1 раз
Каждый символ помещаем в узел дерева с весом, равным числу повторений символа и сортируем по возрастанию весов:
{"П"(1)}
{"Д"(1)}
{"И"(1)}
{"У"(2)}
{"К"(3)}
{"О"(3)}
{"Е"(3)}
{"В"(3)}
{" "(3)}
{"Р"(4)}
{"Л"(5)}
{"А"(7)}
Объединяем 2 узла с минимальным весом в промежуточный узел и помещаем этот узел в список в соответствии с весом.
в результате длина списка уменьшится на 1 узел, этот шаг повторяется до тех пор пока не осмтанется один корневой узел.
после выполнения шага 1 получим:
Шаг 1
объединяем {"П"(1)} и {"Д"(1)} в узел {1 (2)},
первый элемент списка соответствует левому ребру с кодом 0, а второй ребру с кодом 1
{"И"(1)}
{1 (2)}
{"У"(2)}
{"К"(3)}
{"О"(3)}
{"Е"(3)}
{"В"(3)}
{" "(3)}
{"Р"(4)}
{"Л"(5)}
{"А"(7)}
Шаг 2
объединяем {"И"(1)} и {1 (2)} в узел {2 (3)}
{"У"(2)}
{2 (3)}
{"К"(3)}
{"О"(3)}
{"Е"(3)}
{"В"(3)}
{" "(3)}
{"Р"(4)}
{"Л"(5)}
{"А"(7)}
Шаг 3
объединяем {"У"(2)} и {2 (3)} в узел {3 (5)}
{"К"(3)}
{"О"(3)}
{"Е"(3)}
{"В"(3)}
{" "(3)}
{"Р"(4)}
{3 (5) }
{"Л"(5)}
{"А"(7)}
Шаг 4
объединяем {"К"(3)} и {"О"(3)} в узел {4 (6)}
{"Е"(3)}
{"В"(3)}
{" "(3)}
{"Р"(4)}
{3 (5) }
{"Л"(5)}
{4 (6)}
{"А"(7)}
Шаг 5
объединяем {"Е"(3)} и {"В"(3)} в узел {5 (6)}
{" "(3)}
{"Р"(4)}
{3 (5) }
{"Л"(5)}
{5 (6)}
{4 (6)}
{"А"(7)}
Шаг 6
объединяем {" "(3)} и {"Р"(4)} в узел {6 (7)}
{3 (5) }
{"Л"(5)}
{5 (6)}
{4 (6)}
{6 (7)}
{"А"(7)}
Шаг 7
объединяем {3 (5) } и {"Л"(5)} в узел {7 (10)}
{5 (6)}
{4 (6)}
{6 (7)}
{"А"(7)}
{7 (10)}
Шаг 8
объединяем {5 (6)} и {4 (6)} в узел {8 (12)}
{6 (7)}
{"А"(7)}
{7 (10)}
{8 (12)}
Шаг 9
объединяем {6 (7)} и {"А"(7)} в узел {9 (14)}
{7 (10)}
{8 (12)}
{9 (14)}
Шаг 10
объединяем {7 (10)} и {8 (12)} в узел {10 (22)}
{9 (14)}
{10 (22)}
Шаг 11
объединяем {9 (14)} и {10 (22)} в узел {11 (36)}
узел 11 является корневым узлом, строим дерево кодов начиная с узла 11.
по готовому дереву находим коды символов как путь от корня до листа
"А" двоичный код равен 01
"Л" двоичный код равен 101
"Р" двоичный код равен 001
" " двоичный код равен 000
"В" двоичный код равен 1101
"Е" двоичный код равен 1100
"О" двоичный код равен 1111
"К" двоичный код равен 1110
"У" двоичный код равен 1000
"И" двоичный код равен 10010
"Д" двоичный код равен 100111
"П" двоичный код равен 100110
Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:
3*4+3*4+4*3+5*3+3*4+<wbr />3*4+7*2+3*3+2*4+1*6+1<wbr />*6+1*5=123 бит
Длина кодированного сообщения равна 123 бит:
11101111001111110111<wbr />001101010001110011101<wbr />0110111000011000000
10011011111001110100<wbr />110010101010001110010<wbr />010111011100101101100<wbr />0
Анализ сжатия фразы:КОРОЛЕВА КАВАЛЕРУ ПОДАРИЛА КАРАВЕЛЛУ
Длина исходного сообщения 36 байт или 288 бит в ASCII:
сообщение содержит 12 различных символов.
Длина кода одного символа при равномерном кодировании равна log₂(12)=4 бит
при равномерном кодировании длина текста равна 36*4=144 бит
Коэффициэнты сжатия
по отношению к восьмибитному коду К=288/123=~2.34
по отношению к равномерному коду минимальной длинны К=144/123=~1.17