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

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, в данном примере

CDR · 15.09.2008, 17:46

Цитата:

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

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

Круто!

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

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

blokva · 16.09.2008, 08:06

Цитата:

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

Круто!

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

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

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

Соответственно пассажир номер 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: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.
Где я не прав?

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

belugin · 15.09.2008, 18:13

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

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

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:24

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

Dozer · 15.09.2008, 18:34

Цитата:

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

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

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

TGL · 16.09.2008, 16:58

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

А первые 2 задачи решить тривиально сходу у меня не получается и думаю не возможно. Например, 2ю задачу я свел к такому перебору: Любое число >1 до 100 можно представить в виде a**k или a**k x b**m или a**k x b**m х с**n, где a,b,c - простые и разные числа > 1; k,n,m - натуральные числа > 1. Например: 70 = 2**1 х 5**1 х *7**1;
99 = 3**2* х 11**1. Так вот, если некое число представимо в виде a**k x b**m х с**n, то соотв. выключатель "щелкнут"
(k+1)x(n+1)x(m+1) раз. Поэтому если это число будет нечетным - то лампочка в итоге будет гореть. Например, 70-ю лампочку "щелкнут" 2х2х2 = 8 раз => она гореть не будет. Короче будут гореть все лампочки с номерами у которых в упомянутом выше представлениях все числа k,n,m - четные плюс 1я лампочка. Например, 100я лампочка (=2**2х5**2 щелкнется 9 раз) будет гореть. 5 класс это сделает только на спец.кружке по математике

avf · 17.09.2008, 01:09

Первая задачка решается логически. Ведь у кааждого чела, оказавшегося в ситуации, что его место занято, есть выбор - либо разобраться в ситуации и сесть на первое место, предотвратив тем самым дальнейший пересорт по местам, либо забить болт и занять любое другое свободное место. Таким образом вероятность, действительно, 50 на 50.
Формулировка с сумашедшей старушкой в самолете выглядит забавней: ))

Andrew Akhmetov · 17.09.2008, 01:41

100 лампочек:
включены будут номера 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

до пол второго не спал из-за этой задачи

(нечетное число делителей у чисел с полным квадратом)

ivas · 17.09.2008, 18:28

нашел решение задачи про перестановки оказывается все просто нужно в начале элементы отсортировать)
взято отсюда:
http://xpoint.ru/forums/programming/...ad/28625.xhtml

X++:

#include <stdio.h>
#include <string.h>
                                                                                                                                                                      
int main()
{
        char str[20];
        int n,k,t,y;
        int ttt=1;
        strcpy(str,"111223");
        printf ("%s\n",str);
        n=strlen(str)-1;
while(1)
{
        k=n-1;
        while ((str[k]>=str[k+1])&&(k>=0)) k--;
        if (k<0) {return(0);}
        t=k+1;
        while ((t<n)&&(str[t+1]>str[k])) t++;
        y=str[k];
        str[k]=str[t];
        str[t]=y;
        t=0;
        while (t<(int)((double)(n-k)/2.0))
        {
                y=str[n-t];
                str[n-t]=str[k+1+t];
                str[k+1+t]=y;
                t++;
        }
        printf ("%s\n",str);
}
}

avf · 18.09.2008, 00:08

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

X++:

#define.CONDATA([' a', ' b', ' c'])
static void Transpositions(Args _args)
{
    Container       con = #CONDATA;
    Int             pos = 1,
                    len = conlen(con),
                    transCount = factorial(len);

    boolean anyMoreTrans()
    {;
        transCount--;
        return transCount;
    }

    void swap(int _i, int _j)
    {
        AnyType tmp = conpeek(con, _i);
        ;
        con = conpoke(con, _i, conpeek(con, _j));
        con = conpoke(con, _j, tmp);
    }

    void swapNextPair()
    {
        Int nextPos = (pos == len) ? 1 : pos+1;
        ;
        swap(pos, nextPos);
        pos = nextPos;
    }
    ;

    setprefix("Перестановки:");
    info(con2Str(con));
    while (anyMoreTrans())
    {
        swapNextPair();
        info(con2Str(con));
    }
}

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