E-mail:
  infoman@musala.com

брой 2/2000 (18)

Home Page:
  http://infoman.musala.com/

Септември, 2000


 
 


СЪДЪРЖАНИЕ

ТЕМА

1.Интро
2.По-добри решения на някои задачи от ЗМС'2000
3.XVI Олимпиада по информатика - 4ти кръг
4.Динамично оптимиране. Задача за разделянето
5.Три интересни алгоритъма
6.Други две задачи
7.Програминят език C и високата памет
8.Заключение
АВТОР

(Infoman)
Преслав Наков
Мартин Русков
Преслав Наков
Васил Поповски
Светлин Наков
Мартин Русков
(Infoman)


 

1.Интро 

(Infoman)

Здравейте отново български информатици,
Наскоро (6-9 Септември) в Габрово се проведе семинар на тема подготовката по инфроматика в училищата, в рамките на който се проведе и последното контролно за определяне на отбора за МОИ'2000. На този семинар смятам да посветим следващия брой, но сега го споменавам, защото всички, които помолих да изпращат техни решения на редакцията ми отговориха, че са смятали, че Инфоман вече не съществува. За това естествено сме виновни главно ние, защото за дългото време от последния брой издаден от Светлин Наков (Ноември 1999,) ние успяхме да издадем само един мижав брой, който дори не публикувахме на сайта (надявам се когато четете тези редове, той вече да е там.) Едва ли имаме сериозно оправдание за това забавяне, но все пак опитайте се да ни простите и ще се постараем да не се повтаря.
А иначе вие може би вече сте забелязали основните новости: Инфоман вече се издава в HTML формат; в редакцията сме трима - аз (редактор), Валери Дачев от Казанлък (администратор или нещо подобно) и Кай също от Казанлък (ще видим занапред.) и не на последно място е новосъздадения mailing list infoman@infoman.org. Надявам се никой да не злоупотребява с него. Подновен е и сайта на Инфоман като има добавени новини, гласуване и връзките.
Надяваме се новостите в списанието да Ви харесат.
10.9.2000
Мартин Русков
редактор на списание INFOMAN
Съдържание



 
 

2.По-добри решения на някои от задачите на ЗМС’2000

 Преслав Наков

Това са решенията, които ни предложи Преслав Наков. Той е автор на част от решените задачи. За подробности за Зимните Математически Състезания'2000 виж брой 17 (март 2000). Те са във файловете hacker.cpp и bibliot.cpp.

Съдържание



 
 

3.XVI Олимпиада по информатика - 4ти кръг

 Мартин Русков

Мина и замина още една олимпиада. Като се изключат една-две подробности, може да се каже, че тя беше доста добре организирана. Най лошото е, че тези подробности се отнасяха точно до вероятността на някой от участниците да се падне компютър с отдавна остарелия процесор i386, но всъщност и тази архивна машина е част от базата на известния с научната си дейност Инсититут по Математика и Информатика към БАН. Това е и другата лоша подробност: олимпиадата се състоя в 2 сгради, като класиранията в двете се събраха едва в крайното, така че идеята за извеждане на анонимни резултати след първия ден с позагуби. За някои (особено за тези които пишат на C/C++) имаше и още един проблем - всички учасници трябваше да работят на средите на Borland за съвместимост с МОИ (Международна Олимпиада по Информатика,) което направи 32-битовите компилатори само далечна розова мечта.
Иначе нивото на състезанието отново показа упадъка в който се намира информатиката в България. За да се убедите може да видите и резултатите на адрес http://debian.fmi.uni-sofia.bg/sc-club/. Може би като доказателство точно на това идва и факта, че някои от задачите не можах да реша или напиша дори след обсъждане с някои състезатели. Затова моля всички, които са решили някоя от тях, да изпратят решенията си на редакцията. Тези задачи са Контури (зад.1) и Улица (зад.6). Решенията на останалите задачи ще намерите във файловете equal.c, flow.c, sum.c и tickets.c.

Съдържание



 
 

4.Динамично оптимиране. Задача за разделянето

Преслав Наков

