Тернарный условный оператор. Адреса ссылки указатели. Функции. Рекурсия и итерация.

Михаил Медведев

[к списку лекций]

1. Тернарный условный оператор: синтаксис, семантика, примеры.

2. Адреса, ссылки и указатели: определение и использование. Физические и логические адреса. Массивы и ссылки. Выделение памяти, функция malloc.

3. Функции: определение, структура, возвращаемое значение. Формальные и фактические параметры. Передача параметров по значению и по ссылке.

4. Рекурсия и итерация: факториал числа, степень числа aⁿ за линейное O(n) и логарифмическое O(log₂ n) время, сумма цифр числа, биномиальный коэффициент , количество единиц в бинарном представлении числа n, функция Аккермана.

5. Задачи http://acm.uva.es/problemset: 374 (Большой модуль), 10696 (f91), 10774 (Повторяющийся Иосиф), 10994 (Простое сложение).

1. ТЕРНАРНЫЙ УСЛОВНЫЙ ОПЕРАТОР

Рассмотрим условный оператор:

   if (<условное выражение >) <выражение 1>; else <выражение 2>;

Напомним, что если <условное выражение > истинно, то выполняется <выражение 1>, иначе выполняется <выражение 2>.

Тернарный условный оператор имеет синтаксис:

<условное выражение > ? <выражение 1> : <выражение 2>;

и семантически немного отличается от оператора if..then..else. Если <условное выражение > истинно, то оператор возвращает значение, которое возвращает <выражение 1>, иначе возвращается значение выражения <выражение 2>.

Пример 1.1. Вычислить максимум двух чисел a и b.

Для того чтобы присвоить переменной с максимум чисел a и b, можно воспользоваться условным оператором:

if (a > b) c = a; else c = b;

В то же время вычисления можно совершить при помощи тернарного оператора:

c = (a > b) ? a : b;

Пример 1.2. Вычислить значение функции

Присвоим переменной y значение функции y(x):

y = (x > 0) ? x + 1 : x*x;

2. АДРЕСА, ССЫЛКИ И УКЗАТЕЛИ

Когда объявляется переменная, под ее значение автоматически выделяется соответствующий объем памяти. Место расположение ячеек памяти под переменную определяется автоматически компилятором и опрерационной системой во время выполнения программы. Но бывают случаи, когда программисту важно знать адрес, по которому расположен тот или иной объект.

Операция взятия адреса объекта (ссылка на объект) имеет вид: &. Результатом выполнения операции

&<объект>

является адрес ячейки памяти, с которой начинается расположение объекта.

Адрес объекта (ячейки памяти) имеет вид:

<сегмент>:<смещение>

Для вывода адреса объекта в таком формате при помощи функции printf следует воспользоваться форматом вывода “%p”.

Пример 2.1. Определим три глобальные переменные a, b, с. Выведем их физические адреса, используя формат %p.

#include <stdio.h>

int a,b,c;

void main()

{

  a = 1; b = 2; c = 3;

  printf("&a = %p\n&b = %p\n&c = %p\n",&a,&b,&c);

}

Заметим, что память под рядом стоящие переменные выделяется последовательно. Целочисленный тип int занимает в памяти 4 байта, следовательно адреса &a, &b и &c отлчаются между собой на 4.

Указателем называется символьное задание адреса. Например, выражение &x можно трактовать как “указатель на переменную x”. Определение переменных типа “указатель” имеет вид:

<тип данных> *<имя указателя>

Пример 2.2. Определим целочисленную переменную a и указатель p на целочисленный тип:

int a,*p;

Присвоим указателю p адрес переменной a:

p = &a;

Присвоим переменной a некоторе значение, и выведем его при помощи операции неявной адресации (*):

*p = 5;

printf("%d\n",*p);

Массивы и ссылки очень тесно связаны между собой. Имя массива можно использовать как ссылку; точно так же можно индексировать ссылку, как массив. Например, если переменная list определена как массив или указатель, то имеют место равенства:

(list+i) == &(list[i])

*(list+i) == list[i]

Пример 2.3. Объявим целочисленный массив m из 5 элементов и выведем его значения при помощи указателя:

#include <stdio.h>

int m[] = {1,2,3,4,5};

int i,*p=m;

void main()

{

  for(i=0;i<5;i++) printf("%d ",*p++);

}

