Операторы цикла. Ввод-вывод данных. Математические функции.

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

[назад]

1. Операторы цикла: синтаксис и семантика.

1.1. Оператор for.

1.2. Оператор while.

1.3. Оператор do-while.

2. Многократный ввод-вывод. Понятие однократного и многократного ввода-вывода. Чтение данных до конца файла. Возвращаемое значение функции scanf.

3. Форматированный ввод-вывод. Формат целочисленных и вещественных данных.

4. Математические функции. Библиотека <math.h>. Алгебраические и тригонометрические функции. Функции округления. Вычисление степени числа. Константа .

5. Задачи

http://acm.uva.es/problemset: 113 (Сила криптографии), 408 (Однородный генератор), 10127 (Единицы), 10509 (Обмануть Мистера Фреймана), 10633 (На редкость простая задача), 10683 (Десятичные часы), 10773 (Назад к математике средней школы), 10783 (Сумма нечетных чисел), 10784 (Диагональ).

http://acm.timus.ru: 1068 (Sum).

http://www.topcoder.com/tc: SRM 326 (AdditionCycles), SRM 343 (PersistentNumber), TCHS 29 (ReverseSums).

1. ОПЕРАТОРЫ ЦИКЛА

Язык Си имеет три конструкции, реализующие операторы цикла: for, while, do-while.

1.1. ОПЕРАТОР for

Цикл for является одним из основных видов циклов, которые имеются во всех универсальных языках программирования,  включая С. Однако версия цикла for, используемая в С, обладает большей мощностью и гибкостью.

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

Синтаксис:

   for (<выражение инициализации>; <условное выражение>; <выражение цикла>)

                <тело оператора>;

Параметры цикла for, заключенные в скобки, должны разделяться точкой с запятой (позиционный параметр), которая делит в свою очередь пространство внутри скобок на три сектора.

Тело  оператора  for  выполняется  нуль и более раз до тех пор, пока условное выражение <условное выражение> не станет  ложным.

Выражения инициализации <выражение инициализации> и цикла <выражение цикла> могут быть использованы для инициализации и модификации величин во время выполнения оператора for.

Первым шагом при выполнении оператора for является вычисление выражения инициализации, если оно имеется. Далее вычисление продолжается в зависимости от значения условного выражения:

1. Если условное выражение истинно (не равно нулю), то выполняется тело оператора.  Потом вычисляется  выражение  цикла (если оно есть). Процесс повторяется снова с вычислением условного выражения.

2.  Если условное выражение опущено, то его значение принимается за истину и процесс выполнения продолжается, как описано выше. В этом случае оператор for может завершиться только при выполнении в теле оператора операторов break, goto, return.

3. Если условное выражение ложно, то выполнение оператора for заканчивается и управление передается следующему оператору в программе.

Оператор for может завершиться  при  выполнении  операторов break, goto, return в теле оператора. В некоторых случаях использование оператора запятая (,) позволит вводить составные выражения в оператор цикла for.

Пример 1.1.1. Вычислить сумму чисел от 1 до 100.

for (s=0,i=1;i<=100;i++)

  s = s + i;

Выражение инициализации обнуляет переменную суммы s и присваивает 1 переменной i. Операторы, записанные через запятую, выполняются последовательно. Выражение цикла прибавляет 1 к переменной i, а в теле цикла происходит суммирование переменных s и i. Цикл завершает свою работу когда переменная i достигнет значения 101. То есть последним числом, которое будет прибавлено к переменной s, будет 100. В конце работы оператора for переменная s будет содержать число 5050 – сумму натуральных чисел от 1 до 100.

Пример 1.1.2. Тело цикла, которое не выполняется

for (s=0,i=1;i<1;i++)

  s = s + i;

Если в предыдущей программе заменить условное выражение на i < 1, то тело цикла никогда не выполнится. После инициализации s = 0, i = 1 будет проверено условное выражение i < 1. И поскольку оно ложно, то управление программой перейдет на следующий за for оператор.

Пример 1.1.3. Для заданного натурального n вычислить сумму

S =  +  + … +

Сумму будем вычислять в переменной s, имеющей тип double. Каждое слагаемое имеет вид  , где 1 £ i £ n.

На языке Си это выражение можно записать как 1.0 / (i * (i + 1)) или как 1.0 / i / (i + 1). В качестве числительного следует писать 1.0, а не 1, так как результат деления должен быть действительным. В цикле последовательно прибавляем к нулю все слагаемые 1.0 / i / (i + 1) для i от 1 до n.

#include <stdio.h>

int i,n;

double s;

void main(void)

