Для заданного целого Z проверить, можно ли записать Z в виде P^Q, где Q и P - целые положительные числа.

Question

Вот что я пробовал, но это дает мне неправильный вывод. Может ли кто-нибудь указать, в чем ошибка?

function superPower($n) { 
    $response = false; 
    $n = abs($n); 
    if ($n < 2) { 
     $response = true; 
    } 
    for ($i=2;$i<$n;$i++) {  
     for ($j=2;$j<$n;$j++) { 
      if (pow($i,$j) == $n) { 
       $response = true; 
      } 
     } 
    } 

    return $response; 
} 

Например, если я даю ему номер 25, он дает 1 как выход. // Исправлено Но если я дам 26, это все равно дает мне 1, что неправильно.

Answer 1

Используя superPower, вы по существу пытаетесь применить определенную защиту к силе атаки, чтобы увидеть, удерживает ли она ее. Это можно сделать гораздо эффективнее, чем с помощью метода грубой силы, который у вас есть сейчас.

function superPower($hp) { // Niet used Superpower! 
    if($hp <= 1) return true; 

    for($def = floor(sqrt($hp)); $def > 1; $def--) { // Niet's Defence fell 
     for($atk = ceil(log($hp)/log($def)); $atk > 1; $atk--) { // Niet's Attack fell 
      if(pow($def,$atk) == $hp) return true; 
      break; 
      // you don't need the $atk loop, but I wanted to make a Pokémon joke. Sorry. 
     } 
     // in fact, all you really need here is: 
     // $atk = log($hp)/log($def); 
     // if($atk-floor($atk) == 0) return true; 
    } 
    return false; 
} 

Answer 2

В математике на принятый ответ абсолютно блестящий, однако есть несколько проблем с решением:

• функция ошибочно возвращает true для всех следующих входов: monkey, -3 и 0. (Технически 0 беззнаковым, так что нет никакого способа получить его, приняв положительное целое число в степень другого положительного целого числа. То же самое касается любого отрицательного входа.)

• функция сравнивает числа с плавающей с целыми числами (floor() и ceil() возвращение float), которого следует избегать, как чума. Чтобы понять, почему, попробуйте запустить php -r '$n = (-(4.42-5))/0.29; echo "n == {$n}\n".($n == 2 ? "OK" : "Surprise")."\n";'

Следующее решение улучшает на идее, фиксируя все вышеперечисленные вопросы:

function superPower($value) 
{ 
    // Fail if supplied value is not numeric 
    if (!is_numeric($value)) { 
     // throw new InvalidArgumentException("Value is not numeric: $value"); 
     return false; 
    } 

    // Normalise numeric input 
    $number = abs($value); 

    // Fail if supplied number is not an integer 
    if (!is_int($number)) { 
     // throw new InvalidArgumentException("Number is not an integer: $number"); 
     return false; 
    } 

    // Exit early if possible 
    if ($number == 1) { 
     // 1 to the power of any positive integer is one 
     return true; 
    } elseif ($number < 1) { 
     // X to the power of Y is never less then 1, if X & Y are greater then 0 
     return false; 
    } 

    // Determine the highest logarithm base and work backwards from it 
    for ($base = (int) sqrt($number); $base > 1; $base--) { 
     $coefficient = log($number)/log($base); 

     // Check that the result of division is a whole number 
     if (ctype_digit((string) $coefficient)) { 
      return true; 
     } 
    } 

    return false; 
}