Задача 76224

Тема:    [ Многомерные массивы ]

Сложность: 1+ Классы:

Условие

Дано натуральное n. Подсчитать количество решений неравенства x² + y² < n в натуральных (неотрицательных целых) числах, не используя действий с вещественными числами.

Решение

        k := 0; s := 0;
        {инвариант: s = количество решений неравенства
          x*x + y*y < n c x < k}
        while k*k < n do begin
        | ...
        | {t = число решений неравенства k*k + y*y < n
        |  с y>=0 (при данном k) }
        | k := k + 1;
        | s := s + t;
        end;
        {k*k >= n, поэтому s = количество всех решений
          неравенства}

Здесь ... — пока ещё не написанный кусок программы, который будет таким:

        l := 0; t := 0;
        {инвариант: t = число решений
          неравенства k*k + y*y < n c 0<=y<l }
        while k*k + l*l < n do begin
        | l := l + 1;
        | t := t + 1;
        end;
        {k*k + l*l >= n,  поэтому  t = число
          всех решений неравенства k*k + y*y < n}

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.28