Алгоритмическая задачка #511140

Всем привет. Есть ряд 1234567 Случайным образом берем одну цифру из этого ряда, например $i1=3 Случайным образом берем частоту повторений ($i2) этой цифры  от 2 до 4 раз. Необходимо сформировать строку длиной 7, чтобы в ней $i1 повторялась $i2 раз, а остальные цифры (из ряда, кроме равной $i1) были в единственном числе и в произвольном порядке.

в чём подвох?

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

вот сейчас у меня решение таково. Формирую последовательность 0 и 1, где 1 столько раз, сколько частота $i2. Затем заменяю 1 на $i1, а 0 заменяю случайным образом из строки $i3, которая равна типа стрзаменить($i1,"",1234567). В процессе замены 0 из строки $i3 последовательно убираю использованные символы по типу стрзаменить(исползованный_символ,"",$i3) Но этот алгоритм меня не устраивает по быстродействию.

из ряда удаляешь i1 и к результирующей строке прибавляешь первые 7-i2 чисел ряда

если $i2=4 тогда остается 3 свободных места. а цифр 6..

если нужно получить любую строку, удовлетворяющую заданным i1 и i2, то всего вариантов значений параметров 21, выбрать для каждого варианта любое подходящее решение и записать в массив, при вычислении просто брать из массива

6. это не производительно. мне нужны минимум интераций. 5. да, верное замечание, конечно, добавляем столько произвольных цифр из ряда, сколько нулей. ну примерно так $strkey=str_replace($i1,'','1234567'); $key=str_replace('1',$i1,$key); while (strpos($key,'0')!==false){ $chr=substr($strkey,rand(0,strlen($strkey)-1),1); $strkey=str_replace($chr,'',$strkey); $pos=strpos($key,'0'); $key=''.substr($key,0,$pos).$chr.substr($key,$pos+1);

1.убираем из строки число $i1 - это которое многократно будет. 2.в строке типа 0011011 единицы меняем на число $i1 (получаем строку $key) 3. пока находится позиция с символом 0 4. выбираем случайное значение из строки $i3 , ну то есть любой один символ 5. убираем из строки $i3 символ, найденный в пункте 4 6. находим первую позицию 0 в строке $key 7. заменяем найденный ноль на значение из пункта 4.

алгоритм формирования строки типа 0011011 элементарен и занимает 3 строчки. но хотелось бы в идеале передаелать алгоритм так, чтобы не было необходимости формировать промежуточную строку типа 0011011, а сразу в одном цикле делать все.

вобщем, нашел решение после небольшого сна :-) видимо мозги немного остыли. function init { //определим номер массива контрольного цвета $i1=mt_rand(1,7); //сформируем строку добавочных символов $strkey=str_replace($i1,'','1234567'); //определим частоту контрольного цвета $i2=mt_rand(2,4); //размножим номер частотой раз $i1=str_pad($i1, $i2 ,$i1); for ($i=$i2;$i<7;$i++){ //определим случайный добавочный символ $chr=substr($strkey,rand(0,strlen($strkey)-1),1); //уберем добавочный символ из строки добавочных символов, во избежание повтора $strkey=str_replace($chr,'',$strkey); //объединим добавочный символ с контрольным номером $i1.=$chr;} //перемешаем случайным образом полученную строку $i1=str_shuffle($i1); return $i1;}

числовое решение: program create_str; uses sysutils; const  dim=7; var  arr1:array[0..dim-1] of byte;  str1:string;  i1:byte;  i2,i,ind1:byte; begin  randomize;  str1:='';  for i:=0 to dim-1 do arr1[i]:=0;  for i:=1 to dim do    begin      ind1:=random(dim);      while (arr1[(ind1 mod dim)]<>0) do inc(ind1);      arr1[(ind1 mod dim)]:=i;    end;  i1:=random(dim)+1;  i2:=random+1;  writeln('i1 = '+IntToStr(i1)+', i2 = '+IntToStr(i2+1));  for i:=1 to i2 do    begin      ind1:=random(dim);      while (arr1[(ind1 mod dim)]=i1) do inc(ind1);      arr1[(ind1 mod dim)]:=i1;    end;  for i:=0 to dim-1 do str1:=str1+IntToStr(arr1[i]);  writeln('result str = '+str1); end.

Виталик чего-то всплыл...

Маньяки от кодинга... 1. добавить к строке 1-3 искомых символа 2. перемешать 3. взять первые 7 символов.

Питон: l = list(s + s[random.randint(0,6)] * random.randint(1,3)) random.shuffle(l) result = ''.join(l)[:7]

11. Хорошее решение, но у мой алгоритм отрабатывает за меньшее число ходов. 12. Все наверное знакомы с капчей? Неудобна? Мне тоже. Решил заменить ее на более продвинутый способ. 13. немного не понял твоих рассуждений. 14. поясни. зачем ты берешь интервал 0-6? по моеум получится бред.

> поясни. зачем ты берешь интервал 0-6? по моеум получится бред Тебе же нужна строка длиной 7? str_shuffle($i1) перемешивает случайным образом все символы в строке, я так понял? Если так, то условие в у тебя неполное. В общем, моё дело предложить, а твоё - разобраться почему не бред.

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

16. мну нужно в итоге получить строку типа 1262275 , то есть цифра 2(например) повторяется случайным образом с заданной частотой 3 (например), а остальные цифры в диапазоне 1-7 исключая 2, в случайном порядке и в единственном числе

Видишь ли, частота у тебя задаётся случайно, а потому алгоритм выдаёт именно то, о чём ты говоришь.

В дальнейшем по коду ты будешь оперировать со значением частоты, или нет?

Более продвинутый способ - это написать "Введите 123 в это поле:". Никакого программирования, и страницу можно не генерить динамически. По эффективности это будет равнозначно с описываемым способом: пока Джо неуловим - будет защищать, как Джо кому-нибудь потребуется - подставлялка правильного ответа делается меньше чем за 5 минут в обоих вариантах.

Да, заметил огрех - есть вероятность, хоть и небольшая, что символ попадётся в единственном экземпляре. Потому предоставляю другой вариант: s = '1234567' i = random.randint(0,6) с = random.randint(2,4) l = list((s[i] * с + (s[:i] + s[i + 1:] if bool(random.randint(0,1)) else s[i + 1:] + s[:i]))[:7]) random.shuffle(l) result = ''.join(l)

21. это фигня. я легко обойду такую защиту, даже спам-бот не буду юзать, просто 3 строчки кода. 20. Логика такая. Я получаю одновременно 0101100 и 1262275. В 1262275  все цифры - это имена массивов. то ест семь массивов всего. В каждом массиве от 3 и выше значений цвета (то есть подмассив). На форму вешается уникалный id, ссылка по которому приведет к 0101100 . То есть с формы получить доступ к 0101100 нереально.  В то же время на форме ест палитра от 1262275,  юзеру предлагается отметить нужные цвета. В пост обработчике я получаю id->0101100 и сравниваю с ответом юзера, если 0101100 и ответ юзера совпадут - значит это не робот

вобщем проще показать , смотрите

22. По моему подходяще. Буду думать и тестировать.

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

модификация первого варианта: s = '1234567' i = random.randint(0,6) c = random.randint(2,4) l = list((s[1:] if i > 0 else s[:-1]) + s[i] * (c - 1)) random.shuffle(l) result = ''.join(l)[:7]

27. Спасибо! Завтра потестирую, счас спать :-)

Дык с описанным методом тоже немного надо. Просто брать цвета и вычислять разницу. И сразу плюшки: 1. Дальтоники отпадают как класс. 2. Правильность ответов будет зависеть от цветопередачи монитора. 3. Мне попались цвета 8B8B83, 0033CC, 9400D3, FF6347, FFEC8B, FFB90F, EEE685. Ну и сколько там правильный ответ? 2, 3 или 4? Последние 3 цвета примерно одинаковы. А может только FFEC8B и EEE685? Или последние 4 цвета примерно одинаковы? В то же время, просто берем разницу между всеми парами цветов и выбираем минимальную: 1. Находим разницы по компонентам (по модулю):       8B8B83 0033CC 9400D3 FF6347 FFEC8B FFB90F EEE685 8B8B83 ------ 8B5849 098B50 74283C 746108 742E74 635B02 0033CC ------ ------ 943307 FF3085 FFB941 FF86BD EEB347 9400D3 ------ ------ ------ 6B638C 6BEC48 6BB9C4 5AE64E FF6347 ------ ------ ------ ------ 008944 005638 11833E FFEC8B ------ ------ ------ ------ ------ 00337C 110606 FFB90F ------ ------ ------ ------ ------ ------ 112D76 2. Определяем разицу (как корень квадратный из суммы квадратов разницы компонент):       8B8B83 0033CC 9400D3 FF6347 FFEC8B FFB90F EEE685 8B8B83 ------ 000179 000160 000136 000151 000170 000134 0033CC ------ ------ 000156 000291 000321 000344 000306 9400D3 ------ ------ ------ 000202 000268 000289 000259 FF6347 ------ ------ ------ ------ 000152 000102 000145 FFEC8B ------ ------ ------ ------ ------ 000134 000019 FFB90F ------ ------ ------ ------ ------ ------ 000127 По минимуму суммы квадратов разниц в компонентах получаем 2 одинаковых цвета FFEC8B и EEE685. Так что, исходя из математики правильный ответ 2 цвета, и строка 0000101.

Таблицы смотреть с моноширинным шрифтом (например, Courier New).

Попробовал еще раз: с цветами 8B8B83 A020F0 FFEC8B 0000CC FF7256 EEB422 8B8878 получил 2 одинаковых цвета: 8B8B83 и 8B8878 (вес 11, следующий по величине вес - 85 у сочетания FF7256 и EEB422).

29."Дык с описанным методом тоже немного надо. Просто брать цвета и вычислять разницу. " запаришься вычислять эту разницу. даже если делать целеноправленно. массив цветов - 7 цветов, количество отттеноков - константа, счас тоже равна 7. Оттенки формируются каждый раз рамдомно. "И сразу плюшки: 1. Дальтоники отпадают как класс. - возможно, хотя не уверен. даже в черно белом варианте цвета будут отличаться. 2. Правильность ответов будет зависеть от цветопередачи монитора." - ну если монитор поддерживает только 256 цветов... давно таких не видел и по моему их найти можно толко в музее. "Последние 3 цвета примерно одинаковы. А может только FFEC8B и EEE685? " - для человеческого глаза разницы в цвете не будет. Я сейчас немного переделал цвета, разницы не обнаружил. Твой ответ в решении неверен (хотя и гамма тогда была "ручная"). Будет время  - попробуй на текущей версии определить математически правильный ответ.

31 - да, здесь ответ верен. Но повторюсь, палитра тогда была грубовата. Сейчас смещение цветов более плавное

dmpl, а вобще да. твоя логика безупречна. но настройкой основных цветов можно эту разницу нивелировать. Как считаешь? Вообще, считаю эту тему преспективной, потому как градиентом можно оперировать почти безгранично, получая цвета из нескольких, путем наложения 2-3 слоев разных цветов с разной прозрачностью. Формировать цветные картики конечно не хотелось бы.

для примера (степень похожести - цвет) 31.0267801362 - #02EBCC 33.6479357182 - #F30ECD 34.0481531822 - #F6DE0C 31.0267801362 - #02EBCC 21.1899418398 - #030EF7 33.9932336665 - #0EFFCC 22.0432860849 - #13F604 здесь 1,4,6 значения равны, но алгоритму так не кажется.

ввел поправку в алгоритм тестирования на восприятие человеком 30*r 59*g 11*b 141.164142099 - #F7122E 215.071453183 - #FFD913 147.734841064 - #FE03CA 147.734841064 - #FE03CA 168.576908816 - #8F9309 156.02745501 - #F309CE 141.300603655 - #F401D2 правильный ответ 3,4,6,7

может я конечно туплю, но по моему даже такая (без оптимизации палитры) схема вполне работает. проверяю так $a=(sqrt(30*$a['r'])+sqrt(59*$a['g'])+sqrt(11*$a['b'])); print '<br/>'.$a. '  -  '.$this->nom[$i];

Вот такая функция делает все, что нужно: #define WEIGHT_THRESHOLD    40 void CheckColorsForSimilarity(long *Colors) {    long Similar[7] = {0, 0, 0, 0, 0, 0, 0};    long W;    long d1, d2, d3;    for (int j = 0; j < 6; j++)    {        for (int k = j + 1; k < 7; k++)        {            d1 = abs(((Colors[j] & 0x00FF0000) >> 16) - ((Colors[k] & 0x00FF0000) >> 16));            d2 = abs(((Colors[j] & 0x0000FF00) >> 8) - ((Colors[k] & 0x0000FF00) >> 8));            d3 = abs(((Colors[j] & 0x000000FF)) - ((Colors[k] & 0x000000FF)));            W = sqrt(d1 * d1 + d2 * d2 + d3 * d3);            if (W <= WEIGHT_THRESHOLD)            {                Similar[j] = 1;                Similar[k] = 1;            }        }    } }

38. Ну не вижу отличия от 37, кроме как abc. Кроме того for (int j = 0; j < 6; j++)

надо наверное for (int j = 0; j < 7; j++) или for (int j = 0; j < 6; ++j) аналогично для второго цикла. if (W <= WEIGHT_THRESHOLD)  - посмотри 36-35 - там как раз один неправильный цвет имеет более близкий коэффициент, чем правильный.

38. эта функция идеально подходит чтобы выбрать товары похожего цвета, но никак не определить разницу между сходными цветами :-)

понимаю, что уже не актуально, но все же: а кол-во своих ходов ты все считал? а в str_replace, substr, str_shuffle и т.д. ходы считал? ради интереса проведи хронометраж формирования тыщ эдак 100 таких строк обоими алгоритмами и посчитай разницу.

Отличие в том, что берется сумма квадратов разности компонент (это, фактически, определение расстояния между точками в 3-мерном пространстве получается). Поскольку берется разница 2 цветов, то автоматом отпадает половина вариантов (различающихся только порядком членов разности, т.е. если мы посчитали j - k, то k - j даст тот же итоговый результат) и 7 вариантов когда j = k. Для получаются следующие веса (расстояния между точками): У правильных цветов разница 0, 23. У неправильных - не меньше 200.

Для получается следующее: У правильных цветов 0, 13, 12, 9. У неправильных - не меньше 132.

актуально и твое замечание справедливо. Ок. Сегодня ночью буду делать тесты. Просто тема быстрого алгоритма чуток отодвинута в свете . . ага , теперь вкурил. Буду думать. Посоветуешь что?

да уж. использую функцию ., провел три десятка тестов, шансов (против функции) никаких. :-(

Нужно что-то легкое для человека и сложное для решения точными методами. Например, вопросы типа "Что изображено на картинке" или "Сколько будет двадцать четыре прибавить шестнадцать". Также может подойти спамерский метод хитрого HTML форматирования типа шрифта первого размера или белого шрифта на белом фоне: машина увидит кучу мусора, а человек - нужный ответ. Также можно динамически менять формат отдаваемой странички, чтобы нельзя было составить правила автоматизированного поиска вопроса и ответа в исходном коде странички. P.S. Раньше распознавание текста было сложной задачей - но затем в этой области были достигнуты значительные успехи, так что пришлось настолько усложнять картинки, что уже и человеку не всегда возможно правильно распознать текст.