ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz
25 сообщений из 70, страница 2 из 3
  2  все
алгоритм последовательной генерации строк aaa-zzz
    #36688000
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudioZyK_BotaNrstudioвсе мы поняли, что когда речь идет о коротком понятном коде, все Лисперы копируют под кальку шарповый код и удаляют декларации. Возможны птицы высоты полета Ксени выдали нам бы что получше, но пока такой расклад по палатам

причем здесь лисп и декларации?
я лишь предположил, что в ленивом хаскелле, рекурсивный алгоритм сможет выполнится с использованием малого объема памяти.

Теория нам говорит. Что любой рекурсивный алгоритм можно переписать итеративно.
Просто на 95% я уверен что это не нужно ТС. Оптимизировать нужно только тогда, когда это критично.

напиши реализацию ф-и Аккермана, с константным использованием памяти.
хотя вроде есть такое решение, но я его не видел, и оно мне не очевидно.

возможно я вас запутал, говоря рекурсия, вместо рекурсивный процесс.
тогда извиняюсь.
ТС сам упоминал про 20 порядков.
...
Рейтинг: 0 / 0
15.06.2010, 15:43:41
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688007
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudio
Рекурсивный памяти совершенно не жрет. В рекурсионных алгоритмах есть недостаток, они не могут разворачиваться "бесконечно". Стек не резиновый. Но вложенность в 100 вызовов функций, вполне может быть. Здесь же рекурсионный алгоритм разворачивается на длину слова, что весьма приемлимо.

у тебя там древовидная рекурсия, что ужасно.
она не сможет развернутся в цикл.
...
Рейтинг: 0 / 0
15.06.2010, 15:45:53
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688010
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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.
    class Program
    {
        public static string symbols = "abcdefghijklmnop";

        public static string growstr(string s)
        {
            if (s.Length ==  12 )
            {
                Console.WriteLine(s);
                return "";
            }
            else
            {
                string res = "";
                for (int i =  0 ; i <  10 ; ++i)
                {
                    res =s+ symbols[i];
                    res = growstr(res);
                }
                return res;
            }
           
        }
        static void Main(string[] args)
        {
                      growstr("");
        }
}
кушает 2мб памяти и 10% проца
...
Рейтинг: 0 / 0
15.06.2010, 15:46:13
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688027
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
ZyK_BotaNrstudio
Рекурсивный памяти совершенно не жрет. В рекурсионных алгоритмах есть недостаток, они не могут разворачиваться "бесконечно". Стек не резиновый. Но вложенность в 100 вызовов функций, вполне может быть. Здесь же рекурсионный алгоритм разворачивается на длину слова, что весьма приемлимо.

у тебя там древовидная рекурсия, что ужасно.
она не сможет развернутся в цикл.

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

хотя ну его этот алгоритм, без него можно обойтись
...
Рейтинг: 0 / 0
15.06.2010, 15:50:34
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688038
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fleandr
Участник
вариант rstudio память хавает мегабайтами. хранить список - зло
...
Рейтинг: 0 / 0
15.06.2010, 15:54:07
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688043
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
fleandrвариант rstudio память хавает мегабайтами. хранить список - зло

с точки зрения преждевременной оптимизации, которая как известно из букваря корень всех зол - да. С точки зрения универсальности, законченности, рефакторинга и дебага. Гуд.
...
Рейтинг: 0 / 0
15.06.2010, 15:56:43
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688051
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
fleandr,

кстате в коде у тебя уже глючок. Там 10 а там 12. А должни быть числа одинаковые.
...
Рейтинг: 0 / 0
15.06.2010, 16:02:26
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688055
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudio
я еще раз говорю, любой рекурсионный алгоритм ( на шарпе ) с блекджеком и шлюхами, можно развернуть в цикл - это математический догмат.

хотя ну его этот алгоритм, без него можно обойтись

я же выше говорил, что под рекурсией имею ввиду рекурсивный процесс. т.е. процесс занимаемая память которого растет с ростом n. т.е. сложность больше О(1).
сразу прошу не придираться к такому неточному(и содержащему ошибки) определению.
главное суть понять.
и шарп тут не причем, это математическое понятия.
ты сможешь реализовать с помощью цикла, и собственного стека :). но это - рекурсивный алгоритм.
...
Рейтинг: 0 / 0
15.06.2010, 16:03:46
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688059
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
у тебя снова неточность, уже в который раз. Я смогу это реализовать итеративно без собственного стека.
...
Рейтинг: 0 / 0
15.06.2010, 16:05:31
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688061
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudiofleandr,

кстате в коде у тебя уже глючок. Там 10 а там 12. А должни быть числа одинаковые.

поэтому, захардкореные константы - зло
...
Рейтинг: 0 / 0
15.06.2010, 16:06:09
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688065
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudioу тебя снова неточность, уже в который раз. Я смогу это реализовать итеративно без собственного стека.

я говорил про расходование памяти О(1).
емнип, такое решение существует, но я его не видел.
...
Рейтинг: 0 / 0
15.06.2010, 16:07:20
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688072
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudio,

я не мастер излагать свои мысли, советую обратится к вводному курсу по программированию чтобы вспомнить чем рекурсивный процесс отличается от итеративного.
...
Рейтинг: 0 / 0
15.06.2010, 16:09:49
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688074
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fleandr
Участник
хардкод констант зло эт да...
глючка нет:
12 - это длна строки
10 - это длина алфавита
...
Рейтинг: 0 / 0
15.06.2010, 16:10:21
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688076
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
ZyK_BotaNrstudioу тебя снова неточность, уже в который раз. Я смогу это реализовать итеративно без собственного стека.

я говорил про расходование памяти О(1).
емнип, такое решение существует, но я его не видел.

помойму ты не понимаешь как работает компьютер в данном случае.
Обьясняю на пальцах. В рекурсионном алгоритме для слова в 5 символов, будет держаться стек с вложенностью в 5 функций. С 10 символов - вложенность в десять функций. Если на вызов каждой функции с ее локальными переменными требуется допустим 50 байт, то число это можешь домножать соответственно на 5 или 10. Зависимость здесь линейная .
...
Рейтинг: 0 / 0
15.06.2010, 16:10:52
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688082
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
fleandrхардкод констант зло эт да...
глючка нет:
12 - это длна строки
10 - это длина алфавита

так алфавит у тебя не десять символов
...
Рейтинг: 0 / 0
15.06.2010, 16:11:43
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688084
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fleandr
Участник
мож кому не лень написать нерекурсивно... ))) вот и посмотрим как работать будет
меня пока рекурсия устраивает. спс всем ))
...
Рейтинг: 0 / 0
15.06.2010, 16:12:27
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688099
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudio,

на счет данной задачи, уже согласен. и рекурсивная пойдет, главное список не хранить.

а на счет магических возможностей си-шарпа решения рекурсивного алгоритма итеративно, вопрос остается в силе.

итеративно - это не линейная зависимость, а константная.
...
Рейтинг: 0 / 0
15.06.2010, 16:18:17
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688136
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
fleandrмож кому не лень написать нерекурсивно... ))) вот и посмотрим как работать будет
меня пока рекурсия устраивает. спс всем ))

на счет итеративного вопрос снят.
рекурсивная ф-и, легче пишется, и легче читается.

я просто затупил с вложенностью. не сообразил, что она не больше длины слова.
а так, я больше люблю рекурсивные определения, чем итеративные, в том случае, если нет оверхеда по памяти.
...
Рейтинг: 0 / 0
15.06.2010, 16:30:05
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688182
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
ZyK_BotaNrstudio,

на счет данной задачи, уже согласен. и рекурсивная пойдет, главное список не хранить.

а на счет магических возможностей си-шарпа решения рекурсивного алгоритма итеративно, вопрос остается в силе.

итеративно - это не линейная зависимость, а константная.

Да это не магические возможности си-шапра Гыы. Ты просто не понимаешь сути программирования и сути императивного представления программ. Вот итеративное решение. Оно менее наглядное, конечно. И алфавит заменен числами. А так все теже яйца только в профиль.

Код: 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.
private void Form1_Load(object sender, EventArgs e)
        {
            int[] alphabet = new int[] {  1 ,  2 ,  3  };
            List<int[]> list = new List<int[]>();

            //this.F(alphabet, list, "aaaaaaaa",  0 ,  5 );

            this.F(alphabet, list, new int[] {  0 ,  0 ,  0  });
        }

        void F(int[] alphabet, List<int[]> list, int[] word)
        {
            int i =  0 ;
            bool bReset = false;
            
            while (true)
            {
                if (i < alphabet.Length)
                {
                    if(!bReset)
                        list.Add((int[])word.Clone()); ;

                    word[i]++;

                    if (word[i] == alphabet.Length)
                    {
                        word[i] =  0 ;
                        i++;
                        bReset = true;
                    }
                    else if(bReset)
                    {
                        i =  0 ;
                        bReset = false;
                    }
                }
                else
                {
                    break;
                }
            }
        }
...
Рейтинг: 0 / 0
15.06.2010, 16:47:53
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688262
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudio,

то что эту задачу можно решить итеративно я уже упоминал выше(даже настаивал на таком решении).
я попросил итеративное решение ф-и Аккермана.

а итеративное решение обсуждаемой ф-и, я попробую записать и проще.
...
Рейтинг: 0 / 0
15.06.2010, 17:19:13
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688286
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
пробуйте, как попробуете посмотрим на счет Аккермана
...
Рейтинг: 0 / 0
15.06.2010, 17:27:33
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688350
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
хсате на шот анхермана,
тоже самое вайл тру зациклились, пока не выполним условие на отрез отказываемса уходить
...
Рейтинг: 0 / 0
15.06.2010, 18:01:45
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688401
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
rstudioхсате на шот анхермана,
тоже самое вайл тру зациклились, пока не выполним условие на отрез отказываемса уходить

нормально переписать в итеративный процесс не получилось.

в твоем решении я не увидел ф-и зависимой n(переменного размера слова).
да и ты уверен в правильности своего решения? а то у меня закрались сомнения.

и буду благодарен, если выложишь(или дашь ссылку) итеративное решение ф-и Аккермана.
...
Рейтинг: 0 / 0
15.06.2010, 18:24:32
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688404
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rstudio
Участник
ZyK_BotaNrstudioхсате на шот анхермана,
тоже самое вайл тру зациклились, пока не выполним условие на отрез отказываемса уходить

нормально переписать в итеративный процесс не получилось.

в твоем решении я не увидел ф-и зависимой n(переменного размера слова).


фикс вот здесь
Код: plaintext
1.
2.
3.
 while (true)
            {
                if (i < word.Length)

ZyK_BotaN
да и ты уверен в правильности своего решения? а то у меня закрались сомнения.


Код выдает правильный результат ? Выдает. Что еще нужно ?
Могут быть еще смол фиксы, но принцип остался тотже.
И вот я не уверен увижу ли решение которое ты обещал.

ZyK_BotaN
и буду благодарен, если выложишь(или дашь ссылку) итеративное решение ф-и Аккермана.

мне не оч. интересно заниматься довольно рутинной работой. Я просто показал что рекурсию можно довольно просто переписывать итеративно.
...
Рейтинг: 0 / 0
15.06.2010, 18:30:47
| Ответить | Цитировать | Написать  
алгоритм последовательной генерации строк aaa-zzz
    #36688406
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
ZyK_BotaN
да и ты уверен в правильности своего решения? а то у меня закрались сомнения.



алгоритм проверил, была незначительная помарка.
...
Рейтинг: 0 / 0
15.06.2010, 18:31:11
| Ответить | Цитировать | Написать  
25 сообщений из 70, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36688007&tid=1343619]:
 0ms
get settings:
 9ms
get forum list:
 18ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 188ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 84ms
get tp. blocked users:
 2ms
others: 196ms
total:  516ms
созд. / загр.: 516ms
x
x
Закрыть


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