Сейчас на форуме: 2nd, morgot, Rio, CDK123, zds, tyns777, tihiy_grom (+5 невидимых)

 eXeL@B —› Программирование —› Развернуть вложенные циклы
Посл.ответ Сообщение


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 21 марта 2009 15:43
· Личное сообщение · #1

Есть массив:
Code:
  1. Var
  2.   Arr:Array[0..N] Of Byte;

Нужно сделать его обход с выводом всех возможных комбинаций, т.е. если N=3 можно сделать так:
Code:
  1. Var
  2.   A,B,C,D:Byte;
  3. Begin
  4.   For A:=0 To Arr[0] Do
  5.     For B:=0 To Arr[1] Do
  6.       For C:=0 To Arr[2] Do
  7.         For D:=0 To Arr[3] Do
  8.           //Code....
  9. End;

Как организовать программу, чтобы она не зависила от количества элементов массива и не использовала рекурсии?
т.е. при любом значении N максимум 2-3 цикла

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Ранг: 441.3 (мудрец), 297thx
Активность: 0.41↘0.04
Статус: Участник

 Создано: 21 марта 2009 15:48 · Поправил: tihiy_grom
· Личное сообщение · #2

ну наверное как-то так

Code:
  2. var
  3.  arr: array[0..1000] of Byte;
  4.  a,b: Byte;
  5. begin
  6.  for a:=0 to high(arr) do
  7.   for b:=0 to arr[a] do
  8.    //Code...
  9. end;




Ранг: 1.0 (гость)
Активность: 0=0
Статус: Участник

 Создано: 21 марта 2009 15:49 · Поправил: hELLRC
· Личное сообщение · #3

гм... опередили
Code:
  1. Var 
  2.   A:Byte;
  3.   x: integer;
  4. Begin
  5.  for x:=0 to N do
  6.    for A:=0 to Arr[x] do
  7.      //code

мб так? =)




Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 21 марта 2009 16:00
· Личное сообщение · #4

Вы оба не правы... Блин было бы всё так просто я бы сюда не писал
пример:
Code:
  1. Var
  2.   A,B,C,D:Byte;
  3.   Arr:Array[0..3] Of Byte;
  4.   N:Integer;
  5. Begin
  6.   Arr[0]:=3;
  7.   Arr[1]:=3;
  8.   Arr[2]:=3;
  9.   Arr[3]:=3;
  10.   N:=1;
  11.   For A:=0 To Arr[0] Do
  12.     For B:=0 To Arr[1] Do
  13.       For C:=0 To Arr[2] Do
  14.         For D:=0 To Arr[3] Do
  15.           Begin
  16.             Memo1.Lines.Append(IntToStr(N)+'='+IntToStr(A)+'-'+IntToStr(B)+'-'+Int ToStr(C)+'-'+IntToStr(D));
  17.             Inc(N);
  18.           End;
  19. End;

Цикл выполняется 256 раз!
Если так:
Code:
  1. Var
  2.   A,B,C,D:Byte;
  3.   Arr:Array[0..3] Of Byte;
  4.   N:Integer;
  5. Begin
  6.   Arr[0]:=3;
  7.   Arr[1]:=3;
  8.   Arr[2]:=3;
  9.   Arr[3]:=3;
  10.   N:=1;
  11.   For A:=0 To 3 Do
  12.     For B:=0 To Arr[A] Do
  13.           Begin
  14.             Memo1.Lines.Append(IntToStr(N));
  15.             Inc(N);
  16.           End;
  17. End;

Цикл выполняется 16 раз!

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Ранг: 1.0 (гость)
Активность: 0=0
Статус: Участник

 Создано: 21 марта 2009 16:23
· Личное сообщение · #5

видимо недопонял...
это получаецо нужно размещения все вывести. без рекурсии что-то не идет в голову как сделать




Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 21 марта 2009 16:59
· Личное сообщение · #6

hELLRC пишет:
без рекурсии что-то не идет в голову как сделать
вот и мне не идёт
а с ней надо следить за переполнением стека и будет нерационально жрать кучу памяти
в теории сделать такой же массив
2 цикла repeat или while и в каждом проходе уменьшать значение счётчика во втором массиве, как до нуля дойдёт, уменьшать в предыдущем элементе, а в этом восстанавливать счётчик из оригинального
когда счётчик в первом элементе =0 конец
но что-то не получается осуществить

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh


Ранг: 681.5 (! !), 405thx
Активность: 0.42↘0.21
Статус: Участник
ALIEN Hack Team

 Создано: 21 марта 2009 17:03
· Личное сообщение · #7

Это что, брутфорсер будущий? Если да, то тогда не нужно так делать, и рекурсия не нужна, для этого есть другие алгоритмы

-----
Stuck to the plan, always think that we would stand up, never ran.


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 21 марта 2009 17:16
· Личное сообщение · #8

ARCHANGEL пишет:
Это что, брутфорсер будущий?
да
ARCHANGEL пишет:
Если да, то тогда не нужно так делать, и рекурсия не нужна, для этого есть другие алгоритмы
Если просто перебор символов, то согласен, а если нет?
а если не получается? Я упростил просто до безобразия
В оригинале есть массив arr1: array[0..n] of array of byte; и на каждом шагу и массив arr1[n] xorится с SourceArr...
Конечно не все циклы будут до конца, можно будет оптимизировать и прерывать при определённых условиях...
Для этого нужно вычислить координаты массивов... Какие тогда "другие алгоритмы"?

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Ранг: 52.1 (постоянный), 1thx
Активность: 0.02↘0
Статус: Участник

 Создано: 21 марта 2009 18:43 · Поправил: Wyfinger
· Личное сообщение · #9

Isaev пишет:
Цикл выполняется 256 раз!
...
Цикл выполняется 16 раз!

Потому что 4^4=256, а 4^2=16.

Честно говоря не сразу понял что собственно Вам нужно.
Вот мой вариант, вроде работает:
Code:
  1. var
  2.   M : array[0..3] of Byte;
  3.   V : array of Byte;
  4.   P, L,
  5.   i : Integer;
  6.   N : Boolean;
  7. begin
  8.  M[0] := 1;
  9.  M[1] := 3;
  10.  M[2] := 2;
  11.  M[3] := 1;
  12.  // Start bruteforce
  13.  L := Length(M);
  14.  SetLength(V, L);
  15.  P := 0;
  16.  while True do
  17.    begin
  18.      // ------
  19.      Memo1.Lines.Add(IntToStr(V[0])+'-'+IntToStr(V[1])+'-'+IntToStr(V[2])+' -'+IntToStr(V[3]));
  20.      // ------
  21.      N := True;
  22.      for i := 0 to P do
  23.        if V[i] < M[i] then begin N := False; Break; end;
  24.      // Inc cycle
  25.      if N then
  26.        begin
  27.          for i := 0 to L-1 do
  28.            if V[i] < M[i] then Break;
  29.          P := i;
  30.          if P = L then Break; // Exit
  31.          for i := 0 to P-1 do
  32.            V[i] := 0;
  33.          Inc(V[P]);
  34.          P := 0;
  35.        end else
  36.        begin
  37.          if P > 0 then Dec(P);
  38.          Inc(V[P]);
  39.        end;
  40.    end;


Я бы назвал этот алгоритм "пляшуший P".
Наверняка можно оптимизировать, если Вам это нужно для брутфорса.




Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 21 марта 2009 19:37
· Личное сообщение · #10

Wyfinger пишет:
Потому что 4^4=256, а 4^2=16
Я знаю
Wyfinger пишет:
Честно говоря не сразу понял что собственно Вам нужно.
Возможно, криво объяснил... Очевидное для рассказчика не всегда очевидно слушателям
(и мне обращение на "ты" ближе)
Wyfinger пишет:
Я бы назвал этот алгоритм "пляшуший P"
Да, пашет! Спасибо! То, что и хотел...
Вот бывает такое иногда... знаешь что надо, сидишь и тупишь
а иногда сядишь и напишешь за пару минут...
хз. от погоды чтоли зависит

Ещё мучаюсь давно с одним вопросом: algolist.manual.ru/search/lrs/suffix.php
Кто-нибудь пробовал это осуществить?
В нете куча теории и ни одного исходника
Вот распечатал сижу изучаю

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh


Ранг: 673.3 (! !), 400thx
Активность: 0.4↘0.31
Статус: Участник
CyberMonk

 Создано: 22 марта 2009 01:47
· Личное сообщение · #11

Isaev пишет:
Ещё мучаюсь давно с одним вопросом: --> Link <--
Кто-нибудь пробовал это осуществить?
В нете куча теории и ни одного исходника
Вот распечатал сижу изучаю

Интересно =) , но почему то суфиксным деревьям предпочитают код Boyer-Moore string search ...хотя он вроде бы медленее

-----
RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 22 марта 2009 02:18 · Поправил: Isaev
· Личное сообщение · #12

mak
хмм... спасибо за наводку... интересный алго, а я про него не слышал
только предназначен он не для этого
Задумайся: "Максимальная повторяющаяся подстрока"

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh


Ранг: 527.7 (!), 381thx
Активность: 0.16↘0.09
Статус: Участник
Победитель турнира 2010

 Создано: 22 марта 2009 12:16 · Поправил: OKOB
· Личное сообщение · #13

Isaev пишет:
и ни одного исходника

en.wikipedia.org/wiki/Suffix_tree" target="_blank">--> страница Wiki <-- и на ней ссылки на сырки Python, Perl, C.

-----
127.0.0.1, sweet 127.0.0.1


Ранг: 355.4 (мудрец), 55thx
Активность: 0.32↘0
Статус: Uploader
5KRT

 Создано: 22 марта 2009 12:47
· Личное сообщение · #14

Я быстрый поиск использовал в своих проектах
algolist.manual.ru/search/esearch/qsearch.php

Суффиксное дерево, надо будет опробовать

-----
Gutta cavat lapidem. Feci, quod potui. Faciant meliora potentes


Ранг: 673.3 (! !), 400thx
Активность: 0.4↘0.31
Статус: Участник
CyberMonk

 Создано: 22 марта 2009 13:15
· Личное сообщение · #15

Isaev я так чувствую , это университетское задание =) ...тогда Isaev сделает либу) ...первую в сети по суфиксным деревьям. А я потом на асм переведу)

-----
RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube


Ранг: 355.4 (мудрец), 55thx
Активность: 0.32↘0
Статус: Uploader
5KRT

 Создано: 22 марта 2009 20:26
· Личное сообщение · #16

mak реализация уже есть, на "псевдо-коде"
ru.wikipedia.org/wiki/Суффиксное_дерево

-----
Gutta cavat lapidem. Feci, quod potui. Faciant meliora potentes


Ранг: 681.5 (! !), 405thx
Активность: 0.42↘0.21
Статус: Участник
ALIEN Hack Team

 Создано: 23 марта 2009 14:29
· Личное сообщение · #17

Isaev
Табличный на основе xlat, т.е. у тебя есть массив символов, всяких разных, не только букв и цифр, можно и другие, хоть все печатаемые,хоть и непечатаемые тоже, далее по их коду располагаешь их в порядке возрастания, после перемещаешься по таблице, создаваяв результате следующей итерации новый вариант серийника (например, а подробнее прог это можно почитать вот здесь www.wasm.ru/article.php?article=cycle_pwd

-----
Stuck to the plan, always think that we would stand up, never ran.


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 23 марта 2009 18:53
· Личное сообщение · #18

Ну у нас, в общем, то же и получилось... немного помудрённее, т.к. для каждой позиции свой алфавит, но смысл тот же
Если будет очень не приемлима скорость, можно будет асм вставить с xlat... посмотрим

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
 eXeL@B —› Программирование —› Развернуть вложенные циклы
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати