На этой страничке Вы можете предварительно ознакомить с книгой "Программирование в теоремах и задачах", автором которой является . Скачать книгу "Программирование в теоремах и задачах" полностью в архиве можно перейдя по соответствующей ссылке. Другие книги Вы найдёте воспользовавшись поиском книг по автору или по названию произведения. Книгу "Программирование в теоремах и задачах" скачали в нашем Клубе Аудиокниг уже 394 раз. База произведений постоянно растет, данная книга была добавлена "Программирование в теоремах и задачах". Надеемся это именно то, что Вы искали.

(Для n = 173 надо напечатать 371.)

     Решение.

        k:= n;
        {инвариант: осталось напечатать k в обратном порядке}
        while k <> 0 do begin
        | write (k mod 10);
        | k:= k div 10;
        end;

     1.1.28. Дано натуральное n. Подсчитать  количество  решений
неравенства  x*x + y*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="" |="" (при="" данном="" k)="" }="" |="" k="" :="k" +="" 1;="" |="" s="" :="s" +="" t;="" end;="" {k*k="">= n, поэтому s = количество всех решений
          неравенства}

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

        l := 0; t := 0;
        {инвариант: t = число решений
          неравенства k*k + y*y < n="" c="" 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}="" 1.1.29.="" та="" же="" задача,="" но="" количество="" операций="" должно="" быть="" порядка="" (n="" в="" степени="" 1/2).="" (в="" предыдущем="" решении,="" как="" можно="" подсчитать,="" порядка="" n="" операций.)="" решение.="" нас="" интересуют="" точки="" решетки="" (с="" целыми="" координата-="" *="" ми)="" в="" первом="" квадранте,="" попадающие="" внутрь="" круга="" *="" *="" *="" радиуса="" (n="" в="" степени="" 1/2).="" интересующее="" нас="" *="" *="" *="" *="" множество="" (назовем="" его="" x)="" состоит="" из="" объедине-="" *="" *="" *="" *="" ния="" вертикальных="" столбцов="" убывающей="" высоты.="" *="" *="" *="" *="" *="" идея="" решения="" состоит="" в="" том,="" чтобы="" "двигаться="" вдоль="" его="" границы",="" спускаясь="" по="" верхнему="" его="" краю,="" как="" по="" лестнице.="" координаты="" движущейся="" точки="" обозначим="">.  Введем
еще одну переменную s и будем поддерживать истинность такого ус-
ловия:
      нах