Вписанные окружности, программирование? |
Добро пожаловать, гость ( Вход | Регистрация )
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
Вписанные окружности, программирование? |
UNDEFEAT |
20.3.2016, 23:27
Сообщение
#1
|
Avorthoren Группа: Модераторы BrainGames Сообщений: 3 847 Регистрация: 13.11.2010 Из: Kиев Пользователь №: 21 696 |
Есть вот такая задача:
Задача решена, но в решении использовался метод "подбора" решения бинарным поиском. Вопрос в следующем: имеет ли эта задача аналитическое решение в общем случае? Буду признателен, если кто-то поделится своими мыслями по этому поводу. Вот вкратце идея программы: Отрезки проведённые из центров соседних окружностей к точке их касания лежат на одной прямой. Значит из них получается многоугольник с вершинами в центрах окружностей. Пусть Ri - искомые расстояния, а R - радиус вписанной в многоугольник окружности, тогда: R1^2 - r1^2 = R2^2 - r2^2 = ... = Rk^2 - rk^2 = R^2 Пусть величина угла AiOAi+1 равна fi, тогда: f1 + f2 + ... + fk = 2*pi Также: fi = 2 * arctg(ri / R). Итого, бинарным поиском мы можем найти такое R, что сумма углов будет равняться 2*pi. Зная R мы найдём все Ri. Аналитически вроде это решить нельзя... Сообщение было отредактировано UNDEFEAT: 21.3.2016, 2:06 |
alan |
21.3.2016, 2:12
Сообщение
#2
|
zzz... Группа: Администраторы Braingames Сообщений: 13 480 Регистрация: 23.2.2009 Из: Симферополь Пользователь №: 13 114 |
Разве имей задача аналитическое решение она бы могла стать задачей по программированию?
|
UNDEFEAT |
21.3.2016, 2:15
Сообщение
#3
|
Avorthoren Группа: Модераторы BrainGames Сообщений: 3 847 Регистрация: 13.11.2010 Из: Kиев Пользователь №: 21 696 |
Разве имей задача аналитическое решение она бы могла стать задачей по программированию? Естественно! Таких море. Просто даже решив математическую задачу аналитически бывает довольно сложно научить компьютер быстро выдавать ответ. А иногда не решив задачу аналитически в принципе не возможно быстро выдать ответ Сообщение было отредактировано UNDEFEAT: 21.3.2016, 2:19 |
VitalyKolobkov |
22.3.2016, 3:04
Сообщение
#4
|
Участник Группа: Пользователи Braingames Сообщений: 244 Регистрация: 18.2.2011 Пользователь №: 23 171 |
Я что-то вообще не понимаю, в чем проблема. Если нам изначально заданы углы а_1, а_2, а_k, и радиусы r_1, r_2, .. r_k, то из касания окружностей имеем
r_1/tan(a_1/2)=r_2/tan(a_2/2)...=r_k/tan(a_k/2) но тогда R_1=r_1/sin(a_1/2) R_2=r_2/sin(a_2/2) ... R_k=r_k/sin(a_k/2) |
UNDEFEAT |
22.3.2016, 8:40
Сообщение
#5
|
Avorthoren Группа: Модераторы BrainGames Сообщений: 3 847 Регистрация: 13.11.2010 Из: Kиев Пользователь №: 21 696 |
Я что-то вообще не понимаю, в чем проблема. Если нам изначально заданы углы а_1, а_2, а_k, и радиусы r_1, r_2, .. r_k, то из касания окружностей имеем r_1/tan(a_1/2)=r_2/tan(a_2/2)...=r_k/tan(a_k/2) но тогда R_1=r_1/sin(a_1/2) R_2=r_2/sin(a_2/2) ... R_k=r_k/sin(a_k/2) Но ведь углы не заданы. Заданы радиусы окружностей. Если бы был задан хотя бы один угол, вопросов никаких бы не было Сообщение было отредактировано UNDEFEAT: 22.3.2016, 8:42 |
VitalyKolobkov |
25.3.2016, 0:44
Сообщение
#6
|
Участник Группа: Пользователи Braingames Сообщений: 244 Регистрация: 18.2.2011 Пользователь №: 23 171 |
Но ведь углы не заданы. Заданы радиусы окружностей. Если бы был задан хотя бы один угол, вопросов никаких бы не было Тогда такое ощущение, что никак, потому что к выражению f1 + f2 + ... + fk = 2*pi можно применить тангенс, после чего получится алгебраическое уравнение на R порядка k, которое будет зависеть от всех r_k, причем весьма красивым и симметричным образом. Как известно, алгебраическое уравнение степени выше 4 не разрешимо в радикалах в общем случае. Конечно же, коэффициенты этого уравнения будут далеко не произольными числами, но я почти уверен, что это будет эквивалентно общему случаю. |
UNDEFEAT |
26.3.2016, 0:45
Сообщение
#7
|
Avorthoren Группа: Модераторы BrainGames Сообщений: 3 847 Регистрация: 13.11.2010 Из: Kиев Пользователь №: 21 696 |
Тогда такое ощущение, что никак, потому что к выражению f1 + f2 + ... + fk = 2*pi можно применить тангенс, после чего получится алгебраическое уравнение на R порядка k Вообще, там получится уравнение вида: P(x) * Q(x) / R(x) = 0 где х - вектор (r1/R, r2/R, ..., rk/R), P(x) имеет степень k, Q(x) имеет степень k-1, а R(x) имеет степень 2k-1. Так что пока всё совсем не очевидно. |
Упрощённая версия | Сейчас: 25.4.2024, 15:17 |