Какое максимальное число ладей можно расставить в кубе 8×8×8 так, чтобы они не били друг друга?
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #15 : Июль 26, 2011, 14:46:36 � |
|
B2, B4, E5, E7, - неужели не бьют друг-друга Да нет же, проблема возникает в третьем слое. B1 перейдёт в В3 и станет бить В3 из первого слоя.
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
soxjke
Новенький
Offline
Сообщений: 10
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1
|
|
� Ответ #16 : Июль 26, 2011, 15:04:11 � |
|
...которая уже под боем B1 из первого слоя. Идея ясна...думаю дальше тогда.
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #17 : Июль 26, 2011, 15:07:43 � |
|
Для двух максимум, что я пока придумал - 96. Но доказательства максимальности у меня нет. И мне кажется, этот не тот случай, где компьютерным перебором можно решить задачу за разумное время.
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
soxjke
Новенький
Offline
Сообщений: 10
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1
|
|
� Ответ #18 : Июль 26, 2011, 15:11:56 � |
|
Да в том-то и фишка чтобы без компа... Прогу написать не проблема и отработает она за пару минут.
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #19 : Июль 26, 2011, 15:18:59 � |
|
soxjke, да ну? Тупой перебор на современном персональном компьютере потребует порядка 5*10150 лет. С оптимизацией это количество, конечно, сократится... Но для сравнения - моя хорошо оптимизированная программа, искавшая расстановки ферзей на плоской доске 8*8, где каждый бьёт ровно четырёх других, работала порядка суток.
С ладьями, конечно, проще в том смысле, что перестановки плоских "поддосок" не влияют на свойства позиции. И всё же меня терзают смутные сомнения...
|
|
� Последнее редактирование: Июль 26, 2011, 15:21:56 от Sirion �
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
soxjke
Новенький
Offline
Сообщений: 10
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1
|
|
� Ответ #20 : Июль 26, 2011, 15:25:26 � |
|
Ну тогда сейчас попробую.. P.S. Цифра 5*10^150 как получается?
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #21 : Июль 26, 2011, 15:29:13 � |
|
в уме прикинул сейчас посчитал на калькуляторе, вышло 1,4171960013891634005130670765903e+137
количество возможных состояний куба - два в степени количества элементарных кубиков делим на тактовую частоту ядра и на количество секунд в году
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
soxjke
Новенький
Offline
Сообщений: 10
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1
|
|
� Ответ #22 : Июль 26, 2011, 15:32:38 � |
|
Это в том случае, если ядро за такт способно проверить состояние куба =)
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #23 : Июль 26, 2011, 15:35:27 � |
|
Ну, при оценке порядка сложности снизу я обычно делаю подобное допущение. Разница невелика, на самом деле: столько мы не проживём)
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
soxjke
Новенький
Offline
Сообщений: 10
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1
|
|
� Ответ #24 : Июль 26, 2011, 16:39:24 � |
|
Не прокатывает решение в лоб =( Sirion, а как ты располагаешь 76 ладей в кубе, если можно чтобы каждая стояла не более чем под одним боем?
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #25 : Июль 26, 2011, 17:05:32 � |
|
Хм... Это есть у меня в голове, но описывается довольно пространно. Сейчас убегаю. отпишусь ближе к ночи.
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #26 : Август 17, 2011, 04:57:24 � |
|
Sirion, тогда я Вам дам задачку из этой же серии, но задачка - наоборот: Каково минимальное число ладей в кубе К *К * К, чтобы ими простреливались все поля? Трёхмерная ладья ходит в 3-х ортогональных направлениях. По-моему, эта задача будет поинтереснее...
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #27 : Август 17, 2011, 09:12:46 � |
|
забавно я подумаю над этим, когда просплюсь)
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+ +irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+ +iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #28 : Август 18, 2011, 00:47:16 � |
|
при k>2 всегда можно k(k-1) при k=3 точно 6 при k=4 найти меньше 12 не удалось.
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #29 : Август 18, 2011, 02:18:08 � |
|
при k>2 всегда можно k(k-1) при k=3 точно 6 при k=4 найти меньше 12 не удалось.
При К=3, попробуйте 5 ладей... При К=4 попробуйте 8 или докажите, что 8 не хватит. При К >> 2 можно и меньшим числом... => ~0.382*K^2
|
|
� Последнее редактирование: Август 18, 2011, 02:48:29 от buka �
|
Записан
|
|
|
|
|