Для входа в систему используется пароль, который состоит из трех двузначных чисел. Двузначные числа образуют между собой примитивную пифагорову тройку (сумма квадратов двух чисел равна квадрату третьего числа, каждое из чисел натуральное, числа взаимно простые). Известно, что первым всегда стоит наименьшее двузначное число.
Сколько максимально времени потребуется для подбора пароля, если ввод пароля занимает 1 секунду, а задержка между вводом паролей составляет 1 секунду?
Числа необязательно идут по порядку.
После последней попытки задержки нет.
Необходимо найти количество троек чисел (a, b, c) таких, что c2 = a2 + b2 или b2 = a2 + c2 , при этом, 10 £ a,b,c £ 99. Известно, что первое число наименьшее, то есть a < b и a < c.
Числа a,b,c должны быть взаимнопростыми, то есть НОД(a,b) = НОД(b,c) = НОД(a,c) = 1.
Для реализации функции НОД (наибольший общий делитель) можно воспользоваться алгоритмом Евклида: вычитать из большего числа меньшее, пока они не сравняются. Результатом и будет НОД.
Пример реализации функции НОД на языке программирования C приведен в листинге 1.1‑1.
Листинг 1.1-1 – Реализация функции НОД на языке программирования C
/// поиск НОД для 2-х чисел
/// PARAMS
/// a - первое число
/// b - второе число
/// RETURN
/// вычисленный НОД
int NOD(int a, int b)
{
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
}
return a;
}
Общий цикл перебора чисел и поиска требуемых троек на языке программирования C++ приведен в листинге 1.1-2.
Листинг 1.1-2 – Реализация цикла перебора на языке программирования C++
int main()
{
int a, b, c; // искомые числа
int count = 0; // счетчик числа найденных троек
for (a = 10; a < 100; a++)
for (b = 10; b < 100; b++)
for (c = 10; c < 100; c++)
{
if (
// условие на пифагоровы тройки
( c * c == a * a + b * b || b * b == a * a + c * c )
// условие на первое минимальное число
&& a < b && a < c
// условие на взаимнопростые числв
&& NOD(a,b) == 1 && NOD(b,c) == 1 && NOD(a,c) == 1
)
{
count++; // увеличение счетчика на 1
// вывод на экран найденной тройки
cout << count << " - (" << a << "," << b << "," <<c<<")"<< endl;
}
}
}
В результате программа выведет следующие комбинации:
1 - (11,60,61)
2 - (11,61,60)
3 - (12,35,37)
4 - (12,37,35)
5 - (13,84,85)
6 - (13,85,84)
7 - (16,63,65)
8 - (16,65,63)
9 - (20,21,29)
10 - (20,29,21)
11 - (28,45,53)
12 - (28,53,45)
13 - (33,56,65)
14 - (33,65,56)
15 - (36,77,85)
16 - (36,85,77)
17 - (39,80,89)
18 - (39,89,80)
19 - (48,55,73)
20 - (48,73,55)
21 - (65,72,97)
22 - (65,97,72)
Под условия задачи подходит 22 комбинации. Учитывая, что время ввода комбинации 1 секунда и задержка между соседними комбинациями 1 секунда, общее время, требуемое на ввод всех комбинаций T = 22 + 21 = 43 секунды (после ввода последней комбинации нет задержки).