813 / 421 / 169
Регистрация: 08.02.2013
Сообщений: 711
1

Генерация псевдослучайной последовательности

23.11.2014, 07:41. Показов 1610. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Господа, прошу подкинуть идею. Существует таблица вопросов вида:
C++
1
(id, текст, тип_задания, ...)
Из нее нужно сформировать случайный "вариант", в который входит по одному заданию на каждый тип_задания. И некую уникальную для каждого варианта последовательность символов N - номер варианта, по которому можно однозначно восстановить задания входящие в вариант.

Особенности таковы:
  1. Число строк в таблице ~ 10 000 - 20 000. Число типов заданий сопоставимо с 20.
  2. Номер варианта N должен быть читаемым и максимально удобным в использовании человеком.
  3. Строки в таблице могут как добавляться так и удаляться.
  4. Целостность поля id вне таблицы не гарантируется, оно может пострадать, например, при рефакторинге БД.
  5. Минимизация накладных расходов. Но можно добавить несколько полей в исходную таблицу.
  6. Желательна возможность выдачи "варианта" по его номеру одним SQL запросом.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.11.2014, 07:41
Ответы с готовыми решениями:

Генерация неравномернораспределенной псевдослучайной последовательности
Здравствуйте. Смысл задания в следующем: - Нужно сгенерировать последовательность 0-ей и 1-ц. При...

Оценка псевдослучайной последовательности
Задали семестровую. Не совсем понял суть задачи. Может кто-нибудь подсказать с чего начать?

Генерации псевдослучайной последовательности
Необходимо реализовать программу для генерации псевдослучайной последовательности с помощью...

Алгоритм стеганографии с использованием псевдослучайной последовательности
Здравствуйте . У меня есть код встраивания информации в изображение с использованием...

6
26 / 26 / 17
Регистрация: 08.04.2012
Сообщений: 202
29.11.2014, 01:18 2
Цитата Сообщение от rRczZZ Посмотреть сообщение
Номер варианта N должен быть читаемым и максимально удобным в использовании человеком.
Требование конечно хорошее, но я ошибаюсь или в любом случае оно получиться длиннющее?
1
813 / 421 / 169
Регистрация: 08.02.2013
Сообщений: 711
29.11.2014, 10:58  [ТС] 3
ыфырф1992, на данный момент лучшая идея это склеить порядковые номера(!) заданий в варианте, да строка будет большой, но если ее хранить в системе счисления по основанию 67, получим примерно 50 символов по два на задачу
C++
1
01234567890123456789012345678901234567890123456789
ну такую штуку вроде можно по скайпу передать..

Хорошим способом, наверное, было бы объединить два метода задания. Если вариант формируется в ручную - добавляем префикс и сохраняем id в базе данных. Если кто-то жмет на кнопку "случайный вариант" - использовать алгоритм с псевдослучайным генератором, Seed от генератора отдавать пользователю как id. В обоих случаях длину можно унифицировать, например по 5 символов + 1 на префикс
C++
1
1XXXXX
Для последнего нужно придумать алгоритм случайного выбора из множества без верхней границы. Возможно стоит генерировать довольно большие числа и рассматривать их модули в текущему числу заданий. Нужно подумать.
0
Эксперт функциональных языков программированияЭксперт по математике/физике
4300 / 2091 / 431
Регистрация: 19.07.2009
Сообщений: 3,162
Записей в блоге: 24
29.11.2014, 13:11 4
rRczZZ, чем плохо бинарное кодирование? Например, вариант 1-2-4-6-8 задачи из 8 кодируется числом 11010101 или 171.

зы зачем вам обязательно в один запрос?
1
813 / 421 / 169
Регистрация: 08.02.2013
Сообщений: 711
29.11.2014, 13:27  [ТС] 5
Цитата Сообщение от Mysterious Light Посмотреть сообщение
зы зачем вам обязательно в один запрос?
не помню уже Значит не существенно

Цитата Сообщение от Mysterious Light Посмотреть сообщение
бинарное кодирование
т.е. для хранения варианта из 20000 заданий нужно в худшем случае 20000 бит это в десятичной системе займет https://www.cyberforum.ru/cgi-bin/latex.cgi?\log_{10}(2^{20000})<6021 или в 67: https://www.cyberforum.ru/cgi-bin/latex.cgi?\log_{67}(2^{20000})<3298 символов на строку с id. Довольно много.

