Цитата(ioManip @ 27.10.2012, 10:16  ) |
| найти закономерность |
| Код |
|
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Для новичков > Определить цифру на n - ой позиции послед - ти |
| Автор: ioManip 27.10.2012, 09:16 |
| Задача Дано n - целое. Последовательность сост. из степеней 10 - ки (110100100010000....). Определить какая цифра находиться на n позиции последовательности. Вообщем не прошу исходного кода( на Ваше усмотрение ), прошу помочь найти закономерность(алгоритм). Из того, что я увидел: 1. Можно через строки, но ведь должен быть другой способ!? 2. Нашел зависимость, связанную с ариф. прогрессией, т.е. 1 - ы стоят на 0,1,3,6 позициях, но не пойму как реализовать... |
| Автор: feodorv 27.10.2012, 09:56 | ||||
|
| Автор: Ln78 27.10.2012, 10:06 | ||
Сумма членов арифметической прогрессии, в данном случае: k*(k+1)/2. Выяснить, представляется ли заданное n в таком виде. Возможны, например, такие варианты: 1. Просто в цикле увеличиваем переменную k, рассчитываем k*(k+1)/2 и сравниваем с n. Если равно - единица, если меньше - продолжаем цикл, если больше - заканчиваем цикл, считаем, что там нуль. 2. Цикл заменить расчётом квадратного корня из 2*n, взять целую часть от этого корня, т.е. k = int(sqrt(2.0*n)). Если k*(k+1) = 2*n - единица, иначе - нуль. |
| Автор: ioManip 27.10.2012, 10:46 |
| feodorv, Спасибо! Ln78, Спасибо  . Скажите, а как Вы пришли в этой формуле? k*(k+1)/2.  |
| Автор: Dem_max 27.10.2012, 10:59 |
| Это тема должна находиться в разделе Алгоритмы. |
| Автор: Ln78 27.10.2012, 11:01 | ||
ioManip, лет 30 назад учился в школе. Там мне рассказали про эту форурмулу те, кто пришёл к ней ещё раньше.  |
| Автор: feodorv 27.10.2012, 11:38 | ||||
Как рассуждал Гаусс-школьник: напишем ряд чисел от 1 до N в строчку, а под ним ещё один - от N до 1, число под числом:
Нетрудно заметить, что сумма двух чисел в столбце - всегда N+1, столбцов - N, поэтому сумма чисел в двух рядах - N*(N+1), а в одном ряду - N*(N+1)/2 (поскольку ряды совпадают, только записаны в противоположных порядках)... |
| Автор: ioManip 27.10.2012, 11:47 |
feodorv, Спасибо!  Добавлено через 12 минут и 33 секунды Ребята  Последний вопрос! 2 - ой алгоритм предложенный Ln78, почему именно корень из 2 * n? |
| Автор: feodorv 27.10.2012, 12:08 | ||||
Поэтому k ~= sqrt(2*n)  |