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

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

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

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

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

qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Frez
 Программа готова. Сколько платишь за исходнкики?
 выполнено, как и просил, в TP


вечером выложу

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 13:51 20-10-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Мне нужен принцип, а не программа, если что пояснишь?
У меня тоже есть идейка...

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



s@nya.moder
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Что-ли и мне вставить свои 5 копеек...
 
Короче вот:

Код:
 
const a:array[0..9] of byte=(0,0,0,0,0,0,1,3,4,2); {сколько каких цифр}
var count:longint;
 
procedure test(n:string);
var i,j:byte;
var b:boolean;
begin
 b:=false;
 for i:=0 to 9 do if a[i]>0 then begin
  dec(a[i]);
  test(n+chr(i+48));
  inc(a[i]);
  b:=true;
 end;
 if not b then begin
  inc(count);
  writeln(count:5,' - ',n);
 end;
end;
 
begin
 test('');
end.
 

Думаю код настолько простой, что комментировать особо нечего...
 
Добавлено
Да... qwd
Время работы не знаю... Не успел прогу запустить, а она уже закончилась... Конечно если вывод в файл перенаправиьть, а то на экран оно так быстро не успевает выводить...

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

Всего записей: 1365 | Зарегистр. 28-07-2001 | Отправлено: 17:22 20-10-2002 | Исправлено: L0Ve, 21:44 20-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
L0Ve
 Моя прога работает 44 секунды на Пеньке 200. Вывод на экран.
 
 У меня прога в несколько раз длиньше, такие алгоритмы мусолит
 
Добавлено

Код:
 
program perestan;
uses Crt,WinDos;
var
 b:array [1..10] of integer;
 s,q6,q7,q8,q9,w,d2,d:longint;
 z,i,ic:longint;
 h,m,c,cc:word;
 h1,m1,c1,cc1:word;
begin
 clrscr;
 s:=0;
 GetTime(h,m,c,cc);
 for i:=677788889 to 998888777 do
  begin
   ic:=i;
   z:=1;
   q6:=0; q7:=0; q8:=0; q9:=0;
   for d:=1 to 9 do
    begin
     d2:=round(exp((9-d)*ln(10)));
     b[d]:=ic div d2;
     ic:=ic mod d2;
     if b[d]<6 then
      begin
       for w:=d to 9 do
        begin
         z:=1;
         if(q6<1) and (z<>0) then begin b[w]:=6; q6:=q6+1; z:=0; end;
         if(q7<3) and (z<>0) then begin b[w]:=7; q7:=q7+1; z:=0; end;
         if(q8<4) and (z<>0) then begin b[w]:=8; q8:=q8+1; z:=0; end;
         if(q9<2) and (z<>0) then begin b[w]:=9; q9:=q9+1; z:=0; end;
         d2:=round(exp((9-w)*ln(10)));
         i:=i+b[w]*d2;
        end;
       if q6<1 then b[10]:=6;
       if q7<3 then b[10]:=7;
       if q8<4 then b[10]:=8;
       if q9<2 then b[10]:=9;
       d:=9;
      end;
     if b[d]=6  then q6:=q6+1;
     if b[d]=7  then q7:=q7+1;
     if b[d]=8  then q8:=q8+1;
     if b[d]=9  then q9:=q9+1;
   end;
  if q6<1 then b[10]:=6;
  if q7<3 then b[10]:=7;
  if q8<4 then b[10]:=8;
  if q9<2 then b[10]:=9;
 
 
  q6:=0; q7:=0; q8:=0; q9:=0;
  z:=1;
  for w:=1 to 10 do
   begin
    if b[w]=6 then if q6<1 then q6:=q6+1 else begin w:=10; z:=0; end;
    if b[w]=7 then if q7<3 then q7:=q7+1 else begin w:=10; z:=0; end;
    if b[w]=8 then if q8<4 then q8:=q8+1 else begin w:=10; z:=0; end;
    if b[w]=9 then if q9<2 then q9:=q9+1 else begin w:=10; z:=0; end;
   end;
  if z<>0 then
{  if (q6=1) and (q7=3) and (q8=4) and (q9=2) then}
   begin
    s:=s+1;
    write(s,'  -   ');
    for w:=1 to 10 do
     write(b[w]);
    writeln;
   end;
  end;
 writeln;
 writeln('End');
 writeln;
 GetTime(h1,m1,c1,cc1);
 writeln('Время запуска программы:     ',h,':',m,':',c,'.');
 writeln('Время окончания программы:   ',h1,':',m1,':',c1,'.');
 readkey;
 
end.

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 19:15 20-10-2002
IntenT



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

Всего записей: 1584 | Зарегистр. 16-12-2001 | Отправлено: 22:18 20-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
IntenT
 А у меня?

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 07:47 21-10-2002
IntenT



Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
qwd
A u tebya - mnogo..

Всего записей: 1584 | Зарегистр. 16-12-2001 | Отправлено: 17:52 22-10-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Сорри что я  долго молчал...
L0Ve
КЛАСС ! ! !  
 Это то что надо! Весьма хитрая програмка !Сам придумал ?
