Как говорится, сиди-не сиди, а начинать надо :)
Задача
Тройка Пифагора - три натуральных числа a < b < c, для которых выполняется равенство
a² + b² = c²
Например, 3² + 4² = 9 + 16 = 25 = 5².
Существует только одна тройка Пифагора, для которой a + b + c = 1000.
Найдите произведение abc.
Решение
Наивное решение это устроить три вложенных цикла от 1 до 1000, перебирая все комбинации чисел a, b, c:
Для каждой комбинации чисел выясняем, выполняется ли условие a² + b² = c², и если да, то выполняется ли ещё одно условие a + b + c = 1000. Если оба условия выполнились, возвращаем результат a * b * c.
Менее наивное решение откидывает заведомо неподходящие комбинации. Например, если сумма a + b уже превысила 1000, то дальше считать не надо. А переменная с обходится вообще без цикла, так как равна 1000 - a - b.
Наконец, более хитрое решение, которое оказалось хуже. Причины этого обсудим ниже.
Я исходил из того, что нас интересуют только квадраты целых цисел. Т.е. если
a² + b² = c²
то можно просто брать по очереди квадраты натуральных чисел и считать, что это c². Затем пробовать вычитать оттуда один из предыдущих квадратов и считать, что это был b². То, что останется, это a². Надо только проверить, правильный ли это квадрат.
Для этого я беру корень из полученного кандидата на a². Если корень получился дробный, то это было не натуральное число. На самом деле корень просто округляется до целого, но так так дальше число a участвует в проверке и снова возводится в квадрат, это не мешает. Если число a получилось правильно, то всё сработает.
UPDATE: В общем тут всё плохо, не обращайте внимания :)
Ссылка на онлайн-компилятор языка C с текстом программы:
Вся подборка задач: