Более оптимальное решение 5 задачи

@_halmgood · Регистрация: 19.10.2022

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

есть задачка я решил её, но она работает очень долго(~60 сек)
может кто знает как можно оптимизировать, чтобы работала хотя бы менее 15 секунд

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Вычисляется сумма S1 всех нечётных цифр десятичной записи числа N. Если нечётных цифр нет, сумма S1 считается равной 0.
2) Вычисляется сумма S2 всех цифр десятичной записи числа N, стоящих на позициях с чётными номерами. Позиции нумеруются слева направо, начиная с 1. Для однозначных чисел сумма S2 считается равной 0.
3) Вычисляется результат R как модуль разности S1 и S2.
Например, N = Дано число N = 1234. Сумма нечётных цифр S1 = 1 + 3 = 4. Сумма цифр в позициях с чётными номерами S2 = 2 + 4 = 6. Результат работы алгоритма R = 6 – 4 = 2.
Укажите наименьшее число, в результате обработки которого по данному алгоритму получится число 29.

мой код:

Python
1
2
3
4
5
6
7
8
9
10
R = 0
k = 0
m = set()
while R != 29:
    k += 1
    s1 = sum([int(i) for i in list(filter(lambda x: int(x) % 2 != 0, str(k)))])
    s2 = sum([int(i) for i in str(k)[1::2]])
    R = abs(s1 - s2)
 
print(k)

Ответ: 16080808

@Parramon · 17.02.2023, 13:29

А почему ты s1 считаешь одним способом, а s2 другим?
Замени строку 6 на аналог строки 7
И ответ, кстати, будет другой
Пардон, неправильно понял условие

@piton21 · 17.02.2023, 13:35

А где

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

натуральное число N

А зачем m = set()?

@Parramon · 17.02.2023, 13:36

Python
1
2
3
4
5
6
7
8
9
R = 0
k = 0
while R != 29:
    k += 1
    ks = str(k)
    s1 = sum([int(i) for i in ks if int(i) % 2 == 1])
    s2 = sum([int(i) for i in ks[1::2]])
    R = abs(s1 - s2)
print(k)

Добавлено через 53 секунды
piton21, ну это на время выполнения не влияет... Но я убрал, конечно

@_halmgood · 17.02.2023, 13:45 **[ТС]**

пытался по другому решить, забыл убрать

@Parramon · 17.02.2023, 13:49

_halmgood, для сравнения

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from timeit import timeit
 
def f1():
    R = 0
    k = 0
    m = set()
    while R != 29:
        k += 1
        s1 = sum([int(i) for i in list(filter(lambda x: int(x) % 2 != 0, str(k)))])
        s2 = sum([int(i) for i in str(k)[1::2]])
        R = abs(s1 - s2)
    print(k)
 
def f2():
    R = 0
    k = 0
    while R != 29:
        k += 1
        ks = str(k)
        s1 = sum([int(i) for i in ks if int(i) % 2 == 1])
        s2 = sum([int(i) for i in ks[1::2]])
        R = abs(s1 - s2)
    print(k)
 
print(timeit('f1()', number=10, setup='from __main__ import f1'))
print(timeit('f2()', number=10, setup='from __main__ import f2'))

Bash
1
2
204.51764519999998
44.28301339999999

Фактически, в требуемые 4 раза быстрее

@_halmgood · 17.02.2023, 14:15 **[ТС]**

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

_halmgood, для сравнения

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from timeit import timeit
 
def f1():
    R = 0
    k = 0
    m = set()
    while R != 29:
        k += 1
        s1 = sum([int(i) for i in list(filter(lambda x: int(x) % 2 != 0, str(k)))])
        s2 = sum([int(i) for i in str(k)[1::2]])
        R = abs(s1 - s2)
    print(k)
 
def f2():
    R = 0
    k = 0
    while R != 29:
        k += 1
        ks = str(k)
        s1 = sum([int(i) for i in ks if int(i) % 2 == 1])
        s2 = sum([int(i) for i in ks[1::2]])
        R = abs(s1 - s2)
    print(k)
 
print(timeit('f1()', number=10, setup='from __main__ import f1'))
print(timeit('f2()', number=10, setup='from __main__ import f2'))

Bash
1
2
204.51764519999998
44.28301339999999

Фактически, в требуемые 4 раза быстрее

@Parramon, да это сильно улучшило время, но все же надо именно 15

@Parramon · 17.02.2023, 14:27

_halmgood, так это 10 вызовов....

@_halmgood · 17.02.2023, 14:28 **[ТС]**

кстати у меня не особо

Bash
1
2
3
4
16080808
44.28327119999449
16080808
37.22779560000345

@Parramon · 17.02.2023, 15:03

А так:

Python
1
2
3
4
5
6
7
8
9
10
def f2():
    R = 0
    k = 0
    while R != 29:
        k += 1
        n = [(k//(10**i))%10 for i in range(ceil(log10(k))-1, -1, -1)]
        s1 = sum([i for i in n if i % 2 == 1])
        s2 = sum(n[::2])
        R = abs(s1 - s2)
    print(k)

Добавлено через 11 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def f3():
    R = 0
    k = 0
    while R != 29:
        k += 1
        flag = True
        s1, s2 = 0, 0
        for i in str(k):
            if i in '13579':
                s1 += int(i)
            if flag:
                s2 += int(i)
            flag = not flag
        R = abs(s1 - s2)
    print(k)

@Red white socks · 17.02.2023, 18:50

Тут суть в том, что из десятка посчитать эти суммы достаточно один раз.

Добавлено через 1 час 58 минут
Как пример.
Любую вашу функцию берем (пусть f2) и вставляем небольшой кусок

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def f2():
    R = 1
    k = 1
    while R != 29:
        if k % 100 == 0 and abs(R - 29) > 9:
            k += 100
        else:    
            k += 1
        ks = str(k)
        s1 = sum([int(i) for i in ks if int(i) % 2 == 1])
        s2 = sum([int(i) for i in ks[1::2]])
        R = abs(s1 - s2)
    print(k)
    
print(timeit('f2()', number=1, setup='from __main__ import f2'))
 
# 16080808
# 0.3317185999985668

@_halmgood · 17.02.2023, 19:53 **[ТС]**

Red white socks,
пока наилучшее решении, но не идеальное.
потому что некоторые решения она находить позже чем они встречаются при полном переборе

@Red white socks · 17.02.2023, 20:20

_halmgood, бла-бла-бла
Доказательства будут?

@_halmgood · 17.02.2023, 21:17 **[ТС]**

Red white socks, вот тебе докозательство)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from timeit import timeit
 
def f1():
    R = 1
    k = 1
    st = set()
    while R != 29:
        if k % 100 == 0 and abs(R - 29) > 9:
            k += 100
        else:
            k += 1
        ks = str(k)
        s1 = sum([int(i) for i in ks if int(i) % 2 == 1])
        s2 = sum([int(i) for i in ks[1::2]])
        if abs(s1 - s2) not in st:
            st.add(abs(s1 - s2))
            print('k=', k, ' R=',abs(s1 - s2), sep='')
        R = abs(s1 - s2)
    print(k)
    
    
def f2():
    R = 1
    k = 1
    st = set()
    while R != 29:
        k += 1
        ks = str(k)
        s1 = sum([int(i) for i in ks if int(i) % 2 == 1])
        s2 = sum([int(i) for i in ks[1::2]])
        if abs(s1 - s2) not in st:
            st.add(abs(s1 - s2))
            print('k=', k, ' R=',abs(s1 - s2), sep='')
        R = abs(s1 - s2)
    print(k)
 
 
print(timeit('f1()', number=1, setup='from __main__ import f1'))
print(timeit('f2()', number=1, setup='from __main__ import f2'))

Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
вывод при полном:
k=2 R=0
k=3 R=3
k=5 R=5
k=7 R=7
k=9 R=9
k=10 R=1
k=22 R=2
k=24 R=4
k=26 R=6
k=28 R=8
k=109 R=10
k=309 R=12
k=509 R=14
k=709 R=16
k=909 R=18
k=1408 R=11
k=1608 R=13
k=1808 R=15
k=10709 R=17
k=10909 R=19
k=30909 R=21
k=50909 R=23
k=70909 R=25
k=90909 R=27
k=160818 R=20
k=180818 R=22
k=280808 R=24
k=1070909 R=26
k=1090909 R=28
k=3090909 R=30
k=5090909 R=32
k=7090909 R=34
k=9090909 R=36
k=16080808 R=29
16080808
39.07852169999387
 
вывод при твоем переборе:
k=2 R=0
k=3 R=3
k=5 R=5
k=7 R=7
k=9 R=9
k=10 R=1
k=22 R=2
k=24 R=4
k=26 R=6
k=28 R=8
k=10900 R=10
k=30900 R=12
k=50900 R=14
k=70900 R=16
k=90900 R=18
k=140800 R=11
k=160800 R=13
k=180800 R=15
k=1070900 R=17
k=1090900 R=19
k=3090900 R=21
k=3090901 R=22
k=3090903 R=24
k=3090905 R=26
k=3090907 R=28
k=3090909 R=30
k=3090921 R=20
k=5090900 R=23
k=5090909 R=32
k=7090900 R=25
k=7090909 R=34
k=9090900 R=27
k=9090909 R=36
k=16080808 R=29
16080808
0.6267125000013039

@Red white socks · 17.02.2023, 21:48

_halmgood, это проблема твоих кривых рук, а не моего решения)

@anton78spb · 17.02.2023, 21:51

_halmgood, У меня минимальное число получилось 2090909.

Python
1
2
3
4
5
6
7
8
9
10
11
r = 0
i = 0
while r != 29:
    i += 1
    d = []
    j = i
    while j:
        d.append(j % 10)
        j //= 10
    r = abs(sum(d[::2]) - sum(d[1::2]))
print(i)

@Red white socks · 17.02.2023, 22:08

Приведенный мной способ решает поставленную задачу - найти минимум для R = 29. И никто не говорил, что надо подсчитать все минимумы для R от 1 до скольки там. Для этого нужно включать мозг и не тупо вставить принт, а метод модифицировать.
Я легко могу сделать расчет за секунду для всех скопом, но теперь, конечно, не буду. Думай сам.

Добавлено через 1 минуту
anton78spb, нечетные цифры - это не цифры на нечетных позициях.

@Gdez · 18.02.2023, 01:04

Задача легко решается аналитически доказательством, что s1, s2 => (1, 30) или (2, 31). Первая пара возможна только для s1=1 и s2=30 (обратное невозможно) и как следствие минимальные - это восьмизначные числа и первое из них 16080808; а для второй пары s1=31 и s2=2 и первое число 103090929…

@Parramon · 18.02.2023, 01:16

Gdez, 6080818, не?

@Gdez · 18.02.2023, 05:17

Parramon, для этого числа R=0

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	17.02.2023, 13:29
	А почему ты s1 считаешь одним способом, а s2 другим? Замени строку 6 на аналог строки 7 И ответ, кстати, будет другой Пардон, неправильно понял условие 0

@_halmgood 0 / 0 / 0 Регистрация: 19.10.2022 Сообщений: 6
	17.02.2023, 13:45 [ТС]
	пытался по другому решить, забыл убрать 0

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	17.02.2023, 14:27
	_halmgood, так это 10 вызовов.... 0

@_halmgood 0 / 0 / 0 Регистрация: 19.10.2022 Сообщений: 6
	17.02.2023, 19:53 [ТС]
	Red white socks, пока наилучшее решении, но не идеальное. потому что некоторые решения она находить позже чем они встречаются при полном переборе 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	17.02.2023, 20:20
	_halmgood, бла-бла-бла Доказательства будут? 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	17.02.2023, 21:48
	_halmgood, это проблема твоих кривых рук, а не моего решения) 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	17.02.2023, 22:08
	Приведенный мной способ решает поставленную задачу - найти минимум для R = 29. И никто не говорил, что надо подсчитать все минимумы для R от 1 до скольки там. Для этого нужно включать мозг и не тупо вставить принт, а метод модифицировать. Я легко могу сделать расчет за секунду для всех скопом, но теперь, конечно, не буду. Думай сам. Добавлено через 1 минуту anton78spb, нечетные цифры - это не цифры на нечетных позициях. 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	18.02.2023, 01:04
	Задача легко решается аналитически доказательством, что s1, s2 => (1, 30) или (2, 31). Первая пара возможна только для s1=1 и s2=30 (обратное невозможно) и как следствие минимальные - это восьмизначные числа и первое из них 16080808; а для второй пары s1=31 и s2=2 и первое число 103090929… 1

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	18.02.2023, 01:16
	Gdez, 6080818, не? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	18.02.2023, 05:17
	Parramon, для этого числа R=0 0