10145. Возрастающие синусы

Найдите и выведите такие n целых чисел x₁, x₂, ..., x_n, что последовательность их синусов является строго возрастающей, то есть

sin(x₁) < sin(x₂) < ... < sin(x_n)

Вход. Одно натуральное число n (n ≤ 10⁴).

Выход. В одной строке выведите последовательность целых чисел x₁, x₂, ..., x_n, удовлетворяющих условию задачи. Значения каждого числа по модулю не должны превышать 2³¹ – 1 (|x_i| < 2³¹).

Пояснение. Для приведенного примера неравенство sin(-8) < sin(0) < sin(9) < sin(1) справедливо, так как оно эквивалентно -0.989 < 0 < 0.412 < 0.841.

Пример входа	Пример выхода
4	-8 0 9 1

РЕШЕНИЕ

математика

Анализ алгоритма

Конструктивно построим требуемую последовательность. Поскольку синус является периодической функцией с периодом 2π, будем искать ее в виде sin(k(2π + ɛ)), где k = 0, 1, 2, … . Найдем такое натуральное число A, для которого существует целое k, что A = 2πk + ɛ для как можно меньшего значения ɛ. Например, если перебрать A от 1 до 1000, то наименьшее ɛ достигается при A = 710. В этом случае 710 ≈ 2π * 113 + 0.00006028.

Пусть A = 710. Рассмотрим последовательность

sin(A), sin(2A), sin(3A), …, sin(nA)

Значения элементов этой последовательности равны

sin(2π * 113 + ɛ), sin(2*2π * 113 + 2*ɛ), sin(3*2π * 113 + 3*ɛ), …,

sin(n*2π * 113 + n*ɛ)

или с учетом периодичности эти значения эквивалентны

sin(ɛ), sin(2*ɛ), sin(3*ɛ), …, sin(n*ɛ)

Функция sin(x) на промежутке x ∈ [0; π/2] является возрастающей. Для того чтобы последовательность вышеуказанных действительных чисел была мнонотонно возрастающей, достаточно выполнения неравенства: n*ɛ ≤ π/2. Подставив n = 10000 и ɛ = 0.00006028 получим: 10000 * 0.00006028 ≤ π/2 или 0.6028 ≤ 1.57, что верно. Таким образом, данным методом можно найти 10⁴ требуемых целых чисел.

Реализация алгоритма

Читаем входное значение n.

scanf("%d", &n);

На отрезке [1..1000] находим такое натуральное число А, для которого при представлении в виде A = 2πk + ɛ значение ɛ будет наименьшим.

bestA = 0;

bestE = 2 * PI;

for (a = 1; a < 1000; a++)

{

e = fmod(a, 2.0 * PI);

if (e < bestE)

{

bestE = e;

bestA = a;

}

}

Значение x = bestA будет равно 710.

x = bestA;

Выводим искомую последовательность: 0 * 710, 1 * 710, 2 * 710, …, (n – 1) * 710.

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

printf("%d ", x*i);

printf("\n");