Наименьшее число, кратное какому-то произвольному натуральному числу

@Vaska_Pupkin · Регистрация: 06.02.2024

Студворк — интернет-сервис помощи студентам

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

Добавлено через 26 секунд
И желательно поделится своим решением с остальными)

@Shamil1 · 12.02.2024, 23:49

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
import Data.List (sort)
 
check [] _ = True
check _ [] = False
check (x:xs) (y:ys) = case compare x y of
  LT -> False
  EQ -> check xs ys
  GT -> check (x:xs) ys
 
solve sample n = head $ filter (check sample . sort . show) $ map (*n) [m..]
  where m = read sample `div` n
 
main = print $ solve "01122233" 15

Работает очень медленно.

@extrn · 13.02.2024, 02:35

И т.д... до чего?
это все перестановки цифр числа
9999999999888888888777777776666666555555 444443333222110
за исключением тех, что начинаются на 0?

Или цифр может быть меньше? 444443333222110

А может и пропускать цифры можно? 555555222

А может "Я не слушал лекции. Чо дали, то и решайте, холопы, мне завтра сдавать"

Так или иначе, для произвольного n решение найти вряд ли получится,
потому, что как минимум для любого n > 9999999999888888888777777776666666555555 444443333222110
не найдется ни одного кратного числа, удовлетворяющего этим критериям.

Если только условием не является то, что предположил Shamil1: наличие перечисленных цифр в нужном количестве и остальных в произвольном.

Сообщение от Shamil1

Работает очень медленно.

и check "0112223333" $ sort "33333333222110" проходит проверку, хотя не должен бы, потому, что троек не четыре
Но я бы с удовольствием поприсутствовал бы при сдаче преподавателю этого решения

@Vaska_Pupkin · 13.02.2024, 08:08 **[ТС]**

Спасибо за уделённое время. Правда я не совсем понял, как работает код. Просто если я ему ввожу какое-то число, он постоянно выдаёт одно и тоже: 111222330

@Shamil1 · 13.02.2024, 20:01

Сообщение от extrn

проходит проверку, хотя не должен бы, потому, что троек не четыре

Насколько я понял, в искомом числе должны присутствовать заданные цифры. То есть, при проверке все цифры из первого числа должны быть во втором. Но если из заданный цифр нельзя составить число, которое делится на n, то нужно добавлять цифры.

@Shamil1 · 13.02.2024, 22:28

Сообщение от Vaska_Pupkin

Правда я не совсем понял, как работает код.

Берём все числа, кратные n (map (*n) [m..])
Отбираем (filter) из них те, которые проходят проверку (содержат заданные цифры). Для этого превращаем их в строку (show), сортируем (sort) и передаём вторым аргументом в функцию check.
Возвращаем первое такое число (head).

Если будет время, напишу сегодня код через перестановки, но он сложнее.

Добавлено через 2 часа 19 минут
Написал через перестановки, но работает ещё медленнее. Перестановок слишком много, а их ещё нужно отсортировать по возрастанию.

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import Data.List 
import Control.Monad
 
solve sample n = go [sample] where
  -- новый список, образованный добавлением каждой цифры к каждой строке
  newSamples = liftM2 (:) ['0'..'9']
  -- перестановки для всех строк в списке, отсортированные и без дубликатов
  listPermutations =  nub .  sort . filter ((/='0') . head) . concat . map permutations
  -- список чисел, кратных n
  getMultiples = filter ((==0) . flip mod n) . map read
  -- если среди перестановок есть кратные n, то это ответ
  -- иначе добавляем одну цифру и повторяем 
  go samples = case getMultiples (listPermutations samples) of
    (x:_) -> x
    [] -> go (newSamples samples)
 
main = print $ solve "0112223" 15

@Shamil1 · 13.02.2024, 23:20

На всякий случай (вдруг кто не понял)

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-- применяет функцию двух переменных типов a и b к спискам этих типов ([a] и [b])
liftM2 :: (a -> b -> c) -> [a] -> [b] -> [c]
liftM2 f xs ys = f <$> xs <*> ys
  where
  -- применяем функцию двух переменных к каждому элементу списка
  -- и получаем список функций одной переменной
  f <$> xs = fmap f xs
  -- применяем каждуюю функцию из списка функций к каждому элементу списка
  fs <*> ys = join $ fmap (\f -> fmap f ys) fs
  -- для списков
  fmap = map
  join = concat
 
-- то же самое для списков можно записать проще
liftM2' f xs ys = [f x y | x <- xs, y  <- ys]
 
main = do
  print $ liftM2  (:) ['1'..'3'] ["456", "789"]
  print $ liftM2' (:) ['1'..'3'] ["456", "789"]
  -- ["1456","1789","2456","2789","3456","3789"]

@Mikhaylo · 17.02.2024, 14:23

Сообщение от Vaska_Pupkin

Придумайте наименьшее число, кратное какому-то произвольному натуральному числу n

Наименьшее!

Добавлено через 2 часа 57 минут
Мега-число X состоит из 1+2+3+4+5+6+7+8+9+10=55 цифр. В диапазоне примерно между 1E+55 и 10E+55.
Минимальное число - это у которого "тяжёлые" цифры в конце, т.е. такое 1012223333444445555556666666777777778888 888889999999999. Принцип простой, берём на вооружение.

