Алгоритмы обработки строк и массивов — закрепление материала (13/21)

Закрепление: строки и массивы

Проведите вычислительный эксперимент: измерьте, как порядок одинаковых данных влияет на число серий и стоимость RLE.

Лаборатория

1. Для каждого набора найдите n и число серий r.
2. В учебной модели сравните исходную стоимость n и стоимость пар 2r.
3. Исследуйте длинные серии, чередование и все различные значения.
4. Сравните один набор до и после группировки, не забывая, что порядок изменился.
5. Для каждого опыта проверьте decode(encode(a))=a и сформулируйте вывод.

Гипотеза: RLE выгодно в принятой модели только при 2r<n; сортировка не является допустимым улучшением, если важен исходный порядок.

Выходной билет

a=[1,1,2,3,3,3,5] → r=3, n=6, 2r=6: выигрыша нет.

Pascal

После кодирования вычислите r и сравните 2*r с n для каждого экспериментального набора.