Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > PHP: Общие вопросы > БрутФорс


Автор: lifer 19.1.2004, 21:47
Кто подскажет как логичней всего организовать перебор всех комбинаций букв в заданном диапазоне (3-8 символов в слове) на ПХП? (не бойтесь, ломать ничего не собираюсь).

Автор: arial 19.1.2004, 22:35
Для цифр придумал за 5 секунд:
Код
<?php
$from = 0;
$to = 9999;
while ($from <= $to) {
   printf('%0' . strlen($to) . 's', $from);
   ?><br /><?php
   $from++;
}
?>
Для букв - придется подумать.

Автор: lifer 19.1.2004, 22:58
хм, для цифр я и сам за 5 сек напишу, а вот для букв не могу ничего придумать пока-что...
Может создать массив где значениями будут символы, а потом работать с ним?

Автор: arial 19.1.2004, 23:24
Ну это понятно, а потом рекурсией этот массив.

Автор: lifer 20.1.2004, 02:28
Млин, что-то башка совсем не варит сегодня. smile.gif
Пробовал сделать через вложенные циклы for, но это долго и глупо. А с рекурсией никак разобраться не могу. Может хоть набросок какой-нибудь кинете? Пожалуйста.
Код

$chars='qwertyuiopasdfghjklzxcvbnm1234567890';
for ($i=0;$i<strlen($chars);$i++)
    {
     $mass[]=$chars[$i];
    }

Вот мой массив.

Автор: lifer 20.1.2004, 02:30
У меня проблема как от одного символа в слове перейти к 2-м и.т.д. (понимаю, что торможу... но сейчас ничего больше придумать не могу)

Автор: Sardar 20.1.2004, 03:17
У меня на часах 1:20 так что за "качество" кода не ручаюсь smile.gif. Скорость тоже никакая =\. Количество всех возможных комбинаций для задданной длины пароля: количество_символов_алфавита в степень длинна_пароля. Суммируй все для длин от 3-8 - шокирует biggrin.gif.
Код

$chars='qwertyuiopasdfghjklzxcvbnm1234567890';
$from=3; $to=8;
for($i=$from; $i<=$to; $i++) { //длинна пароля
$index[]=array();
for($j=0;$j<$i;$j++) $index[$j]=0;
while(true) {
 $word="";
 for($j=0;$j<$i;$j++) $word+=$chars{$index[$j]};
 putWord($word);
 for($j=$i-1; $j>=0; $j--) {
  if(++$index[$j]>=strlen($chars)) {
   if($j+1==$i) continue 3;
   else $index[$j]=0;
   continue;
   }
  break;
 }
}
}

Идея ясна, оптимизация за тобой.

Автор: Fedor 20.1.2004, 03:23
Вот тебе АЛГОРИТМ полного перебора чео угодно. Попробуй сам перевести его...

Код

АЛГ ПЕРЕБОР

k=1
s[1]=[1..N]

пока k<>0
{
  пока S[k] не пусто
   {
     выбрать следующее a[k] из s[k]
     s[k]=s[k]-[k]
     если - уже решение, то ОБРАБОТАТЬ РЕШЕНИЕ
     
     k=k+1
     вычислить s[k]
   }
  k=k-1
}

Здесь: S[k] - список допустимых значений на k-том шаге
A[k] - последовательность букв в ответе

З.Ы. Этот алгоримт - очень общий. ПЛЮС Я - паскалист, так что код близок к паскалевскому. Если надо, могу написать решение на Паскале, а ты его переведешь куда надо...

Автор: Fedor 20.1.2004, 03:24
Sardar Сори... когда писал, твоего ответа не было...

Автор: MuToGeN 20.1.2004, 10:55
Где-то в ветке по PHP валяется мой алгоритм перебора всех значений из массива.

Автор: lifer 20.1.2004, 15:35
2 sardar
Ругается насчёт ф-ции putWord($word); Говорит что нету такой smile.gif
Я немного изменил скрипт:
Код
<?php

$chars='qwertyasdf';
$from=1; $to=3;

for($i=$from; $i<=$to; $i++)
{
   $index[]=array();
   for($j=0;$j<$i;$j++) $index[$j]=0;

   while(true) {
                $word="";
                for($j=0;$j<$i;$j++) $word.=$chars[$index[$j]];
                echo $word."<br>\n";
                for($j=$i-1; $j>=0; $j--) {
                    if(++$index[$j]>=strlen($chars)) {
                                                      if($j+1==$i) continue 3;
                                                      else $index[$j]=0;
                                                      continue;
                                                }
                    break;
                                          }
               }
}

?>


Вот что получается в рез-те:
Код

q
w
e
r
t
y
a
s
d
f
qq
qw
qe
qr
qt
qy
qa
qs
qd
qf
qqq
qqw
qqe
qqr
qqt
qqy
qqa
qqs
qqd
qqf

т.е. скрипт перебирает далеко не все варианты сочетания символов.

Цитата
Скорость тоже никакая =\ Количество всех возможных комбинаций для задданной длины пароля: количество_символов_алфавита в степень длинна_пароля. Суммируй все для длин от 3-8 - шокирует

Помоему, быстрее не будет.

2 Morpheus

Цитата
З.Ы. Этот алгоримт - очень общий. ПЛЮС Я - паскалист, так что код близок к паскалевскому. Если надо, могу написать решение на Паскале, а ты его переведешь куда надо...

Лучше на Паскале напиши smile.gif Мне так намного понятней будет.

Автор: Sardar 20.1.2004, 23:00
Цитата

Ругается насчёт ф-ции putWord($word); Говорит что нету такой

Ты серьезно biggrin.gif, это должна была быть твоя функция, которая принимает готовое значение.
Цитата
т.е. скрипт перебирает далеко не все варианты сочетания символов.

Я же сказал поздно было, туплю sad.gif
Код

if(++$index[$j]>=strlen($chars)) {
                                                     if($j+1==$i) continue 3;
                                                     else $index[$j]=0;
                                                     continue;
                                               }
замени на:

if(++$index[$j]>=strlen($chars)) {
                                                     if($j==0) continue 3;
                                                     else $index[$j]=0;
                                                     continue;
                                               }

Автор: lifer 20.1.2004, 23:58
Sardar
Цитата
Ты серьезно , это должна была быть твоя функция, которая принимает готовое значение.

Млин, предупреждать надо smile.gif))
А то я уже начал думать что у меня крыша едет... smile.gif

Цитата
Я же сказал поздно было, туплю

Сенкс. Всё заработало. Теперь осталось только разобраться как именно всё это работает smile.gif
У меня что-то последние два дня голова совсем не варит. Ничего понять не могу. Пить меньше надо... smile.gif

И ещё, просто для интереса: эту же задачу возможно решить с помощью рекурсии?

Автор: Sardar 21.1.2004, 00:09
Самый простой способ - представь себе диски как в кодовом замке. На диски нанесенны все символы из алфавита, количество дисков равно количеству символов в пароле. Каждый раз ты крутишь последний диск на одно деление, как только диск сделал полный оборот ты крутишь на одно деление следующй диск. Как только первый(самй последний) диск сделал полный оборт обьявляем что все комбинации перебранны.

Здесь рекурсия не нужна(даже не знаю как ее прикрутить smile.gif), т.к. алгоритм тупо перебирает значения.

Автор: lifer 21.1.2004, 00:41
Понятно. Спасибо за объяснение.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)