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

[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 13: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 0:52

[Lapp]

К моим мозгам она чересчур требовательна))

Ошибаешься; ниже убедишься.

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

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

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

Для этого не нужно глубоко въезжать в алгоритм. С этого и начнем..
Каков бы ни был олгоритм - это все равно перебор. Согласен? Этого знания достаточно.
На первый взгляд кажется, что такие совпадения (описанные в условии, когда сумма равна заданному числу) должны быть достаточно редки. И поэтому когда я подготавливал входные данные, я делал так:
- пишу несколько слагаемых (10 штук, для этого нужно заменить тип integer на LongInt в слагаемых и сумме);
- считаю их сумму и приписываю ее сзади;
- перемешиваю цифры в слагаемых.
Такой способ, конечно, гарантирует ответ YES при правильной работе программы. После этого я запускал прогу.. и она выдает ответ через мгновение. Почему?
Во-первых, я заметил, что ответ не тот, который я поготовил, а другой. Я решил: повезло, оказался еще один ответ! - и немного изменил данные (слагаемые и сумму, чтоб снова гарантировать ответ). И снова аналогичный результат. Вот тогда я, наконец, дал себе труд подумать минуту..
Собственно, минуты не потребовалось. У меня 10 слагаемых, каждое от 2 до 4 знаков. Всего примерно 30 цифр. Сколько существует перестановок 30 цифр? Ответ: бешеное количество, а именно 30!. Даже если учесть, что из этих 30 цифр всего 10 различных, их число все равно остается фантастическим. Это число гораздо больше самой суммы, и больше длины диапазона, в котором сумма может меняться. Что это означает? То, что:
1. если мы наобум напишем слагаемые и сумму, ответ с подавляющей вероятностью будет YES;
2. на каждую сумму существует не просто несколько, а очень много разных комбинаций, удовлетворяющих условию.
Это понятно? Если нет, перечитай, пока не разберешься. А когда разберешься, сразу станет само собой понятно, что программа находит первую из очень многих комбинаций, удовлетворяющих решению, и для этого ей не требуется слишком много времени. Поскольку ей нет нужды сканировать все комбинации. А раз валидных комбинаций много, значит, скорее всего есть и вблизи начала поиска.. )

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

// close(f);
// Halt;

- рассудительно решив, что уж теперь-то истинное время работы программы (перебор всех возможных комбинаций) от меня не уйдет.. Хрен-та! Я запустил прогу, увидел, что она действительно не вышла сразу, прикрыл окошко и пошел заниматься чем-то другим. Когда я минут через 20-30 снова заглянул в то окно, программа все работала. Я прервал ее по Ctrl-C и пошел в Far смотреть выходной файл. Его размер был 50 МБ, в нем было больше миллиона строк.. То есть программа уже нашла примерно миллион решений и прилежно продолжала искать остальные - видимо, полагая, что мне это жизненно важно )). Думаю, она делала бы это всю мою оставшуюся жизнь..

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

Про рекурсию напишу чуть-чуть позже..