Информатика в школе


Видео курсы для чайников фотошоп, joomla, wordpress, php, css 
  Главная  ●  Карта сайта
 
 

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

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

[назад]

 

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).

https://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. Найти количество единиц в минимальном таком числе.

Пример входа

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

3

7

9901

3

6

12

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

Построим последовательность чисел a1 = 1, ai = (10*ai-1 + 1) mod 10. ai содержит остаток от деления числа, состоящего из i единиц, на n. Как только для некоторого i значение ai станет равным 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 * 109.

 

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

 

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

 

Пример входа

n

99

268

86898

 

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

2

4

7

 

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

 

Класс: ReverseSums

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

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

 

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

 

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

 

Пример входа

n

1325

100

1

 

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

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. Например:

число

сумма цифр

конкатенация цифр

26

2 + 6 = 8

68

68

6 + 8 = 14

84

84

8 + 4 = 12

42

42

4 + 2 = 06

26

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

 

Класс: AdditionCycles

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

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

 

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

 

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

 

Пример входа

n

26

55

0

 

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

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 £ 1018). Последняя строка содержит 0 и не обрабатывается.

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

Пример входа

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

18

19 20

0

 

 

Упражнение 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

Case 1: 9

1

Case 2: 8

5

 

3

 

5

 

 

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

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

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

Пример входа

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

-3

-5

 

 

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

 

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

 

тип

формат

int

%<n>d

float

%<n>.<m>f

double

%<n>.<m>lf

 

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

 

переменная

формат вывода

выводимое значение

int a = 456

%1d

456

int a = 456

%3d

456

int a = 456

%5d

  456

float f = 34.1223

%3.2f

34.12

float f = 34.1223

%7.3f

 34.122

float f = 34.1223

%8.4f

 34.1223

float f = 34.1223

%9.4f

  34.1223

double d = 1.123456789

%5.3lf

1.123

double d = 1.123456789

%7.5lf

1.12346

double d = 1.123456789

%12.9lf

 1.123456789

double d = 1.123456789

%15.11lf

  1.12345678900

 

Если <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, следующие строки описывают матрицу. Необходимо найти сумму всех чисел матрицы.

Пример входа

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

3

111

222

333

18

 

Для чтения однозначных чисел следует воспользоваться форматом “%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 5

         3         5    Good Choice

15 20

 

63923 99999

        15        20    Bad Choice

 

 

 

     63923     99999    Good 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. Значение десятичного времени следует округлить вниз.

Пример входа

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

00000000

0000000

23595999

9999998

12000000

5000000

14273467

6024846

02475901

1166552

 

 

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

 

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

#include <math.h>

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

 

функция

вызов функции

квадратный корень,

sqrt(x)

степень числа, xn

pow(x,n)

экспонента, ex

exp(x)

натуральный логарифм, ln x

log(x)

десятичный логарифм, lg x

log10(x)

модуль целого числа, |x|

abs(x)

модуль действительного числа, |x|

fabs(x)

 

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

 

функция

вызов функции

синус, sin(x)

sin(x)

косинус, cos(x)

cos(x)

тангенс, tg(x)

tan(x)

арксинус, arcsin(x)

asin(X)

арккосинус, arccos(x)

acos(x)

арктангенс, arctg(x)

atan(x)

 

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

const double PI = acos(-1);

 

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

 

функция

вызов функции

округление вверх,

ceil(x)

округление вниз,

floor(x)

 

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

xn =  =

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

 =  =  =

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

 

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

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

Выход. Для каждой пары чисел 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)2 = a2 + 2 * a * dx + (dx)2. Если значение dx мало, то при приближенном вычислении слагаемое (dx)2 можно не учитывать, то есть можно положить что n = a2 + 2 * a * dx. Здесь dx = (na2) / 2a. В задаче требуется построить аналогичную схему для вычисления приближенного значения кубического корня.

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

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

Пример входа

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

1729.0300
12.0024

64.0000

4.0000

63.9990

4.3703

0

 

 

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

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

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

Пример входа

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

3

Case 1: 1.079

8 5 6

Case 2: 0.114

1 2 3

Case 3: 0.135

1 5 6

 

 

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

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

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

Пример входа

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

10

Case 1: 7

100

Case 2: 16

1000

Case 3: 47

0

 

 

 

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

 

Упражнение 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 * 109, то произведение цифр числа 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 = (na) / 9. Очевидно, что искомым будет N = 10 * X + a = 10 * (na) / 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)3 = a3 + 3 * a2 * dx + 3 * a * (dx)2 + (dx)3. Если отбросить второе и третье слагаемое в правой части, то приближенно имеем равенство n = a3 + 3 * a2 * dx. Отсюда dx = (na3) / 3a2.

Пример. В первом тесте n = 1729.03, значит a = . = 12. dx = (1729.03 – 123) / (3 * 122) = (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 находим из квадратного уравнения n2 - 3 * n - 2 * N = 0. Положительный корень уравнения равен

Остается округлить сверху вычисленное значение. Поскольку N £ 1015, то вычисления следует проводить, используя тип данных 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++;

  }

 

 

 

[назад]

Книжные новинки
Как сделать свой сайт и заработать на нем Е. Мухутдинов
Копилка
Рабочие программы
Проекты MS Office
Презентации
Открытые уроки
Экзаменационные билеты
Элективные курсы
Бесплатный soft
 Инструкции по ТБ
Подготовка к олимпиадам по информатике
Методика подготовки
"Золотые" алгоритмы
Простые задачи для начинающих
Олимпиадные задачи с решениями
Книги
Среда программирования
Обучение программированию на С++
Справочник по языку Pascal
Обучение
Подготовка к ЕГЭ
Создание сайтов
Уроки FrontPage
Уроки Word 2003
Создание игр на Delphi
Печатаем вслепую

Информация

Наши интервью
Книга почета
Курсы повышения квалификации
Электронная библиотечка
Книжная полка
Статьи
Полезные ссылки
Обратная связь

Конкурсы

Олимпиада
Фотоконкурс
VIP
Персональный раздел профессора
Макаровой Н.В.
Персональный раздел профессора
Смыковской Т.К.