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

[kashperuk]

Не, программку не осилил.
Вот есть вариант, авторство не мое (код на С++):

#include <algorithm>
#include <iostream>
using namespace std;

int A[20];
int n = 4;

int main()
{
      int nf = 1;
      int i,j;


      for(i = 2; i <= n; ++i) nf *= i;

      for(i = 0; i < n; ++i) A[i] = i + 1;

      for(i = 0; i < nf; ++i)
      {
            for(j = 0; j < n; ++j) cout<<A[j];
            cout<<endl;
            int jp = 0;
            for(j = 0; j < n - 1; ++j) if (A[j] < A[j+1]) jp = j;
            int tp = 0;
            for(j = n - 1; j >= 0; --j) if (A[j] > A[jp]) { tp = j; break; }
            swap(A[jp], A[tp]);
            for(j = 0; j < (n - jp) / 2; ++j) swap(A[jp + 1 + j], A[n - 1 - j]);
      }
}

Единственное, что я не уверен, можно ли несколько вложенных циклов иметь уровня вложенности = 1..

[Dozer]

Хм. Я не совсем понял как у вас получилось 1/2?
Я рассуждал таким образом что если даже первый пассажир самовольно занимает любое место, то остальные пассажиры занимают места по возможности согласно билету, следовательно единственный пассажир который займет не своё место это тот, чьё место займёт первый пассажир. Следовательно последний не займет своё место только в одном случае из 71.
Где я не прав?

[CDR]

Цитата:

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

Не, программку не осилил.
Вот есть вариант, авторство не мое (код на С++):

#include <algorithm>
#include <iostream>
using namespace std;

int A[20];
int n = 4;

int main()
{
      int nf = 1;
      int i,j;


      for(i = 2; i <= n; ++i) nf *= i;

      for(i = 0; i < n; ++i) A[i] = i + 1;

      for(i = 0; i < nf; ++i)
      {
            for(j = 0; j < n; ++j) cout<<A[j];
            cout<<endl;
            int jp = 0;
            for(j = 0; j < n - 1; ++j) if (A[j] < A[j+1]) jp = j;
            int tp = 0;
            for(j = n - 1; j >= 0; --j) if (A[j] > A[jp]) { tp = j; break; }
            swap(A[jp], A[tp]);
            for(j = 0; j < (n - jp) / 2; ++j) swap(A[jp + 1 + j], A[n - 1 - j]);
      }
}

Единственное, что я не уверен, можно ли несколько вложенных циклов иметь уровня вложенности = 1..

Хм.. вот вроде бы эквивалент на X++

static void Google(Args _args)
{

    int     A[20];
    int     n = 4;
    int     nf = 1;
    int     i,j;
    int     jp = 0;
    str     line;
    int     tp = 0;

    anyType buffer;

    ;

    // Расчет факториала (количество возможных значений)
    for (i = 2; i <= n; i++)
        nf = nf * i;

    // Генерация массива
    for(i = 1; i <= n; i++)
        A[i] = i;

    // перебор всех возможных значений
    for(i = 1; i <= nf; i++)
    {
        line = '';
        for (j = 1; j <= n; j++ )
        {
            line = line + int2str(A[j]);
        }
        info(line);

        jp = 1;
        for(j = 1; j <= (n - 1); j++)
        {
            if (A[j] < A[j+1]) 
                jp = j;
        }

        tp = 1;
        for(j = n; j >= 1; j--)
        {
            if (A[j] > A[jp]) 
            { 
                tp = j; 
                break; 
            }
        }

        // swap
        buffer  = A[jp];
        A[jp]   = A[tp];
        A[tp]   = buffer;

        for(j = 1; j <= ( (n - jp)/2 ); j++)
        {
            // swap
            buffer = A[jp + 1 + j];
            A[jp + 1 + j] = A[n - 1 - j];
            A[n - 1 - j] = buffer;
        }
    }
}

Че-то не работает ...

[gigz]

Цитата:

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

Хм.. вот вроде бы эквивалент на X++

static void Google(Args _args)
{
 
    int     A[20];
    int     n = 4;
    int     nf = 1;
    int     i,j;
    int     jp = 0;
    str     line;
    int     tp = 0;
 
    anyType buffer;
 
    ;
 
    // Расчет факториала (количество возможных значений)
    for (i = 2; i <= n; i++)
        nf = nf * i;
 
    // Генерация массива
    for(i = 1; i <= n; i++)
        A[i] = i;
 
    // перебор всех возможных значений
    for(i = 1; i <= nf; i++)
    {
        line = '';
        for (j = 1; j <= n; j++ )
        {
            line = line + int2str(A[j]);
        }
        info(line);
 
        jp = 1;
        for(j = 1; j <= (n - 1); j++)
        {
            if (A[j] < A[j+1]) 
                jp = j;
        }
 
        tp = 1;
        for(j = n; j >= 1; j--)
        {
            if (A[j] > A[jp]) 
            { 
                tp = j; 
                break; 
            }
        }
 
        // swap
        buffer  = A[jp];
        A[jp]   = A[tp];
        A[tp]   = buffer;
 
        for(j = 1; j <= ( (n - jp)/2 ); j++)
        {
            // swap
            buffer = A[jp + 1 + j];
            A[jp + 1 + j] = A[n - 1 - j];
            A[n - 1 - j] = buffer;
        }
    }
}

Че-то не работает ...

1) в последнем цикле появилась куча ошибок с индексами