Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 05.09.2021, 01:51
Интересующийся
Отправить личное сообщение для orloff Посмотреть профиль Найти все сообщения от orloff
 
Регистрация: 30.10.2020
Сообщений: 14

Что происходит в задачке?
Всем привет.
На Codewars есть задачка
Given n, take the sum of the digits of n. If that value has more than one digit, continue reducing in this way until a single-digit number is produced. The input will be a non-negative integer.

Пример
16 --> 1 + 6 = 7
942 --> 9 + 4 + 2 = 15 --> 1 + 5 = 6

Я ее честно решил с рекурсией, но потом поискал другие решения и нашел код в одну строку
export const digitalRoot = (n:number): number => {
 // your code here
    return (n - 1) % 9 + 1;
};

Расскажите плиз неучу, что происходит? Мы отнимаем 1 от нашего числа, получаем остаток от деления на 9, и плюсуем единицу. И это подходит к любому числу. Что это вообще за трюк?
Ответить с цитированием
  #2 (permalink)  
Старый 05.09.2021, 01:56
Аватар для Aetae
Тлен
Отправить личное сообщение для Aetae Посмотреть профиль Найти все сообщения от Aetae
 
Регистрация: 02.01.2010
Сообщений: 6,480

Ну вот такая вот закономерность. Ответы искать в институтской программе теории числел. Не думаю что тут найдётся спец по вопросу.)
__________________
29375, 35
Ответить с цитированием
  #3 (permalink)  
Старый 05.09.2021, 02:23
Интересующийся
Отправить личное сообщение для orloff Посмотреть профиль Найти все сообщения от orloff
 
Регистрация: 30.10.2020
Сообщений: 14

Aetae,
Спасибо за ответ. Думал может кто помнит/знает. Уж очень джедайское решение получилось)) Хотя это не решение задачи, а скорее задача под эту закономерность заточена )
Ответить с цитированием
  #4 (permalink)  
Старый 05.09.2021, 03:00
Аватар для Aetae
Тлен
Отправить личное сообщение для Aetae Посмотреть профиль Найти все сообщения от Aetae
 
Регистрация: 02.01.2010
Сообщений: 6,480

Так тоже верно, кстати:
const digitalRoot = (n, base = 10) => {
    return (n - 1) % (base - 1) + 1;
};
__________________
29375, 35
Ответить с цитированием
  #5 (permalink)  
Старый 05.09.2021, 13:54
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 1,126

Это вроде "Арифметика остатков" из теории чисел
Ответить с цитированием
  #6 (permalink)  
Старый 05.09.2021, 18:32
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

Сообщение от orloff
Что это вообще за трюк?
навскидку, немного коряво, но тем не менее.

1) Число делится на 9, если сумма его цифр делится на 9 (признак делимости, можно глянуть в википедии). Т.е. если у нас исходное число М = 9*N, то очевидно, digitalRoot придет к 9.

2) Теперь кейс, когда наше число не делится на 9, то есть равно М = 9*N + k, где k=1..8, или, по другому, M % 9 = k
Здесь можно легко доказать, что сумма цифр будет сохранять остаток от деления на 9, при выполнении digitalRoot, на каждой итерации.

Пусть последняя цифра числа 9*N оказалась равна m. Добавим k. Если m + k < 10, то просто последняя цифра увеличилась на k. Иначе, последняя цифра стала равна m + k - 10, стоящие перед ней n девяток обнулились, а недевятка перед ними увеличилась на 1. Сумма цифр поменялась на (m + k - 10) - m - n*9 + 1 = k - 9*p. То есть в любом случае остаток суммы цифр от деления на 9 стал равен k. Что, собственно, и доказывали.

Вот так и вышло, что сохраняя оный остаток, digitalRoot приходит либо к 9 в случае нулевого остатка, либо. самому остатку.
Ответить с цитированием
  #7 (permalink)  
Старый 05.09.2021, 18:52
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

Сейчас подумал, что п.1 не более чем частный случай п.2, только для нулевого остатка. В общем, всё доказательство в п.2
Ответить с цитированием
  #8 (permalink)  
Старый 05.09.2021, 19:27
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 1,126

Такие вещи проще всего объяснять графически.

Взять базу 9 и отобразить ее в виде типа циферблата часов с делениями от нуля до девяти.
Числовую прямую намотать на такой циферблат в виде спирали согласно делениям.
Тогда станет хорошо заметно что к примеру число 10 будет на линии первого деления циферблата а число 20 на втором делении циферблата а к примеру число 14 будет на пятом делении потому что 10 начинается на первом делении и плюс еще четыре деления, число 24 будет на 6м делении циферблата и.т.д. Это пример с десятками, с сотнями тысячами и так далее работает абсолютно аналогично.

Если разобрать по шагам то станет понятно почему это работает для любого числа
и почему в условиях задачи число не должно превышать базу.
Ответить с цитированием
  #9 (permalink)  
Старый 07.09.2021, 09:32
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,064

MallSerg,
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Отладка: посмотреть, что происходит при событии Petja Общие вопросы Javascript 3 09.07.2013 16:54
Что происходит с переменной? kokacolla Общие вопросы Javascript 5 07.06.2013 09:15
Когда происходит $(document).ready ? zebra741258963 jQuery 8 07.04.2012 23:24
Поюзайте хомячка Nanto Ваши сайты и скрипты 30 06.06.2011 22:16
Что происходит при fadeOut() ? Триви jQuery 3 21.03.2011 15:26