Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Немного комбинаторики...

Модерирует : ShIvADeSt

 Версия для печати • ПодписатьсяДобавить в закладки
Страницы: 1 2 3

Открыть новую тему     Написать ответ в эту тему

Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Такой алгоритм красивее, но у него сложная математика. Во первых рекурсия - это огромный напряг для стёка. Во вторых количество итераций идентично количеству необходимых вариантов, каждый из которых помножен на глубину стёка (рекурсии). В третьих, на языках высокого уровня вы этого не увидите, а всё же строковая математика (сложение строк, выделение/удаление памяти при передаче строк параметром) вся выполнена процедурами (Вы просто их не знаете и не видите). Стоит Вам заглянуть в ассемблерный дамп, сгенеренный по такому алгоритму, то Вы поймете, что свой "геморой проверок" переложили на плечи процессора - и весьма неумело. Моё мнение основано на опыте написания алгоритмов архивирования на ассемблере. Программа написанная мною выше даёт превосходный ассемблерный дамп, по сравнению с строково-рекурсивным алгоритмом. Однако бывают исключения - например если рекурсивный алгоритм напишут на ассемблере.
 
Добавлено
LOVe
Не обижайся, у тебя прикольная фотогаллерея. Пришли мне пожалуйста свою программу - хочу взглянуть на дамп.
Адрес p_keyheyback(^)mail.ru


----------
Meaning this is something additional.

Всего записей: 683 | Зарегистр. 18-11-2002 | Отправлено: 10:56 17-12-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Порни спасибо ОГРОМНОЕ я разобрался ! ! ! !
Может из меня выйдет толк ?
 
Дабы не создавать новый топик.... еще с одной трудностью недавно столкнулся , сделал програмку для подсчета CRC файла
всё бы хорошо,  но с ЕХЕ файлами она работать не хочет, только с текстовыми...Как такую операцию можно провернуть в ТР ?  
 
Pinocchio

Цитата:
даёт превосходный ассемблерный дамп,  

 
Спасибо за замечание, конечно, но мне бы с ТР разобраться для начала...
Ты хочешь сказать, что если пограмму LOVe реализовать без рекурсии то она будет быстрее работать ? Так?

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 23:24 18-12-2002
L0Ve



s@nya.moder
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Pinocchio

Цитата:
Во первых рекурсия - это огромный напряг для стёка.

О да... В моей проге стек просто загнется от глубины рекурсии в 8 уровней.. или сколько там цифр...  
 

Цитата:
Не обижайся

гы, обижаться? это глупо... я тут смеюсь над каждым твоим постингом, а ты про обижаться...
 

Цитата:
Пришли мне пожалуйста свою программу - хочу взглянуть на дамп.  

Программу фотогалереи??? Не пришлю... А сабжевую - сам скомпиль... Вроде должна компилиться без проблем...
 
Frez

Цитата:
если пограмму LOVe реализовать без рекурсии то она будет быстрее работать ?

Может и быстрее... Вот только во-первых ты на глаз этой разницы наверное не заметишь, а во-вторых рекурсию и вообще высокоуровневые языки не зря придумали....
 
FuzzyLogic
А тебе спасибо, что таки разъяснил народу, как работает алгоритм. Я всё собирался, да никак не мог собраться... Проще написать, чем кому-то объяснить, как и почему оно так работает.
 
 
Добавлено
Pinocchio
А еще вот специально для тебя. Маленькое видоизменение и никаких

Цитата:
выделение/удаление памяти при передаче строк параметром


Код:
 
const a:array[0..9] of byte=(0,0,0,0,0,0,1,3,4,2);
var count:longint;
    n:string;
    i,len:byte;
 
procedure test;
var i:byte;
begin
 for i:=0 to 9 do if a[i]>0 then begin
  dec(a[i]);
  n:=n+chr(i+48);
  if byte(n[0])=len then begin
   inc(count);
   writeln(count:5,' - ',n);
  end else test;
  dec(n[0]);
  inc(a[i]);
 end;
end;
 
begin
 for i:=0 to 9 do len:=len+a[i];
 test;
end.
 


----------
In God we trust. Everyone else we are verifying with PGP.

Всего записей: 1365 | Зарегистр. 28-07-2001 | Отправлено: 01:57 19-12-2002 | Исправлено: L0Ve, 02:52 19-12-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
program open_file;
uses crt;
var
f:text;
st,cr:string;
lin,sim,i,sum,x,tmp:integer;
begin
clrscr;
assign(f,'d:\work.ex'); reset(f);
while not eof(f)  do
begin
readln(f,st);
for i:=1 to length(st) do
        begin
        cr:=copy(st,i,1); val(cr,x,tmp);
        sum:=sum+ord(x);
        end;
sim:=sim+length(st); inc(lin);
end;
close(f);
writeln(sim,' simbols');
writeln(lin,' lines');
writeln(sum,' crc');
end.

 
Вот такая трабла парни ! Тут ещё оказалось, что она СRС текстового файла считает не верно...Слишком мало, на мой взгляд , получается...А с ехе файлами она вообще работать отказывается...
                                               
Подскажите, плиз, как заставить ёё правильно считать CRC любого файла.  
 
 
 
Добавлено

Цитата:
program open_file;
uses crt;
var
f:text;
st,cr:string;
lin,sim,i,sum,x,tmp:integer;
begin
clrscr;
assign(f,'d:\work.ex'); reset(f);
while not eof(f)  do
begin
readln(f,st);
for i:=1 to length(st) do
        begin
        cr:=copy(st,i,1); val(cr,x,tmp);
        sum:=sum+ord(x);
        end;
sim:=sim+length(st); inc(lin);
end;
close(f);
writeln(sim,' simbols');
writeln(lin,' lines');
writeln(sum,' crc');
end.

 
Вот такая трабла парни ! Тут ещё оказалось, что она СRС текстового файла считает не верно...Слишком мало, на мой взгляд , получается...А с ехе файлами она вообще работать отказывается...
                                               
Подскажите, плиз, как заставить ёё правильно считать CRC любого файла.  
 
 

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 21:05 22-12-2002
Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
L0Ve

Цитата:
а во-вторых рекурсию и вообще высокоуровневые языки не зря придумали....

Ага - специально для врителенов в техете. Однако прога стала лучше (знаешь как буковку добавить!!!), но рекурсия это стёк + изменение IP (соответственно тики, хотя разное чё бывает)

За фотогаллерею спасибо, я как нибудь так , как нибудь сам. Тем более, что я не вижу разницы между точкой в PHP и плюсом в паскале.

Frez
Я обожаю балансировать между простотой алгоритма и скоростью в конкретной задаче. Моя прога проще для понимания, а стало быть её проще переделывать, когда в последний момент препод вспомнит, что хотел чего нибудь другого


----------
Meaning this is something additional.

Всего записей: 683 | Зарегистр. 18-11-2002 | Отправлено: 11:21 05-01-2003
L0Ve



s@nya.moder
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
нет, как всё-таки весело иногда почитать постинги некоторых личностей...
 
Pinocchio
взглянул вот еще раз на твою прогу и обнаружил там 4 процедуры... Которые вызываются оооочень много раз... Интересно - ты используешь, какой-то скоростной вызов без использования стека? Или всё таки в этой области ты пока ниче не придумал?
 
у меня моя единственная процедура вызывается всего 26248 раз... т.е. всего-то получается по 2 раза на каждый вариант...
а что у тебя? думаю побольше будет... Можно конечно в твоей проге из некоторых процедур позагонять код в основную часть... а код некоторых написать в основной части несколько раз... Но я очень сомневаюсь что кто-то после этого захочет разбираться в твоей проге, и что она вообще от этого станет сильно быстрее работать...
 
Кстати я и свой алгоритм могу выкрутить без рекурсии, но прога станет менее приятна для восприятия, хотя, как и полагается, будет в несколько раз короче твоей...
 


----------
In God we trust. Everyone else we are verifying with PGP.

Всего записей: 1365 | Зарегистр. 28-07-2001 | Отправлено: 14:06 05-01-2003
Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
L0Ve
Благодарю за внимание.
1. Если в школе моему ребёнку начнут пихать теорию относительности прежде, чем он выучит таблицу умножения, то я всех препадов заархивирую.
2. Прежде идёт освоение методов перебора, а уже потом рекурсия.
3. Последовательность символов рассматривать как иерархию рекурсивных вложений - из мухи делать слона.
4. Дать оптимизацию моей программы без процедур?
5. В стандартном пакете Borland Pascal 7.0 есть программа Turbo Profiler, запустите её и не надо будет считать вручную (ни время ни количество вызовов)
 
С большим уважением к Вам,
простой программист Pinocchio.

----------
Meaning this is something additional.

Всего записей: 683 | Зарегистр. 18-11-2002 | Отправлено: 15:38 08-01-2003
zam

Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
L0Ve

Код:
 
@a=qw/0 0 0 0 0 0 1 3 4 2/; # это каких цифр сколько...
sub test {
  local $b;
  map {if ($a[$_]) {local $a[$_]=$a[$_]-1;$b=test(@_[0].$_)}} (0..9); # а тут собсно всё и происходит...  
  print ++$count,"\t",@_[0],"\n" unless $b;
}
test;
 

 
можешь на СИ реализовать это?

Всего записей: 185 | Зарегистр. 19-01-2003 | Отправлено: 06:52 27-01-2003
Fraq



Newbie
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Frez
 

Цитата:
var  
f:text;  
...
readln(f,st);  
...
 

 
По-моему ноги ноги твоих грабель растут из попытки открыть двоичный файл как текстовый и читать его построчно...
Попробуй лучше
var
f: file of byte;  
 
Или файл другого типа, но не текстовый, не то у тебя 0x0D0A глотать будет и это только в лучшем случае.
 

Всего записей: 18 | Зарегистр. 16-12-2001 | Отправлено: 16:11 03-02-2003
Serjik



Full Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
2 All:
Помогите с задачей:
Существует отсортированный массив с числами: {1,2,3,4,5,6,7.....}
Надо найти элементы, сумма которых равняется некому числу X.
Я этот алгоритм оформил ввиде рекурсии, работает замечательно, но! Этот метод (прямого перебора комбинаций) хорош только на небольших массивах, до 30-40 элементов, а как быть если массив состоит из 300-400 или даже тысяч элементов? А искомая комбинация может включать сотни элементов.
 
Возможно известен более интелектуальный алгоритм поиска решения такой задачи?

Всего записей: 471 | Зарегистр. 03-08-2002 | Отправлено: 06:38 03-03-2003
ghosty



Gold Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Срочно нужна помощь!
 
 
Нужно посчитать число возможных комбинаций в словосочетании из трех слов. Например,  
Всемирная Торговая Организация  
 
При условии, что каждое слово может принимать любую форму. Например,  
Всемирной Торговая Организация  
Всемирными Торговой Организацию  
...  
 
Как посчитать, сколько всего может быть таких комбинаций? Очень надо %)  
Заранее премного благодарен!

----------
пропадет-растает

Всего записей: 6808 | Зарегистр. 21-09-2002 | Отправлено: 01:03 02-10-2014
akaGM

Platinum Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
При условии, что каждое слово может принимать любую форму.
без морфологической базы никак...

Всего записей: 24107 | Зарегистр. 06-12-2002 | Отправлено: 02:14 02-10-2014
ghosty



Gold Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
без морфологической базы никак...

Это ясно. Мне нужно хотя бы оценочно прикинуть среднее число таких комбинаций для словосочетания из трех слов (возможно, из четырех). Чтобы убедить австрийских программистов не заниматься фигней
 
Положим, первое слово может встречаться в 7-ми уникальных формах, второе - в 19-ти, третье - в 11-ти. По какой формуле подсчитать число возможных комбинаций?

Все, въехал, надо их тупо между собой перемножить

----------
пропадет-растает

Всего записей: 6808 | Зарегистр. 21-09-2002 | Отправлено: 10:31 02-10-2014 | Исправлено: ghosty, 11:11 02-10-2014
akaGM

Platinum Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
ghosty
 
во, блин, молодец...
я всегда говорил, что в вопросе есть 1/2 ответа...
сразу видно, что меня на три месяца постарше :)

Всего записей: 24107 | Зарегистр. 06-12-2002 | Отправлено: 13:06 02-10-2014
Открыть новую тему     Написать ответ в эту тему

Страницы: 1 2 3

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Немного комбинаторики...


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2024

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru