БЛОГ НА HUSL


Есть ли алгоритм для решения задачи без перебора?

Автор вопроса: contrlc contrlc

Дано натуральное число n.

Представить данное число n в виде суммы двух целых чисел x, y (x, y >= 0), в которых не было бы цифр 8 и 9, и первое из слагаемых было бы минимально возможным.

Например: 859 = 102 + 757 и 849 = 72 + 777.


Источник

Ответы (5 шт):

Автор решения: rotabor

Окончательное решение:

def ut(x):
  sx = '0' + str(x)
  lx = len(sx)
  for i in range(lx):
    if sx[i] < '7':
      j = i
    elif sx[i] > '7':
      sx = str(int(sx[:j + 1]) + 1) + '0' * (lx - j - 1)
      break
  return int(sx)

def dt(x):
  sx = str(x)
  lx = len(sx)
  for i in range(lx):
    if sx[i] > '7':
      sx = sx[:i] + '7' * (lx - i)
      break
  return int(sx)

def p(x):
  y = x - dt(x)
  y, ym = x - dt(x - ut(y)), y
  while (y != ym):
    y, ym = x - dt(x - ut(y)), y
  print('Result: ', x, y, x - y)

p(100)
p(107)
p(108)
p(777)
p(849)
p(853)
p(859)
p(863)
p(890)
p(899)
p(900)
p(985)
p(993)

Result: 100 0 100
Result: 107 0 107
Result: 108 1 107
Result: 777 0 777
Result: 849 72 777
Result: 853 76 777
Result: 859 102 757
Result: 863 100 763
Result: 890 113 777
Result: 899 122 777
Result: 900 123 777
Result: 985 210 775
Result: 993 216 777

Алгоритм:

  1. ut выдаёт ближайшее большее семёрочное число.
  2. dt выдаёт ближайшее меньшее семёрочное число.
  3. p ищет схождение ut и dt.

Из области занимательной математики

Казалось бы, 7 - большое число по отношению к 10, и среди однозначных чисел, включая 0, 8 чисел годных и всего 2 - нет, то есть годных 80%. Но с ростом количества разрядов N доля годных чисел уменьшается: для N = 9 (1 000 000 000 чисел) годных оказывается меньше 13,5% (8 ^ 9). Тем не менее, любое число можно представить суммой двух годных чисел. И число (8/10) ^ N стремительно уменьшается с ростом N!

Очевидно, что такой фокус (представить число суммой двух чисел с ограничением по используемым цифрам) можно проделать вплоть до цифры 5.

Что касается вопроса Станислава о сходимости поиска, то мне кажется, что плохих чисел тут нет, сходимость очень хорошая. Самые плохие числа - периодические, в которых группа цифр [<8]+[>7]+ повторяется. Например, числу '59' * 20 нужно 20 итераций. Судя по всему, каждому переходу границы нужна одна итерация.

→ Ссылка
Автор решения: Qwertiy

Каждая цифра числа превращается в сумму двух: max(x-7, 0) + min(x, 7). Переноса нет. Потом для каждого фрагмента 10 в первом числе проверяем, можем ли мы заменить эти 10 на меньшее число, чтобы в правом разряде второго числа получилось 7, и, если да, то заменяем. tio.run

def solve(x):
  a = []
  b = []

  while x:
    d = x % 10
    x //= 10

    a.append(max(d-7, 0))
    b.append(min(d, 7))

  for i in range(len(a)-1, 1, -1):
    if a[i] == 1 and a[i-1] == 0 and b[i-1] < 5:
      a[i] = 0
      a[i-1] = b[i-1] + 3
      b[i-1] = 7

  l = 0
  r = 0

  for d in a[::-1]:
    l = l*10 + d

  for d in b[::-1]:
    r = r*10 + d
  
  return (l,r)
  

for x in [100, 107, 108, 777, 821, 849, 853, 859, 863, 867, 890, 899, 900, 985, 993, 880088, 821000849, 8000000001]:
  a,b = solve(x)
  print(x, "=", a, "+", b, x == a + b)

100 = 0 + 100 True
107 = 0 + 107 True
108 = 1 + 107 True
777 = 0 + 777 True
821 = 50 + 771 True
849 = 72 + 777 True
853 = 100 + 753 True
859 = 102 + 757 True
863 = 100 + 763 True
867 = 100 + 767 True
890 = 120 + 770 True
899 = 122 + 777 True
900 = 200 + 700 True
985 = 210 + 775 True
993 = 220 + 773 True
880088 = 103011 + 777077 True
821000849 = 50000072 + 771000777 True
8000000001 = 300000000 + 7700000001 True
→ Ссылка
Автор решения: LolPopGames

Для начала нужно разделить число на цифры:

n = 859 # или другое число
x = 0 # первое слагаемое
y = 0 # второе слагаемое

# ------- делим число на цифры
digits = [] # список для цифр n
digits.append(n % 10) # первая цифра

# для остальных цифр
div_a_mod_num = 10
i=0
sub_num = digits[0] # число для вычета
while n > div_a_mod_num/10:
    digits.append((n - sub_num) // div_a_mod_num % div_a_mod_num) # остальные цифры
    i+=1
    div_a_mod_num*=10
    sub_num+=digits[i]
digits.reverse()

Потом нужно найти максимальное число:

# ------- ищем максимальное число
i=0
for e in digits:
    digits[i] = e
    if e > 7:
        digits[i] = 7
    i+=1

Далее пребразовать цифры обратно в число:

# ------- превращаем список цифр в число
digits.reverse()
i=0
j=1
while i < len(digits):
    y += digits[i] * j
    
    i+=1
    j*=10

И вычислить первое:

# ------- вычисляем первое число
x = n - y

Конечный код:

n = 859 # или другое число
x = 0 # первое слагаемое
y = 0 # второе слагаемое

# ------- делим число на цифры
digits = [] # список для цифр n
digits.append(n % 10) # первая цифра

# для остальных цифр
div_a_mod_num = 10
i=0
sub_num = digits[0] # число для вычета
while n > div_a_mod_num/10:
    digits.append((n - sub_num) // div_a_mod_num % div_a_mod_num) # остальные цифры
    i+=1
    div_a_mod_num*=10
    sub_num+=digits[i]
digits.reverse()

# ------- ищем максимальное число
i=0
for e in digits:
    digits[i] = e
    if e > 7:
        digits[i] = 7
    i+=1

# ------- превращаем список цифр в число
digits.reverse()
i=0
j=1
while i < len(digits):
    y += digits[i] * j
    
    i+=1
    j*=10

# ------- вычисляем первое число
x = n - y

# ------- показ конечного результата
print(x, y)
→ Ссылка
Автор решения: Old Skull

Раньше я быдлокодил в основном на Delphi, так что прошу прощения, если что...

  1. Берём число 859.
  2. Вычисляем максимально близкое к нему без 8 и 9. Это число 777.
  3. Далее вычисляем разность: 859 - 777 = 82.
  4. Ближайшее к 82 число без 8 и 9 - это 100. Поскольку из последней цифры числа 859 мы вычли 2, надо к 100 прибавить 2. Получаем 859 = 102 + 757
import numpy as np

# find maximal number which is <= num and does not contain 8 and 9
# ex: 849 => 777; # 178 => 177; # 234 => 234
def normalize_right_part(num):
    num_arr = np.array(tuple(str(num)))
    m = np.argmax(num_arr > '7')
    if m > 0 or num_arr[0] > '7':
        num_arr[m:] = '7'
    
    return int( ''.join(num_arr) )

# if num does not contains 8 or 9 then leave it as is
# otherwise round it up to nearest number which does not contain 8 and 9
# ex: 849 => 1000; # 178 => 200; 234 => 234; 158 => 160
def normalize_left_part(num):
    num_arr = np.fromiter(str(num), dtype=int)

    m = np.argmax(num_arr > 7)
    if m == 0 and num_arr[0] < 8:
        return num

    increase = False

    for i in range(0, m+1):
        if increase:
            num_arr[m-i] += 1
            increase = False
        
        if num_arr[m-i] > 7:
            num_arr[m-i] = 0
            increase = True

    num_arr[m:] = 0

    if increase:
        num_arr = np.insert(num_arr, 0, 1)

    return int( ''.join(num_arr.astype(dtype=str)) )

# find number = a + b, where a and b don't contain 8 and 9
# and a is the minimal possible
def find_sum(num):
    right_part = normalize_right_part(num)
    left_part  = num - right_part

    while True:
        left_part = normalize_left_part(left_part)
        right_part = num - left_part
        
        right_part_new = normalize_right_part(right_part)

        if right_part_new == right_part:
            break
        
        left_part += right_part - right_part_new

    return left_part, right_part

tio.run

100 = 0 + 100
107 = 0 + 107
108 = 1 + 107
154 = 0 + 154
777 = 0 + 777
821 = 44 + 777
849 = 72 + 777
853 = 76 + 777
859 = 102 + 757
863 = 100 + 763
867 = 100 + 767
890 = 113 + 777
899 = 122 + 777
900 = 123 + 777
985 = 210 + 775
993 = 216 + 777
880088 = 102311 + 777777
821000849 = 43223072 + 777777777
8000000001 = 222222224 + 7777777777
858585858585 = 101010101010 + 757575757575
→ Ссылка
Автор решения: Stanislav Volodarskiy

step_down(k) ищет ближайшее число меньшее или равное k свободное от восьмёрок и девяток. Для этого ищем самую старшую восьмёрку-девятку и начиная с этого места меняем хвост числа на сплошные семёрки:

19969
17777

step_up(k) делает такой же поиск в сторону больших чисел. Снова ищем старшую восьмёрку-девятку, но теперь, если перед ней есть семёрки они тоже включаются. Найденный хвост отрезается, начало числа увеличивается на единицу, на место хвоста вписываются нули:

1277953
12
13
1300000

decompose(n) разбивает n на слагаемые a, b. Начальные значения 0, n. Если в слагаемом b есть восьмёрки-девятки, оно заменяется ближайшим меньшим, свободным от них. Значение a обновляется.

Если в слагаемом a есть восьмёрки-девятки, оно заменяется ближайшим большим, свободным от них. Значение b обновляется.

Если оба слагаемых свободны от восьмёрок-девяток, это ответ. Так как пары a, b перебираются от нуля по возрастанию a, мы получаем пару с минимальным первым слагаемым:

Сложность – куб числа цифр O(ln3n) (это в предположении что перевод int ⇄ str делается за логарифм). Если убрать преобразования и всю арифметику сделать на десятичных строках можно получить квадрат логарифма O(ln2n).

import re


def step_down(k):
    s = str(k)
    m = re.search('[89]', s)
    if m is None:
        return k
    i = m.start(0)
    return int(s[:i] + '7' * (len(s) - i))


def step_up(k):
    s = str(k)
    m = re.search('7*[89]', s)
    if m is None:
        return k
    i = m.start(0)
    return int(str(int('0' + s[:i]) + 1) + '0' * (len(s) - i))


def decompose(n):
    a, b = 0, n
    while True:
        b2 = step_down(b)
        if b2 == b:
            break
        a, b = n - b2, b2
        a2 = step_up(a)
        if a2 == a:
            break
        a, b = a2, n - a2
    return a, b


print(*decompose(int(input())))

$ echo 859 | python decompose.py
102 757

$ echo 849 | python decompose.py
72 777

$ echo 19969 | python decompose.py
2202 17767

P.S. Поиск таких n при которых этот алгоритм работает медленнее всего – не плохая задача сама по себе.

→ Ссылка

licensed under cc by-sa 3.0 with attribution.