Великденски Яйца

Програмиране с Python

Курс във Факултета по Математика и Информатика към СУ

Решение на Изберете си проект от Йордан Русев

Обратно към всички решения

Към профила на Йордан Русев

Код

"""Кодирания RLE и Base64
1.RLE
Run-length encoding (RLE) представлява кодиране на низове, при което последователности от еднакви символи се заменят с двойка от символа и броя повторения. Например S = AAAABBBBCCCAABBBB може да се представи с RLE списъка R = (4,A) (4,B) (3,C) (2,A) (4,B).
Ще реализирам следните методи:
- кодират даден низ в RLE списък
- декодират RLE списък до низ
- вмъкват един RLE списък на произволна позиция в друг, като позицията се указва в брой символи от началото на оригиналния низ:
пример: след като вмъкнем (3, C) (1, B) на позиция 6 в R се получава (4,A) (2, B) (3, C) (3, B) (3, C) (2, A) (4, B)
- изтриват последователност от символи от RLE списък
пример: след като изтрием последователност от 8 символа от позиция 6 в R се получава списъкът (4,A) (5, B)
- проверяват дали низът, кодиран от RLE списъка A е подниз на низа, кодиран от RLE списъка B. Проверката да не включва операция по декодиране, с цел ефективност
пример: списъкът (2, B) (1, C) е подсписък на R
пример: списъкът (1,C) (3,A) (1, B) не е подсписък на R (4,B)
- По дадено RLE кодиране на низ, да се построи честотната таблица на низа (за всеки символ, който се среща в низа, се оказават броят на срещанията му в низа). Резултатът да е под формата на RLE списък, в който всеки символ се среща най-много веднъж
пример: (6,A) (8,B) (3,C) е честотна таблица на R
2. Base64
Нека е даден масив F от байтове. Ще дефинирам методи, които:
Преобразуват F до низ, в който се използват само символите “A-Za-z0-9+/”.
От кодиран по този начин низ, възстановяват съдържанието на F
Целта на кодирането е да се избегнат специалните символи като ‘\t’, ‘\n’, ‘\0’ и други. Забележете, че броят на символите в множеството “A-Za-z0-9+/” е 64 (= 26+26+10+2).
Алгоритъм на кодиране:
1) разглеждаме двоичния файл като последователност от групи по 24 бита (три байта от по 8 бита)
2) всеки 24 бита разбиваме на четири 6-битови байта
3) на всеки 6-битов байт съпоставяме съответния символ от “A-Za-z0-9+/”
4) записваме получените символи в текстовия файл
При достигане края на двоичния файл имаме от един от следните случаи:
а) при последната операция сме прочели точно 24 бита и значи всичко е ОК
б) при последното четене е имало само 8 бита
в) при последното четене е имало само 16 бита
В случай “б)” допълваме до 12 бита с нули и получаваме 2 6-битови байта, съпоставяме им символи и допълваме с два символа ‘=’ в текстовия файл.
В случай “в)” допълваме до 18 бита с нули и получаваме 3 6-битови байта, съпоставяме им символи и допълваме с един символ ‘=’ в текстовия файл.
Не е задължително да реализирате случаи “б)” и “в)”, приемете, че размера на файла е кратен на 3.
Това кодиране се нарича base64 и се използва при прикрепяне на файл към e-mail съобщение, заради изискванията на протокола да не се използват специални символи. Резултатът от кодирането е текстов файл с размер 4/3 спрямо оригиналния, но без специални символи и върши работа за всякакви файлове. Недостатък е, че съдържанието на кодирания файл е неразбираемо за човек. Съществува и друго широко използвано кодиране наречено quoted-printable – като при него се разчита, че се изпраща главно текст и малък брой специални символи, които се escape-ват.
Ще напиша една кодираща и декодираща програма използвайки алгоритъма на base64. Програмата ще реализира:
- кодиране:
прочитане на масив от байтове (числа от 0 до 255) от клавиатурата
извеждане на екрана низ, който кодира масива
- декодиране:
прочитане на низ от клавиатурата
извеждане на екрана на масив от байтове
Програмата ми ще използва двоични файлове вместо масиви."""

История (1 версия и 3 коментара)

Йордан обнови решението на 24.04.2015 16:20 (преди около 9 години)

+"""Кодирания RLE и Base64
+
+1.RLE
+
+Run-length encoding (RLE) представлява кодиране на низове, при което последователности от еднакви символи се заменят с двойка от символа и броя повторения. Например S = AAAABBBBCCCAABBBB може да се представи с RLE списъка R = (4,A) (4,B) (3,C) (2,A) (4,B).
+
+Ще реализирам следните методи:
+
+- кодират даден низ в RLE списък
+- декодират RLE списък до низ
+- вмъкват един RLE списък на произволна позиция в друг, като позицията се указва в брой символи от началото на оригиналния низ:
+
+ пример: след като вмъкнем (3, C) (1, B) на позиция 6 в R се получава (4,A) (2, B) (3, C) (3, B) (3, C) (2, A) (4, B)
+
+- изтриват последователност от символи от RLE списък
+
+ пример: след като изтрием последователност от 8 символа от позиция 6 в R се получава списъкът (4,A) (5, B)
+
+- проверяват дали низът, кодиран от RLE списъка A е подниз на низа, кодиран от RLE списъка B. Проверката да не включва операция по декодиране, с цел ефективност
+
+ пример: списъкът (2, B) (1, C) е подсписък на R
+
+ пример: списъкът (1,C) (3,A) (1, B) не е подсписък на R (4,B)
+
+- По дадено RLE кодиране на низ, да се построи честотната таблица на низа (за всеки символ, който се среща в низа, се оказават броят на срещанията му в низа). Резултатът да е под формата на RLE списък, в който всеки символ се среща най-много веднъж
+
+ пример: (6,A) (8,B) (3,C) е честотна таблица на R
+
+2. Base64
+
+Нека е даден масив F от байтове. Ще дефинирам методи, които:
+
+
+ Преобразуват F до низ, в който се използват само символите “A-Za-z0-9+/”.
+
+ От кодиран по този начин низ, възстановяват съдържанието на F
+
+
+Целта на кодирането е да се избегнат специалните символи като ‘\t’, ‘\n’, ‘\0’ и други. Забележете, че броят на символите в множеството “A-Za-z0-9+/” е 64 (= 26+26+10+2).
+
+
+Алгоритъм на кодиране:
+
+
+1) разглеждаме двоичния файл като последователност от групи по 24 бита (три байта от по 8 бита)
+
+2) всеки 24 бита разбиваме на четири 6-битови байта
+
+3) на всеки 6-битов байт съпоставяме съответния символ от “A-Za-z0-9+/”
+
+4) записваме получените символи в текстовия файл
+
+
+При достигане края на двоичния файл имаме от един от следните случаи:
+
+
+а) при последната операция сме прочели точно 24 бита и значи всичко е ОК
+
+б) при последното четене е имало само 8 бита
+
+в) при последното четене е имало само 16 бита
+
+
+В случай “б)” допълваме до 12 бита с нули и получаваме 2 6-битови байта, съпоставяме им символи и допълваме с два символа ‘=’ в текстовия файл.
+
+
+В случай “в)” допълваме до 18 бита с нули и получаваме 3 6-битови байта, съпоставяме им символи и допълваме с един символ ‘=’ в текстовия файл.
+
+
+Не е задължително да реализирате случаи “б)” и “в)”, приемете, че размера на файла е кратен на 3.
+
+
+Това кодиране се нарича base64 и се използва при прикрепяне на файл към e-mail съобщение, заради изискванията на протокола да не се използват специални символи. Резултатът от кодирането е текстов файл с размер 4/3 спрямо оригиналния, но без специални символи и върши работа за всякакви файлове. Недостатък е, че съдържанието на кодирания файл е неразбираемо за човек. Съществува и друго широко използвано кодиране наречено quoted-printable – като при него се разчита, че се изпраща главно текст и малък брой специални символи, които се escape-ват.
+
+
+Ще напиша една кодираща и декодираща програма използвайки алгоритъма на base64. Програмата ще реализира:
+
+- кодиране:
+ прочитане на масив от байтове (числа от 0 до 255) от клавиатурата
+ извеждане на екрана низ, който кодира масива
+
+- декодиране:
+ прочитане на низ от клавиатурата
+ извеждане на екрана на масив от байтове
+
+
+Програмата ми ще използва двоични файлове вместо масиви."""

А става ли да направя desktop приложение, което организира футболни първенства. Евентуално да изпраща e-mail-и на всичките участници за датите и часовете на мачовете, също така да се пази евентуално статистика за всеки един отбор и конкретен състезател.

Ако това не е достатъчно, тогава може ли да доразвиете идеята ми с допълнителни условия към нея.

Звучи интересно, но нека освен статистика за играч да има и такава за мачовете. Кои са били стартовите състави, какви смени са правени, какви картони са давани и важни събития по минути (голове, удари към вратата, картони, ...), колко дълги са били продълженията, краен резултат (очевидно) и т.н.

Иначе какво ще рече "организира"? Нещото, което аз си представих, когато прочетох идеята е, че тегли жребий (за групова фаза) и генерира график въз основа на зададени параметри като:

  • Наличен брой игрища
  • Възможни часове за игра, в които са свободни тези игрища (т.е. в реда на нещата е едно игрище да е годно за игра от 11:00 до 14:00 и от 16:00 до 21:00, примерно).
  • Максимален брой срещи на едно игрище за ден (в името запазване на тревната настилка)
  • Наличен брой съдии (с опция дадени такива да могат да бъдат само странични, но не и главни)
  • Минимална разлика между два мача за един отбор (примерно не е ок даден отбор да има мачове в два поредни дни)

Ако това си имал предвид, ми звучи добре и можеш да считаш идеята си за одобрена.

Между другото, аз бих предпочел да направя това като уеб проект, тъй като идеално ще служи и за публична уеб страница на турнира, но идеята си е твоя и решението за това оставям на теб.