Даны 5 чисел, все разные.
Надо спомошью макс. 6 сравнений найти среднее.
Напрмер. 1,4,5,3,2 - среднее число 3.
|
Printable Version of Topic
Click here to view this topic in its original format |
| Forums > Флейм > На подумать |
| Posted by: Lexus on 14-06-2005, 22:32 |
|
Задачка Даны 5 чисел, все разные. Надо спомошью макс. 6 сравнений найти среднее. Напрмер. 1,4,5,3,2 - среднее число 3. |
| Posted by: muaddib on 14-06-2005, 22:39 |
| построить red-black tree? |
| Posted by: Michael2000 on 14-06-2005, 22:46 |
| В смысле мозгами думать или можно програмку наваять? |
| Posted by: Lexus on 14-06-2005, 23:30 |
|
мозгами, сам процесс надо
|
| Posted by: admik on 14-06-2005, 23:31 |
|
Lexus ну ты садист это же ДУМАТЬ надо!
|
| Posted by: grif on 14-06-2005, 23:40 |
| а их перед сравнением суммировать можно ? |
| Posted by: Lexus on 14-06-2005, 23:54 |
|
сумирование - это тоже операция - поэтому хоть что лижбы не больше 6 операций. я вот чё думаю, может по принципу quicksort это можно сделать. типа отбалды пишем 5 цифр и потом от среднего меняем слева - большее на право - меньшее. |
| Posted by: muaddib on 15-06-2005, 02:56 |
| по моему задача как-то не корректно поставленна. какие пять чисел? любые? в каком-то периоде (выбило из головы как range перевести)? идут подряд или есть пропуски? ну и так далее. |
| Posted by: Lexus on 15-06-2005, 10:21 |
|
любые пять реальных чисел. в периоде от - бесконч, до +бесконечн. |
| Posted by: muaddib on 15-06-2005, 13:37 |
| какое среднее число в ряду - 1,4,6,3,2 ? |
| Posted by: muaddib on 15-06-2005, 15:12 |
|
вроде есть решение, сейчас попробую сформулировать алгоритм: берем пять чисел - а1, а2, а3, а4, а5. 1) сравниваем а1+а2 и а3+а4, если они равны меняем одно из чисел пары на оставшиеся. предположим, что а1+а2 < a3+a4 2) двумя сравнениями выбераем из меньшей пары большее число и наоборот (из большей пары - меньшее число) предположим, что выбрали а2 и а3 3) еще двумя сравнаниями выбераем среднее между а2, а3 и оставшимся а5. всего пять сравнений. вы меня спросите, а где же шестое? а оно в первом пункте, на случай если пары равны. |
| Posted by: Lexus on 15-06-2005, 15:23 | ||
|
| Posted by: muaddib on 15-06-2005, 15:25 | ||||
|
| Posted by: Lexus on 15-06-2005, 15:40 |
|
пока всё высчитывает, ищу противоречия )
|
| Posted by: muaddib on 15-06-2005, 15:43 |
удачи  и кстати, спасибо за хорошую разминку для мозгов, давай еще 
|
| Posted by: Lexus on 15-06-2005, 15:55 |
|
нашёл ) последнии сравнения например а1, а2, а3 сравниваем а1 с а2, а1>a2 сравниваем а2 с а3, a2<a3 тут могёт быть что а1 или а3 средний. |
| Posted by: Lexus on 15-06-2005, 15:57 |
|
напрмиер в конце числа а1=4 а2=1 а3=3 a1>a2<a3 среднее a3 _________ а1=2 а2=1 а3=3 a1>a2<a3 среднее a1 |
| Posted by: muaddib on 15-06-2005, 16:03 |
|
слышь, а простой сорт сделать нельзя 4 1 3 ....... 4 > 1 1 4 3 ....... 4 > 3 1 3 4 ------------- 2 1 3 ....... 2 > 1 1 2 3 |
| Posted by: Lexus on 15-06-2005, 16:17 |
|
)
|
| Posted by: FiL on 15-06-2005, 22:09 | ||
А у тебя - 1) а1+а2 2) а3+а4 3) (а1+а2) vs (a3+a4) 4) a1 vs a2 5) a3 vs a4 6) (4) vs (5) 7) (5) vs a5 ну в общем... много как-то... К тому-же как двумя сравнениями выбрать среднее из 3-х я тоже пока не понял. |
| Posted by: muaddib on 15-06-2005, 22:28 |
|
FiL алеф - в условии ничего про сложения не говорится, бет - ты не понимаешь как отсортировать три числа двумя сравнениями(?), ну и гимел - что-то я не слышу других предложений или задача не решабельная(?). |
| Posted by: FiL on 16-06-2005, 00:01 | ||
|
| Posted by: grif on 16-06-2005, 00:03 |
muaddib а чего ты с FiLом на иврите заговорил ? 
|
| Posted by: FiL on 16-06-2005, 00:03 | ||
 У меня три сравнение получаются. Двумя я только наибольшее (или наименьшее) нахожу. |
| Posted by: FiL on 16-06-2005, 00:04 | ||
|
| Posted by: muaddib on 16-06-2005, 00:04 |
| это потом Lexus приписал и я не думаю что он это имел в виду, т.к. после моего решения про это даже не упоминул. кроме того, с таким условием задача имхо не решимая. |
| Posted by: FiL on 16-06-2005, 00:09 |
|
muaddib, ну и в целом алгоритм неверный. Берем числа - 1 54 50 52 53 - среднее 52 по твоему алгоритму - (1+54) < (50+52) 54 50 53 - среднее 53. |
| Posted by: muaddib on 16-06-2005, 00:13 | ||||
тебе что надо сделать определить среднее между трех чисел при помощи двух сравнений. задачку с монетами или шариками и двумя взвешевании знаешь? здесь сейм принсипал ("а я еще и на машинке шить умею" ©  ) и вообще в место того чтоб приставать предложили бы что дельное
|
| Posted by: Lexus on 16-06-2005, 00:16 |
|
перевожу точно условие: Как можно высчитать середину 5 случайных чисел. Найдите алгоритм, который максимум с 6 сравнениями находит "середину". Скорее всего тока сравнения учитываются, хотя по идее мы математичесткие операции тоже учитываем. Но так как не написано, не будем учитывать )
|
| Posted by: muaddib on 16-06-2005, 00:21 | ||
рега-рега-рега, минуточку-минуточу, что значит
|
| Posted by: FiL on 16-06-2005, 00:29 | ||
КАК? Не дайте умереть молодому 
|
| Posted by: obaldin on 16-06-2005, 02:30 | ||
На мой взгляд, это условие означает, что а) найти надо медиану б) никакие математические операции не разрешены (в противном случае нужо было бы указать, какие именно операции разрешены) в общем, задача действительно на алгоритм, и, насколько я помню, то ли у квиксорта, то ли у хипсорта был вариант который давал медиану в лиейное время. ....проверил. У квиксорта. Но... у него в худшем случае - O(n2)... Продолжаем копать |
| Posted by: Lexus on 16-06-2005, 08:10 | ||||
|
| Posted by: Lexus on 16-06-2005, 08:13 | ||||
Есть у кого линки на описание доказательст эти сортировок, т.к. доказательств того сколько времени каждый требует. |
| Posted by: obaldin on 16-06-2005, 09:33 |
|
посмотри тут (http://www.ics.uci.edu/~eppstein/161/960130.html, кстати, упоминается, что для 5 элементов достаточно 6 сравнений для нахождения медианы. Еще (http://www.ics.uci.edu/~eppstein/161/960125.html немного (http://en.wikipedia.org/wiki/Selection_algorithm GIYF
|