INFOMAN брой 7
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: ßßßÛ Home Page:
infoman@musala.com Üß http://infoman.musala.com/
брой 7 Ноември, 1998 ß (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Intro (Infoman)
2. Международната олимпиада по информатика за ученици - Светлин Наков
решения на задачите и коментари за втория ден
3. Книгата за алгоритми на Преслав Наков (Infoman)
4. Една интересна игра Star Gruhtar
5. Информация за предстоящи състезания (Infoman)
6. Заключение (Infoman)
Intro (Infoman)
ÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Излезе дългоочакваният брой на INFOMAN. Обещаните решения на задачите от
международната олимпиада са факт, въпреки, че участниците в нея, които бяха
обещали да изпратят решения не изпратиха такива.Все пак нашият главен редак-
тор и основен виновник за съществуването на това електронно издание Светлин
Наков ни предостави неговите решения. Решението на едната задача не е много
хубаво, но надяваме се, че все пак някой ще ни изпрати по-добро.
Излезе писаната няколко години книга по алгоритми на Преслав Наков "Осно-
ви на комютърните алгоритми". Тази книга е подходяща не само за участници в
конкурси и състезания по информатика, но и за хора, които изучават информа-
тика или имат намерение сериозно да се занимават с алгоритми. Горещо се пре-
поръчва на всички читатели на INFOMAN като най-доброто ръководство по алго-
ритми на български език. В книгата, която е от две части авторът системати-
зирано ни запознава с основните компютърни алгоритми, които илюстрира в ра-
ботещи програми написани на Турбо Паскал. Това е първата книга на български
език която дава толкова много информация в областта на алгоритмите. Книгата
съдържа следните теми:
- рекурсия - въведение в рекурсията и запознаване с типичните рекурсивни
алгоритми
- рекурсивни структури - въведение в рекурсивните структури от данни като
линеен списък, дърво и граф и др.
- графи - въведение в алгоритмите с графи - представяне на графи, обходжа-
не, търсене на пътища, покриващи дървета и др.
- комбинаторика - алгоритми за пораждане на основните комбинаторни конфи-
гурации
- аритметичен израз - алгоритми изчисляване, представяне в постфиксен за-
пис и за проверка за коректност на аритеметични изрази
- сортиране - въведение в основните методи за сортиране на данни
- алгоритми от теорията на числата - бройни системи,търсене на прости чис-
ла, представяне с римски цифри, високосна година и др.
- числови редици и подредици - ефективни алгоритми за намиране на различ-
ни максимални подредици
- геометрични алгоритми - уравнение на права, пресичане на отсечки, лица
на многоъгълници и др.
Очаквайте обновяване на новия web site на INFOMAN - www.infoman.org. Спи-
санието има намерението да се представи официално пред информационното обще-
ство на България.
Очаква се след широката рекламна кампания на сайта на INFOMAN читателите
му да се увеличат няколко пъти. Това ще доведе до повече изпращани материа-
ли и броевете ще излизат по-често. От редакцията получихме абсолютна подкре-
па от страна на преподаватели в различни университети в страната,както и на
доценти от Софийския университет. Подкрепиха ни български студенти, ученици,
състезатели, журита в конкурси по информатика и други. Има интерес и в пове-
чето математически гимназии в България.
Затова INFOMAN ще продължава да се развива и ще играе все по-съществена
роля при подготовката на нашите състезатели за олимпиадите,конкурсите и със-
тезанията по информатика. Ако се открие възможност,INFOMAN ще започне да ор-
ганизира и собствени състезания по информатика. Очакваме вашата подкрепа и
се надяваме да четете списанието на българските информатици с интерес.
Международната олимпиада по информатика за ученици -
решения на задачите и коментари за втория състезателен ден Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Повече от два месеца след като измина международната олимпиада по информа-
тика за ученици в Португалия - Сетубал'98 се появява насточщата статия, коя-
то ще ви запознае със задачите и методите за решаването им от втория състе-
зателен ден.
За разлика от първия състезателен ден, задачите от втория ден бяха малко
по-трудни. Задачата за пръстена е доста усложнен вариант на основната зада-
ча за умножение на матрици. Тя е решена с динамично оптимиране. Условието и
решението са във файла PRUSTEN.PAS. Задачата за царя и конете по шахматната
дъска е лесна, но само ако човек се досети, че може да провери хитро всички
възможности. Условието и решението са във файла CAMELOT.PAS. Задачата за пе-
риматъра на сечението на правоъгълници, която беше поставена като първа за
втория ден се оказа най-трудната задача от цялата олимпиада.Около нея имаше
много спорове. Имаше съмнения за коректността на тестовете на журито. Имаше
и спорове върху тъкуването на условието. В даденото решение е разгледан са-
мо един от случаите за тълкуване на понятието сечение. За другия случай,кой-
то изглежда авторите са имали предвид не се получи решение. Все пак условие-
то и решението са във файла RECTS.PAS.
Книгата за алгоритми на Преслав Наков (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Както вече писахме, излезе книгата на Преслав Наков "Основи на комютърни-
те алгоритми". Предлагаме извадка от тази книга - решение на проблема наре-
чен "адитивна редица". Статията е във файла ADITIVNA.PAS.
Сорсовете на всички алгоритми от книгата можете да намерите на страница-
та на автора - http://www.comsoft.bg/preslav/
Една интересна игра Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагам решение на задача 4 за 1998 година от задочния конкурс по инфор-
матика на списание "Computer". Задачата се състои в намирането на печеливша
стратегия за една интересна игра. Решенеито е във файла Z4-98.PAS.
Информация за предстоящи състезания (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Първото състезание за ученици, което предстои е чак в края на Януари 99
година - зимните математически празници. За него все още няма много информа-
ция.
Можете да участвате в задочния конкурс по информатика на списание Compu-
ter. Условията можете да откриете на страниците на списанието или на адрес
http://www.math.acad.bg/~keleved/eureka.html
Заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Редакцията на INFOMAN моли всички абонати да изпращат материали за списа-
нието. Умоляват се всички читетели да изпращат съвети, статии или решени за-
дачи с описание на използваните алгоритми и примерна програма. Ако някой чи-
тател има повече информация за предстоящи състезания или информация за дру-
ги конкурси и състезания, молим да ни я изпрати, за да я публикуваме.
Драги читатели, дори и да не изпращате материали (както до момента прави-
те), INFOMAN ще продължи да същсетвува, дори и ако се наложи главният му ре-
дактор сам да го пише отначало докрай!
Успех!
-----------------------------------------------------------------------
ALL INFOMAN 1-7
DOWNLOAD (for DOS and sources) - na .ZIP
INFOMAN 1.
VIEW (html)
DOWNLOAD (for DOS and sources) - na .ZIP
INFOMAN 2.
VIEW (html)
DOWNLOAD (for DOS and sources) - na .ZIP
INFOMAN 3.
VIEW (html) na kirilica
DOWNLOAD (for DOS and sources) - na .ZIP
Download a cyrillic keyboard driver for DOS
. . .