Вместо операции вывода  printf("%d ",*p++); можно писать printf("%d ",*(p+i)); с тем же результатом.

Для выделения памяти можно воспользоваться функцией malloc библиотеки <malloc.h>. Ее синтаксис имеет вид:

void *malloc(int size);

Менеджером памяти выделяется size байт и возвращается указатель на них. Тип возвращаемого указателя можно преобразовать к требуемому.

Пример 2.4. Выделить область для 5 целочисленных значений, заполнить ее значениями от 1 до 5 и вывести используя операцию индексации.

#include <stdio.h>

#include <malloc.h>

int i,*p;

void main()

{

  p = (int *)malloc(5*sizeof(int));

  for(i=0;i<5;i++) p[i] = i+1;

  for(i=0;i<5;i++) printf("%d ",p[i]);

}

Переменная, объявленная как ссылка, служит псевдонимом другой переменной. Ее можно объявить, используя оператор ссылки &:

int i;

int &j = i;

Переменная j определена как ссылка на данные типа int и инициализирована так, что ссылается на переменную i. Таким образом j становится псевдонимом i, то есть i и j ссылаются на одно и то же место в памяти и соответственно всегда имеют одно и то же значение.

Пример 2.5. Определим целочисленную переменную и ссылку на нее. Измененим значение переменной используя ссылку

#include <stdio.h>

int i=5,&j=i;

void main (void)

{

  printf("%d %d\n",i,j); // i = 5, j = 5

  j++;

  printf("%d %d\n",i,j); // i = 6, j = 6

}

3. ФУНКЦИИ

Функция - это именованная часть  программы,   к  которой можно обращаться   из  других  частей  программы произвольное количество раз.

Описание функции имеет вид:

<возвращаемый тип> <имя функции> (<аргументы>)

{<тело функции>}

Здесь:

<возвращаемый тип> – тип  возвращаемого функцией значения (если таковое есть);

<имя функции> – имя функции;

<аргументы> – один или несколько аргументов (параметров) вместе с типами.

Каждая функция, вызываемая в программе, должна быть где-то определена (только один раз). Определение функции – это описание функции, в котором приводится тело. Оно должно следовать как правило перед определением функции main. Любая функция должна возвращать значение. Возвращаемое значение задается оператором return.

Следующая функция вычисляет сумму двух чисел:

#include <stdio.h>

int summa(int a,int b)

{

  return a + b;

}

void main()

{

  int a = 5; b = 7;

  int r = summa(a,b);

}

Семантика передачи параметров идентична семантике инициализации. Проверяются типы параметров, и когда нужно производится неявное преобразование типа. Например, при вызове

double sr2 = sqrt(2);

число 2 будет преобразовано в число с плавающей точкой, а затем уже вызвана функция sqrt.

Когда вызывается функция, дополнительно выделяется память под ее формальные параметры, и каждый формальный параметр инициализируется соответствующим ему  фактическим  параметром. В частности, тип фактического параметра сопоставляется с   типом формального параметра,  и выполняются все стандартные и определенные пользователем  преобразования  типов.

Например, в следующей программе первый параметр a передается по значению,  второй параметр b передается по ссылке. Когда вызывается функция summa(a, b), то оператор a++ увеличивает локальную копию первого фактического  параметра, тогда как b++ увеличивает  на единицу второй фактический параметр. Если функция не возвращает никакого значения, то ее возвращаемый тип равен void. Функция printf выведет на экран значения a = 5, b = 8.

#include <stdio.h>

void summa(int a,int &b)

{

  a++; b++;

}

void main(void)

{

  int a = 5, b = 7;

  summa(a,b);

  printf("%d %d\n",a,b);

}

Передача большого объекта по ссылке может быть гораздо эффективнее, чем передача его по значению. В этом случае параметр можно описать как const, чтобы указать, что ссылка применяется по соображениям эффективности, а также чтобы не позволить вызываемой функции изменять значение объекта. Описание параметра указателя как const говорит о том, что значение объекта, указываемого указателем, функцией не изменяется. Например:

int summa(const int &a,const int &b)

{

  return a + b;

}

Функция может иметь и рекурсивную природу. Тогда в ее теле присутствуют вызовы ее самой. Например, рассмотрим рекурсивное определение факториала числа fact(n):

fact(n) =

Реализуем функцию с использованием тернарного оператора:

int fact(int n)

{

return (n > 1) ? n * fact(n-1) : 1;

}

Упражнение 3.1. Определить функцию вычисления модуля действительного числа, используя тернарный оператор:

_fabs(x) = |x|

4. РЕКУРСИЯ И ИТЕРАЦИЯ

Рекурсией называется такой способ организации обработки данных, при котором программа (или функция) вызывает сама себя или непосредственно, или из других программ (функций).

Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.

Итерацией называется такой способ организации обработки данных, при котором некоторые действия многократно повторяются, не приводя при этом к рекурсивным вызовам программ (функций).

Теорема. Произвольный алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационной форме и наоборот.

Пример 4.1. Факториал числа. Факториалом числа n называется произведение всех натуральных чисел от 1 до n и обозначается n!. Если f(n) = n!, то имеет место рекуррентное соотношение:

Пример 4.2. Степень числа за линейное время. Вычисление степени числа f(a, n) = aⁿ с временной оценкой O(n) можно определить при помощи следующего рекуррентного соотношения:

Пример 4.3. Степень числа за логарифмическое время. Вычисление степени числа f(a, n) = aⁿ с временной оценкой O(log₂n) определим следующим образом:

Пример 4.4. Сумма цифр числа. Сумму цифр натурального числа n можно найти при помощи функции f(n), определенной следующим образом:

Пример 4.5. Число единиц. Количество единиц в двоичном представлении числа n можно вычислить при помощи функции f(n), определенной следующим образом (& - операция побитового ‘И’):

В результате операции n = n & (n – 1) уничтожается последняя единица в двоичном представлении числа n:

               n = a₁a₂…a_k-1a_k10…0

         n – 1 = a₁a₂…a_k-1a_k01…1

n & (n – 1) = a₁a₂…a_k-1 000…0

Рекурсивный вызов функции f будет совершаться столько раз, сколько единиц в двоичном представлении числа n.

Пример 4.6. Биномиальный коэффициент. Значение биномиального коэффициента равно

 =

и определяется рекуррентным соотношением:

 =

int c(int k, int n)

{

  if (n == k) return 1;

  if (k == 0) return 1;

  return c(k-1,n-1) + c(k,n-1);

}

Учитывая, что  =  , можно вычислить значение биномиального коэффициента циклически. При этом все операции деления будут целочисленными.

int c(int k, int n)

{

  int i,res = 1;

  for(i=1;i<=k;i++)

    res = res * (n - i + 1) / i;

  return res;

}

Упражнение 4.1. Рекурсивная функция. Для заданного натурального n вычислить значение функции f(n), заданной рекуррентными соотношениями:

f(2 * n) = f(n),

f(2 * n + 1) = f(n) + f(n + 1),

f(0) = 0, f(1) = 1

Упражнение 4.2. Функция Аккермана. Функция Аккермана A(m, n) определяется рекурсивно следующим образом:

A(0, n) = n + 1,

A(m, 0) = A(m – 1, 1),

A(m, n) = A(m – 1, A(m, n – 1))

Реализовать функцию A(m, n) и протестировать ее для разных входных значений аргументов.

Упражнение 4.3. Отбор в разведку [ACM, 1999]. Из n солдат, выстроенных в шеренгу, требуется отобрать нескольких в разведку. Для того, чтобы сделать это, выполняется следующая операция: если солдат в шеренге больше чем 3, то удаляются все солдаты стоящие на четных позициях, или все солдаты, стоящие на нечетных позициях. Эта процедура повторяется до тех пор, пока в шеренге останется 3 или менее солдат. Их и отсылают в разведку. Вычислить количество способов, которыми могут быть сформированы таким образом группы разведчиков ровно из трех человек.

Вход. Количество солдат в шеренге n ( 0 < n £ 10⁷).

Выход. Количество способов, которыми можно отобрать солдат в разведку описанным выше способом.

10

2

4

0

Упражнение 4.4 [Вальядолид, 374]. Большой модуль. По заданным b, p, m вычислить значение выражения b^p mod m.

Вход. Содержит несколько тестов. Числа b, p, m находятся в отдельных строках. Известно, что 0 £ b, p £ 2147483647, 1 £ m £ 46340.

Выход. Для каждого теста вывести в отдельной строке значение b^p mod m.

3

13

18132

2

17

13195

17

1765

