Помощь - Поиск - Пользователи - Календарь
Полная версия: ПРОГРАММА НА ПАСКАЛЕ
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
СТАРШИНА
ПОМОГИТЕ РЕШИТЬ НА ПАСКАЛЕ
Бесконечная последовательность цифр составлена из записанных друг за другом квадратов всех натуральных чисел, начиная с единицы: 149162536…… Требуется определить, какая цифра находится на k- месте в этой последовательности.
Lapp
Цитата(СТАРШИНА @ 8.11.2007 12:04) *

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.
старшина
Цитата(Lapp @ 9.11.2007 11:08) *

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

Верхний предел k< (2 в степени 31)
старшина
Цитата(klem4 @ 10.11.2007 12:37) *

один из вариантов
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
Цитата(старшина @ 15.11.2007 8:53) *

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

То есть примерно 2 000 000 000, или весь диапазон LongInt.
klem4, твой вариант у меня сорвался на k = 500 000 .. smile.gif
старшина
Цитата(Lapp @ 15.11.2007 9:20) *

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

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

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