*67 это a-zA-Z0-9 и 5 спецсимволов
0
833 / 641 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
29.11.2014, 18:35 6
Лучший ответ Сообщение было отмечено rRczZZ как решение

Решение

Почему бы отдельно таблицу с вариантами не сгенерировать?
Тем более, из-за изменчивости начальной таблицы вряд ли выйдет использовать специфический генератор.
1
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,037
01.12.2014, 11:45 7
Лучший ответ Сообщение было отмечено rRczZZ как решение

Решение

Судя по тому, что таблица с вопросами может быть изменена (да еще и возможен рефакторинг), то скорее всего вам не нужен этот самый генератор псевдослучайных чисел, поскольку если "имя" варианта будет указывать на вопросы, то при удалении вопросов мы получим несуществующий вариант.
Об этом и немного другом под спойлером.
Кликните здесь для просмотра всего текста
Цитата Сообщение от rRczZZ Посмотреть сообщение
т.е. для хранения варианта из 20000 заданий нужно в худшем случае 20000 бит
Вы писали
Цитата Сообщение от rRczZZ Посмотреть сообщение
1.Число строк в таблице ~ 10 000 - 20 000. Число типов заданий сопоставимо с 20.
А значит в одном варианте примерно 20 заданий.
2.Номер варианта N должен быть читаемым и максимально удобным в использовании человеком.
Просто сохраните вариант в БД, и его ID(который является "счетчиком") и будет номером варианта в удобном для чтения виде. Иначе нам потребуется привести к читаемому виду примерно 20*log22000 бит информации, что примерно равно 300 бит. При использовании Base64 это даст название варианта длинной в 50 символов. Что лучше/проще - 50 произвольных символов или одно небольшое число? (ну не собираетесь же вы делать 1050 вариантов) Конечно, в таком случае если вы захотите сообщить кому-то о конкретном варианте, то у вас обоих должна быть одна и та же БД. Для приватного общения можно передавать последовательность номеров вопросов.
3.Строки в таблице могут как добавляться так и удаляться.
До тех пор пока ID имеющихся вопросов не изменяется - этот пункт важен только со стороны удаления. Тогда требуется в таблице с вариантами заменить удаляемый вопрос на другой из того же типа, либо удалить такие варианты (все зависит от того как вы хотите чтобы оно работало). Добавление новых вариантов будет основываться на уже имеющихся данных, с этой точки зрения нам все равно что мы делали с таблицей вопросов ранее.
4.Целостность поля id вне таблицы не гарантируется, оно может пострадать, например, при рефакторинге БД.
Наличие уникальных ID является важной частью для работы с БД, не зря же нормальные формы придумали.
Пока информация внутри БД - поле ID останется всегда, а при рефакторинге (например мы захотим перенумеровать) ID вопросов изменять и в таблице с вопросами, и в таблице с вариантами.
5.Минимизация накладных расходов. Но можно добавить несколько полей в исходную таблицу.
Для вариантов сделать отдельную таблицу, например с полями вида (номер-варианта, ID-вопроса). Займет меньше места и будет быстрее в обработке чем запихивать информацию о вопросах в исходную таблицу.
6.Желательна возможность выдачи "варианта" по его номеру одним SQL запросом.
Согласно п.5 можно будет выполнить вопрос вида
Код
SELECT * 
FROM варианты 
JOIN вопросы 
ON варианты.ид_вопроса = вопросы.ид 
WHERE варианты.ид=номер_варианта
за правильность запроса не уверен.
2
01.12.2014, 11:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.12.2014, 11:45
Помогаю со студенческими работами здесь

Разработка программы Генератора Псевдослучайной Последовательности
Всем привет! Есть задача: написать программу Генератора Псевдослучайной Последовательности (ГПСП)...

Генератор псевдослучайной последовательности с изменяемыми параметрами
как создать генератор псевдослучайной последовательности с изменяемыми параметрами?? помогите плз))

Дополнить приложение кодом формирования псевдослучайной последовательности
Дополнить приложение таким образом, чтобы имелась возможность формирования исходной числовой...

Генераторы псевдослучайной последовательности (Рекурренты в конечном поле )
Нужно сделать генератор псевдослучайной последовательность тип генератора - рекурренты в конечном...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru