Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 19.04.2004, 19:33   #1
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Задачка по поиску...

Есть массив из 256 значений, из которых два достоверно удовлетворяют некому условию... Узнать какие именно можно лишь подставив данные значения в это условие... требуется найти любое одно из этих двух значений... есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности
(80-90 %)... Или хотя бы убедиться что это невозможно..

Другой дополнительной инфы нету, типа отсортированности для бинарного поиска и т.д.
Reply With Quote
Old 20.04.2004, 05:38   #2
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Чтоб я полностью осознал задачу переспрошу:
известно, что только 2 числа равны друг другу, но не извесно какие? нужно найти это число?
Reply With Quote
Old 20.04.2004, 07:09   #3
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

Quote:
Originally Posted by shatver
есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности
(80-90 %)...
боюсь, что нет. подумаю на досуге над доказательством
Reply With Quote
Old 20.04.2004, 07:27   #4
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by Agregat
Чтоб я полностью осознал задачу переспрошу:
известно, что только 2 числа равны друг другу, но не извесно какие? нужно найти это число?
Нет числа не равны друг другу..просто они удовлетворяют некому условию..проверить же это можно непосредственно подставив число в ..ну скажем в некую формулу... Не хотелось бы делать это 256 раз.. раз чисел два то хотелось бы сократить вдвое кол-во проверек...
Reply With Quote
Old 20.04.2004, 07:37   #5
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

кстати, а что подразумевается под нахождением с точносьтю до 80-90%?
Reply With Quote
Old 20.04.2004, 08:00   #6
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Я тоже склонен думать, что не выйдет. Разве, что можешь попробовать искать с двух сторон одновременно, что при равномерном распределение чисел по массиву может уменьшить кол проверок типа:
PHP Code:
for (int i 0128; ++i)
{
  if (
uslovie(p[i])) return p[i];
  else if (
uslovie(p[255 i])) return p[255 i];

Reply With Quote
Old 20.04.2004, 08:40   #7
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.
Reply With Quote
Old 20.04.2004, 09:11   #8
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default заметка

Quote:
Originally Posted by Agregat
Я тоже склонен думать, что не выйдет. Разве, что можешь попробовать искать с двух сторон одновременно, что при равномерном распределение чисел по массиву может уменьшить кол проверок типа:
PHP Code:
for (int i 0128; ++i)
{
  if (
uslovie(p[i])) return p[i];
  else if (
uslovie(p[255 i])) return p[255 i];

при равномерном распределении не имеет значения, с какого конца ведется поиск.
Я к тому, что в данном случае "с двух концов" не увеличивает скорость поиска - всиравно в сумме делаешь 256 проверок, а не 128.

чисто технически наличие условия "if..else" в цикле сильно замедляет скорость выполнения цикла.
Reply With Quote
Old 20.04.2004, 09:25   #9
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

т.е. исходя из него возможно сгруппировать (и/или упорядочить) данные либо перестроить цикл.
Reply With Quote
Old 20.04.2004, 14:50   #10
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by Aram Hambardzumyan
интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.
75% уже неплохой результат... а как получается такая цифра?
Reply With Quote
Old 20.04.2004, 15:03   #11
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

Quote:
Originally Posted by shatver
75% уже неплохой результат... а как получается такая цифра?
если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%. вероятность того, что в данной половине окажутся оба элемента, равна 25%. если в качестве упоминаемой половины рассмотреть невыбранные 128 элементов, то получается, что мы 'промахиваемся' с вероятностью 25%, т. е. вроятность нахождения хотя бы одного элемента - 75%
Reply With Quote
Old 20.04.2004, 16:42   #12
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

И правда же... совсем мозги заржавели... фактически нужно каждый раз случайным образом выбирать 128 элементов... а если выбрать 192 то и за все 90% переходит... но 192 это много...

Вообщем все ясно.. Всем спасибо..
Reply With Quote
Old 20.04.2004, 18:59   #13
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by Aram Hambardzumyan
если случайным образом отобрать половину элементов

считай, что _случайным_ образом я выбрались первые 128 элелемтов ))) почтому слово случайный -- выкидываем )))

так что я бы предложил другой алгоритм - просто идти с начала и проверять. если попал на ответ - хорошо, выходим из цикла, если нет -идем дальше
в среднем у тебя будет 64 итерации на каждый поиск.
вероятность того, что ты сделаешь 253 проверки -1/(253*254), если я все правильно понимаю )))

если у тебя есть возможность оценивать _хорошесть_(ты имешь какую-то оценочную функцию) ответа - то стоит запоминать позицию и значение этой функции. если ты прошел первые N элементов и не нашел искомого значения -- то тогда просто прерываешь поиск и возвращаешь _хороший_ результат. в принципе это актуально для задач реального времени, когда важно найти результат в заданый промежуток времени и приемлемо, если он будет не совсем точным.
Reply With Quote
Old 20.04.2004, 19:06   #14
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

а 64 итерации откуда?
а слово случайный выкидывать не надо.. потому как условие все время меняется..а значит и пары цифр удовлетворяюшие ему...
Ведь то что условие неизвестно, не означает что оно не подчинено определенной логике...и вполне может сказаться что постоянный выбор первых 128 цифр и есть худший вариант... А выбирая каждый раз случайным образом можно эту логику перебить и иметь в среднем эти 75% ...
Reply With Quote
Old 20.04.2004, 19:47   #15
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by shatver
а 64 итерации откуда?
а слово случайный выкидывать не надо.. потому как условие все время меняется..а значит и пары цифр удовлетворяюшие ему...
Ведь то что условие неизвестно, не означает что оно не подчинено определенной логике...и вполне может сказаться что постоянный выбор первых 128 цифр и есть худший вариант... А выбирая каждый раз случайным образом можно эту логику перебить и иметь в среднем эти 75% ...
так. условие насколько сложное ?? ))) я к тому, что генерация _случайного_ числа и выборка _неповторяющегося_ _случайного_ индекса -- задача довольно трудоемкая )))

64 итерации -- если у тебя ответы распределены равномерно по всем 256 индексам, тогда получается след. вариант:
вероятность того, что мы нашли ответ в N-ной итерации -

1/256 /* первое число может быть в любой из N позиций */ x
(255-N)/255 /* второе число должно быть в позиции больше , чем N */ x
2 /* у нас нет _первого_ и _второго_ числа, у нас есть просто число, которое надо найти, т.е. задача симметрична */

вот .... и при помощи простой арифметики получаем, что сумма таких вот вероятностей для N=0 по N=64 получается около 0.45 .... тааак что-то в формуле не так, но вобщем результат имхо именно такой должен быть - за 64 итерации ты с вероятностью 1/2 находишь искомый ответ.

ндя. я уже даже как-то засомневалсь, в том что написал ))) но все-таки мне кажется, именно так, а не иначе
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 07:24.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.