Задачи на перестановки Опции

[Unconnected]

Привет всем.

Меня заинтересовала задача из соседней темы, про перестановки в числах.

Задача 4 "Сумма двух чисел"
Имя входного файла: sum.in
Имя выходного файла: sum.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.

Формат входных данных
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.

Формат выходных данных
Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом.
Примеры входных и выходных файлов
sum.in sum.out
12 31 25 ***YES***
**********12 13***


12 31 26 ***NO***

Вот что я сделал:

const m=6;

type st = string[3];

var a,b:st;
    m1,m2:array[1..m] of st;
    f:text;
    i,j:byte;
    buf1,buf2,c,code,aa,bb:integer;

Procedure generate(m:array of st;v:st);
var buf:char;
    i:byte;
begin
  if (length(v)<3) then repeat v:=v+'0' until (length(v)=3);
  i:=1;
  m[i]:=v;
  repeat
    inc(i);
    m[i][1]:=m[i-1][2];
    m[i][2]:=m[i-1][3];
    m[i][3]:=m[i-1][1];
  until (i=3);
  inc(i);
  m[i][1]:=m[1][1];
  m[i][2]:=m[1][3];
  m[i][3]:=m[1][2];
  repeat
    inc(i);
    m[i][1]:=m[i-1][2];
    m[i][2]:=m[i-1][3];
    m[i][3]:=m[i-1][1];;
  until (i=6);
end;

begin
  assign(f,'sum.in');
  reset(f);
  read(f,aa,bb,c);
  close(f);
  str(aa,a);
  str(bb,b);
  generate(m1,a);
  generate(m2,b);
  for i:=1 to m do
    begin
      val(m1[i],buf1,code);
      for j:=1 to m do
        begin
          val(m2[j],buf2,code);
          if (buf1+buf2=c) then begin
                                  assign(f,'sum.out');
                                  rewrite(f);
                                  writeln(f,'YES');
                                  write(buf1,' ',buf2,' ',c);
                                  close(f);
                                  halt;
                                end;
        end;
    end;
  readln;
  assign(f,'sum.out');
  rewrite(f);
  write(f,'NO');
  close(f);
end.

Мой алгоритм перестановок (для трёхзначных чисел) основан на том, что если в числе переносить первую цифру в конец, пока не получится исходное число, а потом поменять 2 и 3 цифры местами и сделать то же самое, то получатся все перестановки..

Например:
123
231
312
меняем,
132
321
213

Получилось 6 перестановок, как раз 3!, как и должно быть. Моя программа почему-то не заполняет корректно массив (процедура Generate).

Сообщение отредактировано: Unconnected - 18.01.2010 17:21

[Unconnected]

А рекурсия - дубовый метод, много мозгов не требует )).

К моим мозгам она чересчур требовательна)) Короче, я попробовал для начала понять, что она делает эта рекурсия, расставил примерные комментарии..

const
  m=2;  //количество слагаемых
var
  c,i: integer;
  a: array [1..m] of record 
    v,x: integer;
    s: string;
    d: set of byte
  end;
  f: text;

procedure Dig(n,k: integer);
var
  i,z: integer;
begin
  if k=0 then//1-е условие выхода.Длина слагаемого будет 0-ой тогда,когда будет (Dig(n,k-1); k=1) 
    if n=m then begin//если номер обрабатываемого эл-та равен всему числу слагаемых...
      z:=0;
      for i:=1 to m do z:=z+a[i].x;  
      if z=c then begin
        WriteLn(f,'YES');
        for i:=1 to m do Write(f,a[i].x,' ');
        Close(f);
        Halt
      end
    end
    else Dig(n+1,Length(a[n+1].s))//если n-ый элемент был обработан, но есть ещё эл-ты, то обрабатываем следующий
  else with a[n] do for i:=1 to Length(s) do if not (i in d) then begin
    x:=x*10+Ord(s[i])-48; 
    Include(d,i);//здесь самое интересное и непонятное, видимо, собственно запись в a[i].x нужного числа.
    Dig(n,k-1);//смысл этого цикла я не понял..
    Exclude(d,i);
    x:=(x-Ord(s[i])+48) div 10
  end
end;

begin
  Assign(f,'sum.in');
  ReSet(f);
  for i:=1 to m do with a[i] do begin //заполнение массива записей,инициализация полей.
    Read(f,v);//v-численное представление слагаемого, s - строчное.
    Str(v,s);
    d:=[];
    x:=0
  end;
  ReadLn(f,c); //считываем сумму
  Close(f);
  Assign(f,'sum.out');
  ReWrite(f);
  Dig(1,Length(a[1].s)); //первый запуск процедуры,передаётся единица,т.е берем 1е слагаемое, и длина первого слаг-ого
  WriteLn(f,'NO'); //выводим NO,ибо если a+b=c выполнится,то сюда исполнение не дойдёт
  Close(f)
end.

Мне понравилась строка Ord(s[i])-48, получается, это быстрый способ перевести строку с цифрой в цифру.
Куда мне анализировать, почему время не увеличивается - я в механизм работы въехать не могу..)) Хотя, меня преследует ощущение, что в цикле else with a[n] do for i:=1 to Length(s) do if not (i in d) then begin всегда будет обрабатываться только 1ый символ, но это мои интуитивные домыслы конечно)) К ним я пришёл, расписав на бумаге значения переменных при двух двузначных слагаемых. Наверное, ошибся где-то.

Запрос. На комментарии:)

И что, понадобилось передавать num?

Не понадобилось, так лучше.

Сообщение отредактировано: Unconnected - 18.01.2010 4:52

[Lapp]

Так, процесс в целом нам стал более понятен, теперь можно перейти к более техническим вопросам

Запрос. На комментарии:)

RFC? Ok.
Давай я лучше попробую описать способ. Думаю, это будет полезнее.

Для начала забудем про рекурсию. Рекурсия не должна быть самоцелью. Она должна появиться сама собой из естественного пути решения.

Итак, у нас есть набор цифр, записанных в массив (или строку, что то же самое). Нам нужно найти все возможные перестановки. Как?
Извини, но твой способ не совсем ... мм.. удобный, а точнее - неуниверсальный. Давай действовать иначе.. Всего у нас n позиций. На первую мы ставим в цикле по очереди все имеющиеся цифры (элементы массива цифр). Далее, на каждом конкретном шагу этого цикла мы ставим на вторую позицию все элементы массива цифр, кроме того, который поставили на первую. То есть вложенный цикл с проверкой. Если позиций больше двух, повтояем то же самое. Вот пример для перемешивания цифр в 4-значном числе:

a:='2601';
n:=Length(a);  // 4
r:='';
for i1:=1 to n do begin
  r:=r+a[i1];
  for i2:=1 to n do if i2<>i1 then begin
    r:=r+a[i2];
    for i3:=1 to n do if (i3<>i1)and(i3<>i2) then begin
      r:=r+a[i3];
      for i4:=1 to n do if (i4<>i1)and(i4<>i2)and(i4<>i3) then begin // этот цикл можно заменить просто на i4:=10-i3-i2-i1
        ProcessIt; // перемешивание завершено, тут проверка условия задачи и вывод результата
      end
    end
  end
end;

Все просто и понятно, так ведь? Вложенный цикл, причем вложенность равна длине (значности) исходного числа. Но, со всеми преимуществами, налицо и один недостаток. Дело в том, что Паскаль не допускает чего-то типа "вложенности переменной длины". И что же, нам для каждой длины делать свой фрагмент кода?? Вообще-то, не такой уж и абсурдный вариант, как кажется на первый взгляд. Длин будет вряд ли больше 1 - 2 десятков - так, что же? В исходной задаче вообще можно было ограничиться двумя вариантами (двузначные и трехзначниые) - разве это много? Определяем длину числа и переводим стрелки на нужный кусок программы..
Это, конечно, некрасиво .. И никто не гарантирует, что в другой задаче не будет большего числа вариантов, типа сто или тысяча. Как быть?

Путей для разрешения этой проблемы несколько.
Первый, самый банальный..
На каждом этапе вложенности делать проверку глубины. Глубину мы можем отслеживать с помощью некоторой специальной переменной, назовем ее Depth. При входе на очередной уровень, мы инкриминируем эту переменную и сравниваем ее с максимальной глубиной (равной длине числа). Приведенный мной выше кусок можно модифицировать в соответствии со сказанным так, что он будет работать для длин от 1 до 4:

a:='2601';
n:=Length(a);  // 4
Depth:=0;
r:='';
for i1:=1 to n do begin
  r:=r+a[i1];
  Inc(Depth);   // увеличиваем глубину
  if Depth=n then ProcessIt else for i2:=1 to n do if i2<>i1 then begin
    r:=r+a[i2];
    Inc(Depth);   // увеличиваем глубину
    if Depth=n then ProcessIt else for i3:=1 to n do if (i3<>i1)and(i3<>i2) then begin
      r:=r+a[i3];
      Inc(Depth);   // увеличиваем глубину
      if Depth=n then ProcessIt else for i4:=1 to n do if (i4<>i1)and(i4<>i2)and(i4<>i3) then begin
        ProcessIt
      end;
      Dec(Depth);   // выныриваем
    end;
    Dec(Depth);   // выныриваем
  end;
  Dec(Depth);   // выныриваем
end;

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

Я сказал, что путей у нас не один. Что еще мы можем придумать? Строго говоря, есть еще средства.. Например, мы можем организовать схему с одним циклом, но со сложным манипулированием индексом. То есть в тотмомент, когда по индее нужно было бы войти во вложенный цикл мы будем сохранять текущий индекс в специальном массиве (длины, равной длине числа) и присваивать ему начальное значение (единицу). Тем самым цикл уже будет совсем другим, новым. Затем, когда нужно выходить из вложенного цикла, мы будем вынимать заранее сохраненное значение из массива - то есть возвращаться на предыдущий уровень. Цикл при этом будет продолжаться, как ни в чем ни бывало.. Индексом того массива для запоминания параметра цикла будет служить все та же Depth.
Схема вполне осуществимая, хотя и не самая простая. В чем ее суть? В том, что мы повторно используем код несколько раз. Сначала для одного цикла, потом для вложенного, потом для следующего вложенного.. Код один, но параметр цикла, поскольку он сохраняется и перекладывается туда-обратно, различный на разных этапах. Не надо сейчас сразу бросаться писать код для этого алгоритма, просто уясни, что такая схема вполне осуществима.

Уяснил? Продолжаем.
На чем мы остановились? На том, что максимально увеличили КПД написанного нами кода, посредством использования его с различными данными (вспомни, что программа=алгоритм+данные). Позвольте, но ведь в Паскале уже есть средство для этого! Это средство называется процедура/функция. Она делает как раз то, что мы хотим: выполняет тот же самый код с разными данными! Эти данные передаются в параметрах. При этом старые параметры никуда не деваются, не забываются, не затираются, а остаются в стэке. Таким образом, нам даже не нужно будет сохранять параметр цикла (и другие данные, если потребуется) в специально подготовленном для этого массиве! И сам массив, выходит, нам тоже не нужен.

Давай ближе к делу. Нам нужно организовать вложенный цикл? Хорошо. Мы сделаем процедуру, которая содержит цикл. А в том месте, в котором мы должны были бы перейти к вложенному циклу, мы просто поставим вызов этой же самой процедуры. При этом процедура работает с глобальными параметрами (кроме переменной цикла), так что все тип-топ, никакой пуницы. Вот она, рекурсия, и вылезла - сама собой, причем в полной красе )). Осталось добавить только еще одну маленькую деталь..

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

procedure Recurse(l:integer);
begin
  if l<Depth then begin
    ... // тут цикл
      Recurse(l+1);  // вызываем с увеличением параметра
    ...
  end
  else ProcessIt;  // максимальная глубина достигнута, производим обработку
end; 

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

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