VPF::Генерирование строк - Форум программистов

Magister Y0da

Дата 7.2.2007, 16:38 (ссылка)

(нет голосов)

Загрузка ...

Зелёненький

Профиль
Группа: Участник
Сообщений: 235
Регистрация: 30.11.2004

Репутация: 2
Всего: 2

мне нужен рекурсивный АЛГОРИТМ который генерирует все возможные строки составленные из данной, длинной от a до b

Пример:
у нас есть строка "123"
нам надо сгенерировать все строки от 1 до двух символов

Вывод:
1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33

--------------------

nerezus

Дата 7.2.2007, 18:12 (ссылка)

(нет голосов)

Загрузка ...

Вселенский отказник

Профиль
Группа: Участник
Сообщений: 3330
Регистрация: 15.6.2005

Репутация: нет
Всего: 43

Код


def getitem(x1=1,x2=3, alfavit = "abcdefghklmnopqrstuvwxyz"):
    for n in range(x1,x2+1):
        state = [0 for x in range(n)]
        memo = 0
        while memo==0:
            yield ''.join(map(alfavit.__getitem__,state))
            memo = 1
            for i in range(n):
                state[n-i-1] += memo
                if state[n-i-1]==len(alfavit):
                    state[n-i-1]=0
                    memo = 1
                else:
                    memo = 0
for x in getitem(1, 2, "123"):
    print x,

Код


1 2 3 11 12 13 21 22 23 31 32 33

Это сообщение отредактировал(а) nerezus - 7.2.2007, 18:16

--------------------

Сообщество художников Artsociety.ru

Great

Дата 7.2.2007, 19:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 3.12.2006

Репутация: нет
Всего: 1

Код


#include <string>
#include <string.h>
#include <iostream>
#include <math.h>
using namespace std;
string getnext(int a, int b, string alpha)
{
    static long lcur = -1;
    int len = alpha.length() + 1;
_gen:
    if(lcur == -1)
        lcur = pow(len, a-1);
    if(lcur >= pow(len, b))
        return string("");
    char *buf = new char[b+3];
    itoa(lcur, buf, len);
    if(strchr(buf, '0'))
    {
        lcur ++;
        goto _gen;
    }
    for(int i=0;i<strlen(buf);i++)
        buf[i] = alpha.c_str()[buf[i] - '1'];
    buf[i] = 0;
    string ret = buf;
    delete buf;
    lcur ++;
    return ret;
}
int main()
{
    string s;
    do cout << (s = getnext(1, 3, "abc")) << " ";
    while(!s.empty());
    cout << endl;
    return 0;
}

Код


a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc
Press any key to continue

Это сообщение отредактировал(а) Great - 7.2.2007, 19:31

Magister Y0da

Дата 8.2.2007, 21:34 (ссылка)

(нет голосов)

Загрузка ...

Зелёненький

Профиль
Группа: Участник
Сообщений: 235
Регистрация: 30.11.2004

Репутация: 2
Всего: 2

Спасиба конечно
но я просил АЛГОРИТМ =)

--------------------

SoWa

Дата 8.2.2007, 23:36 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

Не понимаю. Алгоритм- рекурсия. Этим все сказано. А чем, допустим, код на Си- не реализация алгоритма?

--------------------

Всем добра smile

pushok

Дата 8.2.2007, 23:49 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 92
Регистрация: 7.2.2007

Репутация: нет
Всего: нет

может вот это подойдет:

процедура П1 (s,a,s1) // s,s1 - строки, a - максимальная длина нужных нам слов
цикл от первой до последней буквы строки s:
если у нас нет слова s1+очередная буква строки s, тогда добавляем/пишем это слово.
если длина такой строки(s1+очередная буква строки s)<а, тогда П1(s,a,s1+очередная буква строки s).
конец цикла.
конец процедуры.

использование такой процедуры:

П1('123',2,''),
т.е. из строки '123' все строки не длинее двух символов начиная с пустой строки (пустая строка не учитывается).

в Delphi (Pascal)

Код


var
slovo:string;
l:integer;
slova:array of string; // массив всех слов, что у нас получились

function is_in(m:array of string;s:string):boolean; // проверяет наличие строки s в массиве m
var i:integer;
begin
 result:=false;
 for i:=0 to high(m) do
  if (m[i]=s) then
   begin
   result:=true;
   break;
   end;
end;

procedure p1(s:string;a:integer;s1:string); // рекурсивная процедура, состовляющая слова
var i:integer;
begin
 for i:=1 to length(s) do
  begin
  if not is_in(slova,s1+s[i]) then
   begin
   setlength(slova,length(slova)+1);
   slova[high(slova)]:=s1+s[i];
   end;
  if (length(s1+s[i])<a) then p1(s,a,s1+s[i]);
  end;
end;

...
write('Введите слово: ');
readln(s);
write('Введите длину слов: ');
readln(l);
p1(slovo,l,'');
...
// вывод слов на экран из массива slova
...

W4FhLF

Дата 9.2.2007, 10:34 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 5
Всего: 121

Код


#include "stdio.h" 
#include "windows.h" 

int main(int argc, char* argv[]) 
{ 
        static char szPassword[256]; 
        ZeroMemory(szPassword, sizeof(szPassword)); 

        static char szAlphabet[256]; 
        strcpy(szAlphabet, "ABC"); 

        static unsigned char bAlphabet[256]; 
        ZeroMemory(bAlphabet, sizeof(bAlphabet)); 

        int i = 0, k = 0; 
        while (TRUE) 
        { 
                bAlphabet[k] = (unsigned char)szAlphabet[i]; 
                if (!szAlphabet[i]) 
                        break; 
                k = (unsigned char)szAlphabet[i]; 
                i++; 
        } 

        while (TRUE) 
        { 
                __asm 
                { 
                    pushad 
                    mov edi,offset szPassword 
                    mov ebx,offset bAlphabet 
                L1: movzx eax,byte ptr [edi] 
                    xlat 
                    cmp al,0 
                    je L3 
                    mov [edi],al 
                    jmp L5 

                L3: xlat 
                    stosb 
                    jmp L1 

                L5: popad 
                } 
                printf("%s\n", szPassword); 
        } 
        return 0; 
}

http://www.insidepro.com/doc/003r.shtml

--------------------

DeadLine

Дата 10.2.2007, 20:51 (ссылка)

(нет голосов)

Загрузка ...

Мыслитель

Профиль
Группа: Завсегдатай
Сообщений: 736
Регистрация: 16.2.2006
Где: Готем

Репутация: нет
Всего: 51

Хм...Мне интересно А Йода не может по приведенному исходнику восстановить алгоритм?

Strannik

Дата 10.2.2007, 22:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2

Код - алгоритм, изуродованный так, чтобы он был понятен компьютеру.

Magister Y0da

Дата 13.2.2007, 05:57 (ссылка)

(нет голосов)

Загрузка ...

Зелёненький

Профиль
Группа: Участник
Сообщений: 235
Регистрация: 30.11.2004

Репутация: 2
Всего: 2

ну или хотя бы можно код на паскале, у меня с C\C++ и Python не очень smile

А блин увидел =))

Это сообщение отредактировал(а) Magister Y0da - 13.2.2007, 05:59

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »