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

[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

[Lapp]

Unconnected, можно я выскажу несколько замечаний?
Во-первых, при входных данных:
53 10 135
- твоя программа выдает:
YES
35 10 135
- что неверно..

Далее, у тебя путаница в передачей массива в подпрограмму. Нужно сделать специальный тип и передавать его. Конструкция, которую использовал ты (array без пределов) в данном случае не годится, она служит другой цели и используется иначе. Я сделал изменения в твоем коде (помечено //), посмотри; так программа не вылетает при включенном range check.

Отступы.. Они должны быть ВСЕГДА на одну и ту же величину. Сдвиг НЕ ДОЛЖЕН зависеть от того, за чем он идет: var, type или begin в конце строки - всегда на одно и то же число позиций (обычно 2, но можно и 4) от начала предыдущей строки. Исключений нет. Точка.
Это было непререкаемое правило. А теперь совет..
Лучше писать begin (repeat, case..) не на новой строке, а на той же. Это не только позволяет сэкономить строчку и отступ, но - самое главное - позволяет практически исключить такую ситуацию:

for i:=1 to 5 do 
  begin
    a:=b;
    b:=1
  end;
c:=d;  // вот эта строчка начинается не с end, это плохо

Лучше так:

for i:=1 to 5 do begin
  a:=b;
  b:=1
end;   // блок закрывается end'ом
c:=d;  // теперь это обычная строка текста

Если пишешь так, то появление в коде сдвинутой влево строки, НЕ начинающеся с end - почти всегда признак ошибки. Блок всегда начинается со строки, заканчивающейся begin (repeat, case..) и заканчивается строкой, начинающейся с end (until), и его тело сдвинуто. Всякое отступление от этого правила - признак возможной ошибки. Исключения случаются (они вносятся обычно оператором if .. then .. else), но их тоже проще отловить, если точно следуешь этому правилу. Очень рекомендую привыкнуть к такому способу написания кода.

Теперь твоя программа, немного исправленная мной.

const
  m=6;

type
  tSt = string[3];               //
  tArSt = array[1..m]of tSt;     //

var
  a,b,cc: tSt;
  m1,m2: tArSt;                  //
  ll: array[1..3] of byte;
  f:text;
  i,j:byte;
  buf1,buf2,c,code,aa,bb:integer;

Procedure generate(m:tArSt; v:tSt; num:byte);     //
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]:=m[i-1][2]+m[i-1][3]+m[i-1][1];
  until (i=3);
  inc(i);
  m[i]:=m[1][1]+m[1][3]+m[1][2];
  repeat
    inc(i);
    m[6]:='123';
    m[i]:=m[i-1][2]+m[i-1][3]+m[i-1][1];
  until (i=6);
  if (num=1) then for i:=1 to 6 do m1[i]:=m[i]
    else for i:=1 to 6 do m2[i]:=m[i]
end;

Function getlength(v:integer):byte;
var
  t:string[3];
begin
  str(v,t);
  getlength:=length(t);
end;

begin
  assign(f,'sum.in');
  reset(f);
  read(f,aa,bb,c);
  close(f);
  str(aa,a);
  str(bb,b);
  str(c,cc);
  ll[1]:=length(a);ll[2]:=length(b);ll[3]:=length(cc);
  generate(m1,a,1);
  generate(m2,b,2);
  if c<100 then c:=c*10;
  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');
        if ll[1]<getlength(buf1) then repeat
          buf1:=buf1 div 10;
        until (ll[1]=getlength(buf1));
        if ll[2]<getlength(buf2) then repeat
          buf2:=buf2 div 10;
        until (ll[2]=getlength(buf2));
        if ll[3]<getlength© then repeat
          c:=c div 10
        until (ll[3]=getlength©);
        write(f,buf1,' ',buf2,' ',c);
        close(f);
        halt;
      end;
    end;
  end;
  readln;
  assign(f,'sum.out');
  rewrite(f);
  write(f,'NO');
  close(f);
end.

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