{

  scanf("%d",&n);

  s = 0;

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

    s += 1.0 / i / (i+1);

  printf("%lf\n",s);

}

Указанную сумму можно также вычислить непосредственно. Заметив, что

 =  –

можно получить:

S =  +  + … +  = –  + –  + . . . +  –  = 1 –

Пример 1.1.4 [Вальядолид, 10127]. Единицы. Дано натуральное число n (0 £ n £ 10000), которое не делится ни на 2, ни на 5. Существуют числа, которые состоят только из единиц и делятся на n. Найти количество единиц в минимальном таком числе.

Для числа n = 3 наименьшим числом, состоящим из одних единиц и которое делится на 3, будет 111. Для n = 7 таким числом будет 111111.

Построим последовательность чисел a₁ = 1, a_i = (10*a_i-1 + 1) mod 10. a_i содержит остаток от деления числа, состоящего из i единиц, на n. Как только для некоторого i значение a_i станет равным 0, останавливаем итерационный процесс. Число, состоящее из i единиц, делится нацело на n.

#include <stdio.h>

void main(void)

{

  int n,one,count_ones;

  for(;scanf("%d",&n) == 1;)

  {

    for(one=1,count_ones=1;one>0;count_ones++)

        one = (10*one+1) % n;

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

  }

}

Упражнение 1.1.1. Вычислить значение произведения

 *  *  * … *

для заданного n при помощи цикла for и непосредственно при помощи математических преобразований.

1.2. ОПЕРАТОР while

В конструкции while вычисляется выражение. Если его значение отлично от нуля (истинно), то выполняется тело оператора и выражение вычисляется снова. Этот цикл продолжается до тех пор, пока значение выражения не станет нулем, после чего выполнение программы продолжается с места после тела оператора.

Синтаксис:

    while (<выражение>) <тело оператора>;

Пример 1.2.1. Вычислить сумму чисел от 1 до 100.

#include <stdio.h>

int s,i;

void main(void)

{

  s = 0; i = 100;

  while(i > 0)

  {

    s = s + i;

    i--;

  }

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

}

Изначально значение суммы s положили равным нулю. В переменной i содержится очередное слагаемое, которое будет прибавляться к сумме s. Первым таким слагаемым будет i = 100. Пока выражение, заключенное в круглые скобки цикла while будет истинным, совершается тело цикла. В теле цикла к сумме s прибавляется слагаемое i и это слагаемое уменьшается на 1. Цикл закончит свое выполнение, когда слагаемое i станет равным нулю и не будет выполняться условие i > 0.

Операторы можно разделять запятой (‘,’), тогда они будут выполняться последовательно. Если два оператора в теле цикла while объединить в последовательное выполнение, то можно не брать в фигурные скобки тело цикла:

#include <stdio.h>

int s,i;

void main(void)

{

  s = 0; i = 100;

  while(i > 0)

    s += i,i--;

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

}

Упражнение 1.2.1 [Топкодер, SRM 343, PersistentNumber]. По заданному числу х определим функцию p(x), равную произведению его цифр. Образуем последовательность x, p(x), p(p(x)), … . Стойкостью числа x назовем наименьший индекс однозначного числа в указанной последовательности. Нумерация индексов в последовательности начинается с нуля. Например, для x = 99 имеем: p(99) = 9 * 9 = 81, p(81) = 8 * 1 = 8. Стойкость числа 99 равна 2.

Класс: PersistentNumber

Метод: int getPersistence(int n)

Ограничения: 0 £ n £ 2 * 10⁹.

Вход. Целое число n.

Выход. Стойкость числа n.

Пример входа

Пример выхода

2

4

7

Упражнение 1.2.2 [Топкодер, TCHS 29, ReverseSums]. Для нахождения обратной суммы следует сложить заданное число с числом, цифры которого идут в обратном порядке. Например, для числа 1325 результатом будет 1325 + 5231 = 6556.

Класс: ReverseSums

Метод: int getSum(int n)

Ограничения: 1 £ n £ 99999.

Вход. Натуральное число n.

Выход. Сумма заданного числа с обратным.

Пример входа

Пример выхода

6556

101

2

1.3. ОПЕРАТОР do-while

Оператор цикла do-while проверяет условие окончания в конце, после каждого прохода через тело цикла; тело цикла всегда выполняется по крайней мере один раз. Сначала выполняется тело оператора, затем вычисляется выражение. Если оно истинно, то тело оператора выполняется снова и т.д. Если выражение становится ложным, цикл заканчивается.

Синтаксис:

do <тело оператора> while (<выражение>);

