KM208(a). Наибольшая разность чисел последовательности

Задача

Известно, что разность между наибольшим и наименьшим из вещественных чисел [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_{10}[/latex] равна [latex]1[/latex]. Какой наибольшей может быть разность между наибольшим и наименьшим из [latex]10[/latex] чисел [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_{10}}{10}[/latex]?

Каков будет ответ, если чисел не [latex]10[/latex], а [latex]n[/latex]?

Входные данные

Количество элементов последовательности [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_n[/latex].

Выходные данные

Наибольшая разность наибольшего и наименьшего элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n} {n}[/latex].

Тесты

Входные данные Выходные данные
2 0.5
4 0.75
6 0.833333
8 0.875

Код программы

Решение задачи

Выведем формулу сразу для [latex]n[/latex] чисел. Сделаем несколько предварительных замечаний.

Обозначим через [latex]y_k[/latex] число [latex]\frac{x_1+x_2+ \ldots+x_k}{k}[/latex], где [latex]k=1, 2, 3, \ldots, n[/latex]. Если прибавить ко всем [latex]x_i[/latex] некоторое число [latex]a[/latex], то вместо чисел [latex]y_i[/latex] мы получим числа [latex]y_i+a[/latex]. Максимальные разности для чисел [latex]y_i[/latex] и для [latex]y_i+a[/latex] совпадают. Поэтому от набора [latex]f\{x_i\}[/latex] с помощью подходящего выбора [latex]a[/latex] можно перейти к такому набору [latex]f\{x_i’\}[/latex], что все [latex]x_i’\le0[/latex], наименьшие [latex]x_i[/latex] равны нулю, а наибольшие — единице. В дальнейшем мы будем рассматривать только такие наборы. Аналогично, если заменить числа [latex]x_i[/latex] на [latex]1-x_i[/latex], то [latex]y_i[/latex] заменятся на [latex]1-y_i[/latex]. Следовательно, от набора [latex]f\{x_i\}[/latex] можно перейти к набору [latex]f\{1-x_i\}[/latex]: максимальные разности между числами [latex]y_i[/latex] и числами [latex]1-y_i[/latex] одинаковы.

Решим задачу. Пусть [latex]y_k[/latex] — наименьшее, а [latex]y_t[/latex] — наибольшее из чисел [latex]f\{y_i\}[/latex].

Если [latex]k<l[/latex], то [latex]y_l-y_k=\frac{k y_k}{l}+\frac{x_{k+1}+\ldots+x_l}{l}-y_k[/latex][latex]=\frac{x_{k+1}+\ldots+x_l}{l}-\frac{l-k}{l} y_k[/latex][latex]\le\frac{x_{k+1}+\ldots+x_l}{l}\le\frac{l-k}{l}\le1-\frac{k}{l}\le1-\frac{1}{n}[/latex]

Если же [latex]k>l[/latex], то [latex]y_l-y_k=\frac{k-l}{k} y_l-\frac{y_{l+1}+\ldots+y_k}{k}\le1-\frac{l}{k}\le1-\frac{1}{n}[/latex].

Из вышесказанного следует, что максимальная разность не больше [latex]1-\frac{1}{n}[/latex]. Набор с такой разностью можно легко указать: [latex]x_1=0[/latex], [latex]x_2=x_3=\ldots=x_n=1[/latex].

Л. Г. Лиманов
Научно-популярный журнал «Квант», 1974 год, №3, страницы 38-39.

Итог:
Формула, которую необходимо использовать для решения этой задачи, это [latex]D=1-\frac{1}{n}[/latex], где D — наибольшая разность элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n}{n}[/latex], а [latex]n[/latex] — их количество.

Ссылки

ML 1

Радик Сиденко
Радик Сиденко

Latest posts by Радик Сиденко (see all)

Условие задачи:

Даны два действительных числа [latex]a[/latex] и [latex]b[/latex]. Получить их сумму,  разность и произведение.

Код №1

Тесты

a z b sum
5 + 6 11
7 8 -1
9 * 11 99

 

Решение №1

Для создания данной программы я описал 4 переменных: [latex]a[/latex], [latex]b[/latex], [latex]z[/latex],  sum.  Для переменных [latex]a[/latex],  [latex]b[/latex],  [latex]sum[/latex] я взял тип переменных «long double» — так как не указано какие числа должны быть. Символом z мы обозначим переменную в  типе «char» —  так как мне надо указать знак операции. Для вычисления суммы надо ввести знак операции «+»,  для разности «-» и для произведения  «*»  выглядит все примерно так мы вводим (первое число «[latex]a[/latex]») (знак «[latex]z[/latex]» ) (второе число «[latex]b[/latex]») и получаем (ответ «[latex]sum[/latex]»).

 

Код №2

 

Решение №2

Это не то, что просили сделать изначально,  но я думаю это тоже будет интересно.

Отличие от первого кода состоит в том, что я добавил дополнительные команды,  а именно:  деления «/»,  возведения в степень «^»  и остаток от деления «%».

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

Ссылки

Условие задачи;
Код программы №1 на Ideone.com;
Код программы №2 на Ideone.com;

А1

Питон Пайтон
Питон Пайтон

Latest posts by Питон Пайтон (see all)

  • А1 - 15/09/2014

Задача. Даны два действительных числа [latex]a[/latex] и [latex]b[/latex]. Получить их сумму, разность и произведение.

[latex]a[/latex] [latex]b[/latex] [latex]a+b[/latex] [latex]a — b[/latex] [latex]ab[/latex] Комментарий
 0  0  0 0.0 0.0 Пройден
 1 2  3.0 -1.0  2.0 Пройден
 100.3 1000.0001  1100.3001  -899.7001  100300.01003 Не пройден из-за ошибки округления
 1.2e2  -2.2e2  -100  340  -26400 Пройден
 1.2e22  -2.2e22  -1e22 3.4e22  2.64e44 Пройден
1e308 1e308 1e308 0 1e616 Не пройден — превышено макс.значение

Диапазон тестов нужно подобрать так, чтобы произведение не выходило за допустимые значение для данного типа. Иначе получаем inf — бесконечность.
Если разница в порядках чисел велика (например, 1e38 и 1e-38), то при сложении и вычитании меньшее по абсолютной величине игнорируется.

Код программы:

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