Но что-то я толком не понял как она работает - поясни плиз.
qwd
Утебя тоже нормально, но немного громозтко - сам понимаешь.СПАСИБО!
 
 
Добавлено
У меня в голове не укладывается как она работает

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 14:21 17-11-2002
rew



Full Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
L0Ve
можешь написать словесно или на си свою прогу, а то паскаль я не знаю, но жутко интересен твой алгоритм

Всего записей: 442 | Зарегистр. 09-09-2001 | Отправлено: 05:26 18-11-2002
Frez



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

L0Ve
Тогда лучше словесно...

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



s@nya.moder
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
rew
Давай я лучше на перл перепишу:  

Код:
 
@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;
 
 

 
Добавлено
Frez
Придумал конечно сам.
Принцип довольно прост:
у меня есть массив, в котором хранится кол-во каждой из цифр.
вот я и начинаю рекурсивно формировать число.  
т.е. функция test пытается добавить к числу еще одну цифру из оставшихся и если таковых нет - выводим число и инкрементируем счетчик, который нужен только для красоты...

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

Всего записей: 1365 | Зарегистр. 28-07-2001 | Отправлено: 23:58 18-11-2002 | Исправлено: L0Ve, 00:01 19-11-2002
Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Двоешники, моя програмки выводит всего 1280 комбинаций.
 
const hash: array[0..3] of char = '6789';
const tcnt: array[0..3] of byte = (1,3,4,2);
type tnum = array[0..9] of byte;
type cnum = array[0..9] of char;
 
const CombNumber: integer = 0;
 
procedure IncreaseNum(var tn: tnum);
begin
  Inc(tn[0]); if tn[0]=4 then tn[0] := 0 else exit;
  Inc(tn[1]); if tn[1]=4 then tn[1] := 0 else exit;
  ...
  Inc(tn[9]); if tn[9]=4 then fillchar(tn, sizeof(tn), 0);
{ прерывание для проверки количества комбинаций }
  WriteLn(CombNumber);
  Halt(0);
end;
 
function CurCount(var tn: tnum; index: integer): Integer;
var i,j: integer;
begin
  j := 0; for i := 0 to 9 do if tn[i]=index then inc(j);
  CurCount := j;
end;
 
function IsOK(var tn: tnum): boolean;
begin
  IsOK := (tcnt[0]<=CurCount(tn,0)) and
          (tcnt[1]<=CurCount(tn,1)) and
          (tcnt[2]<=CurCount(tn,2)) and
          (tcnt[3]<=CurCount(tn,3));
end;
 
procedure Increase(var tn: tnum; var cn: cnum; Count: integer);
var i: integer;
begin
  for i := 1 to Count do
  begin
    repeat
       IncreaseNum(tn);
    until IsOK(tn);
  { получили удовлетворительный номер }
    Inc(CombNumber);
  end;
  for i := 0 to 9 do cn[i]:=hash[tn[i]];
end;
 
var tn: tnum; cn: cnum;
 
begin
  fillchar(tn, sizeof(tn), 0); Increase(tn, cn, 1);  {получаем первый}
  Increase(tn, cn, MaxInt);  { writeln(cn) }
end.

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

Всего записей: 683 | Зарегистр. 18-11-2002 | Отправлено: 12:02 19-11-2002
L0Ve



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

Цитата:
Двоешники, моя програмки выводит всего 1280 комбинаций

 
А ничего что 1280 - это неверно? Проверено математикой...

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

Всего записей: 1365 | Зарегистр. 28-07-2001 | Отправлено: 13:58 19-11-2002
Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Я тут свою прогу писал, но сообщение исчезло.
Может я не то сказал - извините, не со зла

Цитата:
Сложно, на мой взгляд, изложено. Но книга дельная !  

 
Являюсь автором комбинаторного сравнения и сортировки изображений. Если будут трудности - пишу на паскале.
 
 
Добавлено
Ой, появилось 8^))
 
LOVe
 
Выше я прочитал, что перестановки девяток местами несчитаются, а позиционно зависимая система счисления, дающая 1*2*3*4... не предполагает логических фильтров и соответственно формулы переноса этой системы счисления дают завышенный результат. А если я скажу, что между восьмёрками обязательно должно быть от двух до четычёх символов? Вы мне тоже математикой у виска посчитаете?...
Проверте программу сначало и если хоть одна комбинация лишняя или нехватает то тогда прошу меня удивить на  
p_keyheyback@mail.ru


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

Всего записей: 683 | Зарегистр. 18-11-2002 | Отправлено: 12:47 20-11-2002
L0Ve



s@nya.moder
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Pinocchio
Ух... Потратил некоторое время на изменение вашей программы..
А то не хотел компилироваться странный оператор
Цитата:
...
...
Да и не выводит ваша программа сгенеренные перестановки.
 
В общем когда до ума довел - получил списочек...  
Сразу в глаза бросилось, что у вас во всех вариантах последняя цифра - '6'... Это как??? Неужели по-вашему нет ниодной перестановки, где была бы не шестерка на последнем месте...
если очень интересно - сейчас накатаю прогу, которая мне даст список отсутствующих у вас перестановок....  
нужно?
 
Добавлено
Кстати прога ваша вывела всего 1260 перестановок...  
А вот если бы вы еще шестерку двигали, а не закрепили ее на последнем месте - то то было бы в 10 раз больше вариантов...

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

Всего записей: 1365 | Зарегистр. 28-07-2001 | Отправлено: 21:40 20-11-2002 | Исправлено: L0Ve, 22:05 20-11-2002
Pinocchio

Advanced Member
Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
L0Ve
Прости, старая заморочка вышла. У меня на дню, именно
таких по штук двадцать. И все старые - знакомые.
Теперь точно 12600.
 
Если со многоточием понятно то, у меня халт должен
был в условии стоять...
 
  Inc(tn[8]); if tn[8]=4 then tn[8] := 0 else exit;
  Inc(tn[9]); if tn[9]=4 then
  begin
    fillchar(tn, sizeof(tn), 0);
    WriteLn(CombNumber);
    Halt(0);
  end;
 
А список выводить, надеюсь понятно. А шестёрки, они далее двигались, после халта (то есть принудильного стопа).
 
begin
  fillchar(tn, sizeof(tn), 0);
  for I := 0 to MaxInt do
  begin
    Increase(tn, cn, 1);
    writeln(cn);
  end;
end.
 
 
Добавлено
И ещё, Турбень Профулер сказал, что так быстрее:
 
  IsOK := (tcnt[0]=CurCount(tn,0)) and
          (tcnt[1]=CurCount(tn,1)) and
          (tcnt[2]=CurCount(tn,2)) and
          (tcnt[3]=CurCount(tn,3));


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

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



Громозека с баяном
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
SergejKa
qwd
Frez
Не нашел пока книгу за 1976 год, но ждите найду по моему издательство "Мир", возможно подарил знакомым, которые позже учились.

----------
Век живи, век учись...
Всегда сперва думай, а потом действуй. И никогда не действуй прежде, чем подумаешь.

Всего записей: 7904 | Зарегистр. 07-12-2001 | Отправлено: 01:30 27-11-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
L0Ve
       Что-то я никак не вьеду, с этой рекурсией, как твоя програмка работает, а очень бы хотелось разобраться....
       Эту програму можно представить в линейном виде? Не слишком ли громоздко будет?
igcomp
       Как там книга поживает?

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 13:50 13-12-2002
FuzzyLogic



Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Frez
 
Да ведь просто всё. Начали с пустой строчки и заданного кол-ва каждого вида цифирь. А потом рекурсивно сгенерили. То что Love работает с цифирьками, кол-во которых задано, а не скажем с самим числом вида '99932323' пытаясь в нем чего-то переставлять, избавляет его от геморроя проверок а не было ли уже такого числа.
Если идти по вложенности рекурсии то выглядит это приблизно так:
Пусть число вида 2212 (для простоты, то есть одна единица и три тройки).
1. Имеем строку '' Вызываем test.
 test пробегается по всем цифирькам и генерит строчки:
 '1'
 '2'
Других цифирь нету.
2. test. Идем по циклу... Для строки '1' test вызовет себя рекурсивно передав в качестве параметра строчку '1' и предварительно убрав одну (и единственную) единицу из кол-ва единиц в цифре...
 dec(a[i]);  test(n+chr(i+48));
3. test вызванный рекурсивно имеет: '1' в строке и три оставшихся двойки. Делает строчку '12' и отнимает одну из двоек из списка кандидатов.
4. = 3. (но полученная строка уже '12')
5. = 3.  (но полученная строка уже '122')
6. Получает '1222' и нули в массиве кандидатов. В рез-тате выводит 1222 на экран и возвращается на предыдущий шаг рекурсии.
7. На данном шаге мы возвращаем кандидата на место inc(a[i]) и едем дальше...спускаясь по рекурсии ввиду отстутствия кандидатов доходим до низу (шаг '2' там где была сгенерирована строка '1', мы вернулись из рекурсии отработав кандидата 1 в качестве первой цифры. Кладем единицу на место inc(a[i]) (где i=1) и идем дальше по циклу, где генерим '2' и вызываем test, теперь ситуация в точности повторяется с самого начала, только уже имеется фиксированная '2' в начале и к ней генерятся хвосты.
 
Тем, кому интересно, сходите вот сюда:
[url]http://icpc.baylor.edu/past/PastProblems.html [/url]
и сюда
http://icpc.baylor.edu/past/default.htm
Море интересных проблем...

Всего записей: 1920 | Зарегистр. 27-07-2002 | Отправлено: 19:44 14-12-2002 | Исправлено: FuzzyLogic, 19:45 14-12-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Кажется начинаю вьезжать.....

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 00:12 17-12-2002
Открыть новую тему     Написать ответ в эту тему

Страницы: 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