Тело оператора do выполняется один или несколько раз до тех пор, пока выражение <выражение>  станет  ложным  (равным  нулю). Вначале  выполняется <тело оператора>, затем вычисляется <выражение>. Если выражение ложно, то оператор do  завершается и управление передается следующему оператору в программе.  Если  выражение  истинно  (не равно нулю), то тело оператора выполняется снова и снова проверяется выражение. Выполнение  тела оператора  продолжается  до  тех  пор,  пока  выражение не станет ложным.

Пример 1.3.1. Вычислить сумму чисел от 1 до 100.

#include <stdio.h>

int s,i;

void main(void)

{

  s = 0; i = 100;

  do {

    s = s + i;

    i--;

  } while(i > 0);

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

}

В переменной s накапливается сумма, переменная i принимает все значения от 100 до 1. В теле цикла происходит прибавление значения i к сумме s и уменьшение i на 1. Цикл повторяется пока выражение (i > 0) истинно. Как только значение переменной i станет равным 0, цикл завершается и управление передается следующей команде.

Упражнение 1.3.1 [Топкодер, SRM 326, AdditionCycles]. Имеется число n в границах от 00 до 99, записанное двумя цифрами (если число меньше 10, то перед ним стоит ведущий 0). Сложим цифры числа. Припишем к правой цифре первого числа правую цифру суммы и получим новое число. Если повторять несколько раз описанную процедуру, то снова можно получить n. Например:

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

Класс: AdditionCycles

Метод: int cycleLength(int n)

Ограничения: 0 £ n £ 99.

Вход. Целое число n.

Выход. Число шагов преобразований, после выполнения которых снова появится число n.

Пример входа

Пример выхода

4

3

1

2. МНОГОКРАТНЫЙ ВВОД – ВЫВОД

При решении олимпиадных задач различают однократный ввод (single input) и многократный ввод (multiple input). Однократный ввод характеризуется данными для одного теста. Если на вход подаются данные для нескольких тестов, то говорят о многократном вводе. Рассмотри два примера.

Пример 2.1. На вход подаются два числа a и b. Найти их сумму.

Для решения задачи достаточно ввести два числа, найти их сумму и вывести результат (занятие 1, раздел 2.3).

Пример 2.2. На вход подаются несколько строк. Первая строка содержит количество тестов n. Каждая из следующих n строк содержит два числа a и b. Для каждого теста найти сумму двух чисел и вывести ее в отдельной строке.

Читаем в переменную n количество тестов. Далее в цикле для каждой входной строки вводим слагаемые a и b, находим их сумму и выводим на экран.

#include <stdio.h>

int i,a,b,n;

void main(void)

{

  scanf("%d",&n);

  for(i=0;i<n;i++)

  {

    scanf("%d %d",&a,&b);

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

  }

}

Цикл можно организовать и при помощи конструкции while. В таком случае вводить дополнительную переменную i нет необходимости:

#include <stdio.h>

int a,b,n;

void main(void)

{

  scanf("%d",&n);

  while(n--)

  {

    scanf("%d %d",&a,&b);

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

  }

}

Цикл while будет продолжаться до тех пор, пока выражение n-- будет оставаться истинным. А это будет выполняться до тех пор, пока n не станет равным 0.

Пример 2.3. На вход подаются несколько строк. Каждая строка содержит два числа a и b. Для каждой строки вывести сумму двух чисел, находящихся в ней.

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

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

i = scanf("%d %d",&a,&b);

и ввести два числа a и b, то переменная i примет значение 2. Это свойство функции очень удобно использовать при чтении данных до конца файла. Дело в том, что если программа прочитает все данные и дойдет до конца файла, то при следующем вызове функции scanf она вернет значение, равное -1. Решение примера 3.2.3 имеет вид:

#include <stdio.h>

int a,b;

void main(void)

{

  while(scanf("%d %d",&a,&b) == 2)

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

}

В цикле while читаем два числа a и b. Пока вводятся два числа, scanf возвращает 2 и выполняется тело цикла (печать суммы чисел). Кодга дойдем до конца файла, функция scanf не сможет прочитать следующие два числа и вернет -1. Выполнение цикла закончится.

Напоминание! При чтении данных с консоли ввести символ “конец файла” можно, нажав комбинацию клавиш ^Z.

Пример 2.4. На вход подаются несколько строк. Каждая строка содержит два неотрицательных целых числа a и b. Для каждой строки вывести сумму двух чисел, находящихся в ней. Последняя строка содержит два нуля и не обрабатывается.

Пример отличается от предыдущего тем, что окончание работы цикла следует произвести не по достижению конца файла, а при прочтении значений a = 0, b = 0.

#include <stdio.h>

int a,b;

void main(void)

{

  while(scanf("%d %d",&a,&b),a + b)

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

}

Условное выражение цикла while состоит из двух частей: функции scanf и выражения a + b. Цикл продолжается до тех пор, пока оба выражения остаются истинными. Очевидно, что функция scanf всегда будет возвращать 2 (поскольку до конца файла при обработке данных в этой задаче мы не дойдем), а значение a + b будет оставаться истинным пока оба значения a и b не станут равными 0 (по условию a и b целые неотрицательные).

Напоминание! Арифметическое выражение является истинным, если оно не равно 0.

Упражнение 2.1 [Вальядолид, 10633]. На редкость простая задача. N – некоторое целое число, имеющее в десятичной записи хотя бы две цифры. Джон производит над этим числом следующую операцию: он зачеркивает последнюю цифру, получает число M и вычисляет N – M. Зная значение N – M, следует найти N.

Вход. Каждая строка содержит целое положительное число, являющееся значением  N – M (10 £ N – M £ 10¹⁸). Последняя строка содержит 0 и не обрабатывается.

Выход. Для каждого входного значения  N – M вывести все возможные N в возрастающем порядке. Числа в одной строке следует разделять одним пробелом.

Упражнение 2.2 [Вальядолид, 10783]. Сумма нечетных чисел. Вычислить сумму всех нечетных чисел из интервала [a, b]. Например, сумма нечетных чисел из интервала [3, 9] равна 3 + 5 + 7 + 9 = 24.

Вход. Первая строка содержит количество тестов T (1 £ T £ 100). Каждый тест состоит из двух чисел a  и b (0 £ a £ b £ 100), каждое из которых находится в отдельной строке.

Выход. Для каждого теста вывести его номер и сумму всех нечетных чисел из интервала [a, b].

Упражнение 2.3 [Тимус, 1068]. Сумма. Найти сумму чисел от 1 до n включительно.

Вход. Целое число n, не большее 10000 по абсолютному значению.

Выход. Сумма чисел от 1 до n включительно.

3. ФОРМАТИРОВАННЫЙ ВВОД-ВЫВОД

В первом уроке были приведены форматы ввода-вывода элементарных типов данных. Формат позволяет выводить числовые значения переменных с определенным количеством знаков. Следующая таблица описывает форматы данных:

Здесь <n> и <m> – некоторые целые неотрицательные числа. Значение переменной выводится в <n> позициях. При выводе значения действительного типа после десятичной запятой выводится <m> знаков, десятичная точка занимает одну позицию. Если <n> больше чем количество цифр в выводимом значении, то перед числом выводятся пробелы. Если <n> меньше чем количество цифр в выводимом значении, то значение выводится с таким количеством цифр, которое оно содержит.

Если <m> = 0, то действительное число при выводе округляется до целого значения.

Пример 3.1. Вывести таблицу умножения 9*9. Каждое число в таблице должно занимать две позиции, между числами в одной строке должен находиться один пробел.

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

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

{

  for(j=1;j<10;j++)

    printf("%2d ",i*j);

  printf("\n");

}

Пример 3.2. Входная строка задает дату и имеет формат: “DD:MM:YYYY” (день:месяц:год). Необходимо в три разные переменные занести день, месяц и год.

int day,month,year;

scanf("%d:%d:%d",&day,&month,&year);

Пример 3.3. На вход подается квадратная матрица размером n * n (n < 10), каждый элемент которой представляет собой цифру. Первая строка задает n, следующие строки описывают матрицу. Необходимо найти сумму всех чисел матрицы.

Для чтения однозначных чисел следует воспользоваться форматом “%1d”:

#include <stdio.h>

int s,d,n,i,j,m[10][10];

int main(void)

{

  scanf("%d",&n);

  for(i=0;i<n;i++)

    for(j=0;j<n;j++)

    {

      scanf("%1d",&d);

      s += d;

    }

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

  return 0;

}

Упражнение 3.1 [Вальядолид, 408]. Однородный генератор. Псевдослучайные числа можно сгенерировать при помощи формулы:

seed(x + 1) = (seed(x) + STEP) % MOD,

где % – операция взятия остатка. Недостаток такого метода получения случайных чисел состоит в том, что циклически будет генерироваться одна и та же последовательность. Например, если STEP = 3 и MOD = 5, то циклически будет повторяться последовательность 0, 3, 1, 4, 2. Если STEP = 15 и MOD = 20, то получим серию чисел 0, 15, 10, 5.

Выяснить, можно при помощи такого генератора получить все числа от 0 до MOD – 1.

Вход. Каждая строка содержит два числа: STEP и MOD (1 £ STEP, MOD £ 100000).

