Гость
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Посчитать количество символов в предыдущих числах, до числа 'm' включительно / 22 сообщений из 22, страница 1 из 1
10.08.2021, 12:44
    #40089833
Ученик_333
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Код: 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
11.08.2021, 15:04
    #40090080
DarkMaster
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Ученик_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
11.08.2021, 15:13
    #40090082
Мимопроходящий
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Ученик_333
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
хороший тамада. и конкурсы интересные. ©
...
Рейтинг: 0 / 0
11.08.2021, 15:16
    #40090084
swame2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
DarkMaster,

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

Хотя бы так

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

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


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

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

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


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

Считай числа 10ками (div в помощь), только не забывай, что 100 - это уже 3 цифры. 1000 - 4 и т.п.
...
Рейтинг: 0 / 0
11.08.2021, 19:21
    #40090148
DHDD
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Ученик_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
11.08.2021, 19:37
    #40090153
x1ca4064
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
DHDD,

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

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


Все что необходимо - возводить 10 в некоторую степень, если циклы нельзя, можно извратиться StrToInt64('1'+StringOfChar('0',N)), также понадобится (10^N-1)/9 - его делаем StrToInt64(StringOfChar('1',N))
...
Рейтинг: 0 / 0
12.08.2021, 08:20
    #40090189
brick08
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
на коленке, со степенями и циклом
Код: 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
12.08.2021, 13:00
    #40090275
alekcvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
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
12.08.2021, 13:22
    #40090283
alekcvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Косяк:

Код: 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
12.08.2021, 13:40
    #40090291
x1ca4064
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
alekcvp,
Остался последний штрих - избавится от цикла и будет O(1) - но для этого нужно вспоминать формулу геометрической прогрессии (2 раза)
...
Рейтинг: 0 / 0
12.08.2021, 16:20
    #40090360
alekcvp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
x1ca4064,

111112222222333333444444 - это не геометрическая прогрессия.
9 180 2700 36000 - тоже.
...
Рейтинг: 0 / 0
12.08.2021, 16:28
    #40090362
Ученик_333
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
Спасибо за подсказки, немного позже замерю скорость выполнения предоставленных примеров.
Собственно моя проблема заключалась в неправильной формулировке вопроса, т.к. задача из шапки темы выполняется в 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
12.08.2021, 22:17
    #40090431
x1ca4064
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посчитать количество символов в предыдущих числах, до числа 'm' включительно
alekcvp
x1ca4064,

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

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

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

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

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


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