Задачи для самостоятельного решения
- 5.1. Размещение (4)
В массив A1, A2,…, AN помещены числа 2, 3,..., N+1 так, что каждое значение Ai делится на i. Сколько способов такого размещения?
Ввод из файла INPUT.TXT. В единственной строке вводится значение N.
Вывод в файл OUTPUT.TXT. В единственной строке выводится количество вариантов размещения.
- Примеры
Ввод 1 Ввод 2 Ввод 3
6 3 11
Вывод 1 Вывод 2 Вывод 3
1 2 8
5.2. Колесо Фортуны (4)
Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.
Участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью v градусов в секунду, и стрелка, переходя из сектора X к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на k градусов в секунду. При этом если v ≤ k, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор X.
Участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от a до b градусов в секунду.
Требуется написать программу, которая по заданному расположению чисел в секторах, минимальной и максимальной начальной угловой скорости вращения колеса и величине замедления колеса при переходе через границу секторов вычисляет максимальный выигрыш.
Ввод из файла INPUT.TXT. Первая строка входного файла содержит целое число N — количество секторов колеса (3 ≤ N ≤ 100).
Вывод в файл OUTPUT.TXT. В выходном файле должно содержаться одно целое число — максимальный выигрыш.
Пример
Ввод 1 Ввод 2 Ввод 3
5 5 5 7 3
1 2 3 4 5 1 2 3 4 5 5 4 3 2 1
3 5 2 15 15 2 2 5 2
Вывод 1 Вывод 2 Вывод 3
5 4 5
5.3. Упорядоченные дроби (6)
Требуется написать программу, которая выводит в порядке возрастания все несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают N.
Ввод из файла INPUT.TXT. Входной файл содержит целое число N (2 ≤ N ≤ 255).
Вывод в файл OUTPUT.TXT. В выходной файл необходимо вывести все дроби по одной в каждой строке.
Пример
Ввод
5
Вывод
- 1/5
- 1/4
- 1/3
- 2/5
- 1/2
- 3/5
- 2/3
- 3/4
- 4/5
5.4. Делители (8)
Будем называть нормальным набор из k чисел (a1, a2, …, ak), если выполнены следующие условия:
каждое из чисел ai является делителем числа N;
выполняется неравенство a1 < a2 < … < ak;
числа ai и ai+1 для всех i от 1 до k – 1 являются взаимно простыми;
произведение a1a2…ak не превышает N.
Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.
Требуется написать программу, которая по заданным значениям N и k определяет количество нормальных наборов из k делителей числа N.
Ввод из файла INPUT.TXT. Первая строка входного файла содержит два целых числа: N и k (2 ≤ N ≤ 108, 2 ≤ k ≤ 10).
Вывод в файл OUTPUT.TXT. В выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа N.
Примеры
Ввод 1 Ввод 2
90 3 10 2
Вывод 1 Вывод 2
16 4
6. Длинная арифметика
Длинная арифметика позволяет производить точные вычисления с многоразрядными целыми числами без потери точности. Длинными будем называть целые числа, которые записываются в какой-либо системе счисления строкой из своих цифр. При выполнении арифметических операций удобно для выравнивания представлять числа от младших разрядов к старшим. Короткими будем считать числа, представленные стандартными целыми типами.Ниже приводится простой вариант процедур и функций длинной арифметики [2]. Такой подход неэкономичен как по памяти, так и по скорости. Память используется неэффективно, так как для записи каждой цифры используется полный байт. Длина числа не хранится, а находится при вычислениях либо просто не используется, что снижает скорость. К тому же все вычисления производятся в десятичной системе счисления. В системах счисления с основанием 2 операции целочисленного деления и нахождения остатка можно свести к битовым операциям сдвигов, которые выполняются быстрее. Тем не менее, приводимый вариант реализации длинной арифметики пригоден для большинства практических задач и прост в применении. Более полное описание проблем, связанных с длинной арифметикой, можно найти в [3].
-
- Const
- numlen = <максимальное количество знаков в длинных числах>;
- { для параметров циклов используются переменные integer,
- если numlen>MaxInt, нужно использовать переменные типа word }
Type
number=array[1..numlen] of byte;
- { длинное число от младших разрядов к старшим;
- переменной A типа number представлено число SUM(a[i]*10^(i-1))}
- Procedure Set0(var n:number); {обнуление длинного числа}
Var
i: integer;
Begin
For i:=1 to numlen do
n[i]:=0;
End;
- Procedure SetN(Var n: number; short: integer);
- {занесение короткого числа в длинное}
Var
i: integer;
Begin
Set0(n); i:=1;
While short>0 do
begin
n[i]:=short mod 10;
short:=short div 10;
- i:=i+1;
end;
End;
Procedure Move(n1:number; Var n2:number);
- {пересылка длинного числа n2:=n1}
Var
i: integer;
Begin
For i:=1 to numlen do
n2[i]:=n1[i];
End;
Function Len(var n:number): integer;
- {получение длины числа, для нуля длина 1 }
Var
i: integer;
Begin
For i:=numlen downto 1 do
if n[i]<>0 then
begin
Len:=i;
Exit;
end;
Len:=1;
End;
Procedure Show(var n:number);
- {вывод числа и перевод строки }
Var
i: integer;
Begin
For i:=Len(n) downto 1 do
Write(n[i]);
WriteLn;
End;
Procedure AddShort(Var n: number; short: integer);
- {прибавление короткого числа}
Var
- i: integer;
Begin
i:=1;
While short>0 do
begin
short:=short+n[i];
n[i]:=short mod 10;
short:=short div 10;
- i:=i+1;
end;
End;
Procedure MulShort(Var n: number; short: integer);
- {умножение на короткое число}
Var
- i,carry: integer;
Begin
carry:=0;
For i:=1 to numlen do
begin
carry:=carry+n[i]*short;
n[i]:=carry mod 10;
carry:=carry div 10;
end;
- if carry<>0 then {диагностика переполнения}
Halt(1);
End;
Procedure DivShort(Var n: number; divisor: integer; Var rem: integer);
- {деление на короткое число и получение остатка}
Var
i: integer;
Begin
rem:=0;
For i:=numlen downto 1 do
begin
rem:=rem*10+n[i];
n[i]:=rem div divisor;
rem:=rem mod divisor;
end;
End;
Procedure Add(Var n1,n2: number);
- {прибавление длинного числа}
Var
- i,carry: integer;
Begin
carry:=0;
For i:=1 to numlen do
begin
carry:=carry+n1[i]+n2[i];
n1[i]:=carry mod 10;
carry:=carry div 10;
end;
- if carry<>0 then {диагностика переполнения}
- Halt(1);
End;
Procedure Mul(Var n1,n2: number; Var n3: number);
- {умножение длинных чисел}
Var
i1,i2,i3,len1,len2,carry: integer;
Begin
Set0(n3);
len1:=Len(n1);
len2:=Len(n2);
- For i1:=1 to len1 do
- For i2:=1 to len2 do
begin
i3:=i1+i2-1;
carry:=n1[i1]*n2[i2];
While carry>0 do
begin
carry:=carry+n3[i3];
n3[i3]:=carry mod 10;
carry:=carry div 10;
inc(i3);
end;
end;
End;
Function Cmp(Var n1,n2: number): integer;
- { сравнение чисел:
- если n1<n2 выдает -1
- если n1=n2 выдает 0
- если n1>n2 выдает 1
}
Var
i: integer;
Begin
For i:=numlen downto 1 do
begin
if n1[i]<n2[i] then
begin
Cmp:=-1;
Exit;
end;
if n1[i]>n2[i] then
begin
Cmp:=1;
Exit;
end;
end
- Cmp:=0;
- End;
Маг. Имеется N супружеских пар. Маг должен определить, кто кому супруг. Какова вероятность угадать ровно K раз из N?
Ввод из файла INPUT.TXT. В первой задаются через пробел строке K и N (1 ≤ N ≤ 100, 0 ≤ K ≤ N).
Вывод в файл OUTPUT.TXT вероятности угадать ровно K раз из N в виде несократимой дроби либо единственного значения 0.
Примеры
Ввод 1 Ввод 2
2 5 9 10
Вывод 1 Вывод 2
1/6 0
Пронумеруем, например, мужчин от 1 до N. Сейчас нужно найти вероятность такого расположения женщин в позициях от 1 до N, чтобы ровно K из них соответствовали позиции своего мужа.Пусть D(N) – функция, определяющая количество перестановок из N элементов 1, 2, …, N, в которых ни один из элементов не остается на своем месте. Такие перестановки называются беспорядками. Тогда ответ задачи определяет выражение
PNK = (CNK D(N-K)) / N! = D(N-K)) / K! (N-K)! (1)
Действительно, для каждого набора из K элементов, остающихся на своих местах, существуют D(N-K) перестановок остальных элементов, а общее число перестановок N! Остается найти способ вычисления функции D(N).
Очевидно, что D(1) = 0, D(2) = 1, D(3)=2 - перестановки (2, 3, 1) и (3, 1, 2).
При N = 4 существуют 9 перестановок с элементами не на своих местах:
(2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3),
(4, 3, 1, 2), (4, 3, 2, 1), т.е. D(4)=9.
Докажем приведенную в [1] без доказательства рекуррентную формулу
D(N+1) = N ( D(N) + D(N-1)) (2)
Возможны два варианта:
Элемент N+1 находится на месте K, а элемент K находится на месте N+1, то есть перестановка образована обменом элемента N+1 c элементом K. Тогда все остальные N-1 элементов не на своих местах. Поскольку 1 ≤ K ≤ N, таких случаев N D(N - 1). Например, при N+1=5 и K = 2 мы рассматриваем множество перестановок (S1, 5, S 3, S 4, 2), в которых в качестве S1, S 3, S 4 фигурируют элементы 1, 3, 4 и S1 ≠ 1, S3 ≠ 3, S4 ≠ 4.
Элемент N+1 находится на месте K, а на месте N+1 находится элемент M, при этом M ≠ K. Тогда элементы 1, 2, …, M-1, M+1, …, N находятся не на своих местах, а элемент N+1 не должен быть на месте M. Поскольку 1 ≤ M ≤ N, таких случаев N D(N). Например, при N+1 = 5 и M = 3 мы рассматриваем множество перестановок (S1, S 2, S 3, S 4, 3), в которых в качестве S1, S 2, S 3, S 4 фигурируют элементы 1, 2, 4, 5 и S1 ≠ 1, S2 ≠ 2, S3 ≠ 5, S4 ≠ 4.
Суммирование по обоим вариантам доказывает рекуррентную формулу (2). В соответствии с ней, например, D(5) = 44.
Можно получить более очевидное, но и более сложное по форме соотношение для D(N+1). Всего имеется (N+1)! перестановок из N+1 элементов. Число перестановок с единственным элементом на своем месте составляет CN+11 D(N), с двумя на своих местах CN+12 D(N-1) и т. д. Ровно N элементов на своих местах быть не может, так как и последний элемент в этом случае на своем месте. Вычитая из общего числа перестановок количество случаев, когда хотя бы один элемент находится на своем месте, получим формулу
D(N+1)= (N+1)! - CN+11 D(N) - CN+12 D(N-1) -…- CN+1N-1 D(2) – 1
Единица соответствует случаю, когда все элементы на своих местах.
Примеры:
N=4, K=1. Тогда S = CNK D(N-K) = 42 = 8, PNK = 8 / 4! = 1 / 3
N=4, K=2, S = 61 = 6, PNK = 6/24 = 1 / 4
N=5, K=2, S = 102 = 20, PNK = 20 / 120 = 1 / 6 (пример из условия)
N=6, K=2, S = 159 = 135, PNK = 135 / 6! = 135 / 720 = 3 / 16
N=10, K=9, S = C109 D(1) =100 = 0, PNK = 0