Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > алгоритм перебора символов нерекурсивный

Автор: vnm 5.1.2006, 18:14

Кто нибудь подскажите нерекурсивный алгоритм перебора всех вариантов пароля длиной 5 символов из (к примеру) 6 символов( 1 2 9 a J ]). [email protected]

рекурсивный алгоритм:

program combinations;
{$APPTYPE CONSOLE}
Const Simbols : String = 'ab12';
Procedure Generate(S : String; Lev : Integer);
Var I : Integer;
Begin
If (Lev = 0) Then
Begin
Writeln(S); {next password}
Exit;
End;
For I:=1 To Length(Simbols) Do
Generate(S + Simbols[I], Lev - 1);
End;
Begin
Generate('', 3); {3 simbols for password}
Readln;
End.

Автор: SoWa 5.1.2006, 20:28

Пятью вложенными циклами! smile

Автор: nworm 5.1.2006, 20:37

Можно написать процедуру генерирующую следующий за текущим пароль и гонять эту процедуру в цикле от 1 до

<колличество символов в пароле>^<длина пароля>.

Автор: BSOD 5.1.2006, 20:47

как вариант - генерить все размещения...
(сначала генериш все множества из букв (каждую букву пишешь по пять раз), потом из этих множеств перестановки... но ИМХО - рекурсивный как-то рульнее....

Автор: S.A.P. 5.1.2006, 20:49

Цитата(vnm @ 5.1.2006, 18:14

)

Кто нибудь подскажите нерекурсивный алгоритм перебора всех вариантов пароля

то же самое, только в цикле и c "искуственным" стеком.

Автор: vnm 6.1.2006, 02:09

Цитата(SoWa @ 5.1.2006, 20:28)

Пятью вложенными циклами! smile

Мне нужен алгоритм для произвольного кол-ва символов в пароле. Вот моя программа на дельфи:

Код


program combinations;
{$APPTYPE CONSOLE}

Procedure Generate(S, Simbols: String; Lev : Integer);
Var I : Integer;
Begin
 If (Lev = 0) Then
  Begin
   Writeln(S); 
   Exit;
  End;
 For I:=1 To Length(Simbols) Do
  Generate(S + Simbols[I], Simbols, Lev - 1);
End;

function find(s: string; sb: char): boolean;
var
 i: integer;
begin
 result:=false;
 for i:=1 to length(s) do
  begin
   if sb=s[i] then
    begin
     result:=true;
     break;
    end;
  end;
end;

procedure delete_repeat_simbols(var s1: string; s: string);
var
 i: integer;
begin
 s1:=s[1];
 for i:=2 to length(s) do
  begin
   if not find(s1,s[i]) then s1:=s1+s[i];
  end;
end;

var
 Sim, Sim1: string;
 len: integer;
Begin
 Writeln('Put any line, that you want:');
 readln(Sim);
 delete_repeat_simbols(Sim1, Sim);
 writeln('Line after deleting all repeat simbols: ', Sim1);
 writeln('Number simbols of first line: ', length(Sim1));
 writeln('Put number simbols for subline ( this number < ', length(Sim1),' )');
 write('Number simbols of subline: '); readln(len);
 Generate('', Sim1, len); 
 Readln;
End.

Мне срочно нужен нерекурсивный алгоритм. Кто может то помоги[email protected]

Автор: nworm 6.1.2006, 02:58

Я же говорю можно писать процедуру, генерирующую следующий за текушим пароль.
Если пароли из цифр 0-9, то за

01112339

будет

01112340

аналогичную процедуру можно написать для произвольных символов.

Автор: Akina 6.1.2006, 12:19

Для произвольного количества символов либо рекурсия, либо динамическое программирование - а значит тоже рекурсия.
Исключение - цепной инкремент. См. пост nworm.

Автор: nworm 6.1.2006, 21:19

Примерно так.

Код


Function next(Var S: String; Simbols: String): Boolean;
 Var 
  I,J: integer;
  res: Boolean; 
 Begin
  I := Length(S);
  While(S[I] = Simbols[Length(Simbols)]) Do
   Begin
    I := I - 1;
    S[I] := Simbols[1];
   End;
  If (I > 0) Then
   Begin   
    J := 0;
    While (S[I] <> Simbols[J]) Do J := J + 1;
    S[I] := Simbols[J + 1];
    res := 0;
   End;
  Else res :=1;
  result:=res;
 End;

Проверять код было лень smile