powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz
20 сообщений из 70, страница 3 из 3
алгоритм последовательной генерации строк aaa-zzz
    #36688414
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio
мне не оч. интересно заниматься довольно рутинной работой. Я просто показал что рекурсию можно довольно просто переписывать итеративно.

я уже выше упоминал, что сабжевый алгоритм легко преобразовать в итеративный.
а вот итеративной ф-и Аккермана я нигде не нашел.
а так, как ты упомянул выше, что понял как она реализуется, то я и попросил.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688422
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudio
мне не оч. интересно заниматься довольно рутинной работой. Я просто показал что рекурсию можно довольно просто переписывать итеративно.

а вот итеративной ф-и Аккермана я нигде не нашел.


может быть здесь ?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688448
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

извиняюсь что морочил тебе голову, просто вспомнил упражнение которое не смог сделать, и подумал что то была ф-я Аккермана.
а задача была такая:
автор
Упражнение 3.18.
Напишите процедуру, которая рассматривает список и определяет, содержится ли в нем цикл, то
есть, не войдет ли программа, которая попытается добраться до конца списка, продвигаясь по
полям cdr, в бесконечный цикл. Такие списки порождались в упражнении 3.13.

Упражнение 3.19.
Переделайте упражнение 3.18, используя фиксированное количество памяти. (Тут нужна доста-
точно хитрая идея.)


сидел целый час, но ничего не придумал.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688457
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

и в каком из тех решений, занимаемая память не зависит от n?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688469
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
итеративной реализации ф-и Аккермана, наверное не существует.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688483
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Итеративных там несколько вариантов, но с минимумом памяти это нужно исследовать алгоритм в специализированной тулзе. Например кое что о алгоритме может рассказать Research Studio, токма Анкермана нужно переписать на васике
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688516
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
От смотри, от список вызовов функций
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688517
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
От как менялся от функции к функции параметр Ret
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688518
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну и собсно васиковская реализация Анкермана в эмуляторе RS
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688956
Фотография ну я
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
void __fastcall TForm1::Button1Click(TObject *Sender)
{
const int n_symbols = 3;
char buf[ n_symbols + 1];
int imax = pow( 26, n_symbols);
for( int i = 0; i < imax; i++)
{
char* p = buf;
for( int k = 0, s = i; k < n_symbols ; k++)
{
*p ++ = s % 26 + 'a';
s /= 26;
}
*p = 0;
strrev( buf);
Memo1->Lines->Add( buf);
}
return;
}


> плюс что делать если надо генерить варианты 20 символьных строк.

поставить n_symbols = 20, если надо то использовать __int64
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689127
d.p
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
d.p
Гость
Код: plaintext
perl -e "print \"$_\n\" for ('a' x 10 ... 'z' x 10);"
:)
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689270
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну яvoid __fastcall TForm1::Button1Click(TObject *Sender)
{
const int n_symbols = 3;
char buf[ n_symbols + 1];
int imax = pow( 26, n_symbols);
for( int i = 0; i < imax; i++)
{
char* p = buf;
for( int k = 0, s = i; k < n_symbols ; k++)
{
*p ++ = s % 26 + 'a';
s /= 26;
}
*p = 0;
strrev( buf);
Memo1->Lines->Add( buf);
}
return;
}


> плюс что делать если надо генерить варианты 20 символьных строк.

поставить n_symbols = 20, если надо то использовать __int64

не прокатит даже с инт64
2^64 =18446744073709551616
26^20 =19928148895209409152340197376
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689275
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaN,

классический боянчик для linked list'ов. Рекурсивно будет где-то так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
>(defun getCycle (slowL fastL)
    (declare (list slowL fastL))
    (if (not (endp fastL))
        (if (eq (car slowL) (car fastL))
            t
            ;else
            (getCycle (cdr slowL) (cddr fastL))
        )
    )
)
GETCYCLE
>(let ((x (list 'a 'b 'c)))
(rplacd (last x) x)
(print (getCycle x (cdr x)))
)
t
>
Можно переписать и итеративно, тогда будет фиксированный объем памяти использоваться.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689276
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

ткни меня носом.
не нашел я там алгоритма с константным потреблением памяти.
чем отличается итеративный алгоритм от рекурсивного советую почитать.

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

жаль там не пишут потребляемую память.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689332
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNитеративной реализации ф-и Аккермана, наверное не существует.
Мне тоже не верится. Но не в итерации. А в реализацию Аккермана на конечных автоматах, для заранее неизвестного (m,n). Использование стеков, списков, variable arrays - будет фейком по определению.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689350
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Такшо мне Нобелевку дадут если я Анкермана запишу итеративно с фиксированным или линейным потреблением памяти ?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689363
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я скажу спасиб. И попрошу исходник в свою коллекцию.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689386
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Курите скрины с Ресерч Студио. Определенные закономерности она уже показала, например как меняется М.

222 11 00 1111 0000 1111111 000000 ...
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689979
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

c фиксированным.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36691359
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandr,

Нашел, писал когда - то на си шарпе, и вот такое у себя нашел :)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
public class PermutationString
    {
        public PermutationString()
        {
            m_string = "a";
        }

        private string m_string;

        public static PermutationString operator ++(PermutationString word)
        {
            word.m_string = word.next(word.m_string);
            return word;
        }

        public static implicit operator String(PermutationString word)
        {
            return word.m_string;
        }

        public string next()
        {
            return next(m_string);
        }


        private string next(string word)
        {
            return next(char_list(word),  0 );
        }


        private string next(List<char> chars, int depth)
        {
            int
                idx_last = chars.Count -  1 ,
                min =  97 ,
                max =  122 ;


            if (chars[idx_last - depth] < max)
            {
                chars[idx_last - depth]++;

                if (depth >  0 )
                {
                    for (int i = idx_last - depth +  1 ; i < chars.Count; i++)
                        chars[i] = 'a';
                }
            }
            else if (depth < idx_last)
            {
                return next(chars, ++depth);
            }
            else
            {
                reset(chars);
                chars.Insert( 0 , (char)min);
            }

            return chars_to_string(chars);
        }


        private string chars_to_string(List<char> chars)
        {
            string res = "";

            foreach (char smbl in chars)
                res += smbl;

            return res;
        }


        private void reset(List<char> chars)
        {
            for (int i =  0 ; i < chars.Count; i++)
                chars[i] = 'a';
        }



        private List<char> char_list(string word)
        {
            List<char> lst = new List<char>();

            for (int i =  0 ; i < word.Length; i++)
                lst.Add(word[i]);

            return lst;
        }
    }

Зачем эту шняку написал, даже вспомнил.
Надо было с эксел работать, я начал столбцы перебирать по буквам, и тут захотелось мне универсальности
...
Рейтинг: 0 / 0
20 сообщений из 70, страница 3 из 3
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]