INFOMAN брой 9
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: ÜÜ Home Page:
infoman@musala.com Û Û http://infoman.musala.com/
брой 9 - Март, 1999 ßÜÜß (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Интро (Infoman)
2. Решение на задачите от зимните математически празници Светлин Наков
3. Финален кръг на конкурса на PC/Magazine - решение Светлин Наков
4. Магически квадрати - задачи и алгоритми Star Gruhtar
5. Оптимално разрязване на многоъгълник Светлин Наков
6. На опашка за билети - задача от Балканиада Васил Поповски
7. Информация за предстоящи състезания (Infoman)
8. Заключение (Infoman)
Интро (Infoman)
ÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Измина доста време от последния брой на списание INFOMAN. Редакцията се
извинява за голямото забавяне на новия брой, но то е причинено поради дълго-
то чакане някой все пак да напише и изпрати в редакцията решение на задача-
та от финалния кръг на списание PC Magazine/Bulgaria и решения на задачите
от зимните математически празници - Варна'99. Все пак настоящият брой е ве-
че факт и за сметка на дългото чакане в него има значително повече статии и
материали отколкото обикновено. В близките няколко месеца INFOMAN ще излиза
по-често поради приближаването на финалния кръг на най-важното за учениците
в България състезание - националната олимпиада по информатика, която ще се
проведе на 15-16 май.
Проблемите с web-сървъра на INFOMAN вече са отстранени и сайтът му отно-
во е достъпен от адрес:
www.infoman.org
Добавени са и още два огледални web-сайта на INFOMAN на адреси:
www.informan.org
debian.fmi.uni-sofia.bg/infoman
Работят и двата e-mail-a на списанието:
infoman@infoman.org
in_fo_man@hotmail.com
В редакцията все още не се е получило решение на задачата от финалния кръг
на конкурса на вестник ComputerNews за голямата нагарада $1000 и затова ре-
шение не е публикувано.
Обещаните сорсове на програмите от нашумялата напоследък книга по алгортими
на Преслав Наков "Основи на компютърните алгоритми" не успяхме да публилику-
вами на страницата на INFOMAN в ИНТЕРНЕТ защото авторът в момента е в чужби-
на и не може да ни ги предостави. Веднага след завръщането му редакцията на
списанието ще се свърже с него и ще ги предостави на всички читатели на спи-
санието да ги теглят свободно.
Решение на задачите от зимните математически празници Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Съзтезанията по информатика на зимните математически празници, проведени
миналия месец във Варна в групата 10-11 клас бяха по правилата на ACM, пуб-
ликувани в предишния брой. Състезанията протекоха почти нормално като изклю-
чим дребните грешки в проверявъчните тестове на една от задачите и в пример-
ния изход друга довели до объркване много от участниците. Задачите бяха под-
ходящи и не много трудни. Решения на три от четирите задачи в групата 10-11
клас ще намерите във файловете cableset.pas, nightsea.pas и sub1.pas.Четвър-
тата задача си е чиста хамалогия и се решава с backtracking. Решение в този
брой няма да публикуваме. Условията на задачите и описанието на алгоритмите
за решениете останалите три задачи ще намерите в посочените файлове с реше-
ния.
Финален кръг на конкурса на PC/Magazine - решение Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Задачата, която дадоха на финалния кръг на списание PC Magazine/Bulgaria
преди няколко месеца в София, беше доста трудна и изключително подходяща за
такъв род конкурси. Поради сложността на алгоритмичния проблем и поради ред
други причини решение на задачата имаме едва сега. Все пак чакането напълно
си заслужава, защото решението, което ни предложи спечелилият второ място в
конкуса Светлин Наков е наистина много добро. Условието на задачата, описа-
нието на алгоритъма и програма, която блестящо го реализира ще намерите във
файла pcmagaz.pas
Магически квадрати - задачи и алгоритми Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагам на всички читатели на INFOMAN да се запознаят с някои от извест-
ните и полулярни задачи свързани с така наречените "магически квадрати". Из-
следванията върху поставените проблеми са направени на базата на информация
от ИНТЕРНЕТ и лични изследвания по поставените задачи на авторитетния автор
на настоящата статия - небезизвестния Star Gruhtar. Файловете към тази ста-
тия са magic.pas, magic1.pas и magic2.pas.
Оптимално разрязване на многоъгълник Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагам едно прекрасно решение на задачата за оптимално разрязване на
изпълнал многоъгълник на съставящи го триъгълници. Идеята на алгоритъма кой-
то съм използвал в решението на задачата cutpolyg.pas е взаимствана от брой
9/1998 на списание Computer.
На опашка за билети - задача от Балканиада Васил Поповски
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Тази интересна задача беше дадена на 4-тата Балканска олимпиада по инфор-
матика в Кипър през 1996 година. Смятам, че ще е интересна за читателите на
INFOMAN. Файлът е bileti.pas.
Информация за предстоящи състезания (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Известни са датите за провеждане на 2-ри, 3-ти и 4-ти кръг на национал-
ната олимпиада по информатика за ученици в средното училище:
2-ри (регионален) кръг - 28 февруари 1999 г.
3-ти (национален) кръг - 21 март 1999 г.
4-ти (финален) кръг - 15-16 май 1999 г.
Поради големия интерес публикуваме отново условията на националния кон-
курс за програмни продукти за 1998-1999 година.
НАЦИОНАЛЕН КОНКУРС ЗА ПРОГРАМНИ ПРОДУКТИ
ЗАДАНИЕ ЗА РАЗРАБОТКА НА ПРОГРАМЕН ПРОДУКТ
за 1998-1999 година
Трябва да се отбележи, че този конкурс се провежда от няколко години и
по традиция всяка година фондация "Еврика" дава на победителя голямата наг-
рада - стипендия в продължение на цялото обучение - 30% от минималната ра-
ботна заплата за периода на обучение в училище и 50% от минималната работ-
на заплата в периода на обучение във ВУЗ. Повече информация за конкурса за
разработка на програмни продукти можете да получите от регионалния център
за работа с деца - ЦРД (бившия пионерски дом) и от ръководителите на кръжо-
ците по информатика и програмиране на ЦУНТТ (център за ученическо научно и
техническо творчество) към регионалния ЦРД. Поставената тема трябва да се
разработи от ученика и да се предаде на ръководителя до 20 май 1999. Финал-
ния кръг на конкурса ще се проведе както всяка година в края на месец юни
и ще бъде присъствен. На него всеки участник лично ще си защитава разработ-
ката. Ето и условието на заданието:
Мрежа ще наричаме двойката (N,L), където N е съвкупност от обекти, а
L - съвкупността от всички връзки между обектите. Всяка връзка отговаря на
двойка обекти (свързва 2 обекта). Между два обекта може да няма връзка или
да има една или повече връзки. Обектите (елементите на N) ще наричаме въз-
ли на мрежата.
Да приемем, че на всеки възел се приписва някакво име или номер, за
да можем да ги различаваме. Ако между два възела има повече от една връзка,
тези връзки също ще снабдим с имена или номера, по същата причина.
Мрежите често се използват като структура от данни за моделиране на
реално съществуващи или проектни системи от най-различни видове. При това
обикновено се оказва необходимо към възлите и/или връзките между тях да се
прикрепва и друга информация.
Например можем да приемем, че възлите съответстват на населени места
от даден регион, и тогава данни за населените места могат да се прикрепват
към възлите ; тогава пък връзките могат да съответстват на пътищата между
населените места и към тях да се прикрепват данни за дължината, качеството,
пропускателната способност на всеки път. Друг пример:възлите са абонати на
съобщителна мрежа - телефонна централа, радиорелейна мрежа и т.н. - а връз-
ките между тях, където ги има са съобщителните линии. Съответните допълни-
телни данни тогава са други.
ЗАДАНИЕ:
1. Проучете различни приложения на мрежи за моделиране на системи.
2. Проучете различни алгоритми за решаване на задачи върху мрежи, на-
пример такива за намиране на пътища (последователност от връзки) между въз-
ли, определяне дали между два възела изобщо съществува път,избиране на под-
ходяща в даден смисъл подмрежа на зададена мрежа и т.н. Разгледайте мрежи
с двупосочни и еднопосочни връзки (ако от един възел към другия има връзка,
не непременно има такава и от втория към първия, а ако има - не непременно
е същата).
3. Проектирайте и съставете програма за компютри от типа IBM PC, коя-
то използва мрежа за моделиране на някоя конкретно избрана от вас система.
Програмата трябва да позволява въвеждане и изменяне на данните, които зада-
ват мрежата, показване на мрежата в подходящ вид на екрана на компютъра и
решаване на различни задачи, свързани с мрежата.
4. В писмения материал към разработката обосновете избора на модели-
раната система, нейните свойства и какви задачи за тази система решава ва-
шата програма. Ако в програмата са реализирани интересни, оригинални ваши
алгоритми, опишете ги. Ако са използвани известни алгоритми за типови зада-
чи върху мрежи - посочете кои именно.
Освен програмата разработчикът трябва да представи и подробни указа-
ния за нейното ползване и за нейното устройство. Наред с другото,трябва да
бъде ясно посочено какви готови инструментални средства са използвани при
разработката на програмата.
Информация за други състезания
Задочния конкурс по информатика на списание Computer продължава. Услови-
ята можете да откриете на страниците на списанието или на адрес http://www.
math.acad.bg/~keleved/eureka.html.
Заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Редакцията на INFOMAN ще е много благодарна на всички абонати на списани-
ето които изпращат материали за списанието. Умоляват се всички читетели да
изпращат съвети,статии или решени задачи с описание на използваните алгорит-
ми и примерна програма. Ако някой читател има повече информация за предстоя-
щи състезания или информация за други конкурси и състезания, молим да ни я
изпрати, за да я публикуваме. Не забравяйте, че списанието е за напреднали
информатици и затова статии, подходящи само за начинаещи няма да бъдат пуб-
ликувани. Освен това материали, които дават грешен или неефективен начин за
решаване на каквито и да било задачи, също няма да се публикуват.
Не забравяйте, че информатиката е основата на програмирането и че всички
програмисти, които не са добри информатици са си чисти занаятчии!
Учете информатика. Тя е същината на компютърните науки.
Успех на всички информатици!
File List:
cutpolyg.pas
cableset.pas
bileti.pas
infoman9.txt
magic.pas
magic1.pas
magic2.pas
nightsea.pas
pcmagaz.pas
sub1.pas