алгоритм

← →
aids (2007-10-09 23:03) [0]

возможно не по теме но может быть кто то мне поможет...

вообще м у меня такая задача:
дана последовательность 4 3 2 1 - все цифры входят только один раз
надо получить все перестановки вида: 4 3 2 1 - 4 2 3 1 - 4 1 3 2
т.е элементы индексы которых нечетные(1,3,...) должны быть больше своих соседей на четных индексах.

а написал прогу которая получает все перестановки

нерекурсивную:
procedure Next; begin {найти i: X[i]<M,X[i+1]=M,...,X[N]=M}; X[i]:=X[i]+1; X[i+1]:=...:=X[N]:=1 end; program Sequences; type Sequence=array [byte] of byte; var M,N,i:byte; X:Sequence; Yes:boolean; procedure Next(var X:Sequence;var Yes:boolean); var i:byte; begin i:=N; {поиск i} while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end; if i>0 then begin inc(X[i]);Yes:=true end else Yes:=false end; begin write("M,N=");readln(M,N); for i:=1 to N do X[i]:=1; repeat for i:=1 to N do write(X[i]);writeln; Next(X,Yes) until not Yes end.

и рекурсивную
procedure Generate(k:byte); var i,j:byte; begin if k=N then begin for i:=1 to N do write(X[i]);writeln end else for j:=1 to M do begin X[k+1]:=j; Generate(k+1) end end; program SequencesRecursion; type Sequence=array [byte] of byte; var M,N:byte; X:Sequence; procedure Generate(k:byte); ............ begin write("M,N=");readln(M,N); Generate(0) end.
подскажте как переделать чтобы выдавались лишь нужные мне последовательности

П.С : последовательности вида 4 3 2 1 и 2 1 4 3 - считать одинаковыми и выдавать лишь одну из них

← →
Anatoly Podgoretsky © (2007-10-09 23:13) [1]

> aids (09.10.2007 23:03:00) [0]

Можно построить множества и сравнивать их.

← →
aids (2007-10-10 00:18) [2]

то есть? последовательности будут большими до 5000 элементов...
очень важно сократить вычисления

← →
Германн © (2007-10-10 00:58) [3]

> последовательности будут большими до 5000 элементов...

> все цифры входят только один раз

Это как?
Или помимо римских и арабских цифр есть ещё какие-то цифры, про которые я ничего не знаю?

← →
Anatoly Podgoretsky © (2007-10-10 01:06) [4]

> aids (10.10.2007 00:18:02) [2]

А надо правильно задавать вопрос, он сначала был про 1 2 3 4

← →
aids (2007-10-10 01:23) [5]

>Германн ©

цифры только арабские

> Anatoly Podgoretsky © решение 1 2 3 4 - тривиально, тяжелее с большими последовательностями

← →
Германн © (2007-10-10 01:29) [6]

> aids (10.10.07 01:23) [5]
>
> >Германн ©
>
> цифры только арабские
>

Тогда постановка задачи не правильная. Так как на сей вопрос отвечать? Флудом? Так это нам не влом. Только дай знак! :-)

← →
Anatoly Podgoretsky © (2007-10-10 01:37) [7]

> aids (10.10.2007 01:23:05) [5]

Ну не может быть больше 10 цифр!

← →
Германн © (2007-10-10 01:40) [8]

Да и кстати

> write("M,N=");readln(M,N);

это не для пользователей программы. Они на это не способны.
Это для "неумного препода" :-)

Молодец преподаватель, дал задачку, решение которой не висит на каждом углу в инете, и надо самому думать :)

>последовательности будут большими до 5000 элементов
Это вряд ли, т.к. количество перестановок будет расти очень быстро, например, для N = 12 их будет уже 1247400.

P(N) = (N - 1)! / 2^((N - 1) div 2)

← →
aids (2007-10-10 15:42) [10]

>Anatoly Podgoretsky цифры и числа разные вещи...

ну так что не подскажите?

MBo> в условии задачи ограничение на длину последовательности от 1 до 5000

>в условии задачи ограничение на длину последовательности от 1 до 5000
формулу для количества перестановок я уже привел, так что интересно будет посмотреть на процесс получения и вывода 4.5*10^15569 перестановок :)

алгоритм Найти похожие ветки