#java #recursion
#java #рекурсия
Вопрос:
Я пытаюсь вычислить это:
x^y (mod a)
Использование рекурсии, поскольку она лучше работает для больших чисел. Вот что у меня есть:
public int mod (int x, int y, int a){
if(y == 2){
return x^2%a;
}
if(y%2 == 1){
return a%m*mod(x , y/2, a);
}
if(y%2 == 0 ){
return mod(x, y/2, a);
}
}
Код не работает, и другой проблемой является ошибка «отсутствует оператор возврата» в последней скобке. Что можно сделать, чтобы исправить это?
Комментарии:
1. В вашем коде нет рекурсии. Используйте Else if вместо last If,
2. Используйте
else ifиelseдля сортировки вашейreturnпроблемы с отсутствующим оператором, предполагая, что y всегда является целым числом3. @Rishi Goel в его втором и третьем с есть рекурсия
if4.
x^2%aделает не то, что вы думаете. Сначала он оценивает2 % a, затем выполняет побитовое исключающее ИЛИ (^) междуxи результатом2 % aоценки. Предполагая, что вы имели в видуx², попробуйтеx * x % aвместо этого.5. Что такое переменная ‘m’, которая записана в вашем фрагменте кода как «возвращает%m * mod(x, y / 2, a);» ?
Ответ №1:
В Java функция, возвращаемый тип которой не void является, должна возвращать некоторое значение. К сожалению, компилятор недостаточно умен, чтобы понять, что ваши if инструкции охватывают весь диапазон значений входного параметра. Компилятор предполагает, что все ваши условия могут оцениваться false как, таким образом, эта функция не возвращает никакого значения в этом случае. Таким образом, он не может доказать правильность функции и сообщает об ошибке.
Ответ №2:
Ваше последнее if утверждение if(y%2 == 0) является избыточным, потому что есть только две возможности для y%2 : это либо 0, либо 1.
Вы проверили, равно ли оно 1, поэтому, если это условие неверно, вам не нужно проверять, равно ли оно 0, оно определенно будет равно 0, если оно не равно 1.
Удалите последнее if , и оно будет работать нормально:
public int mod (int x, int y, int a){
if(y == 2){
return x^2%a;
}
if(y%2 == 1){
return a%m*mod(x , y/2, a);
}
return mod(x, y/2, a);
}