Имя: Пароль:
IT
 
Задача по информатике
0 raipo
 
20.09.11
16:01
Вот задача по информатике которая мне нравится

Двое играют в игру: один загадывает число от 1 до 1000 а второй задает ему вопросы, на которые первый отвечает "да" или "нет". За десять вопросов типа "больше 500?", "меньше 750?" можно наверняка угадать задуманное число.
Можно ли написать эти 10 вопросов ЗАРАНЕЕ, не зная ответов на 1-й 2-й и т.д.
и по ответам сразу на 10 вопросов назвать число?
1 Grusswelle
 
20.09.11
16:02
Можно. Дели на два и спрашивай, больше или меньше. Даже с небольшим запасом будет (до 1024 можно).
2 Ненавижу 1С
 
гуру
20.09.11
16:04
(0) более точную формулировку разрешаемых вопросов можно?
3 Ненавижу 1С
 
гуру
20.09.11
16:05
(1) вот мне кажется нельзя, если задача про тот класс вопросов, что я думаю
4 raipo
 
20.09.11
16:05
Еще раз условие:
Вопросы пишутся на бумажке ЗАРАНЕЕ и ничего больше НЕ СПРАШИВАЕТСЯ
5 Ненавижу 1С
 
гуру
20.09.11
16:06
(4) еще раз "более точную формулировку разрешаемых вопросов можно?"
6 raipo
 
20.09.11
16:06
Удивлен, задача известная
7 ЛЮС
 
20.09.11
16:06
Заранее пишу вопрос
Ответ1 = Вопрос("Больше 500?")
Ответ2 = ?(Ответ1, Вопрос("Больше 750"), Вопрос("Больше 250"))
и т.д.
можно записать на бумажке :)
8 Волесвет
 
20.09.11
16:07
если к вашему числу прибавить 0 то какое число получится?
.....
ОТВЕТ ....!!!
9 andrewks
 
20.09.11
16:07
(1) не взлетит
10 Ненавижу 1С
 
гуру
20.09.11
16:08
(6) чукча писатель онли?
11 raipo
 
20.09.11
16:08
(5) Любой вопрос, на который первый ответит "да" или "нет". Например в английском (помню) вопросы "Неправда ли, что..."
12 Живой Ископаемый
 
20.09.11
16:09
2(7) можно посмотреть код третьей итерации?
13 Kassius
 
20.09.11
16:09
(1) только делить надо на три.
14 andrewks
 
20.09.11
16:10
(12) лучше 10-й :)
15 sergeante
 
20.09.11
16:10
(0) нельзя
16 Ненавижу 1С
 
гуру
20.09.11
16:11
(11) тогда да, можно, вопросы будут такими:

N-й вопрос: в двоичной записи числа в N-м разряде стоит 0?
N=1..10
17 raipo
 
20.09.11
16:11
(7) очень близко по идее, но не понял формулировку
(8) на этот вопрос ответы да или нет не имеют смысла
(10) не совсем понял вопрос, наверно чукча - математик
18 Wobland
 
20.09.11
16:12
(16) а в какой системе числа загадываются? ;)
19 raipo
 
20.09.11
16:12
(16) да, верно
20 Волесвет
 
20.09.11
16:12
ааа... короче все сводится типо к этому:
сколько разрядов в числе?
делится ли на 2? и т.д
21 Ненавижу 1С
 
гуру
20.09.11
16:12
(18) значение числа не зависит от его записи ))
22 Живой Ископаемый
 
20.09.11
16:13
2(16) так этож читерство! :)
23 1Сергей
 
20.09.11
16:13
Первый бит в числе 0? да/нет
Второй бит в числе 0? да/нет
...
24 Wobland
 
20.09.11
16:13
(21) 1000 в 16й записи записывается 13ю двоичными разрядами
25 1Сергей
 
20.09.11
16:14
(24) чо?
26 Grusswelle
 
20.09.11
16:14
(19) Это и будет равносильно делению на два. :-)))
27 Живой Ископаемый
 
20.09.11
16:14
типа игры в ПолеЧудес только вместо буквы цифры 0 и 1 и позиции... :) такая быдломатематическая игра...
28 1Сергей
 
20.09.11
16:14
2^10 = 1024 есичо
29 Ненавижу 1С
 
гуру
20.09.11
16:14
(24) ну он же не сказал, что не десятичная, значит по дефолту
короче - не придирайся ))
30 Волесвет
 
20.09.11
16:14
мля ...ответы да или нет..((
31 Ненавижу 1С
 
гуру
20.09.11
16:15
(30) чем ты недоволен?
32 Wobland
 
20.09.11
16:15
(29) я смайлики ставлю, не придираюсь
(25) 1000(16)=1000000000000(2)
33 andrewks
 
20.09.11
16:16
вопросов типа "больше 500?", "меньше 750?"
...
N-й вопрос: в двоичной записи числа в N-м разряде стоит 0?
N=1..10

охренеть.

совсем "типа"
34 Волесвет
 
20.09.11
16:16
(31) старая игра угадать личность...
35 Ненавижу 1С
 
гуру
20.09.11
16:17
(33) да я сам офигел, уточнял же
36 Shurjk
 
20.09.11
16:17
(0) О кто то под старость лет открыл для себя двойчный поиск.
37 Ненавижу 1С
 
гуру
20.09.11
16:22
Давайте слегка усложним.
Условия те же, но на ровно один вопрос будет дан ложный ответ. Вопрос: сколько вопросов достаточно заранее написать, чтобы найти число в диапазоне от 1 до 1024?
38 sda553
 
20.09.11
16:23
Есть гораздо более сложная вариация задачи троичного поиска. (в троичной системе исчисления)

Есть 12 монет, все одинаковы по весу кроме одной. Как за три взвешивания выделить монету отличающуюся по весу. (естественно неизвестно более тяжелая оставшаяся монета или нет)
39 Grusswelle
 
20.09.11
16:24
(32) Ну приплыли... :-((
40 GANR
 
20.09.11
16:27
За 10 вопросов типа: "первая половина не исключенного отрезка или вторая" (0 или 1) можно узнать, какое это число. Ну... грубо говоря это запись десятичного числа в двоичном формате - вот и всё.
41 Shurjk
 
20.09.11
16:27
(38) Тоже старая задача.
42 aleks-id
 
20.09.11
16:27
(32) 1000(10) = 1111101000(2)
43 Shurjk
 
20.09.11
16:28
+(38) И она тоже не в троичной системе, там просто вместо двух промежутков береться изначально три а потом то же деление.
44 Живой Ископаемый
 
20.09.11
16:29
2(42,39) он про то, что в (0) не сказано в какой системе исчисления задано первоначальное число 1000. Если оно задано в  16-ричной, то не получится за 10 вопросов
45 aleks-id
 
20.09.11
16:31
(44) вообще то 16-ричные значения обычно пишут 1000h
46 sda553
 
20.09.11
16:31
(41) Не совсем. у этой старой задачи все обычно приводят какой нибудь из вариантов ответов, но не могут написать решение. Это обычно говорит о том, что скорее всего когда то им ответ сказали или подсмотрели.
47 sda553
 
20.09.11
16:33
(43) почему не троичная. Сравнения(взвешивания) могут нести информацию >,<, или = что и дает искомую информацию в троичной системе исчисления
48 mr_K
 
20.09.11
16:42
(37) 14 вопросов, если верить wiki:Код_Хэмминга