Пусть есть массив цифр (0 и 1) получаемый "дописыванием" последовательных степеней 10 справа:
110100100010000100000...
то есть сначала написали 1, потом 10, потом 100 и т.д.
Задано число N требуется узнать какая цифра (0 или 1) находится на N месте массива. Массив нумеруется с 0.

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

последоватльность блоьшая?

массив[N]

(1) да какая разница? скажем так, N-й элемент в массиве точно есть

(2) отличное решение, а теперь если самого массива нет, но требуется найти его N-е значение, можно конечно полностью его восстановить, а проще?

(3) просто если не большая то может просто заполнить зарнее

(4) Ну дык так и пиши, что массива нет

(6) ступил ))

и все таки интернсо это просто задачка или приминяемость есть?

(0) Расположение единицы подчиняется сумме арифметической прогрессии, думаю что надо плясать от этого

если последовательность не большая и нужна пропроизводительность имеет смысл заранее заполнить массив, самый быстрый способ.

(4) Можно и проще - если учесть, что речь идёт о последовательности подстрок длины 2,3,4,...
Формула для "треугольных" чисел - известна.
Итого - время O(1).

Вообще лучше не заполнять полностью массив, а заполнять только только единицы.
k=1;
Для i=0 По КоличествоИтераций Цикл
к=к+i;
МассивЕдиниц.Добавить(к);
КонецЦикла;
А  потом проверять есть ли N в этом массиве, если есть то 1, иначе 0.

(12) Не надо вообще ничего заполнять.
Для m степеней массив имеет длину m(m+1)/2.
При этом единицы расположены на местах k(k+1)/2+1. На прочих местах - нули.

Единицы на местах 1+N(N-1)/2, N-натуральное.
Хотим проверить место X.
решаем уравнение -
1+N(N-1)/2=X
N^2-N+(2-2X)=0

8X-7 должно являться квадратом нечетного числа...
Но так как квдратом четного быть не может - значит просто квадратом целого.

Давайте полагаться на теорию вероятности и при большом N Это скорее всего будет 0 :)

(0)Вероятно простое суммирование и будет самый быстрый по скорости алгоритм. Но если софтина в лёгкую считает квадратные корни, а циклы крутит медленно, то по пути (9) вырисовывается квадратичное неравенство.

(14) Нумерация с нуля, так что единицы находятся на местах N(N+1)/2

ищем минимальное число k, для которого k!>N от него и пляшем
(сравниваем N с (k-1)! ).
х.з. как со скоростью

(16) решение в (14)
Проверить является ли число квадратом целого (взять корень) при больших X - всяко быстрее чем перебирать все N от единицы

(17) Это имеет принципиальное значение?!

Тек = 0;
Для сч = 1 По N Цикл
   Тек = Тек + сч;
   Если Тек = N Тогда
       Сообщить("1");
       Прервать
   ИначеЕсли Тек > N Тогда
       Сообщить("0");
       Прервать
   КонецЕсли
КонецЦикла;

Проверяй 8Х+1 тогда...

(17) Отсюда (продолжая ту же мысль)
Ответ: 1+8N если является квадратом целого числа, то на месте N стоит единица, иначе 0.
Пример N=15
1+8*N=1+8*15=121 , 121 является квадратом целого числа 11, значит на месте с номером 15 стоит единица

(23) Вы похоже неудачно пытаетесь украсть у меня решение :)

(24) Я же приписал "продолжая ту же мысль", имел в виду "продолжая ту же мысль что и в (14) но с учетом поправки (17)"

(25) :) Я же шучу.

Метод Ньютона довольно быстро извлекает корни (LOG N), но, вроде бы, видел (давно) итерационную схему, которая работает существенно быстрее, но вспомнить не могу. Может и ошибаюсь.

Если (sqrt(8N+1)-1)/2 - целое, то элемент = 1, иначе = 0
достаточно быстрое решение?

(27) Я вчера прикинул - вроде быстрее О() от логарифма корень не извлечь.(но это утверждение нужно проверять, и нам не корень надо извлечь, а проверить на квадрат целого) Но это лучше, чем О() от квадратный корень, который получается если проверять значения по очереди.

(28) читайте ветку.

(29) быстрее, чем за О(Log N) не то что корень не извлечь, вообще любая арифметическая операция при больщой разрядности  делается за O(Log N).
Сколько вам надо сделать 32(64) битных  операций, чтобы сложить два числа, состоящих из сто-тыщ мильон знаков?

(30) Да, мигрень у меня. Торможу. Чтоб прочитать число нужен Логарифм операций. (в случае больших чисел)
Но есно это правило не работает, если число влезает в разрядность процессора.

Из 1+N(N-1)/2=X следует что
(N-1)^2 < 2(x-1) < N^2
т.е. вычисляем ЦЕЛУЮ часть корня из 2(x-1)
k = [SQRT(2(x-1))]
проверяем равенство k(k+1) = 2(х-1)

(0)Господа, а у меня вот вопрос. В какой форме подается число на вход алгоритма? И кто (что) будет выполнять алгоритм?

(33) А ни уни ли пенисуально ли?

(34) Нет. Например если число подается в виде символьной последовательности :) то задача решается выборкой нужного символа.

(0) не глядя посты....
нужно решить квадратное уравнение 0.5n^2-0.5n+2-N = 0
Если в решении целое полжительное то на заданной позиции стоит 1 иначе - 0.

(35) Число вообще не подаётся. Оно - константа.

(37) тогда нет смысла разрабатывать алгоритм.

(38) подается число N "в виде числа"
например 2010 и надо узнать какое число стоит в массиве на 2010 месте
самого массива с учетом поправки в (4) нет

Если  (1+SQRT(8*N - 7))/2 - целое тогда 1, иначе 0

(40) Имхо 1 деление у тебя лишнее.

(41) и сложение - см выше

(41) ну если учесть, что N-натуральное, а 8N-7 - всегда нечетное, то остается SQRT(8N-7)

поправочка, если нумерация массива начинается с нуля, целый корень надо искать из 8*(N+1)-7 = 8*N+1

Проверив остаток от деления на 10-ть этого выражения и любых квадратов, выясняем, что N не должно заканчиваться на 2, 4, 7 и 9.