Алгоритм счастливых чисел

Хороший предлог для использования рекурсии за пределами рядов Фибоначчи и факториалов

Большинство студентов-программистов слышали о рекурсии. В большинстве случаев после краткого объяснения инструктор всегда показывает пример использования рекурсии для вычисления ряда Фибоначчи или факториала числа.

После этого учитель говорит ... хорошо, теперь вы знаете, что такое рекурсия, и можете использовать ее всякий раз, когда у вас есть повторяющаяся задача ...

Что ж, все мы знаем, что это не так. Не поймите меня неправильно, я знаю, что ряды Фибоначчи и Факториал - самые простые алгоритмы, чтобы попытаться объяснить, что означает рекурсия. Но, как и все в жизни, понимание и применение рекурсии требует практики. Итак, давайте воспользуемся этим простым алгоритмом и применим эти концепции на практике.

Давайте посмотрим на задачу:

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

Счастливое число - это число, определяемое следующим процессом:

а) Начиная с любого положительного целого числа.

б) Заменить число суммой квадратов его цифр

в) Повторяйте процесс, пока число не станет равным 1.

Те числа, для которых этот процесс заканчивается на 1, являются счастливыми числами.

Пример:

Input: 19
Output: true
Explanation: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Как видите, эта задача требует серии повторяющихся шагов, которые можно выполнить с помощью рекурсивного алгоритма.

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

Предлагаемое решение

const isHappy = (number) => {
  const digitsOfTheNumber =(number, array=[])=>{
     if (number>=1){
        array.push(number%10)
        number = Math.floor(number/10)
        return digitsOfTheNumber(number, array)
     } else{
      return array
     }
   }
const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
}

Я знаю, я знаю… Я почти слышу, как люди кричат на меня: «это плохой код»… «это не ясно»… «зачем использовать этот тернарный оператор таким образом, это просто неправильно». Мои извенения. Я просто хочу показать новым кодировщикам то, что они могут найти, читая код от других. Лучше знать это и не нуждаться в этом, чем нуждаться в этом и не знать этого, верно?

Теперь, когда вы увидели ответ, вы можете нажать кнопку отправки в leetcode, если это все, что вас интересовало. После этого вернитесь и попытайтесь понять, почему это работает.

Анализируем проблему

Что нам нужно решить в первую очередь, когда мы прочитаем эту задачу? Если не знаешь, попробуй разобраться.

Хорошо, ответ ... получите цифры номера. Как мы можем это сделать?

Мы можем разделить число, используя два очень редких математических оператора / и% (деление и модуль), верно, это все, что нам нужно. Итак, чтобы получить каждую цифру, мы собираемся получить модуль и деление числа до тех пор, пока число не станет меньше единицы.

Пример:

N = 19
First Step
19 % 10 --> 9
19 / 10 --> 1.9 --> here we just need to round down --> 1
Repeat the process with result
1 % 10 --> 1
1 / 10 --> 0.1 Stop
Another example
N=123
First step 
  123 % 10 --> 3
  123 / 10 --> 12.3 round down --> 12
Second Step
  12 % 10 --> 2
  12 / 10 --> 1.2 round down --> 1
Third Step
  1 % 10 --> 1
  1 / 10 --> 0.1 Stop
We got the digits

* почему модуль 10 и разделен на 10? потому что это десятичные числа.

Теперь давайте посмотрим на наше решение и посмотрим, когда и как это происходит.

Firs we declare our main function
const isHappy = (number) => { 
Now, here we have another function 
|  const digitsOfTheNumber =(number, array=[])=>{
|     if (number>=1){
|        array.push(number%10) --> look familiar?
|        number = Math.floor(number/10) --> look familiar?
|        return digitsOfTheNumber(number, array)
|     } else{
|      return array
|    }
|   } 
|_____
const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
}

Выделим эту функцию и проанализируем.

const digitsOfTheNumber = (number, array=[])=> {

Мы объявляем функцию с двумя аргументами - числом и массивом. ** Запомните название функции **. Здесь ясно, что «число» - это значение, которое мы собираемся разделить, но как насчет «массива»? Как вы могли заметить, нам нужно сохранять цифры, чтобы работать с ними, и простой способ - поместить их в массив.

if (number>=1) {

Теперь мы объявляем наше условие остановки… хорошо, хорошо, наше «условие работы». Как мы видели в примерах предварительного просмотра, нам нужно повторять процесс модуля и деления, пока наше число не станет равным 1 или меньше.

array.push(number%10)

Здесь мы вставляем первую цифру в наш массив.

number = Math.floor(number/10)

Теперь мы используем функцию Math.floor, чтобы округлить наше деление в меньшую сторону, получив следующее число, которое нам нужно обработать.

return digitsOfTheNumber(number, array)

А теперь взгляните на это. Вот когда происходит волшебство. Вместо использования итеративной структуры мы возвращаем и вызываем одну и ту же функцию. Это означает, что этот процесс повторяется снова и снова. Это рекурсия !!

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

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

else {
return array
}

Когда число меньше 1, функция возвращает массив и останавливает выполнение. Теперь у нас есть все цифры, разделенные в массив в константе «digitsOfTheNumber».

Как у тебя дела? время перерыва? Просто потянитесь и давайте продолжим.

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

Что же мы имеем здесь?

const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)

Давайте посмотрим. У нас есть новая переменная под названием answer. В этой переменной есть что-то под названием «digitsOfTheNumber» «reduce». Подождите, мы только что увидели, что digitsOfTheNumber - это функция, которая дала нам цифры, и эта функция возвращает массив. Это означает, что теперь мы работаем с массивом, и эта функция сокращения имеет смысл.

Давайте удостоверимся, что мы понимаем, что здесь происходит.

Here's our main function
const isHappy = (number->🙋🏻) => {
The first thing this function does is to declare a constant called answer that calls the digitsOfTheNumber function passing the argument "number->🙋🏻"
const answer = digitsOfTheNumber(number->🙋🏻).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
}

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

|  const digitsOfTheNumber =(number->🙋🏻, array=[])=>{
|     if (🙋🏻>=1){
|        array.push(🙋🏻%10)-> now array has a digit [🙋🏻]
|        number = Math.floor(🙋🏻/10) each pass is a new number->🙋🏽
|        return digitsOfTheNumber(🙋🏽, [🙋🏻])
|     } else{
|      return array -->[🙋🏻,🙋🏽]
|    }
|   }

Теперь у нас есть массив, с которым мы работаем с помощью функции сокращения.

const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
  
*** [🙋🏻,🙋🏽].reduce

Функция сокращения суммирует квадраты каждой цифры в массиве и дает нам новое число.

[1,9].reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
first time
accumulator  --> 0
currentValue --> 1 --> 1**2 -> 1 
second time
accumulator --> 1
currentValue --> 9 --> 9**2 ->81
return 1+81 --> 82

Надеюсь, это достаточно ясно.

Давайте посмотрим на последнюю часть функции. Если вы не знакомы с тернарным оператором, это может показаться странным. Но на самом деле это довольно просто.

return answer === 1 ? true : answer === 4 ? false : isHappy(answer)

Вот определение тернарного оператора:

Тернарный оператор - это оператор, который принимает три аргумента. Первый аргумент - это аргумент сравнения, второй - результат истинного сравнения, а третий - результат ложного сравнения . ( Источник )

Давайте разберем этот тернарный оператор:

return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
"Is answer equal 1?"   [answer === 1] [?] 
"yes" *return*         [true] 
"no"                   [:]
"Is answer equal 4?"   [answer === 4] [?]
"yes" *return*         [false]
"no"                   [:] 
return                 [isHappy(answer)]

Конечно, мы можем заменить это обычным оператором if-else.

if(answer === 1){
 return true
} else if (answer===4){
 return false
} else {
 return isHappy(answer)
}

Итак, что вы здесь увидели?

В последнем возврате мы возвращаем ту же функцию с новым значением ответа. И ДА, мы снова используем рекурсию.

Давайте попробуем привести здесь целый пример:

isHappy(19)
Step 1 
const answer =digitsOfTheNumber(19)...Now we call that function
Step 1.1.1
digitsOfTheNumber(19)
|  const digitsOfTheNumber = (19, array=[])=>{
|     if (19>=1){-->YES
|        array.push(19%10)          array --> [9]
|        number = Math.floor(19/10) number --> 1
|        return digitsOfTheNumber(1, [9])
Step 1.1.2
|  const digitsOfTheNumber = (1,[9])=>{
|     if (1>=1){-->YES
|        array.push(1%10)            array --> [9,1]
|        number = Math.floor(1/10)  number-> 0
|        return digitsOfTheNumber(0, [9,1])
Step 1.1.3
|  const digitsOfTheNumber = (0,[9,1])=>{
|     if (0>=1){-->NO
|        ---           
|        ---}
|     --> else{
|      return array -->[9,1]
Step 1.2 
[9,1].reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
Step 1.2.1
accumulator  --> 0
currentValue --> 9 --> 9**2 -> 81 
Step 1.2.2
accumulator --> 81
currentValue --> 1 --> 1**2 ->1
return 81+1 --> 82
 
Now answer is 82
Step 1.3
return 82 === 1 ? true : 82 === 4 ? false : [isHappy(82)]-->true
"Is 82 equal 1?"       [82 === 1] [?] --> No
"yes" *return*         [true] -->discard
"no"                   [:]
"Is answer equal 4?"   [answer === 4] [?]--> No
"yes" *return*         [false]-->discard
"no"                   [:] 
return                 [isHappy(answer)] --> Winner
Step 2
isHappy(82) -->star over

Ну вот и все. Надеюсь, вам понравилась эта статья, и теперь попробуйте применить рекурсию к другой проблеме.

Продолжайте кодировать!

смотрите также:

Новые материалы

Объяснение документов 02: BERT

BERT представил двухступенчатую структуру обучения: предварительное обучение и тонкая настройка. Во время предварительного обучения модель обучается на неразмеченных данных с помощью..

Как проанализировать работу вашего классификатора?

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

Работа с цепями Маркова, часть 4 (Машинное обучение)

Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]

Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..

Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter

Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..

Учебные заметки: создание моего первого пакета Node.js

Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..

Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!

Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..

Метки

Machine Learning JavaScript Data Science Artificial Intelligence Software Development Python Web Development Coding Deep Learning AI React Software Engineering Nodejs Java Front End Development Typescript Computer Science Data Algorithms Development NLP Tech Programming Languages CSS ChatGPT HTML Python Programming Javascript Tips Angular Computer Vision Startup Data Visualization Neural Networks Tutorial Statistics Productivity Reactjs Learning