Выход. Для каждого теста вывести значение STEP в колонках от 1 до 10, выровненное справа, значение MOD в колонках от 11 до 20, выровненное справа, и фразу ‘Good Choice‘ или ‘Bad Choice‘, начиная с колонки 25. Если по входным STEP и MOD будут сгенерированы все числа от 0 до MOD – 1, то выводить фразу ‘Good Choice‘. Иначе следует выводить фразу ‘Bad Choice‘. После вывода результата для каждого теста выводить пустую строку.

Упражнение 3.2 [Вальядолид, 10683]. Десятичные часы. Однажды математик Гильберт Ром изобрел часы с десятичной системой исчисления. День был поделен на 10 часов, в каждом часе было 100 минут, а в каждой минуте – 100 секунд. В задаче требуется перевести время из традиционной системы в десятичную с точностью до одной сотой секунды.

Вход. Состоит из нескольких строк. Каждая строка содержит традиционное время в формате HHMMSSCC, где 0 £ HH £ 23, 0 £ MM £ 59, 0 £ SS £ 59, 0 £ CC £ 99.

Выход. Для каждого теста вывести его соответствующее десятичное время в формате HMMSSCC, где 0 £ H £ 9, 0 £ MM £ 99, 0 £ SS £ 99, 0 £ CC £ 99. Значение десятичного времени следует округлить вниз.

4. МАТЕМАТИЧЕСКИЕ ФУНКЦИИ

Для работы с алгебраическими и тригонометрическими функциями следует поключить к программе библиотеку <math.h>:

#include <math.h>

Алгебраические функции:

Тригонометрические функции:

Константа  в библиотеке <math.h> не определена. Ее можно получить, вычислив arccos(-1):

const double PI = acos(-1);

Функции округления:

При вычислении степеней чисел иногда удобно воспользоваться соотношением

xⁿ =  =

Отсюда, например, следует что

 =  =  =

Для вычисления квадратного корня с удвоенной точностью используют функцию sqrtl.

Упражнение 4.1 [Вальядолид 113]. Сила криптографии. По заданным числам n ³ 1 и p ³ 1 вычислить значение , положительный  n - ый корень числа p. Известно, что всегда существует такое целое k, что kⁿ = p.

Вход. Состоит из последовательности пар чисел n и p, каждое число задается в отдельной строке. Известно, что 1 £ n £ 200, 1 £ p < 10¹⁰¹, 1 £ k £ 10⁹.

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

2

4

16

3

3

1234

27

7

4357186184021382204544

Упражнение 4.2 [Вальядолид 10509]. Обмануть Мистера Фреймана. Мистер Фрейман – известный музыкант, учитель и Нобелевский лауреат. Однажды он в уме смог вычислить значение кубического корня из числа 1729.03 до трех знаков после запятой, получив 12.002.

Приближенно вычислить квадратный корень можно следующим образом. Пусть  = a + dx, где a – целое, 0 £ dx < 1. Тогда n = (a + dx)² = a² + 2 * a * dx + (dx)². Если значение dx мало, то при приближенном вычислении слагаемое (dx)² можно не учитывать, то есть можно положить что n = a² + 2 * a * dx. Здесь dx = (n – a²) / 2a. В задаче требуется построить аналогичную схему для вычисления приближенного значения кубического корня.

Вход. Каждая строка содержит действительное значение n в промежутке от 0 до 1000000 включительно. Последняя строка содержит 0 и не обрабатывается.

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

1729.0300

12.0024

Упражнение 4.3 [Вальядолид 10773]. Назад к математике средней школы. Необходимо пересечь реку длиной d метров. Скорость течения реки v м/с, скорость лодки – u м/с. Существует возможность пересечь реку либо за минимальное время, либо по кратчайшему пути (пути, перпендикулярному течению реки). Если существуют такие два разные пути, то вывести неотрицательную разницу времен P с тремя точками после запятой, за которую их можно преодолеть. Иначе вывести фразу “can’t determine”.

Вход. Входные данные состоят из нескольких тестов. Каждый тест в одной строке содержит три числа d, v, u (v и u – неотрицательны, d – положительно).

Выход. Для каждого теста вывести в отдельной строке его номер как указано в примере, разницу времен P, если существует два разных пути или фразу “can’t determine” иначе.

Упражнение 4.4 [Вальядолид 10784]. Диагональ. Количество диагоналей у выпуклого n - угольника не менее N. Чему равно минимально возможное значение n?

Вход. Каждая входная стока содержит положительное целое число N (N £ 10¹⁵) – количество проведенных диагоналей. Значение N = 0 является концом входных данных и не обрабатывается.

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

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

Упражнение 1.1.1. Можно найти замкнутую формулу представленного выражения, совершив ряд математических преобразований:

 *  *  * … *  =

 *  *  * … *

