Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Другие СУБД [игнор отключен] [закрыт для гостей] / Лучшие задачи проекта / 25 сообщений из 191, страница 1 из 8
28.12.2012, 14:56
    #38096239
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Разработка сверхбыстрой СУБД генерит множество интересных задач.
Буду выкладывать некоторые из самых простых, которые можно решать
не вникая в контекст работы "космической станции":

Генерятся 6 случайных байт (чисел от 0 до 255).
Какова вероятность что любые два числа из этих шести будут совпадать между собой ?
...
Рейтинг: 0 / 0
28.12.2012, 15:28
    #38096292
Лучшие задачи проекта
BAZlST,
...
Рейтинг: 0 / 0
28.12.2012, 15:32
    #38096297
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Честно гря, с формулой сразу сообразить тяжело.
На практике:

Вероятность ~0.05832, или примерно один к двадцати.

Код
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
 Random r = new Random();
            List<int> numbers = new List<int>();
            decimal count = 0;

            for (int j = 0; j < 1000000; j++)
            {
                for (uint i = 0; i < 6; i++)
                {
                    int number = r.Next(0, 255);
                    if (numbers.IndexOf(number) >= 0)
                        count++;

                    numbers.Add(number);             
                }

                numbers.Clear();

            }

            decimal result = count / 1000000;
...
Рейтинг: 0 / 0
28.12.2012, 15:34
    #38096303
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
хм, пофиксил баг в коде. Но результат не изменился, один к двадцати.

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
Random r = new Random();
            List<int> numbers = new List<int>();
            decimal count = 0;

            for (int j = 0; j < 1000000; j++)
            {
                for (uint i = 0; i < 6; i++)
                {
                    int number = r.Next(0, 255);
                    if (numbers.IndexOf(number) >= 0)
                    {
                        count++;
                        break;
                    }

                    numbers.Add(number);             
                }

                numbers.Clear();

            }

            decimal result = count / 1000000;

...
Рейтинг: 0 / 0
28.12.2012, 15:37
    #38096307
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
И сразу по ходу дела, продолжение этойже задачи ( тоже имеет практическое значение ).

Какова вероятность что пять из шести чисел совпадут ?
...
Рейтинг: 0 / 0
28.12.2012, 15:39
    #38096311
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Папин АзиатBAZlST,



У вас один к 35, вродь похоже на правду :)
0.03515625
...
Рейтинг: 0 / 0
28.12.2012, 15:40
    #38096312
Лучшие задачи проекта
Вероятность выпадения некоего числа от 0 до 255 P = 1/256.
Выпадение одного числа никак не связано с выпадением второго. Стало быть события независимые и вероятность их одновременного происхождения равна произведению вероятностей, то есть:
[/quot]
Или нет?
...
Рейтинг: 0 / 0
28.12.2012, 15:41
    #38096316
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Точней стормозил, один к 35 это 3^2/256.
У вас по формуле (3/256)^2, короче неправильно (один к семь тысяч)
...
Рейтинг: 0 / 0
28.12.2012, 15:42
    #38096319
Лучшие задачи проекта
Папин АзиатВероятность выпадения некоего числа от 0 до 255 P = 1/256.
Выпадение одного числа никак не связано с выпадением второго. Стало быть события независимые и вероятность их одновременного происхождения равна произведению вероятностей, то есть:

Или нет?Это в ответ ан вопрос:
авторКакова вероятность что пять из шести чисел совпадут ?
...
Рейтинг: 0 / 0
28.12.2012, 15:45
    #38096324
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Папин АзиатВероятность выпадения некоего числа от 0 до 255 P = 1/256.
Выпадение одного числа никак не связано с выпадением второго. Стало быть события независимые и вероятность их одновременного происхождения равна произведению вероятностей, то есть:

Или нет?[/quot]

Скобки вродь неправильные.
По скобкам 1/256*1/256*1/256*1/256*1/256,
а вам нужно увеличивать вероятность, тоесть 1^5/256, както так
...
Рейтинг: 0 / 0
28.12.2012, 15:46
    #38096327
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
А нет, стормозил. Все верно, вероятность наоборот уменьшается ...
...
Рейтинг: 0 / 0
28.12.2012, 15:49
    #38096334
Лучшие задачи проекта
BAZlST,

вероятность совпадения двух и более независимых исходов не может быть больше вероятности любого из независимых исходов. Стало быть, общая вероятность должна убывать, а не увеличиваться...
...
Рейтинг: 0 / 0
28.12.2012, 15:53
    #38096339
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Папин АзиатBAZlST,

вероятность совпадения двух и более независимых исходов не может быть больше вероятности любого из независимых исходов. Стало быть, общая вероятность должна убывать, а не увеличиваться...

да, дописал свой примерчик, щас поработает несколько минут.
Генерит в цикле 1 млрд билетиков и считает в сколько из них совпало 5 и более чисел :)


Код: c#
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.
Random r = new Random();
            List<int> numbers = new List<int>();
            decimal count = 0;

            for (int j = 0; j < 1000000000; j++)
            {
                int subCount = 0;

                for (uint i = 0; i < 6; i++)
                {
                    int number = r.Next(0, 255);
                    if (numbers.IndexOf(number) >= 0)
                    {
                        subCount++;
                    }

                    numbers.Add(number);             
                }

                if (subCount >= 5)
                    count++;

                numbers.Clear();

            }

            decimal result = count / 100000000;


...
Рейтинг: 0 / 0
28.12.2012, 15:56
    #38096342
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Правда смысла особо нет, 1 к 256^5 примерно ) или 1 к 1024 млрд )
По сути эту ветку алгоритма можно даж не кодить )) вероятность захода в нее стремится к нулю,
если у заказчика через 50 лет алгоритм сбойнет на этом случае, можно списать на ошибку в процессоре )))
...
Рейтинг: 0 / 0
28.12.2012, 15:59
    #38096347
Лучшие задачи проекта
BAZlSTГенерятся 6 случайных байт (чисел от 0 до 255).
Какова вероятность что любые два числа из этих шести будут совпадать между собой ?
Тут подумал, и решил, что формула должна иметь вид:
...
Рейтинг: 0 / 0
28.12.2012, 16:00
    #38096349
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Папин АзиатBAZlSTГенерятся 6 случайных байт (чисел от 0 до 255).
Какова вероятность что любые два числа из этих шести будут совпадать между собой ?
Тут подумал, и решил, что формула должна иметь вид:


да
...
Рейтинг: 0 / 0
28.12.2012, 16:09
    #38096363
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Предлагаю в этом месте закодить пасхальное яйцо

Код: 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.
//fill block
						contentCellType = 6;
						contentCell.Code = lastCode;
						contentCellValueOrOffset = startOffset;

						lastCode++;
						
						for(ushort i = 0; i < countCell; i++)
						{
							uchar idx = indexes[i];
							BlockCell& currBlockCell = pActiveBlock[startOffset + idx];

							uchar count = mapIndexes[idx];
							if(count==1) //one value in block cell
							{
								currBlockCell = blockCells[i];
							}
							else if(count < 5) //create branch cell
							{
								if(currBlockCell.Type == 0) //create branch
								{
									currBlockCell = blockCells[i];
									//....not implemented
								}
								else //fill branch
								{
									currBlockCell = blockCells[i];
									//....not implemented
								}
							}
							else
							{
								printf("ORL'Y shit! WFT?!!!!\nHow did you do it ? You are won a JACKPOT!! Your processor is wrong ... >.< .... bla bla bla ...///// ");
							}
						}

						goto FILL_KEY;
					}
...
Рейтинг: 0 / 0
28.12.2012, 16:11
    #38096366
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Жаль тут многие не поймут юмора, но тот последний элс, вероятность его срабатывания настолько мала .....
что этот месседж скорей всего так и не увидит
Но всеже вероятность есть, если Стебелек будет установлен не менее чем на сто тысячах компьютерах, то тот код прийдется закодить, так как дотошные тестеры всеже найдут багу и тот месседж
...
Рейтинг: 0 / 0
28.12.2012, 16:13
    #38096368
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
BAZlSTYou are won a JACKPOT!Может, всё-таки have?
...
Рейтинг: 0 / 0
28.12.2012, 16:14
    #38096369
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
tanglirBAZlSTYou are won a JACKPOT!Может, всё-таки have?

да похрен, можешь там хоть порноисторию написать, всеравно месседж до пользователя не дойдет :)
...
Рейтинг: 0 / 0
28.12.2012, 16:27
    #38096394
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Шучу, последний элс будет имплементирован, дабы не дать багу не малейшего шанса.
Но попозже.
...
Рейтинг: 0 / 0
29.12.2012, 16:50
    #38097370
Глупый Телевизор
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
BAZlSTГенерятся 6 случайных байт (чисел от 0 до 255).
Какова вероятность что любые два числа из этих шести будут совпадать между собой ?Ты когда-нибудь учил теорию вероятности или мат. логику?
Надо хотя бы уметь формулировать свои "гениальные" задачи.

Условие можно трактовать двумя путями.
1. Совпадение двух любых чисел означает, что какую бы мы не взяли произвольную пару чисел, они будут равны . Соответственно все числа равны между собой. Таких комбинаций 256. Общее число комбинаций 256 6 . Ответ: 1/256 5 .
Иное трактование такое.
2. Существует такая пара чисел которая равна. Здесь уже используется квантор существования, а не всеобщности. Я так понимаю ты подразумевал этот вариант, соответственно условие некорректно. Считается тоже элементарно. Вероятность того, что хотя бы два числа совпадают равна 1 - вероятность того, что все уникальны. То есть: 1 - (256*255*254*253*252*251)/256 6 = ~0,05731
...
Рейтинг: 0 / 0
30.12.2012, 07:00
    #38097620
FVMas-guest
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Если нужна надежная и быстрая СУБД - то надо сразу выбрать FVMas 3.1
...
Рейтинг: 0 / 0
02.01.2013, 14:54
    #38098706
BAZlST
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
Новая задача проекта ( уже посложнее )

Есть четыре числа, типа Integer (32 бита).
Допустим в битовой форме так:

0000 1101 0111 0010 0101 0010 0101 1101
0011 1101 0111 0010 0101 0101 0101 1001
0000 1101 0100 0010 0101 0010 0101 1111
0010 1101 0101 0010 0101 0010 0101 0010

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

Например в этом примере, ответом может быть - позиция 28, количество бит 3

0000 1101 0111 0010 0101 0010 0101 110 1
0011 1101 0111 0010 0101 0101 0101 100 1
0000 1101 0100 0010 0101 0010 0101 111 1
0010 1101 0101 0010 0101 0010 0101 001 0

Это минимальное количество бит, по которым четыре числа не совпадают.
Доп. условия. Ограничений по памяти нет, важна скорость работы алгоритма.
(возможно можно както применить битовые операции)
...
Рейтинг: 0 / 0
02.01.2013, 16:06
    #38098721
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Лучшие задачи проекта
BAZlST
Например в этом примере, ответом может быть - позиция 28, количество бит 3

0000 1101 0111 0010 0101 0010 0101 110 1
0011 1101 0111 0010 0101 0101 0101 100 1
0000 1101 0100 0010 0101 0010 0101 111 1
0010 1101 0101 0010 0101 0010 0101 001 0



А почему не 4 ?
...
Рейтинг: 0 / 0
Форумы / Другие СУБД [игнор отключен] [закрыт для гостей] / Лучшие задачи проекта / 25 сообщений из 191, страница 1 из 8
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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