Nickolay.info. Тексты. Универсальная программа

Статья появилась как результат слегка юмористического переосмысления результатов работы над задачами для олимпиад по программированию.

По сути дела, есть всего 2 способа решения любой задачи на компьютере.

кстати: старый анекдот гласит, что решение любой задачи на ЭВМ можно свести к одному трехшаговому алгоритму:

Во-первых, для решения может понадобиться полный перебор всех подмножеств множества или генерация подмножеств заданной мощности или полный просмотр массива данных для извлечения нужной информации. Так работает большинство алгоритмов отбора и извлечения данных, включая просмотр БД с помощью SQL-запросов, различного рода сортировки и перестановки, требующие сравнения по принципу "каждый с каждым" и т.п.

Во-вторых, приложив усилия, перебор можно сделать неполным, заботясь об отсечении заведомо лишних "неперспективных" конфигураций данных, вводя критерий оптимизации, позволяющий направленно отбирать варианты, используя метод ветвей и границ и т.п.

кстати: один мой знакомый профессор за "рюмкой чая" выразил эту мысль гораздо короче: есть только перебор и недобор.

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

В частности, большинство олимпиадных задач по программированию относятся к задачам дискретной математики, которые, в свою очередь, сводятся к перебору различных подмножеств множества объектов и выбору среди них наилучшего с точки зрения условий той или иной задачи. Поэтому знание алгоритмов генерации наиболее употребительных конфигураций комбинаторики - необходимое условие успеха на олимпиаде по информатике. Немаловажно также уметь оценивать общее количество различных вариантов для той или иной комбинаторной конфигурации, что позволяет реально оценить вычислительную трудоемкость переборного алгоритма для интересующей нас размерности массива данных.

Можно выделить 3 основные комбинаторные конфигурации:

  1. генерация k-элементных подмножеств множества, состоящего из n элементов, где n>k; сюда же относится задача получения различных сочетаний по k элементов из n;
  2. если мощность k искомого подмножества неизвестна, требуется генерация всех подмножеств данного множества из n элементов;
  3. наконец, если ищется не подможество, а лишь порядковая конфигурация элементов, возникает задача о различных перестановках элементов n-элементного множества.

Рассмотрим каждый из этих классов задач.

1. Генерация k-элементных подмножеств

В комбинаторике количество различных сочетаний из n элементов по k обозначается Cnk и считается по хорошо известной формуле

При этом для фиксированного n выполняется соотношение Cn1 = Cnn-1 = n, а максимального значения число сочетаний достигает при k=n/2. Как правило, генерацию k-элементных подмножеств проводят в "естественном" лексикографическом порядке, что не приводит к усложнению или увеличению вычислительной трудоемкости.

Порядок двух подмножеств по k элементов из n называется лексикографическим, если для любых двух подмножеств справедливо, что первым генерируется то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления. Так, для n=10 и k=4 сочетание из третьего, второго, восьмого и шестого элементов генерируется раньше, чем из девятого, третьего, седьмого и четвертого, так как 2368<3479.

Как и в большинстве переборных задач, на помощь приходит рекурсия, суть которой - сведение задачи к "самой себе", но меньшей размерности (путь по лабиринту = один шаг + путь по лабиринту, уменьшенный на один шаг). В нашем случае первым элементом подмножества мощности k может быть любой из элементов, начиная с первого и заканчивая (n-k+1)-ым. После того, как индекс первого элемента подмножества зафиксирован, нам остается выбрать k-1 элемент из элементов с индексами, большими чем у первого. Далее поступаем аналогично, сводя задачу к меньшей размерности до тех пор, пока на низшем уровне рекурсии не будет выбран последний элемент, после чего выбранное подмножество можно распечатать или обработать.

В приведенной ниже программе на Паскале массив A содержит произвольные числовые значения исходного множества, а массив P предназначен для формирования очередного сочетания из k элементов. Процедура cnk имеет параметры m - количество элементов множества, которые осталось выбрать и l - номер элемента в исходном множестве, с которого начинается выбор.

const n1=20; {Максимальная размерность множества!}
type vector=array[1..n1] of integer;
var k,n,i,j:integer;
        a,p:vector;
procedure cnk(m,l:integer);
var i:integer;
begin
  if m=0 then begin
   for j:=1 to k do write(p[j]:4); {Здесь - обработка комбинации}
   write (#9);
  end
  else
  for i:=l to n-m+1 do {цикл по возможным индесам для выбора
                            первого из m элементов}
  begin
   p[k-m+1]:=a[i];
   cnk(m-1,i+1)
  end
end;

begin
  writeln ('Подмножества из N по K');
  writeln ('Введите N,K:');
  read(n,k);
  for i:=1 to n do
    a[i]:=i; {данный массив может быть заполнен произвольно}
  cnk(k,1);
end.

Отказ от рекурсии не порождает каких-либо сложностей: в этом случае необходимо и достаточно описать переход от данного подмножества к следующему за ним в лексикографическом порядке плюс условие окончания генерации подмножеств. При этом первое подмножество состоит из первых k элементов исходного множества.

Если b1, b2, ..., bk - индексы элементов некоторого подмножества, то, при bk1, b2, ..., bk-1, bk+1. Если в результате этого процесса последний элемент уже достиг границы массива bk=n, то на единицу будет увеличен индекс bk-1, а последний индекс в наборе станет равен bk-1+2. После того, как предпоследний индекс также исчерпает возможность для увеличения, изменяться будет элемент bk-2 и т.д. Если минимальный из изменяемых при переходе к очередному сочетанию индексов обозначить q, то следующее сочетание имеет вид b1, b2, ..., b(q-1)-1, bq-1+1, bq-1+2, ..., bq-1+(k-(q-1)+1), если последний индекс в предыдущему сочетании равен n. Если же последний индекс в предыдущем сочетании меньше n, то есть, меняется только последний элемент, величину q-1 в формуле следует заменить на k.

Условием окончания генерации сочетаний может служить невозможность увеличения индекса первого элемента, то есть q=1 и bk = n. Следующая программа, в отличие от первой, формирует не само подможество, а только набор {bj} индексов его элементов, однако получение элементов по этим индексам тривиально - a[bj].

const n1=20; {Максимальная размерность множества!}
type vector=array [1..n1] of integer;
var k,i,j,n,q:integer;
    a,b:vector;
begin
 writeln ('Подмножества из N по K');
 write ('Введите N,K:');
 read(n,k);
 for i:=1 to n do
  a[i]:=i;{данный массив может быть заполнен произвольно}
 for i:=1 to k do
  b[i]:=i;{массив индексов заполняется однозначно}
  q:=k;
 while q>=1 do begin
  for j:=1 to k do write(a[b[j]]:4); {Здесь - обработка комбинации}
  write (#9);
  if b[k]=n then q:=q-1
  else q:=k;
  if q>=1 then begin
   b[q]:=b[q]+1;
   for i:=q+1 to k do b[i]:=b[i-1]+1
  end;
 end;
end.

2. Генерация всех подмножеств данного множества

Весьма часто мы не знаем, сколько именно элементов исходного множества должно входить в искомое подмножество, а это значит, что требуется перебрать все возможные подмножества. Естественным выглядит подобный случаю 1 "лексикографический" перебор, то есть проверка сначала всех подмножеств, состоящих из одного элемента, затем из двух, трех и т.д. Кроме того, немало задач, где требуется найти именно минимальное (или максимальное при обращении порядка перебора) подмножество, и в этом случае первое же подмножество, удовлетворяющее условию задачи будет искомым, что позволит прервать цикл обработки.

У нас уже есть процедура cnk, умеющая формировать подмножества. Для иллюстрации возможно более общей схемы решения мы введем в нее дополнительный параметр-флаг var flag:boolean, который будет обозначать, удовлетворяет текущее сочетание элементов P мощностью k условию задачи либо нет, а проверкой соответствия подмножества условию займется функция check(p,k):boolean.

В основной программе единственное обращение к процедуре cnk для выбора подмножеств мощности n следует заменить циклом по k от 1 до n, позволяющим перебрать все подмножества. Получится следующий код:

const n1=20; {Максимальная размерность множества!}
      SUM=50; {Константа только для примера, см. ниже по тексту}
type vector=array[1..n1] of integer;
var k,n,i,j:integer;
        a,p:vector;
        flag:boolean;

function check (var p:vector; n:integer):boolean;
var i,s:integer;
begin {Здесь критерий решения - сумма элементов множества больше константы SUM}
      {Естественно, в Вашей задаче будет Ваш критерий}
 s:=0;
 for i:=1 to n do begin
  write (p[i]:3); {это только отладочная печать для иллюстрации}
  s:=s+p[i];
 end;
 writeln (s:6); {это только отладочная печать для иллюстрации}
 if s>SUM then check:=true
 else check:=false;
end;

procedure cnk(m,l:integer;var flag:boolean);
var i:integer;
begin
  if m=0 then begin {Здесь - проверка комбинации}
   flag:=check(p,k);
   if flag=true then exit;
  end
  else
  for i:=l to n-m+1 do {цикл по возможным индесам для выбора
                            первого из m элементов}
  begin
   p[k-m+1]:=a[i];
   cnk(m-1,i+1,flag);
   if flag=true then break; {иначе м.б. выдан не 1-й найденный вариант}
  end
end;

begin
  writeln ('Все подмножества из N');
  writeln ('Введите N:');
  read(n); {естественно, k в этой задаче не вводится}
  for i:=1 to n do
    a[i]:=i; {данный массив может быть заполнен произвольно}
  k:=0;
  flag:=false;
  repeat {выбираем все возможные подмножества}
   k:=k+1;
   cnk(k,1,flag)
  until flag or (k=n);
  if flag then begin {есть решение}
   for i:=1 to k do write(p[i]:4);
  end
  else writeln('нет решения');
  reset (input); readln;
end.

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

Для любого возможного подмножества характерно то, что каждый элемент исходного множества либо принадлежит, либо не принадлежит ему :) Выразить столь ученую мысль проще можно, обозначив принадлежность единицей, а не-принадлежность - нулем. Но тогда каждому подмножеству соответствует просто n-значное число в двоичной системе счисления!

Следует только учесть, что двоичные числа в этом случае могут начинаться с произвольного количества незначащих нулей. Иначе говоря, можно сказать, что совокупность всех подмножеств множества мощностью в n элементов - это n- или менее значные двоичные числа.

Отсюда ясно, что полный перебор всех подмножеств данного множества - это перебор всех двоичных чисел от n нулей до n единиц включительно. Первое из этих чисел соответствует пустому множеству, последнее - исходному. Таким образом, сопоставив 2 способа перебора всех подмножеств данного множества, можно прийти к формуле
Cn1 + Cn2 + Cn3 + ... + Cnn-1 + Cnn = 2n-1

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

Взяв пример с суммой чисел, рассмотренный выше, напишем соответствующее решение.

Дан целочисленный массив A размерностью N и число M. Найти такое множество элементов A[i1],A[i2],...A[ik], что 1<=i1<i2<i3<...<ik<=N и A[i1]+A[i2]+...+A[ik]=M.

const n1=31;
type vector=array[1..n1] of integer;
var a:vector;
    i:integer;

function subsets1(n,m:longint):boolean;
var k,s:integer;
    q,j:longint;
begin
 q:=(1 shl n); {это быстрое вычисление q=2 в степени n}
 for j:=1 to q-1 do begin {цикл по всем подмножествам}
  s:=0;
  for k:=1 to n do
   if ((j shr (k-1))and 1)=1 {условие означает, что в
   k-ой справа позиции числа j в двоичной записи стоит 1}
    then s:=s+a[k];
  if s=m then begin
   for k:=1 to n do
    if ((j shr (k-1))and 1)=1 then write(a[k]:4);
   writeln;
   subsets1:=true;
   exit;
  end;
 end;
 subsets1:=false;
end;

var n,m:longint;
begin
 writeln ('Введите N (1..31)');
 read (n);
 writeln ('Введите сумму M');
 read (m);
 for i:=1 to n do a[i]:=i;
 if subsets1(n,m)=false then write ('Решения нет');
 reset (input); readln;
end.

В этом листинге существенно используется умение процессора быстро работать с двоичными числами. Так, операция A shl B, означающая сдвиг двоичного представления операнда A на B бит влево, соответствует B-кратному умножению числа A на 2, выполняемому с минимальными вычислительными затратами. Аналогично, операция A shr B сдвигает операнд A на B бит вправо, производя соответствующее число раз целочисленное деление на 2. Увы, платой за эффективность становится ограничение диапазона обрабатываемых чисел. Тип данных longint, на который отводится 4 байта или 32 бита оперативной памяти, позволяет вводить значение N, не превышающее 31 (231 - предельное значение для longint, т.к. один старший бит используется под знак). При этом, уже для n=30 и m=200 время решения становится заметным - несколько секунд. Но на самом деле, перебор всех подмножеств у множеств большей размерности едва ли актуален - независимо от вычислительной мощности процессора на это потребуется значительное время.

Тем не менее, приведем для сравнения вариант программы, снимающей ограничение на размерность множества. Здесь в массиве B, длина которого соответствует количеству элементов N исходного множества, будет храниться двоичное представление текущего числа. Логическая переменная flag становится истинной тогда, когда прибавить единицу к текущему числу уже невозможно, то есть, достигнуто окончание перебора.

const n1=50;
type vector=array[1..n1] of integer;
var a:vector;
    b:array[1..n1] of 0..1;
    i:integer;
    flag:boolean;

procedure plus1(n:integer);
{прибавление единицы в двоичной системе счисления}
begin
 if n>0 then
  if b[n]=0 then b[n]:=1
  else begin
   b[n]:=0;
   plus1 (n-1);
  end
 else flag:=true;
end;


function subsets2 (n,m:longint):boolean;
var k:integer;
    s:longint;
begin
 for k:=1 to n do b[k]:=0; {начинаем со всех нулей}
 flag:=false;
 repeat {повторять пока не установлен флаг}
  plus1(n);
  s:=0;
  for k:=1 to n do
   if b[k]=1 then s:=s+a[k];
  if s=m then begin
   for k:=1 to n do
    if b[k]=1 then write(a[k]:4);
   writeln;
   subsets2:=true;
   exit;
  end;
 until flag;
 subsets2:=false;
end;

var n,m:longint;
begin
 writeln ('Введите N');
 read (n);
 writeln ('Введите сумму M');
 read (m);
 for i:=1 to n do a[i]:=i;
 if subsets2(n,m)=false then write ('Решения нет');
 reset (input); readln;
end.

За некоторое время (не столь уж малое, несколько часов в фоновом режиме) эта программа нашла решение для N=40 и M=800. Для N=50 и M=1200, думаю, жизни компьютера бы не хватило :)

Из теории Вы наверняка помните, что глубокие рекурсии чреваты переполнением стека. Но подпрограмма plus1 и не обязана быть рекурсивной. Вот ее не-рекурсивный вариант:

procedure plus1(n:integer);
var i:integer; 
begin 
 i:=n; 
 while (i>0) and (b[i]=1) do begin 
  b[i]:=0; i:=i-1;
 end; 
 if i>0 then b[i]:=1
 else flag:=true;
end; 

Цифры двоичных чисел в программах subsets2 занумерованы слева направо, поэтому рассмотрение начинается не с первой цифры, а с последней. Ранее мы нумеровали цифры справа налево, что соответствовало обратному порядку рассмотрения подмножеств. Теоретически это различие несущественно, но оно может привести к тому, что что найденные решения будут различными. При желании можно устранить расхождение, поставив в соответствие последнему элементу массива B первый элемент массива A, предпоследнему - второй и т. д. Второй вариант - переписать процедуру plus1 так, чтобы нумерация цифр поменялась на противоположную.

3. Генерация всех перестановок множества из n элементов

Легко подсчитать, что n элементов могут быть переставлены между собой 1*2*...*n=n! способами. Действительно, на первом месте в перестановке может стоять любой из n элементов массива, после того, как на первом месте зафиксирован какой-либо элемент, на втором месте может стоять любой из n-1 оставшихся элементов и т.д.

Генерация всех перестановок в лексикографическом порядке удобнее всего, если использовать элементы метода ветвей и границ так, как это будет показано далее. Мы будем переставлять только индексы элементов, но по перестановке индексов легко обработать или вывести перестановку самих элементов множества, как уже говорилось выше. Массив индексов элементов, обозначенный P, изначально состоит из чисел 1, 2, ..., n, которые затем будут меняться местами. Алгоритм решения состоит в следующем:

  1. Ищется такой элемент в массиве индексов P, который меньше стоящего за ним элемента, то есть, существует возможность увеличения данного индекса. Необходимо найти максимальный из таких элементов, что легко достигается при просмотре массива P справа налево - тогда первый найденный подходящий элемент и будет искомым.
  2. Найденный элемент p[i] меняется местами с минимальным из элементов, больших p[i] и находящихся правее его.
  3. элементы p[i+1], p[i+2], p[i+3], ..., p[n] переставляются в обратном порядке, то есть меняются местами p[i+1] и p[n], p[i+2] и p[n-1] и т.д.

Описанные шаги дают одну перестановку, а генерация перестановок заканчивается, когда на первом шаге искомая пара индексов p[i] и p[i+1] не будет найдена, что соответствует обратному порядку индексов n, n-1, ..., 2, 1. Теперь программа.

const n1=20; {Размерность множества}
var a,p:array[1..n1] of integer; 
    i,j,k,pp,min,n:integer; 
    flag:boolean; 

begin 
 writeln ('Введите размерность множества от 1 до ',n1);
 read (n); 
 for i:=1 to n do p[i]:=i; {Заполняем массив индексов}
 a:=p; {На самом деле массив a может быть заполнен произвольно} 
 for i:=1 to n do write(a[p[i]]:4);{вывод первой перестановки} 
 writeln; 
 flag:=false; 
 repeat 
  i:=n; 
  repeat 
   i:=i-1 
  until (p[i]<p[i+1]) or (i=1);{шаг 1 выполнен} 
  if p[i]<p[i+1] then begin 
   k:=i; 
   repeat 
    k:=k+1; 
   until (k=n)or(p[k+1]<p[i]); 
   min:=k;
   pp:=p[i];p[i]:=p[min];p[min]:=pp;{шаг 2 выполнен} 
   for k:=i+1 to (i+1+n) div 2 do begin 
    pp:=p[k]; {здесь делает перестановка}
    p[k]:=p[n+i+1-k]; 
    p[n+i+1-k]:=pp 
   end; {шаг 3 выполнен} 
   for i:=1 to n do write(a[p[i]]:4); {вывод перестановки}
   writeln; 
  end 
  else flag:=true 
 until  flag; 
end. 

Для n=10 Вы увидите не так уж мало перестановок (10!=3 628 800) :) Разумеется, львиная доля процессорного времени при этом уйдет на вывод. Но об этих проблемах мы еще поговорим далее, а сейчас рассмотрим рекурсивный вариант программы генерирования всех перестановок в лексикографическом порядке.

Параметром i процедуры Permutations ("перестановки") служит то место в массиве p, начиная с которого должны быть получены все перестановки правой части этого массива. Идея рекурсии состоит в том, что на i-ом месте должны побывать все элементы массива p с i-го по n-ый включительно и для каждого из них должны быть получены все перестановки остальных элементов, начиная с (i+1)-го места в лексикографическом порядке. После получения последней из перестановок, начиная с (i+1)-го места, порядок элементов должен быть восстановлен (для этого используется процедура циклического сдвига Sdvig).

const n1=20; {Максимальная размерность множества!}
var a,p:array[1..n1] of integer;
 i,j,k,pp,min,n:integer;
 flag:boolean;

procedure Sdvig(i:integer); {Процедура циклического сдвига}
var t,k:integer;
begin
 t:=p[i];
 for k:=i to n-1 do p[k]:=p[k+1];
 p[n]:=t; 
end; 

procedure Permutations(i:integer); 
 {Процедура перестановок.
  Параметр i - место в массиве p, начиная
  с которого должны быть получены все перестановки части массива}
var j,k:integer; 
begin 
 if i=n then begin 
  for j:=1 to n do write(a[p[j]]:4);
  writeln; {Здесь - обработка перестановки} 
 end 
 else begin 
  for j:=i to n-1 do  begin 
   Permutations(i+1); 
   k:=p[i]; p[i]:=p[j+1]; p[j+1]:=k 
   {меняются местами i-ый и j+1 - ый элементы} 
  end; 
  Permutations(i+1); 
  Sdvig(i); 
  {элемент, стоящий на i-ом месте, cтановится последним} 
 end;
end; 

begin 
 writeln ('Введите размерность множества от 1 до ',n1);  
 readln(n); 
 for i:=1 to n do p[i]:=i; {заполняем массив индексов}
 a:=p; {на самом деле массив a может быть заполнен произвольно} 
 Permutations(1); 
end.

Конечно же, при решении реальных задач наибольшую сложность будет представлять как раз анализ каждой из перестановок (у нас он заменен ее выводом на экран), однако, умение правильно и быстро их генерировать (плюс навык их увидеть в условии задачи) также не будут лишними. Попробуйте, например, по прочтении статьи решить следующее:
Линейный кроссворд представляет собой цепочку слов, в которой несколько символов в конце одного слова могут являться началом следующего. Для заданного набора слов написать программу составления такой цепочки минимальной длины. Более двух слов одновременно пересекаться не могут.
Пример:
РАСИСТ МАТРАС НАПАЛМ ИСТИНА АЛМАЗ -> МАТРАСИСТИНАПАЛМАЗ

Впрочем, если внимательно поискать по сайту, решение этой и еще ряда олимпиадных задач Вы найдете :) Я же в завершении статьи хочу обнародовать "совершенно секретную инструкцию для служебного пользования".

4. Порядок решения олимпиадных задач.

Во-первых, большая часть олимпиад проводится по-прежнему на DOS-овских компиляторах Borland C++ 3 и Turbo Pascal 7 и отказываться от этой традиции никто не собирается - ведь люди соревнуются именно в разработке быстрых и экономичных алгоритмов, а не в умении рисовать красивые окошечки. Поэтому приведенные ниже советы относятся к этим двум популярным на этапе обучения программированию оболочкам.

Кроме того, на олимпиадах по программированию обычно предполагается, что все входные данные корректны - уточните, так ли это! Ведь всевозможные проверки корректности и учёт вырожденных случаев могут "съесть" (и обычно съедают) львиную долю времени разработки.

1. Первым делом запаситесь "универсальной" заготовкой на Паскале или Си. Вероятнее всего, от Вас потребуется написать консольную программу, читающую исходные данные из файла input.txt и выдающую результат в файл output.txt. Тем более, что жюри почти наверняка пользуется автоматизированной системой тестов, предполагающей наличие именно этих файлов. На Паскале наша заготовка могла бы выглядеть так:

{Заготовка на Паскале}
{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T+,V+,X+,Y+}
{$M 65520,0,655360}
var i:integer;

procedure Input;
var f:text;
begin
 assign (f,'input.txt');
 {$I-} reset (f); {$I+}
 if ioresult <> 0 then begin
  writeln ('Can''t open INPUT.TXT to read data!');
  halt (1);
 end;
 read (f);

 close (f);
end;

procedure Output;
var f:text;
begin
 assign (f,'output.txt');
 {$I-} rewrite (f); {$I+}
 if ioresult <> 0 then begin
  writeln ('Can''t open OUTPUT.TXT to write data!');
  halt (2);
 end;

 write (f);

 writeln ('See the OUTPUT.TXT');
 close (f);
end;

begin
 Input;

 Output;
end.

Обратите внимание на все директивы компилятора, установленные в образце. Для C++ подойдет следующая заготовка:

// Заготовка на Си
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
//#include <string.h>
//#include <values.h>

FILE *f;
int i;

void Input (void) {
 f=fopen ("input.txt","rt");
 if (f==NULL) {
  printf ("\n Can't open INPUT.TXT");
  exit (1);
 }
 //Чтение данных
 fscanf (f,"%d",&i);

 fclose (f);
}

void Output (void) {
 f=fopen ("output.txt","wt");
 if (f==NULL) {
  printf ("\n Can't open OUTPUT.TXT");
  exit (2);
 }
 //Запись данных
 fprintf (f,"%d",i);

 fclose (f);

}

int main (void) {
 Input();

 Output();
 return 0;
}

Для Си следует внимательно проверить настройки среды:

 меню Options, Compiler, Code generation:
  модель памяти Large;
  Word Alignment ON; 
  Floating Point Emulation;
 меню Options, Compiler, Advanced code generation:
  Insruction set: 8088/86;
  Line Numbers debug info ON;
  Debug info in OBJs ON;
  Automatic far data ON;
 меню Options, Compiler, Entry/Exit code:
  Test stack overflow ON;
 меню Options, Compiler, Optimization:
  кнопка Fartest code;
 меню Options, Linker, Libraries:
  Graphics library OFF (если программы не работают с графикой, иначе ON);
  Turbo Vision OFF

Скопируйте эту заготовку  столько раз, сколько задач предложено на олимпиаде и сразу назовите каждый  файл так, как это требуется по условиям (обычно 1.pas, 2.pas и т.д.).

2. Внимательно прочитайте условие задачи, постарайтесь правильно понять, в чем она заключается, если условие или форма вывода результатов в файл не до конца понятны, лучше сразу же задать вопрос, обычно это разрешено.

3. Если с входными и выходными данными все ясно, можно описать основные  глобальные переменные, заполнить процедуру Input для ввода данных, сразу же сделать их формальную проверку на допустимость. Если в условии сказано, что данные корректны или ограничены четко определенным форматом, проверку корректности следует исключить. При чтении из файла на Паскале не нужно использовать readln для чтения чисел (только для строк), а при чтении на Си нужно помнить о поведении строковых шаблонов этого языка - например, шаблон %s для ввода строки считает ее окончанием любой разделитель, в том числе и пробел.

4. После того, как данные читаются, обнулите или присвойте другие нужные начальные значения всем без исключения глобальным переменным. На этом же этапе подготовьте процедуру Output для вывода результата в такой форме, которая требуется в условии задачи. Это как поможет тестированию, так и сэкономит время на переделке "простого" вывода в "правильный". Короче говоря, на этом этапе у Вас уже есть работающая программа, которая компилируется, считывает данные и выводит "нулевые" результаты в нужном формате.

5. При выполнении пунктов 3-4 подумайте над подходами к решению задачи, сделать это помогут ответы на следующие вопросы:

6. Программируем функциональность задачи в виде набора подпрограмм, пока еще, по большей части, представляющей собой "заглушки" (мнимые или пустые действия, имитации настоящего действия, которое должна выполнять  подпрограмма). Логика программы остается работающей и на этом этапе.

7. По одной пишем и отлаживаем подготовленные подпрограммы, добиваясь, чтобы каждая из них правильно выполняла свое действие при любых входных данных - например, подпрограммы поиска максимума или сортировки не должны смутить массивы, состоящие из всех одинаковых элементов, хотя и выполнять над ними полный цикл обработки - плохое решение. Словом, следует обратить особое внимание на вырожденные случаи (может ли эта операция деления в программе стать делением на ноль? И что делать, если так?) и возможность досрочного поиска решения. При программировании циклов они не должны зацикливаться ни при каких входных данных.

8. Если эффективногo решения задачи у Вас нет, как это часто и бывает, применяйте полный перебор или простую эвристику. Если и это сложно, упростите себе задачу, отбросив мешающие условия или добейтесь, чтобы программа работала на простейших тестах (точка, отрезок, треугольник и прямоугольник вместо произвольного многоугольника, вычисление выражений только для одного действия вместо всех и т.п.) Для остальных случаев программа может выдавать любимую фразу программистов "нет решения" или генерировать нечто правдоподобное с помощью датчика случайных чисел :) Особенно это срабатывает, если существует всего два варианта ответа. Часто жюри начисляет ненулевые баллы за программы, прошедшие хотя бы часть тестов, а до внимательного анализа исходника, как правило, ни у кого не доходят руки.

9. Так же поступайте с задачами, на которые не хватает времени. За последние 15-20 минут можно сделать так, чтобы   они работали хотя бы для вырожденных (входные параметры - нули или единицы) и частных случаев. Например, программа вида

if N=1 then writeln(a);    
if N=2 then writeln(a+b);  
if N=3 then writeln(a+b+c); 

иногда производит на жюри лучшее впечатление, чем мог бы произвести ее исходник :)

10. Перед сдачей подумайте о быстродействии. Если Вы использовали отладочную печать, закомментарьте ее - львиная доля времени прогона может уйти именно на ненужный вывод на экран средствами высокого уровня! Я лично в условиях нехватки времени на комментирование решал эту проблему тем, что стазу же ставил в заготовке отладочный флаг

const debug=1;  {Pascal}
#define DEBUG 1 //C++

и всю отладочную печать писал сразу в виде

if debug>0 then writeln (a);  {Pascal}
if (DEBUG) printf ("\n%d",a); //С++

Перед сдачей мне оставалось сбросить флаг в ноль.

С другой стороны, никому не понравится, если программа долго работает "молча", создавая впечатление зависшей. Для решения проблемы можно, например, выводить через каждые 100 или 1000 шагов цикла перебора одну точку на экран.

10. Запустите исполняемый файл *.exe из среды хотя бы для одного   теста, чтобы убедиться в его работоспособности. Еще раз  перечитайте условие. Отправьте программу жюри. Убедитесь, что запрограммировано совсем не то, что требовалось, и, получив свои 0 баллов, спокойно идите домой :)

© PerS, 01.05.08

См. также:
раздел "Обучение" - есть и архив с олимпиадными задачами
раздел "Дистрибутивы и архивы" - там можно скачать компактные дистрибутивы Паскаля или Си
"Правила хорошего кода" из учебника по Паскалю

Рейтинг@Mail.ru
вверх гостевая; E-mail