ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76224
Тема:    [ Многомерные массивы ]
Сложность: 1+
Классы:
В корзину
Прислать комментарий

Условие

Дано натуральное n. Подсчитать количество решений неравенства x2 + y2 < 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .