|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
23.10.2008, 12:27 | #1 |
Новичок
Джуниор
Регистрация: 18.09.2008
Сообщений: 2
|
народ, помогите пож решить олимпиадную задачку
Дан шар радиуса R, центр которого находится в центре координат. определить количество точек с целочисленными координатами, находящихся на его поверхности.
(програма должна: запросить целое число R (0<R<=1000)-радиус шара. Подсчитать и сообщить число точек с целочисленными координатами, лежащих на поверхности шара.) Пример 1: Если R=13, то К=78 Пример 2: если R=16, К=6 Примечание. Ограничение времени на прохождение одного теста - 20 секунд. |
23.10.2008, 14:12 | #2 |
Старожил
Регистрация: 26.04.2008
Сообщений: 2,645
|
Идея такая, проводим сечения сферы параллельно оси Z, получаем 2R+1 окружность (R - целое), В каждой окружности проводим хорды параллельные оси Y, для каждой хорды вычисляем значение X. Проверяем если X - целое, то считаем точку (вернее 2 симметричных точки, исключая совпадающие).
Вот накидал пример. НО!!! Мы то люди если сложим 1/3 и 1/3 и 1/3 получим 1, а компьютер погрешность может дать маленькую. Вот и тут также. Даже если тип переменной менять (double или single), то всё равно есть погрешность. Вобщем вот идея, а програмно доработать надобны будет Код:
Последний раз редактировалось eoln; 23.10.2008 в 14:19. |
23.10.2008, 14:26 | #3 |
Ну и что? :)
Форумчанин
Регистрация: 20.10.2008
Сообщений: 129
|
хм.... а не слишком ли будет долго работать? чилса ведь не маленькие... хотя это решение "в лоб" и является верным... я думаю все же считать только в 1/8 шара (в силу симметрии) а потом значение *8.
а вот как бы от перебора избавится это надо думать
Учиться, учиться и еще раз учиться
|
23.10.2008, 14:36 | #4 |
Старожил
Регистрация: 26.04.2008
Сообщений: 2,645
|
Ламер_001, а ты код скопируй и проверь что с максимально возможными данными (без вывода на экран - это я от себя добавил) время менее полсекунды!!! А про 1/8 я уже упомянул. Как Вы от перебора-то избавитесь? Не полезное у вас сообщение получается...
|
23.10.2008, 15:05 | #5 |
Ну и что? :)
Форумчанин
Регистрация: 20.10.2008
Сообщений: 129
|
ну раз укладывается, то Вы молодец, только вот при 13 ответ Ваш 70.
>>> добавлено ну а насчет упоминания я не заметил т.к. открыл окно чуть раньше
Учиться, учиться и еще раз учиться
Последний раз редактировалось Ламер_001; 23.10.2008 в 21:16. |
23.10.2008, 16:25 | #6 |
Старожил
Регистрация: 13.10.2007
Сообщений: 2,740
|
Мне кажется, решается проще и только в целых числах. На примере окружности это выглядит так. Радиус и его проекции на оси координат образуют прямоугольный треугольник. Координаты будут целыми, если целые числа a,b и R образуют зависимость a^2+b^=R^2, например всем известные тройки 3,4,5; 5,12,13; При R=5 точек с целыми кординатами будет 4 на осях (0,5;0,-5;5,0;-5,0) и 8 не на осях (3,4;4,3;-3,4;-4,3;-3,-4;-4,-3;3,-4;4,-3). Так же и со сферой, только там, если нет целых решений треугольника при данном R, то точек будет 6, если есть, то больше. Это просто идея такая, а воплощать ее тому, кто на олимпиаду собрался. Если и сейчас не решит, то и на олимпиаде делать нечего.
а нахождение количества ненулевых точек на плоскости простое for i:=1 to R do for j:=1 to R do if i*i+j*j=R*R then ... На сфере почти также. Нулевые считать не надо, их на окружности всегда 4, на сфере - 6. |
23.10.2008, 17:09 | #7 |
Старожил
Регистрация: 13.10.2007
Сообщений: 2,740
|
От увиденной сложности сам начал сложно думать, а решается то совсем просто. Они задачи списывают из учебников 1980-х годов, когда 20 сек было круто и с толку сбивают. Вот решение:
Код:
|
23.10.2008, 20:56 | #8 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Вы хотели сказать Код:
И, у меня при R=1000 считалось заметно более 20 секунд... :-( |
|
23.10.2008, 21:19 | #9 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
|
23.10.2008, 22:12 | #10 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Думаю решение в лоб не пройдет. Нужна оптимизация (это все-таки олимпиадная задача). Но по сегодняшним меркам 20 сек. это много.
Чтобы было интересней переформулируем. Определить число точек с целочисленными координатами, лежащих на поверхности шара радиуса R для всех целых R в диапазоне [0 .. 1000] за время менее 10 сек. т.е. получить последовательность: 1 6 6 30 6 30 30 54 6 102 30 78 30 78 54 150 6 102 102 126 30 270 78 150 30 150 78 318 54 174 150 198 6.... Несложная оптимизация позволяет найти все решения за 5 сек. Есть даже вариант, который считает за 3 сек. Подсказка для ТС. Во-первых сферу можно делить не на 8, а на 16, а во-вторых перебирать не все множество (x, y), а только точки на ломаной, лежащей вблизи окружности. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите решить задачку. | [Pr1_Zr4k] | Помощь студентам | 4 | 10.10.2009 17:52 |
Помогите решить задачку:-(( | torrik | Помощь студентам | 32 | 10.10.2008 09:56 |
Помогите решить задачку:-( | torrik | Microsoft Office Excel | 11 | 07.10.2008 13:38 |