В теории чисел теорема Пифагора стала источником плодотворной идеи: найти целочисленные решения алгебраических уравнений.
Пифагорова тройка — это набор целых чисел a, b и c, таких что: a2 + b2 = c2. Геометрически такая тройка определяет прямоугольный треугольник с целочисленными сторонами. Самая маленькая гипотенуза пифагоровой тройки равна 5. Другие две стороны этого треугольника равны 3 и 4. Здесь 32 + 42 = 9 + 16 = 25 = 52.
Пифагоров треугольник с этими сторонами известен с глубокой древности. Он называется египетским, и использовался для построения прямого угла на местности. Вместо вычерчивания применялась верёвка, разделённая 12 узлами на равные части, которая натягивалась на 3 колышка.
Пифагорова тройка (a, b, c) называется примитивной, если она не может быть получена делением всех сторон на целое число из какой-то другой пифагоровой тройки, то есть если (a , b , c) являются взаимно простыми числами. Другими словами, наибольший общий делитель (НОД) примитивной пифагоровой тройки ( a, b, c ) равен 1.
Как вы думаете, много ли найдется таких троек?
Постановка задачи
Требуется найти все примитивные тройки, для которых длина катетов не превышает некоторого заданного числа k, упорядочить тройки по возрастанию площади соответствующих треугольников, вывести их на печать и подсчитать общее число таких троек.
Алгоритм решения
Создадим структуру pif1 c полями a, b,c, s и методом print_P(). Инициализируем массив pif3 , элементами которого будут структуры pif1.
Для поиска (метод static int poisk3(int k)) будем используем прямой перебор и два цикла. В первом цикле a изменяется от 3 до k, а во втором (внутреннем) цикле b изменяется от 4 до k. Если гипотенуза такого треугольника является целым числом, то вычисляется его площадь s, и такой треугольник запоминается в массив pif3.
После этого выполняется упорядочивание массива по возрастанию (по полю s, метод sort3(n)). Очевидно, что сортировка может быть выполнена по любому другому полю, например по гипотенузе с.
При выводе троек (метод output3(n) c использованием print_P() ) выводятся только те, у которых НОД=1 (дважды применяется метод «Наибольший общий делитель» nod(x, y) ).
Максимальная длина катетов задается первыми двумя операторами метода Main(), после чего выполняется поиск, сортировка и вывод результатов.
Программная реализация
// Поиск пифагоровых троек
using System;
namespace ПИФ3
{
class Program
{
// тройка (a,b,c)
struct pif1
{
public int a; // катет
public int b; // катет
public int c; // гипотенуза
public int s; // плошадь
public void print_P() // вывод примитивных троек
{
int d = nod(c, nod(a, b));
if (d == 1) // только, если НОД=1
{
Console.WriteLine("{0}\t{1}\t{2}\t{3}", a, b, c, s);
r++; // подсчет их числа
}
}
}
// массив пифагоровых троек
static pif1[] pif3 = new pif1[1000000];
// найдено троек (с НОД=1)
static int r = 0;
// Наибольший общий делитель (НОД)
static int nod(int x, int y)
{
while (x != y)
{
if (x > y)
x = x - y;
else
y = y - x;
}
return x;
}
// Прямой поиск троек, k - максимальная длина катета
static int poisk3(int k)
{
int n = 0; // счетчик
int x, y, w;
double z;
// Поиск троек целых чисел
for (x = 3; x <= k; x++)
for (y = x + 1; y <= k; y++)
{
z = x * x + y * y + 0.001;
w = Convert.ToInt32(Math.Sqrt(z));
if (Math.Abs(w * w - z) < 0.01)
{
pif3[n].a = x;
pif3[n].b = y;
pif3[n].c = w;
pif3[n].s = x * y / 2;
n++;
}
}
return n;
}
// сортировка по возрастанию площадей треугольников
static void sort3(int n)
{
pif1 p;
for (int i = 0; i < n - 1; i++)
for (int j = i; j < n - 1; j++)
if (pif3[j].s > pif3[j + 1].s)
{
p = pif3[j];
pif3[j] = pif3[j + 1];
pif3[j + 1] = p;
}
}
// вывод треугольников: a b c S
static void output3(int n)
{
Console.WriteLine("Пифагоровы треугольники\n a b c S");
for (int i = 0; i < n; i++)
pif3[i].print_P();
Console.WriteLine("Всего треугольников - {0}",r);
Console.ReadKey();
}
// главная
static void Main(string[] args)
{
Console.Write("Поиск Пифагоровых треугольников\nМаксимальная длина катета - ");
int k = Convert.ToInt32(Console.ReadLine());
int n = poisk3(k);
sort3(n);
output3(n);
}
}
}
Результат
Задание
Исследуйте, как изменяется результат в зависимости от максимальной длины катета k. Обратите внимание на время решения задачи T (используйте секундомер). Является ли зависимость T=f (k) линейной, т.е. действительно ли T ~ k ?
Перейдем к следующей задаче — формированию массива простых чисел.
NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.
|
|
|
|