3

2374859

3029382

36123

Упражнение 4.5 [Вальядолид, 10696]. f91. Вычислить значение функции f91, заданной рекуррентным соотношением:

f91(n) =

Вход. Каждая входная строка содержит натуральное число n (n £ 1000000). Число n = 0 является концом входных данных и не обрабатывается.

Выход. Для каждого входного n вывести значение f91(n) как показано в примере ниже.

500

91

0

Упражнение 4.6 [Вальядолид, 10774]. Повторяющийся Иосиф. По кругу стоят n людей, занумерованных от 1 до n. Начиная отсчет с первого и двигаясь по кругу, будем казнить каждого второго человека до тех пор пока не останется один. Пусть этот выживший имеет номер x. Расставим по кругу x людей и повторим процедуру, после которой выживет человек с номером y. И так далее до тех пор, пока номер выжившего не станет равным первоначальному количеству людей в текущем раунде.

Например, при n = 5 последовательно будут казнены 2, 4, 1, 5. Выживет номер 3. Он не равен 5 (количеству людей в раунде), поэтому следует повторить процедуру. Для n = 3 казнены будут 2, 1. Выживет человек с номером 3, равным n. Процедура заканчивается.

Вход. Входные данные состоят из нескольких тестов. Каждый тест в одной строке содержит одно число n (0 < n  £ 30000)

Выход. Для каждого теста вывести в отдельной строке его номер как указано в примере, количество повторений процедуры казни после первой итерации и номер выжившего в конце процедуры.

Упражнение 4.7 [Вальядолид, 10994]. Простое сложение. Определим рекурсивную функцию f(n) следующим образом:

f(n) =

Определим функцию S(p, q) следующим образом:

S(p, q) =

В задаче необходимо вычислить значение S(p, q) по заданным p и q.

Вход. Каждая строка содержит два неотрицательных 32-битовых знаковых числа p и q (p £ q). Последняя строка содержит два отрицательных целых числа и не обрабатывается.

Выход. Для каждой пары p и q вывести значение S(p, q).

УКАЗАНИЯ К РЕШЕНИЮ УПРАЖНЕНИЙ

Упражнение 3.1. Функция вычисления модуля действительного числа имеет вид:

#include <stdio.h>

double x,y;

double _fabs(double x)

{

return (x >= 0) ? x : -x;

}

void main()

{

  x = -5.65;

  printf("%lf\n",_fabs(x));

}

Упражнение 4.1. Рекурсивная функция. Непосредственная реализация функции f(n) имеет вид:

int f(int n)

{

  if (n <= 1) return n;

  if (n % 2) return f(n/2) + f(n/2+1);

  return f(n/2);

}

При такой реализации некоторые значения функции f могут быть вызваны несколько раз. Определим функцию

g(n, i, j) = i * f(n) + j * f(n + 1),

для которой имеют место равенства:

g(2 * n, i, j) = g(n, i + j, j),

g(2 * n + 1, i, j) = g(n, i, i +  j),

g(0, i, j) = i * f(0) + j * f(1) = j

Используя приведенные соотношения, можно вычислить значение f(n) = g(n, 1, 0) с временной оценкой O(log n).

int g(int n, int i, int j)

{

  if (!n) return j;

  if (n % 2) return g(n/2, i, i + j);

  return g(n/2, i + j, j);

}

int f(int n)

{

  return g(n,1,0);

}

Упражнение 4.2. Функция Аккермана. Рекурсивная реализация функции Аккермана имеет вид:

int a(int m, int n)

{

  if (!m) return n+1;

  if (!n) return a(m-1,1);

  return a(m-1,a(m,n-1));

}

Для малых значений m функцию Аккермана можно выразить явно:

A(0, n) = n + 1

A(1, n) = 2 + (n + 3) – 3 = n + 2

A(2, n) = 2 * (n + 3) – 3 = 2 * n + 3

A(3, n) = 2^{n + 3} – 3

Упражнение 4.3. Отбор в разведку [ACM, 1999]. Обозначим через f(n) количество способов, которыми можно сформировать группы разведчиков из n человек в шеренге. Поскольку нас интересуют только группы по три разведчика, то f(1) = 0, f(2) = 0, f(3) = 1. То есть из трех человек можно сформировать только одну группу, из одного или двух – ни одной.

Если n четное, то применяя определенную в задаче операцию удаления солдат в шеренге, мы получим в качестве оставшихся либо n / 2 солдат стоящих на четных позициях, либо n / 2 солдат, стоящих на нечетных позициях. То есть f(n) = 2 * f(n / 2) при четном n.

Если n нечетное, то после удаления останется либо n / 2 солдат стоявших на четных позициях, либо n / 2 + 1 солдат, стоявших на нечетных позициях. Общее количество способов при нечетном n равно f(n) = f(n / 2) + f(n / 2 + 1).

Таким образом, получена рекуррентная формула для вычисления значения f(n):

f(n) = 2 * f(n / 2), если n четное

f(n) = f(n / 2) + f(n / 2 + 1), если n нечетное

f(1) = 0, f(2) = 0, f(3) = 1

Реализация функции f имеет вид:

int f(int n)

{

  if (n <= 2) return 0;

  if (n == 3) return 1;

  if (n % 2) return f(n/2) + f(n/2+1);

  return 2*f(n/2);

}

Упражнение 4.4 [Вальядолид, 374]. Большой модуль. Из ограничений на входные данные следует, что в процессе вычисления достаточно использовать тип данных int. Возведение в степень b^p будем производить с логарифмической временной сложностью O(log p) используя алгоритм, базирующийся на двоичном разложении показателя степени p:

b^p =

Пример. Для вычисления значения из первого теста 3¹⁸¹³² (mod 17) следует представить показатель степени в двоичной системе исчисления: 18132₁₀ = 100011011010100₂. Далее 3¹⁸¹³² (mod 17) = 3¹⁶³⁸⁴ * 3¹⁰²⁴ * 3⁵¹² *  3¹²⁸ *  3⁶⁴ *  3¹⁶ *  3⁴ (mod 17) = 13.

Для второго теста 17¹⁷⁶⁵ (mod 3) = (17 mod 3) ¹⁷⁶⁵ (mod 3) = 2 ¹⁷⁶⁵ (mod 3) = 2.

Реализация. Функция pow вычисляет выражение b^p mod m с оценкой сложности O(log p).

#include <stdio.h>

int b,p,m,res;

int pow(int b, int p, int m)

{

 int  res=1;

 while(p > 0)

 {

   if (p & 1) res = (res * b) % m;

   p >>= 1;

   b = (b * b) % m;

 }

 return res;

}

void main(void)

{

Прочитав входные значения b, p и m, следует воспользоваться формулой

b^p mod m = (b mod m)^p mod m

При передаче параметров функции pow основание степени b должно быть не больше чем модуль m. Если этого не сделать, получим Time Limit. Отдельно следует обработать случай, когда p = 0: b⁰ mod m = 1.

  while (scanf("%d %d %d",&b,&p, &m) == 3)

  {

    b = b % m;

    if (!p) res = 1; else res = pow(b,p,m);

    printf("%d\n",res);

  }

}

Упражнение 4.5 [Вальядолид, 10696]. f91. Необходимо вычислить значения функции f91(n) для n £ 100.

Имеем: f91(100) = f91(f91(111)) = f91(101) = 91, f91(99) = f91(f91(110)) = f91(100) = 91. Аналогично продолжая, можно заметить что f91(n) = 91, где 1 £ n £ 100.

Таким образом, имеет место соотношение:

f91(n) =

Реализация. Читаем входные значения n, пока не встретится 0. Выводим результат согласно приведенному выше соотношению.

#include <stdio.h>

int n,res;

void main(void)

{

  while(scanf("%d",&n), n != 0)

  {

    if (n >= 101) res = n-10; else res = 91;

    printf("f91(%d) = %d\n",n,res);

  }

}

Упражнение 4.6 [Вальядолид, 10774]. Повторяющийся Иосиф. Пусть n – количество людей в круге. Обозначим через f(n) номер последнего уцелевшего. Положим f(1) = 1.

Если n = 2 * k – четное, то после прохода первого круга будут удалены люди с четными номерами: 2, 4, ..., 2 * k. Останутся люди с нечетными номерами, а отсчет продолжаем с номера 1. Это все равно, что если бы у нас было k людей, а номер каждого удвоился и уменьшился на 1. То есть получим соотношение f(2 * k) = 2 * f(k) – 1.

Если n = 2 * k + 1 – нечетное, то после прохода первого круга будут удалены люди с четными номерами 2, 4, ..., 2 * k, а жертва с номером 1 уничтожается сразу же после жертвы с номером 2 * k. Остается k людей с номерами 3, 5, 7, …, 2 * k + 1. Это все равно, что люди занумерованы от 1 до k, только номер каждого удвоился и увеличился на 1. Получаем соотношение: f(2 * k + 1) = 2 * f(k) + 1.

Объединяя полученные соотношения, получим рекуррентность:

f(1) = 1

f(2 * k) = 2 * f(k) – 1, k ³ 1

f(2 * k + 1) = 2 * f(k) + 1, k ³ 1

Теорема. Значение f(n) получается путем циклического сдвига двоичного представления n влево на один бит. Например, f(100) = f(1100100₂) = 1001001₂ = 73.

Многократное применение функции f порождает последовательность убывающих значений, достигающих неподвижной точки n такой что f(n) = n. Число n будет состоять из одних единиц со значением 2^v(n) – 1, где v(n) – количество единиц в бинарном представлении числа n.

Пример. Рассмотрим входные данные для второго теста. При n = 13 последовательно будут казнены 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3. Выживет номер 11. Он не равен 13 (количеству людей в раунде), поэтому следует повторить процедуру. Для n = 11 казнены будут 2, 4, 6, 8, 10, 1, 5, 9, 3, 11. Выживет человек с номером 7, равным n. При n = 7 выживет номер 7. После первой итерации проведено еще 2 повторения процедуры казни.

Реализация. Функция last по первоначальному количеству людей n в круге возвращает номер уцелевшего согласно рекуррентному соотношению.

#include <stdio.h>

int k,n,i,r,tests;

int last(int n)

{

  if (n == 1) return 1;

  if (n%2 == 0) return 2*last(n/2)-1;

           else return 2*last((n-1)/2)+1;

}

void main(void)

{

  scanf("%d",&tests);

  for(i=1;i<=tests;i++)

  {

Переменная r содержит количество повторений процедуры казни (изначально r = 0). По заданному входному n ищем номер уцелевшего k. Если он не равен n, то повторяем в цикле процедуру казни.

    scanf("%d",&n); r = 0;

    while ((k = last(n)) != n) r++, n = k;

    printf("Case %d: %d %d\n",i,r,n);

  }

}

Упражнение 4.7 [Вальядолид, 10994]. Простое сложение. Приведенная в условии функция f(n) находит последнюю ненулевую цифру числа n. Обозначим через

g(p) =

Тогда S(p, q) = g(q) – q(p – 1). Для вычисления функции g(p), суммы последних значащих цифр для чисел от 1 до p, разобьем числа от 1 до p на три множества (операция деления ‘/’ является целочисленной):

1. Числа от (p/10)*10 + 1 до p;

2. Числа от 1 до (p/10)*10, не оканчивающиеся нулем;

3. Числа от 1 до (p/10)*10, оканчивающиеся нулем;

Например, при p = 32 к первому множеству отнесутся числа 31, 32, ко второму 1, …, 9, 11,  …, 19, 21, …, 29, к третьему 10, 20.

Сумма последних значащих цифр в первом множестве равна 1 + 2 + … + p%10 = t(1 + t) / 2, где t = p % 10. Во втором множестве искомая сумма равна p / 10 * 45, так как сумма всех цифр от 1 до 9 равна 45, а число полных десятков равно p / 10. Требуемую сумму для третьего множества найдем рекурсивно: она равна g(p / 10).

Реализация. Поскольку выполняется обработка 32-битовых знаковых чисел, то при вычислениях используем тип long long (__int64).

#include <stdio.h>

long long p,q;

Функция g(p) вычисляет сумму значений функции f(n) для значений аргумента n от 1 до p.

long long g(long long p)

{

  long long t = p % 10;

  if (!p) return 0;

  return t*(1+t)/2 + p/10 * 45 + g(p/10);

  return 0;

}

Значение функции S(p, q) считаем как g(q) – q(p – 1).

long long s(long long p, long long q)

{

  return g(q) - g(p-1);

}

void main(void)

{

Основной цикл программы. Для каждой пары чисел p и q выводим значение s(p, q).

  while(scanf("%lld %lld",&p,&q),p+q>=0)

     printf("%lld\n",s(p,q));

}

[к списку лекций]