powered by simpleCommunicator - 2.0.37     © 2025 Programmizd 02
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Посчитать количество символов в предыдущих числах, до числа 'm' включительно
22 сообщений из 22, страница 1 из 1
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40089833
Ученик_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.
28.
29.
30.
31.
32.
33.
34.
35.
uses Math;

procedure TForm1.Button1Click(Sender: TObject); // Посчитать количество символов в предыдущих числах, до числа 'm' включительно
var
m,m2,L,i,Nm,N1,n: integer;
Lc0,Lc1: extended;
Sm,Sn1: string;
begin
 m := 11; // Любое целое число кроме 0

 Lc0 := -((Abs(m)/m)-1)/2; // 1-если "m" отрицательное, иначе 0
 m2 := Abs(m); // Любое положительное целое число
 L := IntToStr(m2).Length; // Количество символов в числе "m2" [промежутки: 1=(0..9), 2=(10..99), 3=(100..999)]

 Sm := '1';
 Sn1 := '0';

 // Добавить (L-1) символов в строки "Sm","Sn1"
 for i := 0 to L-2 do
 begin
  Sm := Sm+'0'; // 1000....
  Sn1 := '1'+Sn1; // 1110....
 end;

 Sn1[1] := '0'; // Убрать первую цифру из числа

 // Перевести строки в числа
 Lc1 := -Floor((L-2)/L); // 1-если "L"=1, иначе 0
 Nm := Floor(StrToInt(Sm)-Lc1); // Минимальное значение промежутка "L"
 N1 := StrToInt(Sn1); // Взаимосвязь между "L" и количеством единиц, с нулем на конце (1=0, 2=10, 3=110, 4=1110)

 n := Floor(Nm*(L-1)-N1+(m2-Nm+1)*L+m2*Lc0); // Количество символов в предыдущих числах, до числа 'm' включительно (с учетом нуля)

 Form1.Caption := 'Число: '+inttostr(m)+' Количество символов: '+inttostr(n);
end;


Есть ли более простой способ? Желательно без циклов и переменных степеней.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090080
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ученик_333,

Что-то я не совсем понял задачу. В числе 1 - один символ, 22 - 2 символа и т.п.

Код: pascal
1.
2.
3.
4.
5.
6.
S:='';

for I:=M downto 0 do
     S:=S+IntToStr(I);

L:=Length(S);
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090082
Мимопроходящий
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ученик_333
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
хороший тамада. и конкурсы интересные. ©
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090084
swame2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
DarkMaster,

За алгоритм маляра и скорее всего переполнение оперативной памяти я бы сразу выгнал с собеседования.

Хотя бы так

Код: pascal
1.
2.
3.
4.
L := 0;

for I:=M downto 0 do
     L:=L+Length(IntToStr(I));


Но задача все-таки, видимо, должна решаться суммированием групп чисел с одинаковым количества разрядов на количество чисел с этим количеством разрядов.
Стебом не посчитал, потому что половина программистов там и пишет, посмотрите например топик про преобразование Фурье
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090105
Ученик_333
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Все правильно, но нужно считать до больших чисел, к примеру 10000000.
Складывание строк в таком случае, не быстрый процесс.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090140
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ученик_333,

Тебе скорость нужна? А так-то да - swame2 слушай - приемлемое решение. Особенно, если не string а классические ShortString пользовать. Хотя там IntToStr() - он может дать просадку по скорости.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090145
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DarkMaster
Ученик_333,

Тебе скорость нужна? А так-то да - swame2 слушай - приемлемое решение. Особенно, если не string а классические ShortString пользовать. Хотя там IntToStr() - он может дать просадку по скорости.


Дело не в скорости, в асимптотике : вместо O(1) или O(log(n)) предлагается использовать O(N), что есть очень плохо.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090146
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ученик_333,

Считай числа 10ками (div в помощь), только не забывай, что 100 - это уже 3 цифры. 1000 - 4 и т.п.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090148
DHDD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ученик_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.
function IntStrLength(m: integer): integer;
var v: integer;
begin
    Result := 1;
    v := m div 10;
    while v >= 1 do begin
        v := v div 10;
        Inc(Result);
    end;
end;

function Test1: integer;
var m: integer;
begin
    Result := 0;
    //for m := 0 to 12 do begin
    for m := 0 to 10000000 do begin
        Inc(Result, IntStrLength(m));
    end;
end;

procedure TForm1.FormCreate(Sender: TObject);
var startTime: TDateTime;
begin
    startTime := Now;
    showmessage(inttostr(Test1) + sLineBreak + TimeToStr(Now - startTime));
end;
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090153
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DHDD,

А сколько времени считает для 18446744073709551615 (2^64-1))?
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090168
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ученик_333

