VPF::Как оптимизировать, или обойтись без перебора???

sofware

Дата 4.12.2006, 17:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1

Дано радиус круга R(R<=20000).Нужно найти количество целочисульных точек, пренадлежащих этому кругу.
Для 5 будет 81.Для 3 будет 27.
Вот мой код, он работает, но очень долго:

Код


var r,a,b,n,k,i,j:longint;
begin
read(r);
for i:=1 to r do
for j:=1 to r do
 begin
  a:=i;b:=j;
  if (r*r-a*a<b*b)and(r*r-b*b<a*a) then inc(k);
 end;
k:=sqr(r*2+1)-k*4;
write(k);
end.

Zero

Дата 4.12.2006, 23:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Но как вариант, можно попробывать так:
1. Находишь площадь круга;
2. Находишь, область площади, которая концовку точек делает дробной;
3. вычитаешь результат два из результата один;
4. Делиш результат три, на условную площадь точки.

Dottik

Дата 9.12.2006, 11:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 13.10.2006
Где: Ukraine

Репутация: нет
Всего: 2

Цитата

Для 5 будет 81.Для 3 будет 27.

1) На полуосях всегда будет лежать R точек. Есть 4 полуоси + точка(0,0).
Тоесть на осях лежит (4*R+1) точка.
2) Круг семитричен. Достаточно рассмотреть 1 четверть.

Из этого следует, что ответ на задачу имеет вид: 4*S + 4*R + 1
В случае 81 = 4*15 + 4*5 + 1
Ответ, который вы дали для 3 неверен.
Правильный ответ:
4*4+4*3+1 = 29

Вот код моей програмы, алгоритм O®

Код


program Circle;

var
  i, j, r, S: Integer;

begin
  ReadLn(r);
  S := 0;
  for i := 1  to r do
  begin
    S := S + Trunc(Sqrt(r*r-i*i));
  end;
  S := 4*S + 4*r+1;
  Writeln(S);
end.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »