Вопрос о формуле Лежандра и рекурсии?

В настоящее время я изучаю формулу Лежандра. До сих пор мне удалось решить алгоритм со следующим подходом:

const legendre = (p,n,res=0) => Array.from({length:n},(_,i) => res+=Math.floor(n/p**++i)) && res;

console.info(legendre(5,90)); // 21
console.info(legendre(2,130)); // 128
console.info(legendre(3,60)); // 28
console.info(legendre(9,5)); // 0
console.info(legendre(5,1250)); // 312

Однако я просто не мог рекурсивно преодолеть горб. Это то, что у меня есть до сих пор:

const legendre = (p,n,i=1,res=0) => p > n ? res : res + legendre(p**i,n,i+1,Math.floor(n/p**i))

console.info(legendre(5,90)); // 21
console.info(legendre(2,130)); // 99 
console.info(legendre(3,60)); // 26
console.info(legendre(9,5)); // 0
console.info(legendre(5,1250)); // 300

Как видите, большинство результатов неверны. Я на правильном пути? Может ли кто-нибудь указать мне правильное направление или показать мне, что я делаю неправильно? Любая обратная связь будет принята с благодарностью. Заранее миллион спасибо :)

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
1
0
36
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я начал с преобразования вашего первого кода в обычную функцию:

const legendre = (p, n) => {
  let res = 0;
  for (let i = 1; i <= n; i++) {
    res += Math.floor(n/p**i);
  }
  return res;
}

console.info(legendre(5,90)); // 21
console.info(legendre(2,130)); // 128
console.info(legendre(3,60)); // 28
console.info(legendre(9,5)); // 0
console.info(legendre(5,1250)); // 312

и преобразовал это в рекурсивную функцию:

const legendre = (p, n, i=1, res=0) => {
  // base case -> done
  if (i > n) return res + Math.floor(n/p**i);
  return legendre(p, n, i+1, res + Math.floor(n/p**i));
}

console.info(legendre(5,90)); // 21
console.info(legendre(2,130)); // 128
console.info(legendre(3,60)); // 28
console.info(legendre(9,5)); // 0
console.info(legendre(5,1250)); // 312

и это можно превратить в oneliner следующим образом:

const legendre = (p,n,i=1,res=0) => i > n ? res + Math.floor(n/p**i) : legendre(p,n,i+1,res +Math.floor(n/p**i))

console.info(legendre(5,90)); // 21
console.info(legendre(2,130)); // 128
console.info(legendre(3,60)); // 28
console.info(legendre(9,5)); // 0
console.info(legendre(5,1250)); // 312

Я не изучал этот алгоритм, и эти ответы основаны только на вашем первом фрагменте кода и ваших тестовых примерах.

Спасибо за оперативный и потрясающий ответ!!! Использование «i» в качестве базового случая — это просто чертовски гениально :) Я смог немного изменить код следующим образом: Я просто в шоке! Я многому научился, следуя твоей логике. Еще раз спасибо ???

noirsociety 09.04.2022 00:28

Другие вопросы по теме