Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2001 - 2002
Сезон 2000 - 2001
Описание на алгоритъма на задача 1 - Компресия: (от Валери Стефанов Вучов)

Кодиращият алгоритъм използва двойна компресия. Първоначално кодиращата програма чете входния файл и за всяка цифра генерира описание на шрифта във временен файл. Описанието се състои в следното: чете се последователно изображението и се записва: брой последователни нули,брой единици,… При това за съхранение на броя на нулите и единиците във временния файл се използва ASCII кодовата таблица, тъй като това позволява съхранение на достатъчно голям брой нули или единици в един символ. По такъв начин отпада и нуждата от разделители между броя нули и брой единици, тъй като след едното винаги следва другото и обратно. В началото на описанието на всяка цифра се записва съответната цифра, която се описва. Като разделител между описанията на изображенията се използва ASCII код 254. Има също и един масив от флагове pointer , който показва дали цифрата, която текущо трябва да се опише е описана преди това. В такъв случай във временния файл просто се записва само цифрата и се преминава към описание на следващата. Дори няма нужда от разделител 254, тъй като при декодиране се чете сифрата и се проверява в съответният масив от указатели дали цифрата е описана преди това. Така във временния файл се пазят описанията само на десет цифри(0-9) и самите N цифри.

Втората допълнителна компресия има за цел намаляването на временния файл тъй като и при него се наблюдава последователно повтаряне на символи. Чете се временния файл и ако текущо прочетеният символ е различен от предишния то просто се копира символа в кодирания файл. Ако обаче се срещне повтаряне на символи, то се броят повторенията и като се срещне друг символ се записва кодираща последователност ,състояща се от: символ с ASCII код 255,съответния символ и броя на повторенията на символа. Ако даден символ се повтаря повече от 253 пъти също се записва кодираща последователност и се нулира брояча за следващата последователност, тъй като максималното число, което може да се вмести в 1 символ е 253, като изключим кодове 254 и 255, използващи се за разделители. Файлът, получен след втората компресия, е num.cod.

Декодиращата програма прави точно обратното. Първо се декодира num.cod във временен файл, като се декодират повторенията на символи. Следва втора декомпресия от временния файл към изходния, като се пази масив от указатели към описанието на всяка цифра във временния файл. Ако при четене на временния файл се срещне неописана досега цифра, то съответният указател запомня позицията, в която започва описанието.Ако се срещне описана цифра то се преминава чрез съответния указател към описанието.


За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.