Задача 1.
Число вводится своим двоичным представлением (длина числа не
превышает 10000 двоичных разрядов). Необходимо определить делится
ли число на 15.
Задача 2.
Дано число в K-ичной системе счисления
a a ...a (K<=36).
n n-1 0
Найти остаток от деления его на m.
Числа K, n, m, как и остаток от деления на m, представляются
в десятичной системе счисления.
Задача 3.
Любое натуральное число N можно единственным способом
представить с помощью некоторых целых неотрицательных d[0], ... ,
d[s] в виде
N=d[s]*(s+1)!+d[s-1]*s! +...+d[1]*2!+d[0] (*)
при условии, что 0<=d[i]<=i+1, i=0,..,s, где d[s]<>0.
Дано s+1 натуральное число d[0], ..., d[s], и натуральное K,
s<200,d[i]<65535, K<65535. Найти остаток от деления числа N, опре-
деляемого в факториальной системе (*) числами d[0], ..., d[s], на
число K.
Задача 4.
Числа Фибоначчи U[1], U[2], ... определяются начальными зна-
чениями U[1]=1, U[2]=2 и соотношением
U[N+1] = U[N] + U[N-1].
Рассмотрим систему счисления с двумя цифрами 0 и 1, в кото-
рой, в отличие от двоичной системы весами являются не степени
двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой
системе счисления каждое положительное целое число единственным
образом представляется в виде строки нулей и единиц, которая начи-
нается с 1 и в которой нет двух единиц, стоящих рядом.
Даны две строки, представляющие числа A и B. Найти строку,
представляющую число A+B.
Пример. Исходные строки '10101' и '100' представляют числа
8+3+1=12 и 3. Ответом является строка '100010', представляющая
строку 13+2=15=12+3.
Примечание. Строки могут быть столь длинны, что числа A и B
превысят максимально допустимое в вашем компьютере целое число.
Задача 5.
Сосчитать количество единиц в двоичной записи числа i.
Задача 6.
Последовательность 011212201220200112... строится так: снача-
ла пишется 0, затем повторяется следующее действие: уже написанную
часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.
0 -> 01 -> 0112 -> 01121220 ->...
Составить алгоритм, который по введенному N, (0<=N<=3000000000)
определяет, какое число стоит на N-ом месте в последовательности.
Задача 7.
Дан массив X(100) и Y(100). Записать алгоритм, меняющий
последовательно местами значения элементов X(k) и Y(k) для этих
таблиц, для k=1,2,...,100, не используя промежуточных переменных.
Задача 8.
Точки с целочисленными координатами из 1-го квадранта помеча-
ются числами 0,1,2,... слева направо и снизу вверх таким образом,
что очередной точке приписывается минимальное число,отсутствующее
в вертикали и горизонтали,проходящей через точку. Первой помеча-
ется точка (0,0).
Написать программу, которая
1. По заданным координатам x и y, x>=0, y>=0, x,y- целые, оп-
ределяет пометку точки.
2. По заданной координате x и пометке точки y, x>=0, y>=0, x,
y - целые, определяет вторую координату точки.
Задача 9.
Найти длину периода и сам период бесконечной степенной дроби
по основанию Р, представляющей рациональное число N/M (для конеч-
ных дробей считать, что длина периода равна 1). M,N,P - целые
десятичные числа, 0<N<M, 1<P.
Задача 9.1.
Для введенных действительного числа r>0 и натурального числа
qmax необходимо найти наилучшее приближение r в виде рациональной
дроби p/q, где q<=qmax.
Задача 10.
Известно, что запись числа A в позиционных системах счисления
с основанием p и q имеет вид бесконечной периодической дроби с пе-
риодом 2:
A = O,(ab) = O,(ba) (*)
p q
где a и b - различные цифры в этих системах счисления.
Написать программу, которая для введенных натуральных чисел p
и q (2<=p,q<=30, p>q) находит и выводит все возможные пары значе-
ний цифр a и b, удовлетворяющих соотношению (*). Если таковых нет,
вывести сообщение 'Пригодных цифр нет'.
Предусмотреть защиту от ввода ошибочных данных.
Примечание: Значением числа, запись которого в позиционной
системе счисления с основанием S есть 0,cdef (где c,d,e,f - цифры),
являются
c d e f
--- + --- + --- + --- .
S^1 S^2 S^3 S^4
Задача 11.
Определим множества K[i] рекуррентно. Пусть K[0] = [0,1].
Разделим сегмент [0,1] на три части точками 1/3 и 2/3 и удалим из
него интервал (1/3,2/3). Получим множество K[1], состоящее из двух
оставшихся сегментов [0,1/3] и [2/3,1]. Каждый из них разделим на
три части (точками 1/9 и 2/9 для первого сегмента, и точками 7/9 и
8/9 - для второго ) и удалим средние интервалы (1/9,2/9) и
(7/9,8/9). Таким образом получаем множество K[2], и т.д. Пусть мы
построим множество K[i]. Поделим каждый оставшийся сегмент из K[i]
на 3 части и удалим из этих сегментов средние интервалы. Получим,
таким образом, из K[i] множество K[i+1].
Вводятся 3 целых числа n,a,b.
Необходимо определить, принадлежит ли точка с координатой
a/b множеству K[n].
Задача 12.
Найти наибольший общий делитель и наименьшее общее кратное
чисел a и b.
Задача 13.
Число называется совершенным, если оно равно сумме всех своих
делителей за исключением его самого. Любое четное совершенное
число представимо в виде
p-1 p
2 * (2 - 1), где р натуральное число.
Найти двоичное представление для максимального совершенного
четного числа меньшего введенного N.
Задача 14.
Заданы натуральные числа E,K,M,T в записи химической реакции
ХеАk + Y -> YmAt + X,
где A,X,Y - атомы или группы атомов. Написать алгоритм, который
находит такие натуральные коэффициенты, чтобы знак "стрелки" можно
было заменить знаком равенства.
Задача 15.
Вводятся целые числа a и b. Пусть у треугольника ABC коорди-
наты A=(0,0), B=(a,b), а обе координаты C=(x,y) - целые числа, и
площадь треугольника ABC не равна нулю.
Какую минимальную площадь может иметь треугольник ABC?
Задача 16.
Имеется N банок с целочисленными объемами V1, ..., Vn литров,
пустой сосуд и кран с водой. Можно ли с помощью этих банок налить
в сосуд ровно V литров воды.
Задача 17.
Вычислить число e (основание натурального логарифма) с точ-
ностью n значащих десятичных цифр после запятой. Можно использо-
вать числовой ряд:
e=1+1/1!+1/2!+...+1/А!...
Задача 18.
Вывести на экран число 2^n, n<=10000, n - натуральное.
Задача 19.
Определить количество повторений каждой из цифр 0,1,2,...,9 в
числе N^N (N в степени N), N <= 1000.
Задача 20.
Найти все простые числа, не превосходящие N.
Задача 21.
Вводится N. Необходимо найти, на сколько нулей оканчивается
N!=1*2*3*...*N.
Задача 22.
На входе программе даются два числа N и P. Программа на выхо-
де должна дать такое максимальное число M, что N! делится на P в
степени M, но не делится на P в степени M+1.
Примечание.
1.Числа N и P так велики , что нет смысла считать значение N!.
2.Числа N и P являются натуральными.
Задача 23.
Натуральное число N>1 представить в виде суммы натуральных
чисел так, чтобы произведение этих слагаемых было максимально.
Задача 24.
Задается любое положительное действительное число R.Найти по-
ложительные действительные R1,R2,...,Rn, Ri<4 ,i=1,...,n, такие,
что R=R1*R2*...*Rn=R1+R2+...+Rn
Задача 25.
Даны целые числа А(0),А(1),...,А(5). Найти множество корней
уравнения
А(5)*X^5 + А(4)*X^4 + ... + А(0) = 0,
если известно, что все корни - целые числа, A(0)<>0.
Задача 26.
Вывести в порядке возрастания все обыкновенные несократимые
дроби, заключенные между 0 и 1, знаменатели которых не превышают
15. Массив при этом заводить не следует.
Задача 27.
Дан многогранник, в вершинах которого записаны целые числа.
Одним ходом можно выбрать одно ребро, и к числу, записанному
в одном из его концов прибавить один, а из числа, записанного в
другом конце - вычесть 1.
Какому необходимому и достаточному условию должны удовлетво-
рять записанные числа, чтобы с помощью таких ходов можно было до-
биться, чтобы во всех вершинах был одновременно записан ноль? От-
вет обосновать.
Задача 28.
a). Полином
p(x)=A[n]*x^n+A[n-1]*x^(n-1)+ ... +A[1]*x+A[0]
задается своими коэффициентами A[n], ... ,A[0]. Найти его значение
P в точке x.
b). Число в k-ичной системе задается своим представлением
(A[n], ... ,A[0]),
т.е. в десятичной системе оно имеет значение
A[n]*k^n+A[n-1]*k^(n-1)+ ... +A[1]*k+A[0].
Найти это значение.
Задача 29.
n
Полином N-ой степени A(x) = SUM a[i] * x^i задается своими
i=0
коэффициентами a[i]. Найти коэффициенты b[i],i=0,...,n*m, m-ой сте-
пени полинома A(x). Числа n,m<=40.
Задача 30.
Вычислить коэффициенты A[1], A[2], ..., A[N]
многочлена
n n-1
P(x) =x + A[1]*x +...+ A[N-1]*x + A[N]
с заданными действительными корнями X[1], X[2], ..., X[N].
Задача 31.
n
Многочлен SUM a[i]*x^i задается набором своих коэффициентов
i=0
a[i], i=0,..,n. Необходимо вычислить коэффициенты b[i] такого мно-
гочлена, что
n n
SUM b[i]*x^i = SUM a[i]*(x+d)^i
i=0 i=0
для заданного d.
Задача 32.
Вычислить значение полинома
f(x)=ax^4+bx^3+cx^2+dx+e
для x=1, ..., 10000, используя не более 51000 операций *,+.
Задача 1.
Если вспомнить, что признаком деления на 9 в десятичной
системе счисления является делимость на 9 суммы цифр числа
(действительно, пусть есть число
S = a[n]*10^n + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].
S mod 9 = (a[n]*(10^n-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] +
+ ... + a[1]*(10-1)+a[1] + a[0]) mod 9
А так как 10^k - 1 делится на 9 нацело, то и
S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,
ч.т.д.), то аналогично получаем, что признаком деления на 15 в
системе счисления с базисом 16 будет делимость на 15 суммы
всех шестнадцатеричных цифр числа.
Мы разбиваем двоичное число справа налево на тетрады, ко-
торые однозначно можно преобразовать в шестнадцатеричные циф-
ры, находим их сумму и делим ее на 15. Если остаток 0, то вве-
денное число делится на 15, иначе - нет.
Задача 2.
Разумеется, можно непосредственно вычислить это число в
десятичной системе счисления, после чего разделить его на m,
но в этом случае придется представлять число в виде (например)
массива цифр и моделировать операции над этим числом. Сущест-
вует другой простой алгоритм.
В системе счисления с основанием K число представляется в
виде
a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0.
Найдем остаток от деления его на m (остаток от деления a
на b обозначим a mod b):
(a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0) mod m =
┌ n ┐ ┌ n ┐
=│ SUM a[i]*K^i│ mod m = │ SUM a[i]* (K^i mod m)│ mod m =
└ i=0 ┘ └ i=0 ┘
Это следует из следующих соображений: пусть K^i mod m=t,
тогда K^i =p*m+t, и
(a[i]*K^i) mod m = (a[i] * (p*m+t)) mod m =
= (a[i]* p*m) mod m + (a[i]*t) mod m =
= (a[i] * (K^i mod m)) mod m,
при этом для любых чисел b[i] выполняется
n n
( SUM b[i] ) mod m =( SUM b[i] mod m ) mod m.
i=0 i=0
Отметим также очевидное равенство
K^i mod m =[(K^(i-1) mod m) * K] mod m,
т.к. если K^(i-1) = p*m+t, то K^(i-1) mod m = t,
K^i = p*m*K+t*K и K^i mod m = t*K mod m =
= [(K^(i-1) mod m)*K] mod m.
Запись этого алгоритма (тут a[i] - K-ичные цифры числа):
s:=0; t:=1;
for i:=0 to n do
begin
s:=(s+a[i]*t) mod m;
t:=t*K mod m;
end;
В переменной S после окончания работы алгоритма будет
храниться искомый остаток.
Задача 3.
Задача решается также, как и предыдущая:
┌ s ┐
N mod K =│ SUM (d[j] mod K) * ((s+1)! mod K)│ mod K,
└ j=0 ┘
┌ ┐
где (s+1)! mod K = │ (s! mod k) * ((s+1) mod k)│ mod k,
└ ┘
Алгоритм запишется следующим образом:
остаток:=0;
faktorial:=1;
for i:=1 to s+1 do
begin
остаток:=(остаток+(d[i-1] mod k)*faktorial) mod k;
faktorial:=(faktorial * ((i+1) mod k)) mod k;
end;
В переменной остаток после выхода из цикла будет искомое зна-
чение.
Задача 4.
Воспользуйтесь тем, что
U[1] + U[1] = U[2], (1)
U[i] + U[i] = U[i] + U[i-1] + U[i-2] = U[1+1] + U[i-2], (2)
U[i] + U[i-1] = U[i+1]. (3)
Суммируем числа A и B поразрядно, используя приведенные выше
правила, начиная со старших разрядов. После применения любого из
правил опять начинаем просмотр числа со старших разрядов.
Проведем суммирование чисел '10101' и '100' из задачи.
10101
+ 100
-------
10 Первые два разряда просто сносятся,
+ 1001 затем применяем правило (2),
+ 01 и добавляем последние два разряда
+ 00 чисел A и B
-------
11001 Для двух первых разрядов применяем правило (3)
+ 01
+ 00
-------
100001
+ 01 Правило (1)
+ 00
------
100010
Задача 5.
Алгоритм следующий:
cnt:=0; cnt -- счетчик единиц в i.
while (i<>0) do цикл повторяется число раз, равное
begin числу единиц в i. " Убираем " край-
i:=(i-1) and i; нюю справа единицу в двоичной записи
cnt:=cnt+1; числа.
end; Пример: 110 = i
101 = i-1
------------------
100 = i and (i-1)
Задача 6.
Пусть a(k) - k-ый член последовательности.
Рассмотрим последовательность, формируемую по следующему пра-
вилу:
a(0)=0;
ряд
a(0)...a(2**k-1)
получаем приписыванием к этой последовательности справа этой же
последовательности, но при этом каждый член приписываемой части
увеличивается на единицу. Получаем
0->01->0112->01121223->...
Докажем, что a(k) есть сумма единиц в двоичном представлении
числа k.
Доказательство проведем по индукции. Для a(0)=0 это справед-
ливо. Пусть предположение справедливо для всех a(i),
0<=i<=2^(k-1)-1 (т.е. для всех чисел i, состоящих из не более чем
k-1-го двоичных разрядов). Тогда в двоичном разложении числа l,
2^(k-1)<=l<2^k, в k-ом разряде появляется добавочная единица, и
поэтому
a(l)=1+a(l-2^(k-1)),
ч.т.д.
Возьмем a(i) mod 3, и получим число, стоящее на i-ом месте в
последовательности, описанной в условии задачи.
Для того, чтобы найти a(i), необходимо, по доказанному,сосчи-
тать количество единиц в двоичной записи числа i - см. задачу 5.
Задача 7.
Будем менять местами содержимое переменных A и B. Сущест-
вует несколько способов сделать это.
1. Оператор Значение в A Значение в B
A:=A+B; A+B B
B:=A-B; A+B A
A:=A-B; B A
2. Можно использовать логическую операцию XOR (исключаю-
щее или). Таблица истинности для XOR следующая:
1 XOR 1 = 0 1 XOR 0 = 1
0 XOR 0 = 0 0 XOR 1 = 1
Операция XOR над двумя переменными в машине реализуется
как побитовая операция над двоичным представлением чисел. Поэ-
тому, в частности, A XOR A =
Оператор Значение в A Значение в B
A:=A XOR B A XOR B B
B:=A XOR B A XOR B (A XOR B) XOR B=
=A XOR (B XOR B)=
=A XOR 0 = A
A:=A XOR B (A XOR B) XOR A= A
= B XOR (A XOR A)=
= B
Задача 8.
Если рассмотреть битовые представления числа A[i,j], по-
мечающего точку (i,j) и чисел i и j, то обнаруживается, что
A[i,j]=i XOR j, откуда получается, что A[i,j] XOR i=j,
A[i,j] XOR j=i.
Покажем, что A[i,j]=i XOR j.
1) Число A[i,j]=i XOR j не встречалось еще ни в строке i,
ни в столбце j. От противного: существует такое j', что
i XOR j = i XOR j' => i XOR j XOR i = i XOR j' XOR i =>
=> j'=j;
2) Пусть существует такое k<i XOR j, что k=i XOR L =
= j XOR M, и k еще не встречалось в строке i и столбце j (на-
помним, что по предположению все остальные уже заполненные
элементы равны i XOR j, поэтому L>j и M>i).
Тогда, так как M>i, то существует бит с номером t такой,
что для любого R>t биты Mr и ir равны, t-ый бит Mt=1, it=0. Но
так как j XOR M < j XOR i, то Jt=1.
Так как L>j и L XOR i=j XOR M, то L = j XOR M XOR i.
Рассмотрим i XOR M. В силу вышесказанного для любого бита с
номером R, R>t, (i XOR M)r=0, а (i XOR M)t=1.
При этом Jt=1, следовательно
(i XOR j XOR M)r = Jr для r>t и
(i XOR j XOR M)t = 0 для r=t,
то есть L<j ?! Противоречие.
Задача 9.
Введем переменную N1=N.
Пусть N1 и M заданы в десятичной системе счисления. Пере-
ведем дробь N1/M в систему счисления с основанием p:
Пусть в системе с основанием p искомая дробь 0.a(1)a(2)...
Получаем:
a(1)*p^(-1)+a(2)*p^(-2)+ ... =N1/M.
Умножим правую и левую части равенства на p:
a(1)+a(2)*p^(-1)+ ... = N1*p/M.
Выделяя целую часть выражений слева и справа от знака ра-
венства, получаем
a(1) = целая часть (N1*p/M).
Обозначим N2 = N1*p mod M; очевидным образом получаем
a(2)*p^(-1)+ ... = N2/M.
Домножая на p и находя целую часть, опять же имеем
a(2) = целая часть (N2*p/M);
продолжая аналогично, определяем коэффициенты a(3), a(4) и т.д.
В ходе выделения цифр ai мы можем получить различных зна-
чений Ni не более чем M (по алгоритму выше у нас всегда Ni<M).
Если вдруг какие-то два остатка совпадают: Ni=Nj, i<>j,
то совпадают и цифры разложения: a(i+1)=a(j+1), a(i+2)=a(j+2),
... , т.е. цифры (a(i+1), ... ,a(j)) образуют один из кратных
периодов. Нам надо найти минимальную длину такой периодически
повторяющейся последовательности, которая равна количеству
цифр между двумя ближайшими повторяющимися остатками, и сами
цифры.
Поступаем следующим образом:
Выделяем M цифр p-ичной дроби (исходя из вышесказанного, к
этому моменту период уже обязан начаться). Запоминаем Nm, и
ищем первый такой остаток Nk, k>m, что Nm=Nk. Величина k-m как
раз и есть искомая длина периода.
Задача 9.1.
Алгоритм:
p:=0; q:=1;
metka:
if p/q < r then p:=p+1;
if p/q = r then stop;
if p/q > r then q:=q+1;
if q > qmax then stop;
goto metka;
PROGRAM ratap;
VAR p,q,qmax:integer;
d, r, min: real;
BEGIN
write('r,qmax='); readln(r,qmax);
p:=0; q:=1; min:=r;
REPEAT
IF p/q<r THEN p:=p+1 ELSE q:=q+1;
d:=abs(r-p/q);
IF d<min THEN BEGIN min:=d; writeln(p:7,'/',q) END
UNTIL (q>=qmax) OR (d=0);
readln; END.
Задача взята из книги "Еxploring mathematics with your
computer" by Arthur Engel (The Mathematical Association of
Задача 10.
Так как q<p, то цифры a и b должны лежать в пределах от 0
до q-1.
Распишем A в системе с основанием p:
a b a b 1 1
A = - + ─── + ─── + ─── + ... = ─── (ap+b) + ─── (ap+b)+
p p^2 p^3 p^4 p^2 p^4
+ ... = (ap+b)(p^(-2) + p^(-4) + ...) = { находим сумму бесконечно
убывающей геометрической прогрессии со знаменателем p^(-2)} =
p^(-2) ap+b
= (ap+b)─────── = ───── .
1-p^(-2) p^2-1
Аналогично для A в системе с основанием q выполняется
bq+a
A = ───── .
q^2-1
Получаем
(bq+a)(p^2-1)=(ap+b)(q^2-1)
a[p(q^2-1)-(p^2-1)]=b[q(p^2-1)-(q^2-1)].
Вычисляем выражения в квадратных скобках; обозначим их
соответственно u и v: au=bv.
Находим НОД(u,v)=s; обозначим r=u/s, f=v/s.
Получаем
ar=bf,
r и f взаимно просты, следовательно, решениями этого равенства
будут числа
a=fk, b=rk, k=1,2, ... ,
при этом мы берем только те a и b, для которых одновре-
менно выполняется
а) a<>b
b) a<r
c) b<r
Нахождение НОД - см. задачу 12.
Задача 11.
Очевидное решение: При попытке непосредственно вычислять коор-
динаты концов сегментов, принадлежащих множеству K[n], и опреде-
лить, принадлежит ли a/b одному из этих сегментов даже для не
слишком больших n за счет потери точности при вычислениях и из-за
ограниченного числа знаков в машинном представлении чисел с плава-
ющей точкой данный подход дает неверный ответ для большинства
входных данных. При больших n вообще будет наблюдаться потеря зна-
чимости: число при делении на 3 станет таким малым, что в машине
оно будет представляться нулем.
Рассмотрим другой метод решения этой задачи. Так как мы посто-
янно должны делить сегменты на три части, то это наталкивает на
мысль использовать троичную систему счисления и троичные дроби.
В первой из удаленных интервалов (1/3,2/3) попадают только
те точки
x=0.a[1] a[2] a[3] ...
в троичном разложении которых a[1]=1, кроме точки 1/3=0.1000... --
правого конца сегмента [0,1/3]. Таким образом, в K [1] остаются
все те точки, у которых a[1] <>1, либо a[1]=1, a[2] = a[3] = ...=
= 0. Аналогично, в множестве K[i], i>=0, содержатся точки, у кото-
рых ни одно из чисел a[j], 1<=j<=i, не равно 1, а также точки,
удовлетворяющие условию: a[j]=1, j - фиксировано, 1<=j<=i,
a[l]<>1, l<j, и a[l] =0 для любого l>j (то есть, в записи троичной
дроби только одна позиция равна 1, после нее все остальные позиции
нулевые. Эти дроби соответствуют правым концам сегментов из мно-
жества K[i]).
Запись алгоритма на Паскале имеет вид:
x:=a; i:=1;
while (i<=n) or (x<>1) or (a<>0) do
begin
a:=a*3 mod b;
x:=a*3 div b;
i:=i+1;
end;
if (x=1) and (a<>0) and (n<>0)
then writeln(' Не принадлежит')
else writeln(' Принадлежит');
Задача 12.
Как известно НОК(a,b)=ab/НОД(a,b).
Для нахождения НОД используем алгоритм Евклида. Будем обозна-
чать НОД(a,b) просто как (a,b).
Шаг алгоритма. Пусть a>=b (если это не так, то просто поменя-
ем содержимое переменных a и b местами).
Если b=0, то (a,b)=a, СТОП.
Иначе (a,b)=(a mod b,b).
Действительно, если g=(a,b), то он делит и a, и b, и остаток
r от деления a на b: a=bs+r, тут s - частное a div b, r = a mod b.
Покажите, что (a,b)=(r,b).
Обозначим через a величину a mod b. Снова выполним шаг алго-
ритма.
Существует и другой, более быстрый ('машинный') вариант на-
хождения НОД:
Для вычисления НОД воспользуемся следующими очевидными ра-
венствами:
1). (0,a)=a, (a,b)=(b,a)
2). (a,b)=(a-b,b)
3). Если a и b оба четны, то (a,b)=2*(a/2,b/2)
4). Если a четно, а b - нет, то (a,b)=(a/2,b)
5). Если a и b оба нечетны и a>b, то (a-b) - четное число,
при этом (a-b)<max{a,b} и (a,b)=(a-b,b).
Алгоритм :
Шаг 1. k:=1
Шаг 2. Пока a и b одновременно четны, выполняем
a:=a/2
b:=b/2
k:=k*2
Шаг 3. Если оба числа a и b нечетны,
то на место большего из них заносим разность его и
меньшего из чисел,
иначе,
если одно из чисел a или b четно,
то делим его на 2.
Шаг 4. Если одно из чисел (a или b) равно нулю,
то (a,b) равен произведению другого числа на k, и ал-
горитм завершает работу,
иначе перейти на шаг 3.
Задача 13.
p-1 p
Число вида 2 * (2 - 1), в двоичном представлении имеет р
единиц и р-1 нулей. Максимальное значение р определяется как
[(log N)/2]+1.
2
Затем проверяется является ли число совершенным для получен-
ного значения p. Оно является совершенным, если для простого зна-
p
чения p, число 2 -1 является простым. Если получили несовершенное
число, уменьшаем p на 1 и снова проверяем, является ли данное
число простым.
Совершенные числа получаются для значений р равных
2,3,5,7,13,17,19,31,61,89,107,127.
Задача 14.
Запишем уравнение в виде
sXeAk + pY = nYmAt + rX.
Приравнивая коэффициенты при X,A и Y, получаем:
X │ se=k
A │ p=nm (*)
Y │ sk=nt
Так как коэффициенты в формуле должны быть взаимно простыми,
то следует найти НОД чисел k и t (Задача 12). Пусть (k,t)=d. Тогда
s*(k/d)=n*(t/d), и числа k/d и t/d являются взаимно простыми, сле-
довательно, n=k/d, а s=t/d.
По (*) находим остальные коэффициенты.
Задача 15.
По заданным координатам трех вершин мы можем найти площадь
треугольника ABC
Sabc=(bx-ay)/2
Если a=0, то минимальная площадь Smin=b/2, если b=0, то
Smin=a/2. Если же обе координаты отличны от нуля, то из алгоритма
Евклида для нахождения НОД(a,b)=(a,b), следует существование таких
целых x и y, что ABS(bx-ay)=(a,b), и именно эти x и y минимизируют
площадь треугольника ABC.
Нахождение НОД - задача 12.
Задача 16.
Обозначим S=НОД(V1,...,Vn). Если V делится нацело на S, то в
сосуд с помощью банок можно налить V литров воды, иначе - нет.
Задача 17.
Заведем два массива: E[0..N+1] и S[0..N+1]. Элементы массивов
- байты. В E будем хранить текущую частичную сумму
e_n=1+1/1!+1/2!+ ... +1/(k-1)!, (*)
вычисленную с точностью N+1 знаков после запятой (в ячейке E[i]
хранится значение i-го разряда после запятой, то есть коэффициент
при 10^(-i)). В массиве S будет храниться последнее слагаемое
частичной суммы, т.е. 1/(k-1)! (опять же в S[i] находится i-я циф-
ра после запятой, все незначащие цифры, разумеется, нули).
Оценим погрешность формулы (*) c учетом равенства
e=1+1/1!+1/2!+ ... +1/(k-1)!+...
Погрешность представления числа е будет
F_n = e-e_n = 1/(n+1)! + 1/(n+2)!+ ...
= 1/(n+1)! * (1 + 1/(n+2) + 1/(n+2)(n+3) + ...)
< 1/(1+n)! * (1 + 1/(n+2) + 1/(n+2)^2 + ...)
1 1 1 n+2
= ────── ─────────── = ───── ────
(n+1)! 1-(n+2)^(-1) (n+1)! n+1
Т.к. F_450 < 10^(-10002), то для вычисления, например, 1000
знаков после запятой необходимо 450 итераций. По точности N и вы-
шеприведенной формуле вычисляем количество итераций С (можно взять
грубо С=N).
Будем делить число, представленное массивом S, на очередное
число k. Результат 1/k! прибавим к массиву E. Сложение реализуется
так:
perenos:=0; { перенос из предыдущего разряда }
for i:=N+1 downto 0 do
begin
E[i]:=E[i]+S[i]+perenos;
perenos:=E[i] div 10; { формируем новый перенос }
E[i]:=E[i] mod 10; { корректируем E[i] }
end;
Вычисление новых слагаемых и суммирование проводится С раз.
Рассмотрим процедуру деления S на k. Делить будем так, как
это обычно делается вручную - "столбиком":
m:=0; { m - текущее делимое, m - Longint }
for i:=0 to N+1 do begin
m:=m*10+a[i]; { дописываем к делимому сзади еще }
{ одну цифру }
a[i]:=m div k; { находим очередную цифру частного }
m:=m mod k; { и очередное делимое }
end;
Задача 18.
В переменной стандартного типа такое большое число не по-
местится. Будем моделировать возведение 2 в степень n вычисляя
последовательно 2^1, 2^2, ... , 2^n, используя массив. В каждой
ячейке массива будем хранить по (например) 4 десятичных цифры
числа (т.е. в элементе A[1] - 4 последних цифры числа (разряды 0 -
3), в A[2] - 4 предпоследних (разряды 4 - 7) и т.д.).
Оценим количество десятичных цифр в числе 2^n, n<=1000. Это
10 000 * log10 (2) + 1 < 15 000 цифр. Количество элементов массива
возьмем равным 15000/4=3750. Введем переменную Nach, в которой бу-
дем хранить индекс элемента массива A, в котором находятся старшие
значащие разряды вычисляемого сейчас числа.
var A: array[1 .. 3750] of word;
Nach: word;
i,N,j: word;
begin
for i:=2 to 3750 do A[i]:=0;
A[1]:=1; { сначала число в массиве A - это 2^0=1 }
read(N); { читаем степень }
Nach:=2; { индекс первой еще не использованной ячейки }
{ в массиве A }
for i:=1 to N do
begin
Perenos:=0; { перенос в следующий элемент массива A }
for j:=1 to Nach+1 do
begin
A[i]:=A[i]+A[i]+Perenos;
{ складываем 4 текущих разряда друг с другом, }
{ добавляя перенос из предыдущих 4-х разрядов }
if A[i]>=10000 { если в числе > 4 цифр }
then begin
Perenos:=A[i] div 10000; {то формируем перенос}
{ в старшие разряды }
A[i]:=A[i] mod 10000; { и оставляем в числе }
{ 4 последних цифры }
end
else Perenos:=0 { иначе переноса нет }
end; { к вложенному циклу for j }
if A[Nach+1]>0 { если был перенос в еще не }
then Nach:=Nach+1; { использованную ячейку }
{ массива A, то увеличиваем Nach }
end; { для цикла for i }
{ распечатка }
{ старшая тетрада печатается без ведущих нулей }
j:=1000; { ищем первую значащую цифру }
while (A[Nach] div j)=0 do j:=j div 10;
while j<>0 do begin
write(A[Nach] div j); { печать цифры }
A[Nach]:=A[Nach] mod j; { отбрасываем }
j:=j div 10; { напечатанную цифру }
end;
for i:=Nach-1 downto 1 do
begin
j:=1000;
for j:=1 to 4 do { 4 разряда }
begin
write(A[i] div j); { печатаем цифру }
A[i]:=A[i] mod j; { и отбрасывает ее }
j:=j div 10;
end
end
end. { программы }
Задача 19.
Решается, аналогично задаче 18, моделированием вычисления
N^1, N^2, ... , N^N.
Задача 20.
Можно просто каждое число S, 1<S<=N, делить на все предыдущие
натуральные числа k, 1<k<S, и если хоть один остаток от деления
равен нулю, то S - не простое. Пусть S - составное, S=ab, при этом
обязательно a<=SQRT(S), а b>=SQRT(S), так что для проверки просто-
ты S имеет смысл проверять не все значения делителя k от 2 до S, а
только k не превосходящее SQRT(S). Если число S - составное, то
его можно разложить в произведение простых чисел, поэтому, так как
мы уже нашли все простые числа меньшие S, то S имеет смысл делить
только на простые числа, не превосходящие SQRT(S). Если S>2, то
следует рассматривать только нечетные числа.
Алгоритм.
Пусть A - упорядоченное по возрастанию множество простых
чисел, сначала A={2,3}.
Пусть N>3.
Для S от 5 до N с шагом 2 повторять
Для всякого простого числа x<=SQRT(S) повторять
если остаток от деления S на x не равен нулю,
то S - простое, добавляем S в A
иначе S - составное.
Задача 21.
Мы можем представить N! в виде произведения простых сомножи-
телей:
N!=(2^A2)*(3^A3)*(5^A5)*(7^A7)*...,
где Ap - показатель степени, с которой простое число р входит в
разложение. Видно, что нулей в конце числа столько же, сколько ну-
лей в конце произведения (2^A2)*(5^A5), но так как, очевидно, что
A2>A5, то количество нулей равно A5.
Для того, чтобы найти A5, необходимо вычислить сумму
┌ N ┐ ┌ N ┐ ┌ N ┐
A5=│ ─── │ + │ ─── │ + │ ─── │ + (*)
└ 5^1 ┘ └ 5^2 ┘ └ 5^3 ┘ ... ,
┌ ┐
где │ │ -- целая часть числа,
└ ┘
т.к. каждое пятое число в произведении N! делится на 5, каждое
двадцать пятое число еще раз делится на 5, каждое 5^3 число, еще
раз делится на 5, и т.д. То есть в (*) мы находим, сколько чисел в
произведении N! делится на 5. Фрагмент программы выглядит следую-
щим образом :
k:=5;
s:=0;
repeat
s:=s+N div k;
k:=k*5;
until (k>N);
После работы цикла в переменной S будет находиться A5.
Задача 22.
Найдем простые множители числа P. Пусть это будут p1,...,
pk. Для каждого множителя pi найдем число si - степень, с ко-
торой pi входит в разложение P на простые сомножители. Как и в
задаче 21 найдем максимальные числа m1, ..., mk, такие что N!
делится на pi в степени mi, но не делится на pi в степени
mi+1.
Получаем для нахождения m следующее уравнение:
N! (p1^m1)*(p2^m2)*...*(pk^mk)*R
─── = ─────────────────────────────── ,
P^m ((p1^s1)*(p2^s2)*...*(pk^sk))^M
где R=N!/[(p1^m1)*(p2^m2)*...*(pk^mk)].
Минимальное из чисел mi div si и даст искомую степень M.
Рассмотрим пример: N=15, P=135.
P=3*3*3*5, p1=3, s1=3, m1=15 div 3 + 15 div (3*3)=6
p2=5, s2=1, m2=3.
Получаем, что M=min{6 div 3, 3 div 1}=2.
Объясните, почему мы не можем применить формулу
M=N div P + N div (P**2) + N div (P**3) + ... ?
Приведем полностью программу, реализующую этот алгоритм.
{ Условие задачи.
На входе программе даются два числа N и P. Программа на
выходе должна дать такое максимальное число M, что N! делится
на P в степени M, но не делится на P в степени M+1.
Примечание.
1. Числа N и P так велики, что нет смысла считать значение N!.
2. Числа N и P являются натуральными.
}
uses crt;
const
max_long = 2147483647;
var
n,p,i,stp,m,mn,km : longint;
flag : boolean;
ch : char;
{ Функция howmany считает, сколько раз в разложении числа n!
присутствует множитель mn.
}
function howmany(mn,n:longint):longint;
var
pr1,pr2,pr3 : longint;
begin
pr1:=mn; pr2:=0; pr3:=1;
while pr3<>0 do
begin
pr3:=trunc(n/pr1);
pr1:=pr1*mn;
pr2:=pr2+pr3
end;
howmany:=pr2
end;
{ Функция st находит степень множителя mn в разложении числа p
на простые множители.
}
function st(mn:longint; var n:longint):longint;
var
prom: longint;
begin
prom:=0;
while (n mod mn)=0 do
begin
inc(prom);
n:=n div mn
end;
st:=prom
end;
begin
clrscr;
while true do
begin
write('Введите число N и P => '); read(n,p); { ввод }
if p<>1 then { если p=1 то число m }
begin { не существует }
m:=max_long;
i:=2;
flag:=true;
repeat
stp:=st(i,p); { stp после присваивания будет равно числу }
if (stp<>0) then { вхождений множителя i в разложении числа p }
begin { на простые множители. Если stp<>0, то km }
{ будет равно числу вхождений множителя i }
km:=howmany(i,n); { в разложении числа n! на простые множители }
if (trunc(km/stp)<m) then { если km/stp меньше минимального отно- }
begin { шения, то сохраняем это значение. }
m:=trunc(km/stp);
if m=0 then flag:=false
end;
end;
if i=2 then i:=3 else inc(i,2);
until (i>p) or (not flag);
writeln('Число M равно ',m)
end
else
writeln('Число M не существует.');
write('Продолжить ? (y/n) ');
repeat
while keypressed do ch:=readkey;
ch:=readkey;
case ch of
'Y','y': writeln('y');
'N','n': begin writeln('n'); exit end
end;
until ch in ['N','n','Y','y'];
end;
end.
{ Описание задачи.
Если взять два любых натуральных числа a и b, то a будет делиться на b,
если все степени множителей при разложении числа a на простые множители
больше либо равны аналогичных степеней, получаемых при разложении числа b.
Пример :
120 = 2*2*2 * 3 * 5
40 = 2*2*2 * 5
120 делится на 40
Следовательно, n! делится на p в степени m, если степень любого прос-
того число mn (2<=mn<=p) в разложении числа n! на простые множители
больше, чем в аналогичном разложении числа p в степени m.
Если F(i,p) - степень простого числа i в разложении числа p на прос-
тые множители, то F(i,p^m)=F(i,p)*m.
Отсюда алгоритм решения :
степень m будет равна целой части от минимального отношения степени
простого числа i в разложении n! к степени числа i в разложении числа p,
где 2<=i<=p.
Алгоритм разложения числа р на простые множители достаточно прост.
Основную трудность представляет алгоритм разложения числа n!.
алгоритм степень_простого_числа_в_разложении_числа_n! (нат n,mn,s,k)
дано n,mn
надо s
нач
s:=0
k:=mn
пока [n/k]>0
нц
s:=s+[n/k]
k:=k*mn
кц
кон.
Задача 23.
Воспользуемся тем, что для n>=4 выполняется неравенство
n<=(n-2)*2, т.е. разбивать число на слагаемые, большие 3, не имеет
смысла. Выделяем из числа n слагаемые-двойки, пока не получим ос-
таток меньший либо равный 3 (остаток может быть либо 3, либо 2).
Так как 2*2*2<3*3, то заменим каждые три двойки на две тройки. По-
лученное разложение и является искомым.
Разберите самостоятельно случаи
1) когда необходимо максимизировать произведение, и слагаемые
в разложении числа n должны принадлежать промежутку [A,B], A и B
вводятся пользователем.
2) когда необходимо минимизировать произведение, и слагаемые
в разложении числа n должны принадлежать промежутку [A,B], A и B
вводятся пользователем.
Задача 24.
Если S>=4 то существуют единственные S1 и S2, такие что
S=S1*S2=S1+S2.
Более того, наименьшее из S1 и S2 больше 1 и <=2:
S1=(S-SQRT(S^2-4S))/2, S2=(
(S-4)^2=S^2-8S+16<=S^2-4S<(S-2)^2
и
1<S1=(S-SQRT(S^2-4S))/2<=2.
Итак, если r<4 то разложение на множители закончено, иначе
проводим разложение r на два множителя, один из них <=2 (и тем
более <4 ), если другой <4 , то процесс закончен, иначе повто-
ряем факторизацию S до тех пор, пока не получим искомое разло-
жение.
Задача 25.
Из теоремы Виета получаем, что
x1*x2*x3*x4*x5=-A(0)/A(5)
откуда следует, что число xi должно быть делителем A(0)/A(5). На-
ходим все делители A(0)/A(5)=R (Если A(0)=A(1)=...=A(i)=0, то i+1
корень уравнения равен 0. Мы делим уравнение на x^(i+1), дальше
ищем делители числа r=A(i+1)/A(5)).
i:=1;
пока i<=R повторять
если R делится нацело на i
то проверить, являются ли числа +i
и -i корнями полинома
i:=i+1
конец пока
Задача 26.
Пусть m/n - текущая несократимая дробь. Покажем, как найти
следующую по значению дробь. Понятно, что она будет среди несокра-
тимых дробей вида k/р, где р может принимать значения от 2 до 15.
Учитывая условие k/р > m/n можно для каждого р прямо вычислять ми-
нимальное значение k следующим образом:
k=m*p/n+1.
При этом каждая дробь k/р, полученная описанным выше образом,
несократима.
m:=0; n:=1
Повторять
i:=1; j:=1;
для р:=2 до 15 выполнять
нц
k:=m*p div n + 1;
если k*j < p*i
то i:=k; j:=p;
все
кц
m:=i; n:=j;
пока i>=j
Задача 27.
Это условие - равенство нулю суммы всех чисел. Мы всегда мо-
жем "перетащить" с помощью последовательности ходов все ненулевые
числа, помечающие вершины, в одну какую-либо вершину. Если сумма
всех чисел равна 0, то после этих ходов окажется, что во всех вер-
шинах записан 0.
Задача 28.
а). Программа вычисления следующая:
P:=a[N]
for i:=N-1 downto 0 do
P:=P*x+a[i];
Посмотрите, как эта схема работает, вручную найдя значение
полинома по его коэффициентам и точке x.
b). Решается аналогично.
Задача 29.
Продемонстрируем метод нахождения коэффициентов полинома
на примере возведения p(x)=(x**2+2*x+1) в четвертую степень.
Будем последовательно возводить полином в степени 2, 3,
4. Для второй степени справедливо равенство
p(x)*p(x)=(x^2+2x+1)*(x^2+2x+1)=(x^2+2x+1)*x^2+
+(x^2+2x+1)*2x+(x^2+2x+1)*1
Будем складывать коэффициенты у одинаковых степеней x,
выписывая коэффициенты полинома первой степени с соответствую-
щим сдвигом и умножаем на коэффициент:
x^4 x^3 x^2 x^1 x^0
───────────────────────────────────┐
1 2 1 │ x^2+2x+1
2 4 2 │ (x^2+2x+1)*2x
1 2 1 │ (x^2+2x+1)*x^2
───────────────────────────────────┘
1 4 6 4 1
Получили коэффициенты второй степени полинома. Для треть-
ей степени, поступая аналогично, получаем такую таблицу:
x^6 x^5 x^4 x^3 x^2 x^1 x^0
──────────────────────────────────────────┐
1 4 6 4 1 │ p(x)*p(x)
2 8 12 8 2 │ 2x*p(x)*p(x)
1 4 6 4 1 │ x^2*p(x)*p(x)
──────────────────────────────────────────┘
1 6 15 20 15 6 1
Коэффициенты 4-ой степени:
x^8 x^7 x^6 x^5 x^4 x^3 x^2 x^1 x^0
──────────────────────────────────────────────┐
1 6 15 20 15 6 1 │
2 12 30 40 30 12 2 │
1 6 15 20 15 6 1 │
──────────────────────────────────────────────┘
1 8 28 56 70 56 28 8 1
С произвольным полиномом поступаем так же: последователь-
но находим степени 2,3, ..., m. Когда мы знаем коэффициенты
полинома в степени i, то вычисляем коэффициенты степени i+1,
выписывая со сдвигом коэффициенты полинома степени i, умножен-
ные на соответствующие коэффициенты исходного полинома, а за-
тем складываем их в столбик.
Задача 30.
Решается аналогично предыдущей задаче. Рассмотрите полином
p(x)=(x-A[1])*...*(x-A[N])
и вычислите его коэффициенты. На каждом из шагов, в отличие от
предыдущей задачи, умножение будет производиться на новый одночлен
(x-A[i]).
Задача 31.
Рассмотрим следующую задачу:
Разделить полином p(x)=a[n]*x^n + ... + a[1]*x+a[0] на
v(x)=(x-d), т.е. найти такую константу - остаток r и такое частное
s(x)=s[n-1]*x^(n-1)+ ... + s[1]*x+s[0], что
p(x)=s(x)v(x)+r.
Делить будем в столбик. Рассмотрим операцию деления полиномов
на примере:
3x^2+2x+5 │x-2
3x^2-6x └──── Тут r=21, s(x)=3x+8.
─────── 3x+8 Видно, что коэффициент s[n-1] при
8x+5 старшей степени x в s равен коэф-
8x-16 фициенту при старшей степени x в
───── p, а остальные коэффициенты в s
21 находятся по формулам:
s[t-1]=(-d)*s[t]+p[t];
r=(-d)*s[0]+p[0].
В наглядной форме это можно записать в виде так называемой
схемы Горнера:
p[n] p[n-1] ... p[1] p[0]
┌────────────────────────────────────────────────────────
-d │s[n-1]=p[n] ... s[0]=-d*s[1]+p[1]
│ s[n-2]=-d*s[n-1]+p[n-1] r=-d*s[0]+p[0]
Тогда проведенное выше деление можно записать в следующем ви-
де:
3 2 5
┌───────────────┬─────┬─
2 │ 3 8 │ 21 │ <- остаток
│ └─────┘
Тут 3 сносится, 8=2*3+2, 21=2*8+5.
Вернемся к исходной задаче. Приравняем полиномы:
p0(x)=a[n]*x^n+a[n-1]*x^(n-1)+ ... +a[1]*x+a[0]=
=b[n](x-d)^n+ ... +b[1]*(x-d)+b[0].
Находим остаток от деления полиномов справа и слева от знака
равенства на (x-d). Слева все слагаемые, кроме последнего, делятся
на (x-d) нацело. Поэтому
p0(x)=(x-d)*p1(x)+b[0].
Получаем, что
p1(x)=b[n]*(x-d)^(n-1)+ ... +b[2]*(x-d)+b[1].
Аналогично находим b[1]:
p1(x)=(x-d)*p2(x)+b[1],
затем по p2(x) определяем b[2], и т.д., пока не найдем b[n].
Особенно удобно это записывается в виде схемы Горнера (обра-
тите внимание, что в верхней строке записаны коэффициенты p0, то,
что получается в строке ниже - это коэффициенты p1, к которым так-
же можно применить схему Горнера, находя коэффициенты p2, и т.д.)
Пример: p(x)=3x^2+2x+5, d=-2,
3 2 5
┌─────────┬────┐
2 │ 3 8 │ 21 │ =b[0]
│ ┌────┼────┘ 14=2*3+8
2 │ 3 │ 14 │ =b[1]
├────┼────┘
2 │ 3 │ =b[2]
└────┘
Получаем
3x^2+2x+5=3(x-2)^2+14(x-2)+21.
Задача 32.
Пусть f(x)=ax^4+bx^3+cx^2+dx+e. Выразим f(x+1) через f(x):
f(x+1)=f(x)+(4ax^3+(6a+3b)x^2+(4a+3b+2c)x+(a+b+c+d)=f(x)+g(x),
где
g(x)=Ax^3+Bx^2+Cx+D.
Поступим аналогично и с g(x):
g(x+1)=g(x)+(3Ax^2+(3A+2B)x+(A+B+C))=g(x)+h(x), где
h(x)=A'x^2+B'x+C'.
Далее:
h(x+1)=h(x)+(2A'x+(A'+B'))=h(x)+p(x),
где
p(x)=A"x+B". p(x+1)=p(x)+A".
Имеем:
f(x+4)=f(x+3)+g(x+3)
g(x+3)=g(x+2)+h(x+2)
h(x+2)=h(x+1)+p(x+1)
p(x+1)=p(x)+A".
Отсюда получаем фрагмент программы:
< BLOCK 1 >
x:=5;
repeat
P:=P+A2;
H:=H+P;
G:=G+H;
F:=F+G;
writeln(x,F);
x:=x+1;
until x=10001;
Итак, на каждое значение, начиная с 5, тратится 5 операций
сложения. Остается около 1000 операций на вычисление f(1), f(2),
f(3), f(4), для инициализации
P:=p(1); H:=h(2); G:=g(3); (F:=f(4));
и на вычисление A2:=A". Ясно, что 1000 операций хватит на все эти
вычисления.