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

Генерятся 6 случайных байт (чисел от 0 до 255).
Какова вероятность что любые два числа из этих шести будут совпадать между собой ?
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #38096292
BAZlST,
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #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
Лучшие задачи проекта
    #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
Лучшие задачи проекта
    #38096307
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И сразу по ходу дела, продолжение этойже задачи ( тоже имеет практическое значение ).

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



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

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

Или нет?[/quot]

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

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


да
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #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
Лучшие задачи проекта
    #38096366
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Жаль тут многие не поймут юмора, но тот последний элс, вероятность его срабатывания настолько мала .....
что этот месседж скорей всего так и не увидит
Но всеже вероятность есть, если Стебелек будет установлен не менее чем на сто тысячах компьютерах, то тот код прийдется закодить, так как дотошные тестеры всеже найдут багу и тот месседж
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #38096368
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BAZlSTYou are won a JACKPOT!Может, всё-таки have?
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #38096369
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tanglirBAZlSTYou are won a JACKPOT!Может, всё-таки have?

да похрен, можешь там хоть порноисторию написать, всеравно месседж до пользователя не дойдет :)
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #38096394
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Шучу, последний элс будет имплементирован, дабы не дать багу не малейшего шанса.
Но попозже.
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #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
Лучшие задачи проекта
    #38097620
FVMas-guest
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Если нужна надежная и быстрая СУБД - то надо сразу выбрать FVMas 3.1
...
Рейтинг: 0 / 0
Лучшие задачи проекта
    #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
Лучшие задачи проекта
    #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]