- •2008 № I информатика
- •2008 № 4 Информатика
- •2. Статья "Частотный анализ"
- •1. Общие вопросы
- •2. Особенности выполнения рекурсивных алгоритмов
- •3. Рекурсивные функции и процедуры для обсуждения
- •2008 Nt 5 информатика
- •4. Задания на использование рекурсии
- •2008 № 5 Информатика
- •2008 N» 5 информатика
- •2008 N» 5 информатика
- •2008 № 5 Информатика
- •5. Прямая и косвенная рекурсия
- •5. Формы рекурсивных процедур6
- •2008 № 5 Информатика
2008 № 4 Информатика
for i : '■ to n do
read(x[i]); for i := 0 to n - 1 do begin
1 := ( (x[i + 1) - x[i) ) -u • v - (xU ! ■
x[i + 1]))/2;
if 1 > maxl then maxl :- 1 end;
write(maxl:0:4) end. Задача "Последовательность"
Дана последовательность, состоящая на 2N натуральных чисел. Известно, что все числа этой последовательности можно разбить на пары таким образом, что сумма чисел во всех парах будет одинаковой. Например, числа последовательности 99, 23, 77, 1 можно разбить на пары 1 + 99 = 77 + 23.
Напишите програллму. которая по такой последовательности определяет, можно ли эту последовательность разбить на пары таким образом, чтобы произведение чисел во всех парах было одинаковым.
Формат входных данных
Первая строка содержит натуральное число М — количество тестов в файле. Первая строка каждого теста содержит число 2N — количество чисел в последовательности. В каждой из последующих 2N строчек содержится целое число от 1 до 10" — элементы последовательности (1 < N < 50 000).
Формат выходных данных
Ответом на тест является символ 1, если входную последовательность можно разбить на пары, произведения в которых были бы одинаковыми, и 0 в противном случае. Ответ на каждый тест следует выводить в отдельной строке.
Пример
Входные данные |
Выходные данные |
2 |
0 |
4 |
1 |
99 |
|
23 |
|
77 |
|
1 |
|
2 |
|
1 |
|
10101 |
|
Решение
Нам необходимо научиться решать задачу для одного теста, а затем просто запустить это решение для всех М тестов.
Обозначим сумму чисел за X. Допустим, у нас есть две разных пары чисел (У, X — У) и (Z, X — Z). Произведения этих чисел также должны быть равны, т.е.
Перенесем Л" п левую часть:
X х (V - Z) - (YJ - Z") - (У + Z)x (У - Z). По поставленному нами условию Y*Z. а значит, мы можем разделить обе части на (Y-Z), после чего получим равенство Л ~ Z + У , т.е. У и Z образуют пару, что противоречит поставленному условию (пары должны быть различны).
Таким образом, мы от противного доказали, что не существует двух таких различных пар. Значит, пара должна быть всего одна. По поставленному условию нам известно, что все числа можно разбить на пары с равной суммой, а значит, нам достаточно проверить, что в тесте встречается не более двух различных чисел. Будем делать это следующим образом: заведем массив из двух элементов, в котором будем хранить встретившиеся числа. Если очередное число уже есть в массиве, то не будем предпринимать никаких действий, иначе добавим его в массив. Если количество элементов в какой-то момент стало больше двух, то следует запомнить, что ответ должен быть 0 и считать оставшиеся числа массива, следя, чтобы нигде не произошло выходов за пределы .массива.
Один из вариантов такой реализации приведен ниже: var
х : array[1..2] of longint; nownum, m, n, i, j, k, с : longint; flag, bad : boolean; begin
read(m);
for k := 1 to m do begin // идем по всем тестам read(n);
nownum := 0; // пока нет встретившихся чисел bad := false;
// ничего плохого не случилось for i := 1 to n do begin read(c); flag := false; // не нашли среди имеющихся
for j := 1 to nownum do // идем по имеющимся
if x[j] = с then
flag :■= true; // нашли if not flag then begin //не нашли
inc(nownum); // увеличиваем количество встретившихся различных
if nownum > 2 then begin // больше двух
dec (nownum); // чтобы не выйти за пределы - уменьшим
bad := true
// случилось плохое - переполнились end
х[nownum] := с; // запомним, что за число встретили
end end;
if bad then writeln(O) // выводим ответ
else writeln(1) end end.
38
200В N« I Ш1<1Н)РМЛШК\
•jf
-ли ivixu гдков, 4iv iwe civ населенно, cikvoulv лито. »u kukivm "тур--"' н.кп'чит
ciuevb нл велосипеде, составляет 0.1,5 тысячи, то п j\ic-смат^ваемьт момент, т.е. на S-м "t\]V '. лапши да^ж-iu иссякнлтк Все окол»лпсь втянутыми в нее. Но оОла-д;»ет велоснпед;1Л1П 1\\\ько пят-ая ч;1сть, у ост.иьных же
■имеются iu руках ou.\eTi,i, которые некому сбытк
Задание для самостоятельной работы
1 Кчюлклуя электронную таблицу Microsoft Excel или p;U]Xil4»T.iB компьютерную программу, опреде-
п области, п которой число лкчмпч-леп пс.мкипс von" сост.пинет 1.5 ми«. чслопск. и п лкударстве. ..._...... ..^.„..„ruv^nia- колпчсспю p:,nuo .V) мл..
Литература
1. Пср-льмм ЯМ. Злннметслы...». м.мем.пнк.1. М, Им^тельство Русаном, 1е' '"'■
к заданиям,
опубликованным в газете "В мир информатики" № 96 ('Информатика" №20/2007)
1. Статья "Гармонические числа"
Если бы нужно оыло Bbi4itc,v>m. он:А\\1*ныс значения гармонических чисел, то для этого можно было применить .«обую и.< двух функций, приведенных п статье. Но поскольку в условии требовалось получить ряд пос\еловате.\ьных глр.«оническ1с< чнсе.\. целесообразно для расчета очередного значения использовать
ганее вычисленное (имея в виду, что Н ^ Н _, + —):
" ' п адг ~=.рмс нач пед i
JJCJHUC -.
Здесь также целесообразно для расчета очередного значения использовать ранее вычисленные значения. Каких именно величин — видно из следующей программы:
адг . 5смонические_ч;:с-~5 нач пел числ, знам, i
ч.'-гг. := 1 [Числитель дроби знам := 1 |Знаменатель !Выводим первую строку значений вывод не. I, числ, "/", энам нп для i qt 2 до 10
I Вычисляем числитель и знаменатель ;очередной простой дроби числ := числ * i + знам знам := знам » i
Выводим новые значения вывод нс. i, числ, "/", знам '■ S3 кон
В особенностях расчета "новых значений вел. чин Ч1«:\ и .шли разберитесь самостоятельно. И ей;. В приведенной программе есть существенный нел. CTaixiK. Какой'-
Програмл\ы npuc.va.Mi:
— Баженов Василий и Баженов Muxaiu. средняя школа села Горелом Тамбовской обл.. учитель Шитова Л.А.;
— Ветлугин Денис, средняя школа села Татарское. Дальне-Константнновский р-н Нижегородской обл.. учитель Салова Т.В.;
— Деминцев Борис, средняя школа села Сердар, Республика Марий Эл. учитель Чернова Л.И.;
— Максимова Наталья, село Ни коло-Берёзовка, Республика Башкортостан. Краснокамский р-н, школа № 1. учитель Ситдикова А.Г.;
— Яценко Иван, средняя школа села Кубайка, Красноярский край, учитель Чудов Н.А.