Как написать программу на C, соответствующую требованиям

-4

Сегодня я столкнулся с вопросом. В нем говорится, что:Как написать программу на C, соответствующую требованиям

Вам нужно найти, может ли число быть выражено в виде суммы двух совершенных степеней. То есть, если x найти, если существуют неотрицательные целые числа a, b, m, n такие, что a^m + b^n = x где 1 < = x < = 1000000 и m> 1, n> 1

Не мог бы кто-нибудь объяснить мне, как это можно сделать?

Я знаю, что мы можем написать что-то вроде этого:

for(int a = 1; true; a++){ 
    for(int b = 1; true; b++){ 
     // And so on and so forth 
    } 
}

Но это не очень эффективно (или правильно) способ сделать это.

Спасибо.

источник

2013-12-05 user3035992

На самом деле с некоторой базовой математикой вы можете поместить некоторые ограничения на 'a, b, m, n', чтобы петли были действительно короткими. Потому что ваши 'm, n> = 2'' a, b' должны идти только до '1000', так как' 1000² = 1000000' –

Проверьте этот [алгоритм] (http://stackoverflow.com/questions/3967769/represent- Естественное число-как-сумма-квадратов-использование-динамическое программирование) –

Ну, как бы я попытался увидеть, как сила множества всех возможных допустимых квадруплетов '(a, b, m, n) 'масштабируется с' x'. Итак, что такое 'O (solve (x))'. Если бы его линейный или лучший, я бы дал ему перебор с грубой силой. Если это неудовлетворительно, я бы попросил математика, если есть лучший (более интеллектуальный) способ разложения чисел таким образом. – luk32

Иногда это единственный способ решить эти проблемы. Тот, который вы выложили принадлежит к классу задач под названием «один путь функции»: существует нетривиальная реализация задачи одним способом ...

Учитывая четыре неотрицательными целыми числами, a, b, m and n, find x so a^m + b^n = x

Но другие способ ...

Учитывая х, найти четыре неотрицательными целыми числами a, b, m and n, so a^m + b^n = x

нетривиально. На самом деле, это невозможно было бы решить, или ваш лучший шанс, использовать алгоритм принудительного перебора, чтобы решить его, что вы предложили.

источник

2013-12-05 11:29:27

Мне также нравится определение «односторонних функций» или проблем: «Их очень сложно решить, но очень легко проверить решение». Это то же самое, но сформулировано по-разному. Может быть, легче понять смысл. – luk32

Как написать программу на C, соответствующую требованиям

ответ

Смежные вопросы