Lexus
@ 14-06-2005, 22:32
Задачка :)
Даны 5 чисел, все разные.
Надо спомошью макс. 6 сравнений найти среднее.
Напрмер. 1,4,5,3,2 - среднее число 3.
muaddib
@ 14-06-2005, 22:39
построить red-black tree?
Michael2000
@ 14-06-2005, 22:46
В смысле мозгами думать или можно програмку наваять?
Lexus
@ 14-06-2005, 23:30
мозгами, сам процесс надо :)
admik
@ 14-06-2005, 23:31
Lexus ну ты садист :) это же ДУМАТЬ надо!
а их перед сравнением суммировать можно ?
Lexus
@ 14-06-2005, 23:54
сумирование - это тоже операция - поэтому хоть что лижбы не больше 6 операций.
я вот чё думаю, может по принципу quicksort это можно сделать.
типа отбалды пишем 5 цифр и потом от среднего меняем слева - большее на право - меньшее.
muaddib
@ 15-06-2005, 02:56
по моему задача как-то не корректно поставленна. какие пять чисел? любые? в каком-то периоде (выбило из головы как range перевести)? идут подряд или есть пропуски? ну и так далее.
Lexus
@ 15-06-2005, 10:21
любые пять реальных чисел.
в периоде от - бесконч, до +бесконечн.
muaddib
@ 15-06-2005, 13:37
какое среднее число в ряду - 1,4,6,3,2 ?
muaddib
@ 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.
всего пять сравнений. вы меня спросите, а где же шестое? а оно в первом пункте, на случай если пары равны.
Lexus
@ 15-06-2005, 15:23
| QUOTE (muaddib @ 15-06-2005, 12:37) |
| какое среднее число в ряду - 1,4,6,3,2 ? |
3
muaddib
@ 15-06-2005, 15:25
| QUOTE (Lexus @ 15-06-2005, 12:23) |
| QUOTE (muaddib @ 15-06-2005, 12:37) | | какое среднее число в ряду - 1,4,6,3,2 ? |
3 |
это я уже понял, как решение-то?
Lexus
@ 15-06-2005, 15:40
пока всё высчитывает, ищу противоречия :))
muaddib
@ 15-06-2005, 15:43
удачи :hi:
и кстати, спасибо за хорошую разминку для мозгов, давай еще :punk:
Lexus
@ 15-06-2005, 15:55
нашёл :))
последнии сравнения
например а1, а2, а3
сравниваем а1 с а2, а1>a2
сравниваем а2 с а3, a2<a3
тут могёт быть что а1 или а3 средний.
Lexus
@ 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
muaddib
@ 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
Lexus
@ 15-06-2005, 16:17
:))
| QUOTE (muaddib @ 15-06-2005, 09:12) |
вроде есть решение, сейчас попробую сформулировать алгоритм:
берем пять чисел - а1, а2, а3, а4, а5.
1) сравниваем а1+а2 и а3+а4, если они равны меняем одно из чисел пары на оставшиеся.
предположим, что а1+а2 < a3+a4
2) двумя сравнениями выбераем из меньшей пары большее число и наоборот (из большей пары - меньшее число)
предположим, что выбрали а2 и а3
3) еще двумя сравнаниями выбераем среднее между а2, а3 и оставшимся а5.
всего пять сравнений. вы меня спросите, а где же шестое? а оно в первом пункте, на случай если пары равны. |
Просили 6 операций (сложение есть операция).
А у тебя -
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-х я тоже пока не понял.
muaddib
@ 15-06-2005, 22:28
FiL алеф - в условии ничего про сложения не говорится, бет - ты не понимаешь как отсортировать три числа двумя сравнениями(?), ну и гимел - что-то я не слышу других предложений или задача не решабельная(?).
| QUOTE (Lexus @ 14-06-2005, 17:54) |
сумирование - это тоже операция - поэтому хоть что лижбы не больше 6 операций.
|
нихрена себе не написано...
muaddib а чего ты с FiLом на иврите заговорил ? :wink:
| QUOTE (muaddib @ 15-06-2005, 16:28) |
| бет - ты не понимаешь как отсортировать три числа двумя сравнениями(?) |
нет, не понимаю :(
У меня три сравнение получаются. Двумя я только наибольшее (или наименьшее) нахожу.
| QUOTE (grif @ 15-06-2005, 18:03) |
| muaddib а чего ты с FiLом на иврите заговорил ? :wink: |
алеф-бет-гимел - это еще не "на иврите заговорил". А остальное вроде как по-русски.
muaddib
@ 16-06-2005, 00:04
это потом Lexus приписал и я не думаю что он это имел в виду, т.к. после моего решения про это даже не упоминул. кроме того, с таким условием задача имхо не решимая.
muaddib,
ну и в целом алгоритм неверный.
Берем числа - 1 54 50 52 53 - среднее 52
по твоему алгоритму -
(1+54) < (50+52)
54 50 53 - среднее 53.
muaddib
@ 16-06-2005, 00:13
| QUOTE (FiL @ 15-06-2005, 21:03) |
| QUOTE (muaddib @ 15-06-2005, 16:28) | | бет - ты не понимаешь как отсортировать три числа двумя сравнениями(?) |
нет, не понимаю :( У меня три сравнение получаются. Двумя я только наибольшее (или наименьшее) нахожу. |
тебе что надо сделать определить среднее между трех чисел при помощи двух сравнений. задачку с монетами или шариками и двумя взвешевании знаешь? здесь сейм принсипал ("а я еще и на машинке шить умею" © :shuffle:) и вообще в место того чтоб приставать предложили бы что дельное
Lexus
@ 16-06-2005, 00:16
перевожу точно условие:
Как можно высчитать середину 5 случайных чисел.
Найдите алгоритм, который максимум с 6 сравнениями находит "середину".
Скорее всего тока сравнения учитываются, хотя по идее мы математичесткие операции тоже учитываем. Но так как не написано, не будем учитывать :))
muaddib
@ 16-06-2005, 00:21
рега-рега-рега, минуточку-минуточу, что значит
| QUOTE |
| середину 5 случайных чисел |
? это median или mean? можно подробнее определение дать этому понятию.
| QUOTE (muaddib @ 15-06-2005, 18:13) |
| тебе что надо сделать определить среднее между трех чисел при помощи двух сравнений. задачку с монетами или шариками и двумя взвешевании знаешь? здесь сейм принсипал ("а я еще и на машинке шить умею" © :shuffle:) и вообще в место того чтоб приставать предложили бы что дельное |
задачку про нахождение среднего не знаю. найти среднее не могу. Туплю.
КАК? Не дайте умереть молодому :help:
obaldin
@ 16-06-2005, 02:30
| QUOTE (Lexus @ 15-06-2005, 23:16) |
Как можно высчитать середину 5 случайных чисел. Найдите алгоритм, который максимум с 6 сравнениями находит "середину".
|
На мой взгляд, это условие означает, что
а) найти надо медиану
б) никакие математические операции не разрешены (в противном случае нужо было бы указать, какие именно операции разрешены)
в общем, задача действительно на алгоритм, и, насколько я помню, то ли у квиксорта, то ли у хипсорта был вариант который давал медиану в лиейное время.
....проверил. У квиксорта. Но... у него в худшем случае - O(n2)... Продолжаем копать :)
Lexus
@ 16-06-2005, 08:10
| QUOTE (muaddib @ 15-06-2005, 23:21) |
рега-рега-рега, минуточку-минуточу, что значит | QUOTE | | середину 5 случайных чисел |
? это median или mean? можно подробнее определение дать этому понятию. |
median
Lexus
@ 16-06-2005, 08:13
| QUOTE (obaldin @ 16-06-2005, 01:30) |
| QUOTE (Lexus @ 15-06-2005, 23:16) | Как можно высчитать середину 5 случайных чисел. Найдите алгоритм, который максимум с 6 сравнениями находит "середину".
|
На мой взгляд, это условие означает, что
а) найти надо медиану
б) никакие математические операции не разрешены (в противном случае нужо было бы указать, какие именно операции разрешены)
в общем, задача действительно на алгоритм, и, насколько я помню, то ли у квиксорта, то ли у хипсорта был вариант который давал медиану в лиейное время.
<!--DoHtmlBegin-->
....проверил. У квиксорта. Но... у него в худшем случае - O(n<sup>2</sup>)... Продолжаем копать :)
<!--DoHtmlEnd-->
|
вот я тож в хипе и квик сорте рою, так как тема как раз эта у нас сейчас.
Есть у кого линки на описание доказательст эти сортировок, т.к. доказательств того сколько времени каждый требует.
obaldin
@ 16-06-2005, 09:33
посмотри
тут, кстати, упоминается, что для 5 элементов достаточно 6 сравнений для нахождения медианы.
ЕщенемногоGIYF :)