Есть ли более простой способ? Желательно без циклов и переменных степеней.


Все что необходимо - возводить 10 в некоторую степень, если циклы нельзя, можно извратиться StrToInt64('1'+StringOfChar('0',N)), также понадобится (10^N-1)/9 - его делаем StrToInt64(StringOfChar('1',N))
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090189
Фотография brick08
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
на коленке, со степенями и циклом
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
function LenPrevNumb(m: int64): int64;
var
  i, lm: Integer;
begin
  lm := Length(IntToStr(m));
  Result := (m - ((10 ** (lm - 1)) - 1)) * lm;
  for i := lm - 1 downto 1 do
  begin
    Result := (10 ** i) * i + Result;
  end;
end;
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090275
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
brick08
на коленке, со степенями и циклом
Код: pascal
1.
    Result := (10 ** i) * i + Result;



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.
var
  I, L, C: Int64;
begin
  C := 0;
  L := Trunc(Log10(M));
  for I := 0 to L do
    C := C + 9 * Trunc(Power(10, I)) * (I + 1);
  C := 1 + (M - Trunc(Power(10, L)) - 1) * (L + 1) + C;
  WriteLn(C);
end;
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090283
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Косяк:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
var
  I, L, C: Int64;
begin
  C := 0;
  L := Trunc(Log10(M));
  for I := 0 to L - 1 do
    C := C + 9 * Trunc(Power(10, I)) * (I + 1);
  C := 1 + (M - Trunc(Power(10, L))) * (L + 1) + C;
  WriteLn(C);
end.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090291
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp,
Остался последний штрих - избавится от цикла и будет O(1) - но для этого нужно вспоминать формулу геометрической прогрессии (2 раза)
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090360
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064,

111112222222333333444444 - это не геометрическая прогрессия.
9 180 2700 36000 - тоже.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090362
Ученик_333
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Спасибо за подсказки, немного позже замерю скорость выполнения предоставленных примеров.
Собственно моя проблема заключалась в неправильной формулировке вопроса, т.к. задача из шапки темы выполняется в 5-6 действий.
Порыскав в интернете, понял как надо было назвать тему:
Найти сумму всех цифр используемых для записи всех натуральных чисел от 0 до любого положительно целого числа.
И поставить это не в виде вопроса, а скорее ответа на вопрос.

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
0. Любое целое положительное число		              	m = 99999
1. Определить кол-во символов в числе "m"			L = 5
2. Количество нолей = ("L"-1) и единица в начале		Nm = 10000
3. Количество единиц = ("L"-2) и ноль на конце			N1 = 1110
4. Сумма количества символов, от нуля, до ("L"-1)		n = Nm*(L-1)-N1 = 38890
5. Добавляем оставшийся промежуток от ("L"-1) до "m"		n = n + (m-Nm+1)*L = 488890
----------------------------------------------------
6. Если "-m", то добавляем к полученной сумме "+m"		n = n + m = 588889


x1ca4064
Ученик_333

Есть ли более простой способ? Желательно без циклов и переменных степеней.


Все что необходимо - возводить 10 в некоторую степень, если циклы нельзя, можно извратиться StrToInt64('1'+StringOfChar('0',N)), также понадобится (10^N-1)/9 - его делаем StrToInt64(StringOfChar('1',N))

Да как раз это я и имел ввиду, судя по всему из переменных "m" и "L", без циклов никак не получится определить переменные "Nm" и "N1".
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090431
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp
x1ca4064,

111112222222333333444444 - это не геометрическая прогрессия.
9 180 2700 36000 - тоже.

Никто и не утверждал, что 9*N*10^(N-1) геометрическая прогрессия, но для суммирования этого ряда пригодится сумма геометрической прогрессии, причем 2 раза :)
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090445
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ученик_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)), проблема ведь не в самих циклах, а в том, сколько итераций они делают.
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090599
Ученик_333
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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 все быстро просматривается - интрига исчезает

Ну да, тут интрига пропала) Можно немного усложнить,
найти количество символов от отрицательного значения до положительного,
но с учетом вышеописанных формул, это не так сложно...
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090631
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x1ca4064
alekcvp
x1ca4064,

111112222222333333444444 - это не геометрическая прогрессия.
9 180 2700 36000 - тоже.

Никто и не утверждал, что 9*N*10^(N-1) геометрическая прогрессия, но для суммирования этого ряда пригодится сумма геометрической прогрессии, причем 2 раза :)

Ну так продемонстрируйте...
...
Рейтинг: 0 / 0
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
    #40090670
x1ca4064
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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й раз пригодится формула геом. прогрессии!
Как-то так
...
Рейтинг: 0 / 0
22 сообщений из 22, страница 1 из 1
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]