|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Код: pascal 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.
Есть ли более простой способ? Желательно без циклов и переменных степеней. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.08.2021, 12:44 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333, Что-то я не совсем понял задачу. В числе 1 - один символ, 22 - 2 символа и т.п. Код: pascal 1. 2. 3. 4. 5. 6.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 15:04 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333 Посчитать количество символов в предыдущих числах, до числа 'm' включительно ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 15:13 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
DarkMaster, За алгоритм маляра и скорее всего переполнение оперативной памяти я бы сразу выгнал с собеседования. Хотя бы так Код: pascal 1. 2. 3. 4.
Но задача все-таки, видимо, должна решаться суммированием групп чисел с одинаковым количества разрядов на количество чисел с этим количеством разрядов. Стебом не посчитал, потому что половина программистов там и пишет, посмотрите например топик про преобразование Фурье ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 15:16 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Все правильно, но нужно считать до больших чисел, к примеру 10000000. Складывание строк в таком случае, не быстрый процесс. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 15:53 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333, Тебе скорость нужна? А так-то да - swame2 слушай - приемлемое решение. Особенно, если не string а классические ShortString пользовать. Хотя там IntToStr() - он может дать просадку по скорости. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 18:47 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
DarkMaster Ученик_333, Тебе скорость нужна? А так-то да - swame2 слушай - приемлемое решение. Особенно, если не string а классические ShortString пользовать. Хотя там IntToStr() - он может дать просадку по скорости. Дело не в скорости, в асимптотике : вместо O(1) или O(log(n)) предлагается использовать O(N), что есть очень плохо. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 19:16 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333, Считай числа 10ками (div в помощь), только не забывай, что 100 - это уже 3 цифры. 1000 - 4 и т.п. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 19:18 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333, Код: pascal 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 19:21 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
DHDD, А сколько времени считает для 18446744073709551615 (2^64-1))? ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 19:37 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333 Есть ли более простой способ? Желательно без циклов и переменных степеней. Все что необходимо - возводить 10 в некоторую степень, если циклы нельзя, можно извратиться StrToInt64('1'+StringOfChar('0',N)), также понадобится (10^N-1)/9 - его делаем StrToInt64(StringOfChar('1',N)) ... |
|||
:
Нравится:
Не нравится:
|
|||
11.08.2021, 21:36 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
на коленке, со степенями и циклом Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 08:20 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
brick08 на коленке, со степенями и циклом Код: pascal 1.
i = 2: 100 * 2 = 200 символов (00, 01, 02, 03, ... ?). i = 1: 10 * 1 = 10 символов + 200 символов от предыдущей итерации?.. У меня вот так получилось, но проверять лень: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 13:00 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Косяк: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 13:22 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
alekcvp, Остался последний штрих - избавится от цикла и будет O(1) - но для этого нужно вспоминать формулу геометрической прогрессии (2 раза) ... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 13:40 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
x1ca4064, 111112222222333333444444 - это не геометрическая прогрессия. 9 180 2700 36000 - тоже. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 16:20 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Спасибо за подсказки, немного позже замерю скорость выполнения предоставленных примеров. Собственно моя проблема заключалась в неправильной формулировке вопроса, т.к. задача из шапки темы выполняется в 5-6 действий. Порыскав в интернете, понял как надо было назвать тему: Найти сумму всех цифр используемых для записи всех натуральных чисел от 0 до любого положительно целого числа. И поставить это не в виде вопроса, а скорее ответа на вопрос. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8.
x1ca4064 Ученик_333 Есть ли более простой способ? Желательно без циклов и переменных степеней. Все что необходимо - возводить 10 в некоторую степень, если циклы нельзя, можно извратиться StrToInt64('1'+StringOfChar('0',N)), также понадобится (10^N-1)/9 - его делаем StrToInt64(StringOfChar('1',N)) Да как раз это я и имел ввиду, судя по всему из переменных "m" и "L", без циклов никак не получится определить переменные "Nm" и "N1". ... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 16:28 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
alekcvp x1ca4064, 111112222222333333444444 - это не геометрическая прогрессия. 9 180 2700 36000 - тоже. Никто и не утверждал, что 9*N*10^(N-1) геометрическая прогрессия, но для суммирования этого ряда пригодится сумма геометрической прогрессии, причем 2 раза :) ... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 22:17 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
Ученик_333 Собственно моя проблема заключалась в неправильной формулировке вопроса, т.к. задача из шапки темы выполняется в 5-6 действий. Ваша формулировка великолепна - очень хорошая задача для собеседования: O(1) - самостоятельная разработка O(log(n)) - реализация готовых алгоритмов O(N) - директор O(N^2) - президент В формулировке с вычислением Nm и N1 все быстро просматривается - интрига исчезает Да как раз это я и имел ввиду, судя по всему из переменных "m" и "L", без циклов никак не получится определить переменные "Nm" и "N1". Если вычисление 10^N нельзя считать атомарной операцией, то можно использовать быстрое возведение в степень, сложность исходной задачи будет O(log(log(N)), проблема ведь не в самих циклах, а в том, сколько итераций они делают. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.08.2021, 23:02 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
x1ca4064 проблема ведь не в самих циклах, а в том, сколько итераций они делают. Да так и есть, тут без циклов не получится. x1ca4064 Ваша формулировка великолепна Спасибо конечно, но я и во второй раз сформулировал неправильно... Найти сумму всех цифр, если не ошибаюсь, означает сложить их между собой (10, 11, 12, 13, 14 = 1+0, 1+1, 1+2, 1+3, 1+4 = 1, 2, 3, 4, 5 = 15) Так уже будет точнее: Найти сумму количества символов используемых для записи всех натуральных чисел от 0 до любого целого числа. x1ca4064 В формулировке с вычислением Nm и N1 все быстро просматривается - интрига исчезает Ну да, тут интрига пропала) Можно немного усложнить, найти количество символов от отрицательного значения до положительного, но с учетом вышеописанных формул, это не так сложно... ... |
|||
:
Нравится:
Не нравится:
|
|||
13.08.2021, 16:33 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
x1ca4064 alekcvp x1ca4064, 111112222222333333444444 - это не геометрическая прогрессия. 9 180 2700 36000 - тоже. Никто и не утверждал, что 9*N*10^(N-1) геометрическая прогрессия, но для суммирования этого ряда пригодится сумма геометрической прогрессии, причем 2 раза :) Ну так продемонстрируйте... ... |
|||
:
Нравится:
Не нравится:
|
|||
13.08.2021, 18:33 |
|
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
|
|||
---|---|---|---|
#18+
alekcvp Ну так продемонстрируйте... Ну Вы, прям, Макиавелли какой-то :) Распишем Sum(N=1..N,N*10^(N-1)) по строкам: 1. 1 2. 10 10 3. 100 100 100 4. 1000 1000 1000 1000 ... N. 10^(N-1) ... 10^(N-1) [N слагаемых] Теперь будем суммировать по столбцам - в каждом столбце есть геометрическая прогрессия: 1. 1 10 100 1000 ... 10^(N-1) [N слагаемых, первый член 1] S1=1*(10^N-1)/(10-1) 2. 10 100 1000 ... 10^(N-1) [N-1 слагаемых, первый член 10] S2=10*(10^(N-1)-1)/9 ... K. 10^(K-1) ... 10^(N-1) [N-K+1 слагаемых, первый член 10^(K-1)] SK=10^(K-1)*(10^(N-K+1)-1)/9 ... N. 10^(N-1) [1 слагаемое, первый и последний член 10^(N-1)] SN=10^(N-1)*(10-1)/9 Используя первый раз сумму геом. прогрессии получили SK=10^(K-1)*(10^(N-K+1)-1)/9=(10^N-10^(K-1))/9=1/9*(10^N)-1/9*10^(K-1) Теперь считаем Sum(K=1..N,SK)=N/9*10^N-1/9*Sum(K=1..N,10^(K-1)) и вот здесь 2й раз пригодится формула геом. прогрессии! Как-то так ... |
|||
:
Нравится:
Не нравится:
|
|||
13.08.2021, 21:12 |
|
|
start [/forum/topic.php?fid=58&msg=40090148&tid=2037107]: |
0ms |
get settings: |
8ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
44ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
others: | 275ms |
total: | 418ms |
0 / 0 |