От този брой нататък смятаме да публикуваме по някоя статия на утвърден в България автор. В брой 18 наш "гост" е Преслав Наков, а статията му е издавана в сп. Byte Bulgaria (бр. 11/99). Статията е във файла razdel.doc.

Съдържание



 
 

5.Три интересни алгоритъма

 Васил Поповски

Ето няколко задачи, които Васил Поповски даде преди доста време но едва сега се сетихме и за тях. Задачите са известни, но все пак не от тези, които се падат на всяко сътезание. Те са във файловете findroot.pas, n_minmax.pas и matpath.pas

Съдържание



 
 

6.Други две задачи

 Светлин Наков

Светлин Наков и този път се включи със две задачи. Сорсовете са в tables.pas и turist.pas.

Съдържание



 
 

7.Програминят език C и вискоката памет

Мартин Русков

Много често в практиката на програмирането се случва някой бърз алгоритъм да не може да се напише заради недостиг на памет. Особено често това се случва на състезания, където всяка секунда е ценна. Този проблем е направо смешен при днешните машини, които разполагат с десетки мегабайти RAM памет, но си има и логичното обяснение: Компилаторите, които се използват са 16-битови и един от недостатъците им е факта, че те могат да работят само с долните 64K от паметта. Дотук едва ли казвам на някой нещо ново, но целта на тази статия е именно да предложи решение на този проблем.
Единия изход от ситуацията е да се премине на 32-битови компилатори, което за съжаление не зависи от нас - състезателите. Все пак който се интересува, може да изтегли безплатни версии на някои 32-битови компилатори като GCC (http://www.delorie.com) и Borland C 5.0 (http://www.borland.com.) Специално с Borland C нещата стоят по следния начин: версия 5.0 е първата 32-битова и вече безплатна, а МОИ (доколкото знам и ACM,) разрешават ползването само на версия 3.1. Не съм сигурен за номера на версията, но със сигурност е 16-битова.
Тук му е мястото да спомена, че аз използвам 32-битов компилатор и затова може би на 16-битов компилатор някои решения, публикувани в Инфоман, извеждат грешка за недостиг на памет.
Нещото, което беше ново за мен, и надявам се, за вас е това, че в тази най-популярна версия на Borland C има и команди за управление на високата памет. Те разбира се са много по-бавни от тези за ниската, но все пак представляват едно доста голямо предимство. Едно от нещата характерни за тях е, че поддържат само динамична памет. Едва ли има много смисъл от много приказки още, при положение, че за целта си има help. Само ще дам един малък пример, за да имате представа какви ключови думи да търсите и как да си организирате алокирането и освобождаването на паметта.
#include <stdio.h>
#include <alloc.h>
#include <dos.h>
#include <mem.h>

#define N 1000

int far * a[N];

main()
{
  for( i = 0; i <= N; i++ )
  {
    a[i] = (int far *) farmalloc( N * sizeof( int ));
    if( a[i] == NULL )
    {
      printf( "Allocation error" );
      for( j = 0; j < i; j++ )
        farfree( a[j] );
      exit( 0 );
    }
    _fmemset( a[i], 0, sizeof( int ) * N );
  }

  for( i = 0; i < N; i++ )
    for( j = 0; j < N; j++ )
      a[i][j] = i - j;

  for( i = 0; i <= N; i++ )
    farfree( a[i] );
}

Може би сега е момента да спомена, че това "откритие" го направи Мартин Вълканов от СМГ.
А иначе проблема си остава за така наречените паскалджии... може би. Ако някой от вас намери подобни команди в Borland Pascal 7.0, ще се радваме ние да сме тези, които ще го разпространят. А 32-битови компилатори за Паскал също има. Например GPC (http://www.delorie.com,) но засега той е много бъгав. А и винаги остава възможността да се премине не C.
 

Съдържание



 
 

8.Заключение

(Infoman)

Както обикновенно всяка помощ от Ваша страна е винаги добре дошла, така че ако имате интересни задачи, алгоритми, решения или просто забележки, моля изпращайте ни ги. Всякакви коментари за новостите и препоръки са също добре дошли при нас.
Това е засега и очаквайте скоро брой 19 посветен на семинара в Габрово.
 

Съдържание