Заметим, что

 = =  = 1

Поэтому искомое выражение равно

 * *  *  =  *  =

Программа, вычисляющая значение выражения при помощи цикла, имеет вид:

#include <stdio.h>

int i,n=100;

double res;

void main(void)

{

  res = 1;

  for(i=2;i<=n;i++)

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

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

}

Упражнение 1.2.1 [Топкодер, SRM 343, PersistentNumber]. Последовательно вычисляем значения x, p(x), p(p(x)), … до тех пор, пока очередное число в последовательности не станет меньше 10. Поскольку n £ 2 * 10⁹, то произведение цифр числа n может не помещаться в тип int. Используем 64-битовый целочисленный тип __int64.

#include <stdio.h>

class PersistentNumber

{

  public:

  int getPersistence(int n)

  {

    __int64 res=0,c;

    int t;

    while(n >= 10)

    {

      t = n;c = 1;

      while(t > 0)

      {

        c  = c * (t%10);

        t = t / 10;

      }

      n = c; res++;

    }

    return res;

  }

};

Упражнение 1.2.2 [Топкодер, TCHS 29, ReverseSums]. В цикле для заданного n находим число, записанное теми же цифрами, но в обратном порядке. Складываем его с исходным значением n.

#include <stdio.h>

class ReverseSums

{

public:

  int getSum(int n)

  {

    int m=0,nn=n;

    while(n)

      m = m * 10 + n %10,

      n /= 10;

    return nn + m;

  }

};

Упражнение 1.3.1 [Топкодер, SRM 326, AdditionCycles]. В задаче достаточно промоделировать описанный процесс преобразования числа. Начиная со входного значения n, повторяем процесс преобразования, пока снова не получим это же число. Параллельно подсчитываем количество таких преобразований в переменной len.

Описанное преобразование над числом n можно записать и одной командой:

n = n%10*10 + (n%10 + n/10)%10

#include <stdio.h>

class AdditionCycles{

public:

  int cycleLength(int n)

  {

    int sum,k=-1,len=0,Initn = n;

    while(Initn != k)

    {

      sum = n%10 + n/10;

      k = n%10*10+sum%10;

      len++;n = k;

    }

    return len;

  }

};

Программу можно упростить следующим образом, записав преобразование числа в одной команде:

#include <stdio.h>

class AdditionCycles{

public:

  int cycleLength(int n)

  {

    int len=0,Initn = n;

    do{

     n = n%10*10 + (n%10 + n/10)%10,len++;

    } while(n != Initn);

    return len;

  }

};

Упражнение 2.1 [Вальядолид, 10633]. На редкость простая задача. Пусть N = 10 * X + a, где а – последняя цифра числа N (0 £ a £ 9). Тогда M = X, N – M = 10 * X + a – X = 9 * X + a. Обозначим n = N – M. Тогда a = n mod 9, X = (n – a) / 9. Очевидно, что искомым будет N = 10 * X + a = 10 * (n – a) / 9 + n mod 9.

Если a = n mod 9 = 0, то последняя цифра a может равняться 9, так как 9 mod 9 = 0. Тогда X = (n – 9) / 9 = n / 9 – 1, откуда N = 10 * X + a = 10 * (n / 9 + 1) + 9.

Таким образом если значение N – M делится на 9, то существует два разных значения N. Иначе – одно.

Пример. Если N = 19, то M = 1 и N – M = 18. При N = 20 получим M = 2 и N – M = 18. Если N – M = 18 (делится на 9), то существует два разных значения N: 19 и 20.

Реализация. Объявим переменные a, n, x типа double.

double a,n,x;

Вводим n = N – M. Последовательно вычисляем значения a, x и выводим результат согласно приведенному выше анализу.

while (scanf("%lf",&n),n > 0)

{

  a = n % 9;

  x = (n - a) / 9;

  if (!a) printf("%lf ",10*(x-1)+9);

  printf("%lf\n",10*x+a);

}

Упражнение 2.2 [Вальядолид, 10783]. Сумма нечетных чисел. Пересчитаем значения a и b так, чтобы a равнялось наименьшему нечетному числу из интервала [a, b], а b – наибольшему. Если a > b, то сумма рана 0. Иначе сумму всех нечетных чисел из интервала [a, b] считаем по формуле суммы арифметической прогрессии. Поскольку значения a и b нечетные, то количество нечетных чисел в интервале [a, b] равно (b - a) / 2 + 1, а сумма всех нечетных чисел равна

Пример. Путь a = 4, b = 10. После пересчета интервал [4, 10] превратится в [5, 9]. Количество нечетных чисел равно (9 – 5) / 2 + 1 = 3. Сумма всех нечетных чисел равна (5 + 9) / 2 * 3 = 21.

Реализация. После прочтения входных данных пересчет границ интервала совершаем по правилу: если значение a четно, то увеличиваем его на 1; если b четно, то уменьшаем его на 1. Далее используем формулу суммы членов арифметической прогрессии.

scanf("%d",&tests);

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

{

  scanf("%d %d",&a,&b);

  if (a % 2 == 0) a ++;

  if (b % 2 == 0) b --;

  if (b < a) res = 0;

    else res = (b + a) * ((b - a)/2 + 1) /2;

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

}

Упражнение 2.3 [Тимус, 1068]. Сумма. Если считать сумму, последовательно складывая числа от 1 до n, то получим Time Limit. Следует воспользоваться формулой суммы арифметической прогрессии. Если n > 0, то результатом будет

res = (1 + n) * n / 2

Иначе сумма равна

res = ((1 + n) * (abs(n) + 2)) / 2

Реализация. Читаем входное значение n и вычисляем сумму res согласно приведенным выше формулам.

scanf("%d",&n);

if (n >= 1) res = (1 + n) * n / 2;

else res = ((1 + n) * (abs(n) + 2)) / 2;

Выводим результат res.

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

Упражнение 3.1 [Вальядолид, 408]. Однородный генератор. Положим seed(0) = 0. Если будут сгенерированы по выше приведенной формуле все числа от 0 до MOD – 1, то seed(i) ¹ 0, i = 1, 2, …, MOD – 1. При этом seed(MOD) = 0. Фразу ‘Bad Choice‘ следует выводить, если  существует такое i, 1 £ i £ MOD – 1, что seed(i) = 0.

Реализация. Читаем входные значения STEP и MOD. Положим seed = 0. Совершим MOD – 1 итераций генерирования псевдослучайных чисел. Если хотя бы на одном этапе получится seed = 0, то все числа от 0 до MOD – 1 сгенерированы не будут и следует вывести ‘Bad Choice’. Иначе – ‘Good Choice‘.

while(scanf("%d %d",&step,&mod) == 2)

{

  seed = 0;

  for(i=0;i<mod-1;i++)

  {

    seed = (seed + step) % mod;

    if (!seed) break;

  }

  if (i == mod - 1) printf("%10d%10d    Good Choice\n\n",step,mod);

  else printf("%10d%10d    Bad Choice\n\n",step,mod);

}

Упражнение 3.2 [Вальядолид, 10683]. Десятичные часы. Вычислим, сколько миллисекунд в обыкновенной нотации приходится на одну миллисекунду в десятичной. Для этого следует поделить суммарное число миллисекунд в сутках в десятичной системе (оно равно 10 * 100 * 100 * 100) на число миллисекунд в обыкновенной (24 * 60 * 60 * 100). Далее следует вычислить число миллисекунд во входном традиционном  времени, умножить его на полученное выше соотношение и округлить до целого снизу. Полученное десятичное время следует выводить с ведущими нулями.

Пример. Соотношение между секундой в десятичной системе и секундой в обыкновенной системе равно 10 * 100 * 100 * 100 / 24 * 60 * 60 * 100 = 1.1574074. Для второго теста общее число миллисекунд равно 23 * 3600 * 100 + 59 * 60 * 100 + 59 * 100 + 99 = 8639999. Умножив его на выше полученное соотношение, получим 8639999 * 1.1574074 = 9999998,7785926. Округлив значение до целой части, получим 9999998. Это и есть соответствующее время в десятичной системе.

Реализация. Объявим необходимые переменные. В переменной TotalMiliSeconds содержится количество миллисекунд в сутках при стандартной записи времени, в переменной TotalDecSeconds – при десятичной. Переменная rate содержит их отношение.

int h,m,s,c,MiliSeconds;

int TotalMiliSeconds = 24*3600*100;

int TotalDecSeconds = 10*10000*100;

int Res;

double rate = (double)TotalDecSeconds / TotalMiliSeconds;

Читаем количество часов h, минут m, секунд s и миллисекунд c, вычисляем общее количество миллисекунд MiliSeconds в текущем времени в стандартной нотации и умножаем полученное значение на rate. Округляем его, выделяя целое число, и печатаем в формате с обязательным выводом ведущих нулей (если таковы имеются). Всего выводится 7 цифр, поэтому формат вывода будет "%07d".

while (scanf("%2d%2d%2d%2d",&h,&m,&s,&c) == 4)

{

  MiliSeconds = h*3600*100+m*60*100+s*100+c;

  Res = int(rate * MiliSeconds);

  printf("%07d\n",Res);

}

Упражнение 4.1 [Вальядолид 113]. Сила криптографии. Известно, что  =  =  = . В соответствии с ограничениями на числа n, p и k достаточно присвоить этим переменным тип double и вычислить  , что в языке С будет записано как exp(log(p)/n).

Пример. Рассмотрим третий тест:   = 1234.

Реализация. Читаем в цикле (пока не конец файла) значения n и p, вычисляем и печатаем значение .

while(scanf("%lf %lf",&n,&p) == 2)

{

  res = exp(log(p)/n);

  printf("%.0lf\n",res);

}

Упражнение 4.2 [Вальядолид 10509]. Обмануть Мистера Фреймана. Если  = a + dx, то n = (a + dx)³ = a³ + 3 * a² * dx + 3 * a * (dx)² + (dx)³. Если отбросить второе и третье слагаемое в правой части, то приближенно имеем равенство n = a³ + 3 * a² * dx. Отсюда dx = (n – a³) / 3a².

Пример. В первом тесте n = 1729.03, значит a = . = 12. dx = (1729.03 – 12³) / (3 * 12²) = (1729.03 – 1728) / 432 = 1.03 / 432 = 0.0001 * 10300 / 432 = 0.0024. Откуда  = a + dx = 12 + 0.0024 = 12.0024.

Реализация. Читаем входное значение n, вычисляем a =  =  = . Последнее выражение на языке С запишется как (int)(exp(log(n)/3) + 0.0000001). Перед взятием целой части следует добавить к exp(log(n)/3) некое малое значение eps = 0.0000001, чтобы избежать ошибки округления. Находим значение dx и выводим a + dx с четырьмя знаками после десятичной точки.

while(scanf("%lf",&n),n>0)

{

  a = (int)(exp(log(n)/3) + 0.0000001);

  dx = (n - a*a*a) / (3*a*a);

  printf("%.4lf\n",a+dx);

}

Упражнение 4.3 [Вальядолид 10773]. Назад к математике средней школы. Если направить вектор скорости лодки перпендикулярно течению реки, то достичь второго берега можно за минимальное время. В этом случае течение реки будет сносить лодку, однако скорость ее приближения к противоположному берегу будет максимально возможной и равной u м/с. Время пересечения реки равно d / u. В случае движения по кратчайшему пути лодку следует направить таким образом, чтобы равнодействующая ее скорости и скорости течения была направлена перпендикулярна течению реки. Тогда скорость приближения к берегу равна  и время пересечения реки равно d /

Два пути совпадут, если скорость реки равна 0, в этом случае необходимо вывести фразу “can’t determine”. Эту фразу следует также вывести, если скорость течения не меньше скорости лодки (v ³ u). Если скорость лодки равна нулю (u = 0), то неравенство v ³ u справедливо при любом v.

Пример. Рассмотрим входные данные для первого теста. Время пересечения реки за кратчайшее время равно 8 / 6 = 1.3333. Скорость приближения к берегу в случае движения по кратчайшему пути равно , время преодоления реки – 8 /   = 2.4121. Разность вычисленных времен с округлением до трех знаков после запятой равна 1.079.

Реализация. Читаем входные данные и проверяем условия, при которых не существует двух разных путей. Переменная q содержит номер текущего теста.

scanf("%lf %lf %lf",&d,&v,&u);

if ((v >= u) || (v == 0.0))

{

  printf("Case %d: can't determine\n",q);

  continue;

}

Переменной t1 присваиваем кратчайшее время переправы, переменной t2 – время переправы по кратчайшему пути. Находим их разность с учетом того, что t2 ³ t1 и печатаем результат с тремя точками после запятой.

t1 = d / u;

t2 = d / sqrt(u*u - v*v);

res = t2 - t1;

printf("Case %d: %.3lf\n",q,res);

Упражнение 4.4 [Вальядолид 10784]. Диагональ. Количество диагоналей выпуклого n – угольника равно n * (n - 3) / 2. Если n * (n - 3) / 2 = N, то n находим из квадратного уравнения n² - 3 * n - 2 * N = 0. Положительный корень уравнения равен

Остается округлить сверху вычисленное значение. Поскольку N £ 10¹⁵, то вычисления следует проводить, используя тип данных long long (__int64)

Пример. Рассмотрим второй тест. Для N = 100 получим

n =  = 16

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

  long long n,res;

  int cs=1;

  while(scanf("%lld",&n),n>0)

  {

   res = int(ceil((3 + sqrtl(9.0 + 8*n)) / 2));

   printf("Case %d: %lld\n",cs,res);

   cs++;

  }

[назад]