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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


Цитата(Unconnected @ 17.01.2010 15:28) *
К моим мозгам она чересчур требовательна))
Ошибаешься; ниже убедишься.

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

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

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


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  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 14:42
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name