Задачи на собеседовании в одну небезызвестную контору - Страница 3 - Курилка

belugin · 15.09.2008, 17:10

http://www.codeplex.com/IronPython

X++:

import operator
def permutationStep(xs, i):
    rests = permutations(xs[:i] + xs[i+1:])  
    return map(lambda x:[xs[i]] + x, rests)
def sumLists(lists):
    return reduce(operator.add, lists, [])
def permutations(xs):
    if xs == []:
       return [[]]    
    return sumLists(map(lambda x: permutationStep(xs, x), range(len(xs)) ))
print permutations([1, 2])
print permutations([1, 2, 3])

[[1, 2], [2, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Только так не честно, наверное

CDR · 15.09.2008, 17:13

Цитата:

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

Правильный ответ = 1/2

Щас правда пытаюсь понять, как это доказать математически/логически

Ваня сегодня жжот

.
Осталось написать программку и можно с Microsoft в Google

belugin · 15.09.2008, 17:14

да, я ошибся

CDR · 15.09.2008, 17:18

Цитата:

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

http://www.codeplex.com/IronPython

X++:

import operator
def permutationStep(xs, i):
    rests = permutations(xs[:i] + xs[i+1:])  
    return map(lambda x:[xs[i]] + x, rests)
def sumLists(lists):
    return reduce(operator.add, lists, [])
def permutations(xs):
    if xs == []:
       return [[]]    
    return sumLists(map(lambda x: permutationStep(xs, x), range(len(xs)) ))
print permutations([1, 2])
print permutations([1, 2, 3])

[[1, 2], [2, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Только так не честно, наверное

Ну вообщем-то да... Подразумевалось использование стандартных циклов, типов данных и операторов. Допускается использовать только простейшие математические функции типа возведение в степень, извлечение корня и т.д.

kashperuk · 15.09.2008, 17:26

Доказал, с помощью мат.индукции:

общая формуля для n получилась: 1/n + 1/2 * 1/n * (n-2)

CDR · 15.09.2008, 17:27

Цитата:

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

Доказал, с помощью мат.индукции:

общая формуля для n получилась: 1/n + 1/2 * 1/n * (n-2)

А что такое n?

kashperuk · 15.09.2008, 17:30

Цитата:

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

А что такое n?

n - число мест в автобусе.
71, в данном примере

kashperuk · 15.09.2008, 17:34

Я просто задачу решал мат.индукцией. Не знаю, или это правильный подход

Решил для n = 2, увидел, что вероятность равна 1/2.
Решил для n = 3, увидел, что вероятность равна 1/2.
Решил для n = 4, увидел, что вероятность равна 1/2 и смог предположить формулу (приведена выше).

Осталось только доказать, что формула сводится к 1/2 для этого случая и для случая n+1, что я и проделал

Заумно правда как-то получилось

CDR · 15.09.2008, 17:46

Цитата:

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

n - число мест в автобусе.
71, в данном примере

Круто!

У меня доказательство попроще, используя логику. Это конечно не так солидно, как мат. индукция, но все же...

Для любого пассажира, начиная с первого, существует два результата, 100% определяющих решение задачи. Если очередной пассажир занимает место №1, то последний пассажир 100% занимает свое место, так как все последующие пассажиры рассаживаются по своим местам. Если пассажир занимает место №71, то последний пассажир 100% пролетает со своим местом. Занятие пассажиром любого другого места не влияет на итоговый результат. Можно, конечно, заморочиться с расчетом отдельных вероятностей для каждого пассажира занять определенное место, однако очевидно, что вероятность занять первое место для любого пассажира равна вероятности занять последнее место. Именно из равности этих вероятностей итоговая вероятность получается 1/2.

CDR · 15.09.2008, 17:58

Для полного самоутверждения осталось написать маленькую программку

.

kashperuk · 15.09.2008, 18:02

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

X++:

#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 · 15.09.2008, 18:07

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

belugin · 15.09.2008, 18:13

"следовательно единственный пассажир который займет не своё место это тот, чьё место займёт первый пассажир."

если это второй пассажир, то куда он денется?

CDR · 15.09.2008, 18:24

первый "случайно" занимает место второго, второй "случайно" занимает место третьего, третий - четвертого и т.д.

Dozer · 15.09.2008, 18:34

Цитата:

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

первый "случайно" занимает место второго, второй "случайно" занимает место третьего, третий - четвертого и т.д.

Ну вот тут как раз видимо и расхождение. Согласно условию "пацан" только первый пассажир, и я предполагал что остальные будут стараться занять своё место если это возможно.

Dozer · 15.09.2008, 18:35

Цитата:

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

"следовательно единственный пассажир который займет не своё место это тот, чьё место займёт первый пассажир."

если это второй пассажир, то куда он денется?

Он сядет на первое место - место первого пассажира.

CDR · 15.09.2008, 18:40

Цитата:

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

Чувак в автобусе.
На остановке в ожидании 71-местного автобуса стоит 71 пассажир. У каждого из пассажиров есть билетик с номером места, которое ему необходимо занять при посадке в автобус. Для простоты пусть номер пассажира в очереди равен номеру его места в автобусе (1-ый чел должен занять место №1, 2-ой - №2, ... 71-ый - место №71 ). Однако первый стоящий в очереди пассажир - чувак, и при посадке в автобус он плюхается в кресло, которое ему понравилось больше всего (случайным образом от 1 до 71). Какова вероятность того, что последний (71-ый) пассажир займет свое (71-ое) место?
UPDATED: Упустил предложение, что каждый последующий пассажир, после первого, садится на свое место, если оно не занято, в противном случае ему достается случайное место из свободных.

Цитата:

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

Он сядет на первое место - место первого пассажира.

Внимательно читаем условие задачи

CDR · 15.09.2008, 18:43

Цитата:

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

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

X++:

#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++

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 · 15.09.2008, 22:44

Цитата:

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

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

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) в последнем цикле появилась куча ошибок с индексами

blokva · 16.09.2008, 08:06

Цитата:

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

Круто!

У меня доказательство попроще, используя логику. Это конечно не так солидно, как мат. индукция, но все же...

Для любого пассажира, начиная с первого, существует два результата, 100% определяющих решение задачи. Если очередной пассажир занимает место №1, то последний пассажир 100% занимает свое место, так как все последующие пассажиры рассаживаются по своим местам. Если пассажир занимает место №71, то последний пассажир 100% пролетает со своим местом. Занятие пассажиром любого другого места не влияет на итоговый результат. Можно, конечно, заморочиться с расчетом отдельных вероятностей для каждого пассажира занять определенное место, однако очевидно, что вероятность занять первое место для любого пассажира равна вероятности занять последнее место. Именно из равности этих вероятностей итоговая вероятность получается 1/2.

А по моему гораздо проще:
"Какова вероятность того что Вы встретите на улицах города динозавра? Ответ: 1/2 Либо встречу, либо нет!" (с)

Соответственно пассажир номер n (в данной задаче это 71 просто уловка ИМХО) либо сядет на свое место либо нет!

Похожие темы
Тема	Автор	Раздел	Ответов	Посл. сообщение
ARIS-задачи	itfs	Курилка	9	02.11.2006 12:35