на первую страницу

РЕШЕНИЯ ИЗБРАННЫХ ЗАДАЧ

1. Вычисление значений арифметических выражений

/********************************************************************/
/*                                                                  */
/*  EXPR_VAL.C                                                      */
/*  Вычисление значения выражения. Алгоритм Бауэра-Замельзона       */
/*                                                                  */
/********************************************************************/
#include 
#include 
#include 
#include 

struct ChStackElem {
  char symbol;
  struct ChStackElem *next;
};

struct IntStackElem {
  long number;
  struct IntStackElem *next;
};

/* используется для хранения операторов и скобок */
struct ChStackElem  *operators = 0; 
/* используется для хранения операндов */
struct IntStackElem *operands  = 0; 
/* используется для хранения считанного числа */
char   number[11];           

char operators_top (void);
char operators_pop (void);
void operators_push(char); /* операции для работы со стеками */
long operands_pop  (void);
void operands_push (long);
void do_operation(char); /* выполнение конкретной 
арифметической операции */
/*
   Алгоритм предполагает последовательное считывание 
символов и выполнение двух основных шагов:
   1. Если считано число, то оно помещатся в стек операндов.
   2. Если считан символ операции или скобки, 
о либо он помещается в стек операторов, 
либо выполняется операция, обозначаемая оператором
 на вершине стека.
*/
int main()      
{
  FILE *in, *out; int i, ch, count=0;
  in  = fopen("expr_val.in", "r");
  out = fopen("expr_val.out","w");
  while((ch=getc(in)) != '0') {
    top_of_switch: switch(ch) {
    case ' ': case '\t': case '\n':
     if(operators_top()=='\x00') {/* конец обработки 
                очередного выражения */
        if(count!=0) fprintf(out,"\n\n");
        fprintf(out,"Expression #%d\n%ld",++count,operands_pop());
        if(ch!='\n') while(getc(in) != '\n'); /* пропуск хвостовых */
        continue;                             /* пустых символов   */
      }
      else /* любой оператор */
        { do_operation(operators_pop()); goto top_of_switch; }
    case '(': /* при любом содержимом вершины стека */
      operators_push(ch); continue;
    case ')':
      if(operators_top()=='(')
        { operators_pop(); continue; }
      else /* любой оператор */
        { do_operation(operators_pop()); goto top_of_switch; }
    case '+': case '-':
      switch(operators_top()) {
      case '\x00': case '(': operators_push(ch); continue;
      case '+'   : case '-': do_operation(operators_pop()); 
                             operators_push(ch); continue;
      default    : /* операторы '*', '^' */
        do_operation(operators_pop()); goto top_of_switch;
      }
    case '*':
      switch(operators_top()) {
        case '*': do_operation(operators_pop()); operators_push(ch); 
                  continue;
        case '^': do_operation(operators_pop()); goto top_of_switch;
        default : /* пустой стек, '(' и операторы '+', '-' */
          operators_push(ch); continue;
      }
    case '^': /* при любом содержимом вершины стека */
      operators_push(ch); continue;
    default :/* если цифровой символ, то считываем 
                      число и заносим в стек */
      i = 0;
      do number[i++] = ch; while(isdigit(ch=getc(in)));
      number[i] = '\x00';  ungetc(ch,in);
      operands_push(atol(number));
    }
  }
  fcloseall();
  return 0;
}                  

void do_operation(char oper)
{
  long op1,op2,res;
  op2 = operands_pop();
  op1 = operands_pop();
  switch(oper) {
  case '+': res = op1+op2; break;
  case '-': res = op1-op2; break;
  case '*': res = op1*op2; break;
  case '^': res = pow(op1,op2);
  }
  operands_push(res);
}

char operators_top(void)
{
  return operators ? operators->symbol : '\x00';
}

char operators_pop(void)
{
  struct ChStackElem *to_delete; char ch;
  if(operators==0) return '\x00';
  to_delete = operators;
  operators = to_delete->next;
  ch = to_delete->symbol;
  free(to_delete);
  return ch;
}

void operators_push(char ch)
{
  struct ChStackElem *new_elem;
  new_elem = (struct ChStackElem*)
         malloc(sizeof(struct ChStackElem));
  if(new_elem==NULL) exit(1);
  new_elem->symbol = ch;
  new_elem->next   = operators;
  operators        = new_elem;
}

long operands_pop(void)
{
  struct IntStackElem *to_delete; long number;
  if(operands==0) return 0; /* на всякий случай */
  to_delete = operands;
  operands  = to_delete->next;
  number    = to_delete->number;
  free(to_delete);
  return number;
}

void operands_push(long number)
{
  struct IntStackElem *new_elem;
  new_elem = (struct IntStackElem*)
       malloc(sizeof(struct IntStackElem));
  if(new_elem==NULL) exit(1);
  new_elem->number = number;
  new_elem->next   = operands;
  operands         = new_elem;
}

2. Унификация термов 

/********************************************************************/
/*                                                                  */
/*  TERMUNIF.C                                                      */
/*  Унификация термов (нахождение наиболее общего унификатора)      */
/*                                                                  */
/********************************************************************/

#include 
#include 
#include 
/*
  Нахождение наиболее общего унификатора основано на 
сопоставлении деревьев, 
которые строятся при вводе термов. В ходе сопоставления 
создается список, содержащий элементы 
подстановки. В случае успеха подстановка выводится в файл. 
Так как в процессе вывода списка 
элементы перебираются в порядке обратном добавлению, 
то термы-деревья обходятся справа - налево, 
а не слева - направо.
*/
FILE *in, *out;
char token; /* последняя считання лексема */

enum NodeType {constant,variable,function};
struct TermNode {
  enum NodeType type;
  char name;
  struct TermNode *left_term;
  struct TermNode *right_term;
};
typedef struct TermNode* Term;

struct ListNode {
  Term variable;
  Term term;
  struct ListNode *next;
};
struct ListNode *substitution = 0;

Term read_term  (void);
void write_term (Term);
void free_term  (Term);
int  unify_terms(Term,Term);
void add_to_substitution(Term,Term);
void write_substitution (void);
void delete_substitution(void);

int main(void)
{
  Term term1,term2; int i,pairs;
  in  = fopen("termunif.in", "r");
  out = fopen("termunif.out","w");
  fscanf(in,"%d",&pairs);
  while(getc(in) != '\n');   /* пропускаем хвостовые 
                                 пустые символы */
  for(i=1; i<=pairs; ++i) {
    while(getc(in) != '\n'); /* пропускаем пустую строку */
    term1 = read_term(); while(getc(in)!='\n');
    term2 = read_term(); while(getc(in)!='\n' && !feof(in));
    fprintf(out,"Pair #%d\n",i);
    if(unify_terms(term1,term2)) write_substitution();
    else fprintf(out,"Not unified");
    if(iname = token;
  switch(token) {
  case 'a': case 'b': case 'c': case 'd':
    node->type = constant; break;
  case 'u': case 'x': case 'y': case 'z':
    node->type = variable; break;
  case 'f': case 'g': case 'h': case 'j':
    node->type = function;
    getc(in); /*'('*/
    node->left_term  = read_term();
    getc(in); /*','*/
    node->right_term = read_term();
    getc(in); /*')'*/
  }
  return node;
}

void write_term (Term term)
{
  fputc(term->name,out);
  if(term->type==function) {
    fputc('(',out);
    write_term(term->left_term);
    fputc(',',out);
    write_term(term->right_term);
    fputc(')',out);
  }
}

void free_term(Term term)
{
  if(term->type==function)
    { free_term(term->left_term); free_term(term->right_term); }
  free(term);
}

int unify_terms(Term term1, Term term2)
{
  if(term1->type==constant && term2->type==constant)
    return term1->name==term2->name;
  if(term1->type==function && term2->type==function)
    return term1->name==term2->name /* обходим дерево 
                           справо-налево */
        && unify_terms(term1->right_term,term2->right_term)
        && unify_terms(term1->left_term, term2->left_term);
  if(term1->type==variable)
    { add_to_substitution(term1,term2); return 1; }
  if(term2->type==variable)
    { add_to_substitution(term2,term1); return 1; }
  return 0;
}

void add_to_substitution(Term var, Term term)
{
  struct ListNode *new_node
    = (struct ListNode*)malloc(sizeof(struct ListNode));
  if(new_node==NULL) exit(1);
  new_node->variable = var;
  new_node->term     = term;
  new_node->next     = substitution;
  substitution       = new_node;
}

void write_substitution(void)
{
  struct ListNode *cur_node;
  if(substitution==0)
    fputs("{}",out);
  else {
    fputc('{',out);
    for(cur_node=substitution; cur_node; cur_node=cur_node->next) {
      write_term(cur_node->variable);
      fputc('/',out);
      write_term(cur_node->term);
      if(cur_node->next) fputc(';',out); /* после 
                            последнего элемента */
    }               /* ';' выводить 
                            не надо */
    fputc('}',out);
  }
}

void delete_substitution(void)
{
  struct ListNode *cur_node;
  while(substitution) {
    cur_node = substitution;
    substitution = cur_node->next;
    free(cur_node);
  }
}


3. Замкнутый путь

{******************************************************************
Замкнутый путь
Дана матрица соединений, отражающая соединения 
вершин некоторого графа (ненаправленного),
 требуется определить существует ли такой 
замкнутый путь, который проходит 
через все вершины графа.
Проблемы создает то что требуется найти замкнутый 
путь и он должен обойти все вершины, 
а не часть из них и то что каждая вершина в пути 
должна встречаться один раз.
Будем считать, что матрица соединений составлена 
таким образом, что соединения первой 
вершины с остальными записаны в первой строке, 
второй вершины - во второй строке и т.д. 
На самом деле это не принципиально, т.к. матрица 
соединений симметрична относительно главной 
диагонали a[i,j]=a[j,i].
Алгоритм выглядит следующим образом:
Берем первую строку матрицы, проверяем последовательно 
каждый ее элемент. Если находим
 что элемент равен единице, то запоминаем номер 
первой вершины во множестве и проверяем 
строку, соответствующую данному элементу и т.д.  
После того как путь замкнулся, требуется 
проверить все ли вершины входят в составленный путь.
 Если нет, то начинаем проверять 
опять первую строку, но последующие элементы равные 
единице. Можно исключать преждевременно 
замкнутые пути в ходе проверки строк матрицы 
например 7 вершин графа, 
соединения 1-2, 2-3, 3-1 3-4 3-5, исключить 
краткий путь 1-2-3-1). 
Также требуется исключить пути, которые включают 
одну вершину дважды. Проверив таким образом 
все элементы первой строки, если мы нашли путь, 
который  проходит через все вершины, то 
указываем, что он существует. Если же ни один 
путь, начиная с первой вершины не существует, то 
можно сделать вывод, что замкнутого пути, 
проходящего через все точки, не существует.

Программные реализации могут отличаться. 
Данная программа реализована на основе рекурсивного 
вызова одной функции.
 ******************************************************************}

PROGRAM matrix;

VAR
   i,j,k,r:byte;
   points:set of byte;

VAR
  str1,st               : string[255];
  p,code,n              : integer;
  m:array [1..50,1..50] of byte;
  f_input,f_output      : text;



function link(i,j:byte):boolean;
var t:byte;
    L:boolean;
begin
points:=points+[i];r:=r+1;
L:=False;
For t:=1 to N do
 If (t<>i) and (m[i,t]=1) and 
            ( Not(t in points) or ((r=N) and (t=1))) then
           Begin
            if t=j then L:=True else
               if link(t,j) then L:=True;
                      End;
points:=points-[i];r:=r-1;
link:=L;
end;

BEGIN

assign(f_input,'input.txt');
Reset(f_input);

readln(f_input,str1);
Val(copy(str1,1,3),N,code);

  i := 0;
  REPEAT
    i := i + 1;
    readln(f_input,str1);
    j := 0;
    IF str1[length(str1)] <> ' ' THEN str1 := str1 + ' ';
    REPEAT
      j := j + 1;
      p := pos(' ',str1);
      Val(copy(str1,1,p-1),m[i,j],code);
      str1 := copy(str1,p+1,length(str1)-p)
    UNTIL length(str1)=0;
  UNTIL eof(f_input);
  Close(f_input);


r:=0;
assign(f_output,'output.txt');
rewrite(f_output);

if link(1,1) then begin
{                 writeln('1');}
                  writeln(f_output,'1');
                  end
             else begin
{                  writeln('0');}
                  writeln(f_output,'0');
                  end;
close(f_output);
end.


4. Точки (2)
{*************************************************************
Точки (2)

Дано N точек на плоскости, требуется построить 
на их основе фигуру наибольшей площади, 
при этом некоторые точки могут оставаться внутри фигуры.

Фигурой наибольшей площади в данном примере 
будет выпуклый многоугольник. Процедура 
определения выпуклого многоугольника выглядит 
следующим образом.

Выпуклый многоугольник - это многоугольник, для 
которого выполняется следующее условие:

Если через любые две его вершины провести прямую, 
то остальные вершины должны находиться 
по одну сторону от этой прямой.

Выполняем цикл для каждой пары точек. Составляем 
для каждой пары точек уравнение прямой. 
Подставляем в это уравнение все остальные точки и 
смотрим находятся ли они с одной стороны от прямой. 
Для этого требуется выбрать некую точку в стороне от 
прямой и подставить координаты ее и тестируемой точки 
в уравнение прямой. Если знак в уравнении прямой > 0, 
то они лежат по одну сторону от прямой, если нет - то по разные. 

Функция - уравнение прямой f(x,y)=(x-x1)/(x2-x1)-(y-y1)/(y2-y1)

выбранная точка N(n1,n2)
проверяемая точка K(k1,k2)

f(N)*f(K) > 0 - точки лежат по одну сторону

f(N)*f(K) < 0 - точки лежат по разные стороны

На одной прямой они лежать не могут, т.к. по 
условию задачи более двух точек не лежат на 
одной прямой одновременно, а точка N выбирается 
таким образом, чтобы не лежать на одной прямой с 
теми точками, через которые строится прямая.

Подсчитав число точек с той и другой стороны, 
можно сделать вывод о том,
 что эта пара точек (через которые проведена прямая) 
подходит или не подходит в качестве вершин выпуклого 
многоугольника. Выполнив цикл для всех точек, мы определим все 
вершины многоугольника и какая с какой соединена.
******************************************************************}

PROGRAM points;
USES graph;
TYPE point=array [1..100] of integer;

{CONST Number_of_points=3;}

{VAR
 grDriver: Integer;
 grMode:   Integer;
 ErrCode:  Integer;}

VAR

Number_of_points:     Integer;

x,y:                  array[1..100] of Integer;
result:               array[1..100,1..100] of Integer;
i,j,k:                Integer;
one_side,other_side:  Integer;
tmp:                  Real;
x4,y4:                Integer;
string_number:        String[3];

f_input:              text;
f_output:             text;
str1,st:              string[255];
p,m,n,code:           integer;


FUNCTION F(x1,y1,x2,y2,x3,y3,x4,y4:integer):real;
VAR f1,f2:real;
BEGIN

if (x1=x2) then f:=(x3-x1)*(x4-x1) else
if (y1=y2) then f:=(y3-y1)*(y4-y1) else
begin
f1:=(x3-x1)/(x2-x1)-(y3-y1)/(y2-y1);
f2:=(x4-x1)/(x2-x1)-(y4-y1)/(y2-y1);
f:=f1*f2;
end;

END;


BEGIN

assign(f_input,'input.txt');
Reset(f_input);

readln(f_input,str1);
Val(copy(str1,1,3),Number_of_points,code);
{writeln('Val=',Number_of_points);}

for i:=1 to Number_of_points do begin
  readln(f_input,str1);
  p := pos(' ',str1);
  Val(copy(str1,1,p-1),x[i],code);
  str1 := copy(str1,p+1,length(str1)-p);
  p := pos(' ',str1);
  IF p > 0 THEN  Val(copy(str1,1,p-1),y[i],code) 
           ELSE Val(str1,y[i],code);
end;

close(f_input);


for i:=1 to Number_of_points do
for j:=1 to Number_of_points do
result[i,j]:=0;


{Случайные точки на плоскости}

{Randomize;
for i:=1 to Number_of_points do begin
x[i]:=random(299)+1;
y[i]:=random(299)+1;
end;}

{
x[1]:= 3; y[1]:= 7;
x[2]:= 9; y[2]:= 5;
x[3]:= 4; y[3]:= 3;
x[4]:= 6; y[4]:= 6;
x[5]:= 7; y[5]:= 2;
x[6]:= 9; y[6]:= 9;
x[7]:= 2; y[7]:= 4;
x[8]:= 6; y[8]:= 4;
x[9]:= 6; y[9]:= 7;
x[10]:= 8; y[10]:= 6;
}

{Все, кроме одной, точки лежат на одной прямой}

{x[1]:= 10; y[1]:= 10;
x[2]:= 50; y[2]:= 10;
x[3]:= 10; y[3]:= 50;
{x[4]:= 50; y[4]:= 50;
x[5]:= 50; y[5]:= 50;
x[6]:= 60; y[6]:= 60;
x[7]:= 70; y[7]:= 70;
x[8]:= 80; y[8]:= 80;
x[9]:= 90; y[9]:= 90;
x[10]:= 40; y[10]:= 10;

{
x[1]:= 4; y[1]:= 9;
x[2]:= 1; y[2]:= 8;
x[3]:= 2; y[3]:= 4;
x[4]:= 3; y[4]:= 6;
x[5]:= 4; y[5]:= 5;
x[6]:= 6; y[6]:= 6;
x[7]:= 5; y[7]:= 2;
}


{assign(f_output,'points.txt');
rewrite(f_output);
writeln;
for i:=1 to Number_of_points do begin
writeln(x[i],' ',y[i]);
writeln(f_output,x[i],' ',y[i]);
end;
close(f_output);
readln;
}


{grDriver := Detect;
InitGraph(grDriver, grMode,' ');
ErrCode := GraphResult;
if ErrCode = grOk then
begin
  for i:=1 to Number_of_points do begin
  putpixel(200+x[i],100+y[i],14);
  str(i,string_number);
  outtextxy(200+x[i]-10,100+y[i]-10,string_number);
  end;
  Readln;
  CloseGraph;
end
else
  Writeln('Graphics error:', GraphErrorMsg(ErrCode));
}

{writeln;writeln('Result points:');}

for i:=1 to Number_of_points do begin

for j:=1 to i{Number_of_points} do begin

x4:=-Random(1234);
y4:=-Random(4321);

if (i<>j) then begin

one_side:=0; other_side:=0;

for k:=1 to Number_of_points do begin

if (k<>i) AND (k<>j) then begin

tmp:=f(x[i],y[i],x[j],y[j],x[k],y[k],x4,y4);

if tmp>=0 then Inc(one_side) else Inc(other_side);

end; {if k<>i and k<>j}

end; {for k}

if (other_side=Number_of_points-2) or 
          (one_side=Number_of_points-2) then
begin
{writeln('Point',i,':','x',i,'=',x[i],' y',i,'=',y[i]);
writeln('Point',j,':',' x',j,'=',x[j],' y',j,'=',y[j]);}
{writeln('Point',i,'->',j);}
result[i,j]:=1;
result[j,i]:=1;
end;

end; {if i<>j}

end; {for j}

end; {for i}


assign(f_output,'output.txt');
rewrite(f_output);

{writeln;}
for j:=1 to Number_of_points do begin
for i:=1 to Number_of_points do begin
write(f_output,result[i,j],' ');
{write(result[i,j],' ');}
end;
writeln(f_output,' ');
{writeln;}
end;

close(f_output);
END.

Председатель жюри:
Дьяконов Максим Валерьевич
e-mail: mdia{at}cs.karelia.ru