| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
алгоритм
aids © (2007-10-09 23:03:00)возможно не по теме но может быть кто то мне поможет...
вообще м у меня такая задача:
дана последовательность 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 - считать одинаковыми и выдавать лишь одну из них
MBo (2007-10-10 16:12:00) [1]>в условии задачи ограничение на длину последовательности от 1 до 5000
формулу для количества перестановок я уже привел, так что интересно будет посмотреть на процесс получения и вывода 4.5*10^15569 перестановок :)
aids (2007-10-10 15:42:00) [2]>Anatoly Podgoretsky цифры и числа разные вещи...
ну так что не подскажите?
MBo> в условии задачи ограничение на длину последовательности от 1 до 5000
MBo (2007-10-10 09:24:00) [3]Молодец преподаватель, дал задачку, решение которой не висит на каждом углу в инете, и надо самому думать :)
>последовательности будут большими до 5000 элементов
Это вряд ли, т.к. количество перестановок будет расти очень быстро, например, для N = 12 их будет уже 1247400.
P(N) = (N - 1)! / 2^((N - 1) div 2)
Германн (2007-10-10 01:40:00) [4]Да и кстати
> write('M,N=');readln(M,N);
это не для пользователей программы. Они на это не способны.
Это для "неумного препода" :-)
Anatoly Podgoretsky (2007-10-10 01:37:00) [5]> aids (10.10.2007 01:23:05) [5]
Ну не может быть больше 10 цифр!
Германн (2007-10-10 01:29:00) [6]
> aids (10.10.07 01:23) [5]
>
> >Германн ©
>
> цифры только арабские
>
Тогда постановка задачи не правильная. Так как на сей вопрос отвечать? Флудом? Так это нам не влом. Только дай знак! :-)
aids (2007-10-10 01:23:00) [7]>Германн ©
цифры только арабские
> Anatoly Podgoretsky © решение 1 2 3 4 - тривиально, тяжелее с большими последовательностями
Anatoly Podgoretsky (2007-10-10 01:06:00) [8]> aids (10.10.2007 00:18:02) [2]
А надо правильно задавать вопрос, он сначала был про 1 2 3 4
Германн (2007-10-10 00:58:00) [9]
> последовательности будут большими до 5000 элементов...
> все цифры входят только один раз
Это как?
Или помимо римских и арабских цифр есть ещё какие-то цифры, про которые я ничего не знаю?
aids (2007-10-10 00:18:00) [10]то есть? последовательности будут большими до 5000 элементов...
очень важно сократить вычисления
Anatoly Podgoretsky (2007-10-09 23:13:00) [11]> aids (09.10.2007 23:03:00) [0]
Можно построить множества и сравнивать их.
| |
