IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Задачи на перестановки
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Привет всем.

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

Задача 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 -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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


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

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 -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Unconnected   Задачи на перестановки   16.01.2010 2:08
volvo   Потому что она у тебя вылетает за пределы этого ма…   16.01.2010 2:40
Unconnected   Получается, надо константу m сделать равной 7? Всё…   16.01.2010 4:43
volvo   Во-первых, я не совсем понял вот этот твой финт: З…   16.01.2010 5:54
Unconnected   Короче, я решил... вроде бы... Добавил кое-что, ко…   16.01.2010 21:37
volvo   Мало просто скопировать символы... Надо еще и длин…   16.01.2010 21:40
Unconnected   А как установить её, длину, вручную? Может, SetLen…   16.01.2010 21:41
volvo   Если у тебя 32-битный компилятор - то SetLength, е…   16.01.2010 21:51
Unconnected   Ого, не знал, спасибо за помощь :)   16.01.2010 21:53
Lapp   Обычно в подобных случаях генерировать перестановк…   17.01.2010 3:44
Lapp   Unconnected, можно я выскажу несколько замечаний? …   17.01.2010 7:34
volvo   А я уже говорил, что надо бы описывать тип (в сооб…   17.01.2010 15:10
Unconnected   Короче, переделал я вообще механизм программы, т.к…   17.01.2010 15:31
volvo   Ничего не забыл?   17.01.2010 15:46
Unconnected   Мм нет вроде, а что, что-то забыл?:) Там массивы у…   17.01.2010 15:53
volvo   Там не хватает слова Var... Не надо передавать в п…   17.01.2010 16:00
Lapp   volvo, я понимаю твое возмущение: пишите, "чт…   17.01.2010 17:08
Unconnected   Да, и правда, если добавить var, то переписывание …   17.01.2010 16:25
Lapp   А я уже говорил, что надо бы описывать тип ... Пос…   17.01.2010 16:41
volvo   Это тебе только кажется :) Это значит что? Ты про…   17.01.2010 16:49
Unconnected   К моим мозгам она чересчур требовательна)) Короч…   17.01.2010 19:28
Lapp   К моим мозгам она чересчур требовательна))Ошибаешь…   18.01.2010 8:25
Lapp   Так, процесс в целом нам стал более понятен, тепер…   18.01.2010 11:17
Unconnected   //подновил время, правил пост   18.01.2010 4:54
Unconnected   :good: :yahoo!: :good: Lapp, спасибо огром…   18.01.2010 14:17
Lapp   редкий случай, когда в статье (тянет на неё) я пон…   19.01.2010 6:21
Unconnected   Я тут решил для закрепления решить сам задачку на …   18.01.2010 16:23
volvo   У тебя строка пустая (сам же ее опустошил :) ), з…   18.01.2010 17:21
Unconnected   Ага, теперь нормально, только на входных данных 5 …   18.01.2010 17:24
volvo   P.S. Не совсем так... Это не неизвестное исключени…   18.01.2010 17:25
Unconnected   Нормально - в смысле ошибка не вылетает:) А резуль…   18.01.2010 17:48
volvo   Еще бы... У тебя переменная res описана локально, …   18.01.2010 18:08
volvo   P.S. На самом деле, твоя задача может решаться вот…   18.01.2010 18:38
Unconnected   Ого.. решение короче намного, без множества и запо…   18.01.2010 19:09
volvo   Смотри. Начинаем с генерации строки S. Что у тебя …   18.01.2010 21:17
Unconnected   Да, сначала я хотел заполнить строку с двумя непод…   18.01.2010 21:26
Unconnected   Ага, правильно. Надеюсь, эта тема поможет ещё ко…   19.01.2010 11:29
Unconnected   И снова я... Уж очень хочется что-то самому полнос…   20.01.2010 4:18
Unconnected   Короче я вроде бы разобрался, уже несколько задач …   20.01.2010 22:19


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 3:09
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name