Javascript, простая рекурсивная функция - PullRequest
Новая
       5

Javascript, простая рекурсивная функция

3 голосов
/ 04 апреля 2020

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

Я могу получить правильный ответ в консоли, но не могу понять, как сделать свою функцию признать, что он дал правильный ответ.

Задача: «Напишите алгоритм, чтобы определить, является ли число« счастливым ».

Счастливое число - это число, определяемое следующим процессом: Начиная с любого положительного целого числа, замените число на сумму квадратов его цифр и повторяйте процесс до тех пор, пока число не станет равным 1 (там, где оно останется), или пока оно не зациклится в цикле, который не содержит 1. Эти числа для которого этот процесс заканчивается в 1 - это счастливые числа. "

Моя попытка: 

let num = 19;

let isHappy = (n) => {

  let sNum = `${n}`;
  let sArray = sNum.split('');
  let nArray = sArray.map(el => Number(el))
  let total = nArray.reduce((acc, curr) => {
  return acc += curr * curr
}, 0);
  if(isHappy(total) === 1) {
    return true
  } else {
   return false
  }
}

isHappy(num)

Я использовал циклы while и делал разные попытки при выполнении теста базового случая, но не повезло , Любая помощь будет принята с благодарностью.

Ответы [ 3 ]

4 голосов
/ 04 апреля 2020

Вы можете сначала вернуть проверку указанного номера ( выйти с раннего захода на посадку ) и использовать Set для видимых чисел

  • , если один , счастлив возврат true,
  • - это число, которое вы видели раньше, затем у вас есть цикл, затем возврат false,
  • или возврат результата рекурсивный вызов с суммой всех квадратов цифр. 

function isHappy(value, seen = new Set) {
    if (value === 1) return true;
    if (seen.has(value)) return false;
    seen.add(value);
    return isHappy(value.toString().split('').reduce((s, d) => s + d * d, 0), seen);
}

console.log(isHappy(1));
console.log(isHappy(19));
console.log(isHappy(4));
console.log(isHappy(22));
3 голосов
/ 04 апреля 2020

Вот способ вычислить ответ без использования списка ранее увиденных чисел. 

// This function calculates the next number in the sequence from the current number.
const digitSquareSum = n => {
  let sum = 0;
  let num = n;

  while (num > 0) {
    const rem = num % 10;
    num = (num - rem) / 10;
    sum += rem * rem;
  }

  return sum;
};

// Floyd's hare and tortoise algorithm is used to detect cycles in a sequence.
const floyd = (f, n) => {
  let tortoise = f(n);
  let hare = f(f(n));

  while (hare !== tortoise) {
    tortoise = f(tortoise);
    hare = f(f(hare));
  }

  return hare;
};

// If the number in the cycle is 1 then the number is happy.
const isHappy = n => floyd(digitSquareSum, n) === 1;

console.log(isHappy(1));  // true
console.log(isHappy(19)); // true
console.log(isHappy(4));  // false
console.log(isHappy(22)); // false

В отличие от ответа Нины , это решение эффективно использует память.

1 голос
/ 04 апреля 2020

Вот глобально кэшированная версия ответа @Nina 

const emotion_unknown = Symbol('emotion_unknown');
const happy_cache = new Map;
happy_cache.set(1, true);

function isHappy(value) {
  if (happy_cache.has(value)) {
    if (happy_cache.get(value) == emotion_unknown) return false
    else return happy_cache.get(value)
  }
  //optional: only set cache for value < 1000 since next(999)<1000
  //there should be a tighter bound, but 1000 is not large :P
  //and you can use an array for bounded cache
  let next = value.toString().split('').reduce((s, d) => s + d * d, 0)
  happy_cache.set(value, emotion_unknown)
  let result = isHappy(next)
  happy_cache.set(value, result)
  return result
}

//the SO console seems to have 50 line limit
//for (let i = 1; i < 100; ++i) {if (isHappy(i)) console.log(i);}
let happy_numbers=new Set;
for (let i = 1; i < 1000; ++i) {if (isHappy(i)) happy_numbers.add(i);}
console.log(...happy_numbers)
...