Задачи на собеседовании в одну небезызвестную контору

[dn]

Ещё один вариант...

BMRandom    bmrandom = new bmRandom();
    container   a = ['a','b','c','d'];
    container   b;
    int         i,L,N;
    set         result = new set(types::Container);
    set         exception;
    int random(int _max)
    {
        int ret;
        ;
        ret =  bmrandom.num(_max,1);
        if (exception.in(ret))
        {
            ret = random(_max);
        }
        else
        {
            exception.add(ret);
        }
        return ret;
    }
    container fillcon()
    {
        container c;
        ;
        exception = new set(types::Integer);
        for (i = 1;i<=L;i++)
        {
            c=conins(c,conlen(c)+1,conpeek(a,random(L)));
        }
        return c;
    }
    ;
        L = conlen(a);
        N = factorial(L);
        result.add(a);
        info(con2str(a));
        do
        {
            b = fillcon();
            if(!result.in(b))
            {
                result.add(b);
                info(con2str(b));
            }
        }
        while (result.elements() < N);

[CDR]

Цитата:

Сообщение от avf

перестановки: Всё гениальное - простынь)
Произвольную перестановку можно представить в виде суперпозиции транспозиций соседних элементов. [[Липский] Комбинаторика_для программистов.] Т.е. достаточно n! раз последовательно попарно переставить соседние элементы:

Хм... Не плохой вариант, основной недостаток - алгоритм не работает для n>3 .

Цитата:

Сообщение от dn

Ещё один вариант...

BMRandom    bmrandom = new bmRandom();
    container   a = ['a','b','c','d'];
    container   b;
    .......
    while (result.elements() < N);

Ура! Это решение вроде как работает для всех n!
Единственный серьезный минус - количество проходов цикла. В лучшем случае цикл делает в 2 раза больше проходов, чем нужно для поиска всех перестановок. У меня этот алгоритм выдал следующие результаты:

• Для n = 3 количество решений 6, количество проходов цикла 12
• Для n = 5 количество решений 120, а количество проходов цикла уже 696

И еще желательно в решении не используются нестандартные типы данных: контейнер, множество. Лучше все-таки обойтись стандартными типами данных - целые и вещественные числа, строки, а так же их массивы.
Небольшая оптимизация цикла и используемых типов данных - и решение получится идеальным .

[dn]

Цитата:

Сообщение от CDR

Ура! Это решение вроде как работает для всех n!
Единственный серьезный минус - количество проходов цикла.

...
И еще желательно в решении не используются нестандартные типы данных: контейнер, множество. Лучше все-таки обойтись стандартными типами данных - целые и вещественные числа, строки, а так же их массивы.
Небольшая оптимизация цикла и используемых типов данных - и решение получится идеальным .

Задачу можно решить либо быстро, либо красиво... Решение с "бросанием костей" изначально не претендует на минимизацию кол-ва проходов цикла, но зато не надо долго ломать голову над алгоритмом.
Теперь насчет стандартных типов данных. Все правильно, но только для программиста на X++ container и set, являются более стандартными типами, чем массив, ИМХО. Я не припомню что-то практических задач в Axapta, где мне бы потребовалось использовать массив...
А на закуску "красивое" решение, вообще без циклов

#define.N(5)
static void job001(Args _args)
{
    str 1 a[#N];
    void init()
    {
        a[1] = 'a';
        a[2] = 'b';
        a[3] = 'c';
        a[4] = 'd';
        a[5] = 'e';
    }
    str makestr(str 1 b[#N], int level = 1)
    {
        return (level<#N)?b[level]+makestr(b,level+1):b[level];
    }
    void show (str 1 b[#N])
    {
        ;
        //info(b[1]+b[2]+b[3]+b[4]+b[5]);
        info(makestr(b));
    }
    void f(str 1 b[#N], int level=1, int shift=1)
    {
        str 1   c[#N];
        ;
        if (level < #N-1)
        {
            f(b,level+1,1);
        }
        if(shift <= #N-level)
        {
            c=b;
            c[level] = b[level+shift];
            c[level+shift] = b[level];
            show(c);
            f(c,level,shift+1);
        }
    }
    ;
    init();
    show(a);
    f(a);
}

[CDR]

Цитата:

Сообщение от dn

Задачу можно решить либо быстро, либо красиво... Решение с "бросанием костей" изначально не претендует на минимизацию кол-ва проходов цикла, но зато не надо долго ломать голову над алгоритмом.
Теперь насчет стандартных типов данных. Все правильно, но только для программиста на X++ container и set, являются более стандартными типами, чем массив, ИМХО. Я не припомню что-то практических задач в Axapta, где мне бы потребовалось использовать массив...
А на закуску "красивое" решение, вообще без циклов
***

Эта, однозначно, пять! "Респект и уважуха" (с).
Что бы вы не делали, всегда нужно стремиться сделать это красиво! Ведь "красота спасет мир" (С) .
Позволю себе небольшое исправление вашего "шедевра"

#define.N(5)
static void job001(Args _args)
{
    str 1   a[#N];
    str     resource = 'abcdefghijklmnopqrstuvwxyz';
    
    Set     validateSet; // Автоматическая проверка
    
    void init(Int _idx)
    {
        if (_idx == 0)
            return;

        a[_idx] = substr(resource, _idx, 1);
        init(_idx - 1);
    }

    str makestr(str 1 b[#N], int level = 1)
    {
        return (level<#N)?b[level]+makestr(b,level+1):b[level];
    }

    void show (str 1 b[#N])
    {
        str result;
        ;

        result = makestr(b);

        if (validateSet.in(result))// Автоматическая проверка
        {
            error('Doubling!');
        }
        else
        {
            info(result);
            validateSet.add(result);
        }
    }
    void f(str 1 b[#N], int level=1, int shift=1)
    {
        str 1   c[#N];
        ;

        if (level < #N-1)
        {
            f(b,level+1,1);
        }
        if(shift <= #N-level)
        {
            c=b;
            c[level] = b[level+shift];
            c[level+shift] = b[level];
            show(c);
            f(c,level,shift+1);
        }
    }
    ;

    validateSet = new Set(Types::String);  // Автоматическая проверка
    
    init(#N);
    show(a);
    f(a);

    info(strfmt('Total: %1 elements.', validateSet.elements()));  // Автоматическая проверка
}

Ну, собственно, на этом можно считать DAX-сообщество подготовленным к собеседованию в Goooogle .

[HorrR]

Про 4ех беглецов. Задача решается очень просто, если понять как оптимизировать процесс. Надо что бы 3ий и 4ый( 5, 10 минут перехода - самые медленные) бежали вместе и не возвращались(условно вместо 15ти получаем 10ть - пересечение скорости). Итак перебегают 1ый и 2ой, 1ый возвращается, неся фонарик 3ему и 4му( 2минуты+1 минута на возвращение 1го, итого: 3) 5 и 10 бегут за 10 минут и передают фонарик второму, который возвращается за первым(2 минуты) и они оба перебегают за 2 минуты. Итого: 3+10+2+2=17.


З.Ы Не перебегут эти 4ро за 17 минут. Только думать минут 10 будут)

[MikeR]

вот куда стремимся попасть на работу

[Qaz Qwerty]

Вот же, не работать мне в Гугле. Все понимаю, кроме вероятности 1/2. Ну почему 1/2 а не 1/71, кто-нибудь может объяснить?

[Qaz Qwerty]

Ага, вот здесь: http://kasparovchess.crestbook.com/v...287&action=new нашлось понятное объяснение.