ПРОГРАММА НА ПАСКАЛЕ, КВАДРАТЫ Опции

[СТАРШИНА]

ПОМОГИТЕ РЕШИТЬ НА ПАСКАЛЕ
Бесконечная последовательность цифр составлена из записанных друг за другом квадратов всех натуральных чисел, начиная с единицы: 149162536…… Требуется определить, какая цифра находится на k- месте в этой последовательности.

[Lapp]

149162536…… Требуется определить, какая цифра находится на k- месте в этой последовательности.

Каков верхний предел для k?

[klem4]

один из вариантов

uses crt;

function digit(value: LongInt; digit_num: Byte): Byte;
begin
  while digit_num > 0 do begin
    value := value div 10;
    dec(digit_num);
  end;
  digit := value mod 10;
end;

function DigitsCount(n: LongInt): Byte;
var
  count: Byte;
begin
  count := 0;

  while n > 0 do begin
    inc(count);
    n := n div 10;
  end;

  DigitsCount := count;
end;

function GetDigit(const k: LongInt): LongInt;
var
  s, i: LongInt;
begin
  s := 1;
  i := 2;

  while (s < k) do begin
    s := s + DigitsCount(i * i);
    i := i + 1;
  end;

  GetDigit := digit(pred(i) * pred(i), abs(s - k));
end;

var
  k, i: LongInt;

begin

  clrscr;

  write('k = '); readln(k);

  writeln('result = ', GetDigit(k));
  writeln;

  for i := 1 to 1000 do begin // можно увеличивать ... это для наглядности
     if i = k then TextColor(Red) else TextColor(White);
     write(GetDigit(i));
     if i mod 70 = 0 then writeln;
  end;
  readln;
end.

[старшина]

Каков верхний предел для k?

Верхний предел k< (2 в степени 31)

[старшина]

один из вариантов

uses crt;

function digit(value: LongInt; digit_num: Byte): Byte;
begin
  while digit_num > 0 do begin
    value := value div 10;
    dec(digit_num);
  end;
  digit := value mod 10;
end;

function DigitsCount(n: LongInt): Byte;
var
  count: Byte;
begin
  count := 0;

  while n > 0 do begin
    inc(count);
    n := n div 10;
  end;

  DigitsCount := count;
end;

function GetDigit(const k: LongInt): LongInt;
var
  s, i: LongInt;
begin
  s := 1;
  i := 2;

  while (s < k) do begin
    s := s + DigitsCount(i * i);
    i := i + 1;
  end;

  GetDigit := digit(pred(i) * pred(i), abs(s - k));
end;

var
  k, i: LongInt;

begin

  clrscr;

  write('k = '); readln(k);

  writeln('result = ', GetDigit(k));
  writeln;

  for i := 1 to 1000 do begin // можно увеличивать ... это для наглядности
     if i = k then TextColor(Red) else TextColor(White);
     write(GetDigit(i));
     if i mod 70 = 0 then writeln;
  end;
  readln;
end.

Спасибо!

[Lapp]

Верхний предел k< (2 в степени 31)

То есть примерно 2 000 000 000, или весь диапазон LongInt.
klem4, твой вариант у меня сорвался на k = 500 000 ..

[старшина]

То есть примерно 2 000 000 000, или весь диапазон LongInt.
klem4, твой вариант у меня сорвался на k = 500 000 ..

Нужен весь диапазон LongInt.
Тесты обычно бывают на самые последние позиции.

[volvo]

В принципе, воспользовавшись вот этой последовательностью:
Number of squares (of positive integers) with n digits (или формулой, приведенной там же) реально практически мгновенно найти число, в квадрате которого будет находиться искомая цифра, и собственно номер цифры в этом числе... Основную сложность представляет возведение числа в квадрат (скажем, для получения 2147483645-ой цифры заданной последовательности надо будет найти седьмую цифру 17-значного числа 132985066²)...

Сомневаюсь, что есть способы это сделать, кроме использования длинной арифметики, но тут надо смотреть на скорость других методов (без использования последовательности A049415)...