Необходимо найти количество троек чисел (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 секунды (после ввода последней комбинации нет задержки).