Пусть n=1234.

Есть некоторое целое число L = X:n.

Умножаем столбиком:

000000001234
L...LLLLLLLLLL
------------------------

------------------------
X...XXXXXXXXX

Смотрим на цифры чисел L, X с конца. Таблица умножения:
1234x0=0
1234x1=1234
1234x2=2468
1234x3=3702
1234x4=4936
1234x5=6170
1234x6=7404
1234x7=8638
1234x8=9872
1234x9=11106

В результате умножения последняя цифра 0, 2, 4, 6, 8 может быть получена двумя вариантами множителей.

Шаги построения дерева по умножению столбиком:
1. L-цифра - любая, но выгодны 2 или 7, тогда X-цифра=8. Первое слагаемое 2х1234=2468 или 7х1234=8638.
2. L-цифра - любая, но выгодны 4 или 9, тогда X-цифра=9. Второе слагаемое 4х1234=4936 или 9х1234=11106. Первое слагаемое 2468 отбрасываем.
3. L-цифра - любая, но выгодны 0 или 5, тогда X-цифра=9. Третье слагаемое 0х1234=0 или 5х1234=6170. Второе слагаемое 11106 отбрасываем.
4. L-цифра - любая, но выгодны 3 или 8, тогда X-цифра=9. Третье слагаемое 3х1234=3702 или 8х1234=9872. Третье слагаемое 6170 отбрасываем.
5. И так далее. В какой-то момент закончатся девятки и придется "расходовать" восьмёрки и т.д.

4 последние цифры 55-значного числа получил на листочке бумаги.
9998 - последние цифры числа X.
3047 - последние цифры числа L.

Добавлено через 34 минуты
Конечно же у меня пока нет доказательства, что такой жадный алгоритм в какой-то момент не придет к противоречию, когда все цифры мега-числа начнут заканчиваться... Возможно не следует отбрасывать все варианты в дереве, особенно последние 4(?). Но я бы попробовал сверх-жадный алгоритм...

Добавлено через 1 час 4 минуты
Запустил Haskell с числами "01122233":13, получил ответ 10212332:13=785564.

Мой жадный алгоритм не сошёлся, а правильный ответ показывает, что жадность с самого начала - это плохо.

Следовательно, требуется строить дерево полное, без усечений.

Добавлено через 11 минут
Ещё раз посидел с карандашом, понял, что выгоднее умножать столбиком, наоборот, с начальной цифры числа L. Таким макаром можно обходить дерево с минимального числа, например, с 10122233, потихоньку двигая "тяжёлые" цифры вперёд.

@Vaska_Pupkin · 24.02.2024, 21:58 **[ТС]**

Это решение очень хорошо собой, но вы не совсем поняли условие: Каждая цифра содержится в числе с+1 раз, где с-сама цифра. Но если мы используем цифру хотя-бы один раз, нам нужно использовать все цифры, которые стоят до неё столько раз, сколько от нас требует условие. Но при этом нам не обязательно использовать для записи числа все возможные цифры. К примеру, нам подойдут такие числа, как 101, 101222, 1012333232 и т.д.

@Shamil1 · 25.02.2024, 01:28

Vaska_Pupkin,
А откуда взялась эта задача? (кто автор)

@Mikhaylo · 25.02.2024, 08:46

Сообщение от Vaska_Pupkin

числу n , в десятичной записи которого один ноль, две единицы

Русский язык как и любой язык программирования весьма точен. Есть разница между "есть" и "может быть".

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

Наименьшее число, кратное какому-то произвольному натуральному числу

Решение

Решение

@Vaska_Pupkin 0 / 0 / 0 Регистрация: 06.02.2024 Сообщений: 12

	Наименьшее число, кратное какому-то произвольному натуральному числу 12.02.2024, 20:37. Показов 1453. Ответов 10 Метки алгоритмы (Все метки) Придумайте наименьшее число, кратное какому-то произвольному натуральному числу n , в десятичной записи которого один ноль, две единицы, три двойки, четыре тройки и т. д. Для решения данной задачи вам нужно написать алгоритм по нахождению такого числа для любого натурального n Добавлено через 26 секунд И желательно поделится своим решением с остальными) 0

@Vaska_Pupkin 0 / 0 / 0 Регистрация: 06.02.2024 Сообщений: 12
	13.02.2024, 08:08 [ТС]
	Спасибо за уделённое время. Правда я не совсем понял, как работает код. Просто если я ему ввожу какое-то число, он постоянно выдаёт одно и тоже: 111222330 0

@Vaska_Pupkin 0 / 0 / 0 Регистрация: 06.02.2024 Сообщений: 12
	24.02.2024, 21:58 [ТС]
	Это решение очень хорошо собой, но вы не совсем поняли условие: Каждая цифра содержится в числе с+1 раз, где с-сама цифра. Но если мы используем цифру хотя-бы один раз, нам нужно использовать все цифры, которые стоят до неё столько раз, сколько от нас требует условие. Но при этом нам не обязательно использовать для записи числа все возможные цифры. К примеру, нам подойдут такие числа, как 101, 101222, 1012333232 и т.д. 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,876
	25.02.2024, 01:28
	Vaska_Pupkin, А откуда взялась эта задача? (кто автор) 1