Есть некая комбинация комбинация знаков - пусть будет длина 5.
Как быстрее её подобрать?
Перебрать все возможные комбинации, или генерировать случайные значения?

Что перебором, что рандомом, вероятность угадывания числа на N-ом шаге одинаковая. Но рандом организовать сложнее чем перебор.
Вероятность того что загадали число 9 и рандомом его угадать будет быстрее компенсируется тем что есть такая же вероятность что будет загадано число 1 и перебором будет быстрее.

(0) рандом быстрей, если мы "запоминаем" предыдущие значения.

(35)+ если основное время уходит не на получение цифры, а на проверку ее в качестве результата

(32) нельзя заставить рандом исключить какой-то значение. Тебе придётся генерить рандомное число, потом сравнивать его со списком уже проверенных чисел, а потом сравнивать с основным. И зачем?

(37) Спортивнй интерес. Разве нет?

(37) в этом есть смысл.

Количество опытов: 10 000 рандом:98 469 перебор:54 612
Количество опытов: 100 000 рандом:975 523 перебор:549 340

(38) (39) замедлит. Проще просто сравнивать с искомым и идти дальше. Так будет быстрее

Это тест рандома по методу балабаса - без запоминания ранее проверенных значений.

(42) Почему же без запоминания?

(41) см(36)

средствами 1С можно сделать так:
создать список со всем возможными значениями, потом рандомно выбирать значение из списка, проверять на соответствие и удалять из списка

(45) + но, это опять же будет дольше

(43) Потому что запоминание убьет производительность вхлам.

(0) А тебе не приходил в голову вопрос "Почему все bruteforce используют последовательный перебор (по словарю или без словаря)?" а уж в bruteforce как раз самое критичное это скорость подбора

Количество опытов: 1 000 000 рандом:9 690 835 перебор:5 500 031

Где то явно косяк с генерацией случайных числе у 1С.

дихотомию таки попробуйте

хотя туплю.. все нормально с генерацией.

А чего вы только числа берете? А буквы, латиница, кирилица, верхний/нижний регистр, спецсимволы. Это нихера не 99 999!!!

(49) а длина числа какая была?

(52) это не суть важно

(50) Блин расскажи нам алгоритм дихотомии. Я вот со своей подготовкой в области математики не знаю  способа его применения тут.

(50) по какому признаку блин поможет дихотомия ? если нам известно только то что мы не попали, и неизвестно в меньшую или в большую сторону не попали

(55) начинать проверку со значений располагающихся на 50% поддиапазона.

(56) речь идёт о половинном делении, а не о поиске половинным делением

(57) дальше говори :) *приготовил попкорн*

(57) То есть ты предлагаешь сверять в таком порядке 5,3,1,0,2,4,8,7,6,9 ? (обход дерева вглубь)

(59) 50%, 25%, 75%...

(61) смысл то в чем ? в том что вероятность выпадения экстремума типа меньше ?

(62) да

так это бред при нормальном количестве экспериментов

(37) ну ты как бы повторил мою мысль в (32) что в "рандоме" все так же сводится к перебору.

Как в том анеке либо один перебор, но большой. Либо рандом и маленькие переборы, но много раз.

(61) Подробнее. Есть число в диапазоне 0..9. В каком порядке сверять? Мне не лень накодить и проверить.

вероятность выпадения цифры 5 равновелика вероятности выпадения 0

(64) о свойствах значений нам ничего не сказали. что рендом бред ещё никто не сказал, хоть и намекают.

(0) Иди на мехмат, ща вспомню на каком курсе у нас был тервер .. на третьем вроде

итак эксперимент показал, что рандом нашел число 9892 за
4166 итераций

число само выбиралось рандомно из от 0 до 99999

помница на 7.7 делал игру быки и коровы. Там 1С сама загадывала число и пыталась отгадать число задуманное пользователем. Отгадывала она не тупым брутфорсом и не рандомом, а методом исключения. Но, там задача другая

(70) Дружище смотри выше результаты для 1 миллиона экспериментов.

(70) с исключением проверенных?

(66) 5, 3, 8, 1, 4, 7, 9, 0, 2, 6 , если нигде не ошибся

(70) ага, а число 107 перебор найдет за 108 шагов и что ?

(73) да

private var cH:int =  0;
public function Check(f1:int, f2:int):Boolean
{
   //trace(" fintNum " + f1 + " " + " fintNum " + f2);
   cH++;
   if (f1 == f2) return true;
   return false;
}
var FNum:Array = new Array();
public function GetRandom():int
{
   var lastNum:int = -1;
   lastNum = Math.round(Math.random() * 99999);
   var _if:Boolean = false;
   for (var i:int = 0; i < FNum.length; i++)
       if (FNum[i] == lastNum)
       {
           _if = true;
           break;
       }
   if(!_if)
       FNum.push(lastNum);
   else
       return -1;
   return lastNum
}
public function Main():void
{
   var fintNum:int = Math.round(Math.random() * 99999);
   var lastNum:int = -1;
   while (true)
   {
       while (true)
       {
           lastNum = GetRandom();
           if (lastNum!= -1) break;
       }
       if(Check(lastNum, fintNum)) break;
   }
   trace("cH " + cH + " fintNum " + fintNum + " " + " fintNum " + fintNum);
}

При 1000 разных значений [0..1000]
Перебор: 489 686
Рандом: 1 011 571

Количество опытов: 100 000 рандом:965 238 перебор:550 964 ебанутыйспособ:550 497

(78) Что за 3 способ такой?

Как видим вышеупомянутый HeroShima способ аналогичен перебору

(79) метод HeroShima

итак эксперимент_2 показал, что рандом нашел число 18148 за
79428 итераций

2 эксперимента провалились, ибо процесс выполнялся больше 15 секунд, а данная платформа умирает, если задумывается больше 15(типа я зависла) (эт когда 25000 проверок превышает)

короче ну вас работать надо

(80) при нормальном количестве экспериментов все три способа (если конечно рандом с исключением проверенных) дадут равное количество итераций, но! что рандом что "метод хирошимы" будут выполнятся дольше по времени

что дает однозначный ответ: перебор без вариантов

остальное онанизм и дебилизм

Вот вам старая баянистая задачка, но зато поинтереснее:
" Разборчивая невеста
В 1962 году Гарднер сформулировал очень интересную задачу, популярность которой сейчас достигла пика. Это задача о разборчивой невесте. Итак, к невесте (принцессе некоторого царства) явилось, допустим, 1000 женихов. Она может одновременно общаться только с одним женихом и по окончании беседы обязана дать ему согласие или отказ. Какую стратегию необходимо принять принцессе, чтобы с наибольшей вероятности выбрать наиболее достойного?"

http://stastu.livejournal.com/4140.html

(35) >> рандом быстрей, если мы "запоминаем" предыдущие значения.

не быстрее.

(84) (85) (86) Так точно.

(87) Я думаю первым 500 нужно отказать, и согласиться на любого который лучше самого лучшего из предыдущих. Вероятность успеха 50%

(87) Дружище, если некоторые не понимают основ тервера, оценки трудоемкости алгоритмов и методов оптимизации - что говорить о задачах Гарднера - которые как правило небанальны.

(91) да ладно, мы же на форуме 1Сников ... тут это норма :)

(84) накладные расходы у "моего" метода и метода перебора сопоставимы и гораздо меньше чем проверка рендома по таблицам.

(93) В коде метод перебора занимает 3 строчки а твой 30

(93) Это если кодировать для 0..9 Если же реализовывать универсальный метод - то большие вычислительные затраты на деление пополам.

(87) Почему-то в задаче правильный ответ странный... Почему "е" ?? Так вероятность выбора лучшего меньше чем в моем способе!

(93) с чего бы вдруг ... i++ работает быстрее чем даже i=i+1 не то что операции деления и прочие

(91) сама по себе она не так страшна как ее интерпритации.

" Математически это задача выбора наилучшего объекта без возможности возвращения.
Задача была решена быстро и сейчас ее предлагают школьникам в популярной математической литературе.
...
Сухая математическая формулировка многим не понравилась и задачу попытались приблизить к жизни. Стали решать менее формальные задачи. Как выбрать лучшего или одного из лучших. Эта веселая задача, которая ставит в тупик простого человека, породила новое направление в математике – теории рекордов, а так же теорию оптимизации случайных процессов."

Короче, метод перебора лучший.

(97) >> ...  i++ работает быстрее чем даже i=i+1 ...

Выдыхай

(67) спасибо, с ассемблером знаком
(100) с отключенной оптимизацией быстрее)

(100) схерали ? :)

*(101) (97), конечно же

(98) Вообще нашим студентам и школьникам не хватает таких задач. Нихрена не умеют решать более менее практические вещи, где требуется построение модели.

ну кстати забыл, еще быстрее будет преинкремент ++i

Объясните по задаче. Схера "е" ??????

А, всё. Сам допер.

(90) ну вообщем то ответ правильный. Только оптимальный размер первой выборки математики вычислили менее чем 50%, но это уже действительно уровень не для простых людей.

(107) рассказывай теперь нам :-)

так как на счёт от центра к периферии?)

+(110) при маловероятных крайностях

(110) Я выложил результаты выше

(112) там был последовательный перебор от 50% декрементом к 0% и инкрементом к 100%?

//класический обход дерева

анализируемоеЧисло = 3244353454
Разрядность = ЧислоЗнаков(анализируемоеЧисло)
правило = массив(6,5,7,0,3,2,1,4,9,8)
КусокПравила = массив()

ПолучитьРекурсивно (анализируемоеЧисло, КусокПравила, Разрядность, Правило)

Процедура ПолучитьРекурсивно (анализируемоеЧисло, КусокПравила, Разрядность, Правило)
для каждого текЗнак из правило цикл
 мКусокПравила = КусокПравила.Скопировать()
 мКусокПравила.Добавить(текЗнак)
 Если мКусокПравила.Количество() = Разрядность Тогда
    ОбработатьПроверку(мКусокПравила)
 Иначе
    ПолучитьРекурсивно (анализируемоеЧисло, КусокПравила, Разрядность, Правило)
 КонецЕсли

конецЦикла


конецПроцедуры

(110) при равновероятных вариантах и достаточно количестве экспериментов нету разницы никакой, сколько говорить то можно ... но затраты выше при любом методе чем при переборе

и еще раз повторюсь посмотрите любой алгоритм брутфорса

(115) я не говорю о равновероятных вариантах

(113) писал ранее
Количество опытов: 100 000 рандом:965 238 перебор:550 964 ебанутыйспособ:550 497

(114)+ писал от балды, ошибко наверно море, но сам принцеп думаю ясен

(117) Если речь идет о нормальном распределении то задача СОВСЕМ другая.

(116) в криптографии крайние значения маловероятны
(118) ебанутым был назван метод через "пополам", который был предложен в самом начале ветки не мной

10 числе от 0 до 1000

1 из 29

Перебор: 4 918
Рандом: 4 835

(114)+
достоинства что для каждого вычисления можно генерить массив правила свой, например на основании какой-то статистики (например 0 и 9 поставить в конец ряда)

(121) хех, какова вероятность использования идиотами паролей типа 111 или 123

(124) 80%

ахаха

(125) если не больше :)

Вот процедура генерации не повторяющихся случайных чисел:

Процедура Рандом()
   хре = (хре * Л + Й) % Ж;
   Возврат (хре / Ж);
КонецПроцедуры

Л, Й и Ж взаимно простые числа.
Генерируемые числа не повторяются Ж раз подряд.

Нужно изначально инициализировать переменную хре, например:
хре = 0;

ага, давайте ещё присовокупим статистику по кол-ву идиотов на душу населения)

(128) А где  Л и Й и Ж указать?

(130) Вместо  Л и Й и Ж можешь цифрами впечатать. Или еще где-нибудь.

где то видел алгоритм "ход конем", то же типа случайный...

Например для периода 65536:Процедура Рандом()
   хре = (хре * 25173 + 13849) % 65536;
   Возврат (хре / 65536);
КонецПроцедуры