Определить, какая цифра стоит на заданном месте в последовательности

@neske · Регистрация: 26.03.2010

Студворк — интернет-сервис помощи студентам

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

первая, это когда все числа начинают выписывать в ряд (123456789101112123.. и т.д.) и нужно узнать, какая цифра стоит на i - том месте.
и вторая, это когда окружность, для простоты пирог круглой формы, начинают разрезать по диаметру, и нужно узнать, сколько максимально можно получить кусков за n разрезов.

спасибо!

@alkagolik · 09.12.2011, 23:28

судя по длине числа испльзуется массив, предположу что можно использовать memcpy для

Сообщение от neske

какая цифра стоит на i - том месте.

надо подробней.

Сообщение от neske

сколько максимально можно получить кусков за n разрезов.

2n

@AncinetHero · 09.12.2011, 23:29

Насчет второй, точно по диаметру?

Не по теме:

Читал похожую задачу. Там можно любым образом провести n прямых, в этом и уловка задачи

@neske · 09.12.2011, 23:32 **[ТС]**

alkagolik, я не понял, что подробнее? решение в лоб не пройдет.

AncinetHero, да, вы правы, это я не верно написал, n прямых.

@AncinetHero · 09.12.2011, 23:33

Ко второй задаче ответ выражается формулой

C++
1
n*(n+1)/2+1

Алгоритм кажется такой.

Для получения максимального ответа каждую следующую прямую мы будем проводить так, чтобы она пересекала все предыдущие, а значит если было проведено i прямых, наша прямая пройдет через i частей, значит количество станет равно +i (каждую часть она поделит на 2 части, всего из i частей станет 2*i частей).
И так далее, арифметическая прогрессия.
То есть если у нас проведена 1 прямая, max кусков 1+1=2. Если 2 прямых, кусков 2+2=4. Если 3 прямых, кусков 4+3=7 и т.д.

@neske · 09.12.2011, 23:35 **[ТС]**

а само решение не помните?

@alkagolik · 09.12.2011, 23:38

допустим разрядность m числа x, надо узнать цифру y из разряда n <= m.
y = ( x / 10 ^ (m - n) ) mod 10

Добавлено через 1 минуту

Сообщение от neske

я не понял, что подробнее?

длина числа, тип массива. Это длинная арифметика?

@Dani · 09.12.2011, 23:40

в 1 задаче пару ифов и моды... решал когда-то

@AncinetHero · 09.12.2011, 23:40

Решение вписал выше.

@neske · 09.12.2011, 23:46 **[ТС]**

а вы точно так поняли задачу?
к примеру имеется строка, ну или массив с цифрами, в принципе неважно.
s = 1234567891011121314..
и на 13 месте стоит единица.
а нам необходимо найти на i - том месте.

@Dani · 09.12.2011, 23:49

ограничения?

@alkagolik · 09.12.2011, 23:52

Сообщение от neske

к примеру имеется строка, ну или массив с цифрами, в принципе неважно.

принципиально важно. длинная арифметика в uint - 10 разрядов, есть смысл скопировать нужные байты с помощью memcpy и вычислить число по формуле

@AncinetHero · 09.12.2011, 23:52

Сообщение от Dani

ограничения?

1 <= N <= 10^4 скорее всего)

@Dani · 09.12.2011, 23:54

когда я решал было 1 - 10^9

@AncinetHero · 10.12.2011, 00:01

Сообщение от alkagolik

принципиально важно. длинная арифметика в uint - 10 разрядов, есть смысл скопировать нужные байты с помощью memcpy и вычислить число по формуле

А откуда вы взяли эту формулу? Где можно прочитать про вывод данной формулы?

@alkagolik · 10.12.2011, 00:57

Сообщение от AncinetHero

А откуда вы взяли эту формулу?

из головы. Автор же упорно молчит, числа целые, не целые, символьные, не символьные. Я предположил что речь идет о целых числах, если да то формула имеет вид
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y_{P} = \frac{x_{P}} {P^{m - n}} mod P$ она даст цифру из разряда n<=m числа x, разрядности m. сс = P

Добавлено через 47 минут
если разряды считать справа (как и положено) то P^n

valeriikozlov · 10.12.2011, 01:43

neske, ссылку на задачи можете дать?

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105

	Определить, какая цифра стоит на заданном месте в последовательности 09.12.2011, 23:18. Показов 5723. Ответов 16 Метки нет (Все метки) всем вечер добрый. интересует алгоритм решения к двум задачам. честно говоря, довольно долго думал, но ничего дельного я не придумал. первая, это когда все числа начинают выписывать в ряд (123456789101112123.. и т.д.) и нужно узнать, какая цифра стоит на i - том месте. и вторая, это когда окружность, для простоты пирог круглой формы, начинают разрезать по диаметру, и нужно узнать, сколько максимально можно получить кусков за n разрезов. спасибо! 0

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	09.12.2011, 23:29
	Насчет второй, точно по диаметру? Не по теме: Читал похожую задачу. Там можно любым образом провести n прямых, в этом и уловка задачи 1

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	09.12.2011, 23:32 [ТС]
	alkagolik, я не понял, что подробнее? решение в лоб не пройдет. AncinetHero, да, вы правы, это я не верно написал, n прямых. 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	09.12.2011, 23:35 [ТС]
	а само решение не помните? 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	09.12.2011, 23:40
	в 1 задаче пару ифов и моды... решал когда-то 1

@AncinetHero 50 / 50 / 12 Регистрация: 22.05.2011 Сообщений: 326
	09.12.2011, 23:40
	Решение вписал выше. 1

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	09.12.2011, 23:46 [ТС]
	а вы точно так поняли задачу? к примеру имеется строка, ну или массив с цифрами, в принципе неважно. s = 1234567891011121314.. и на 13 месте стоит единица. а нам необходимо найти на i - том месте. 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	09.12.2011, 23:49
	ограничения? 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	09.12.2011, 23:54
	когда я решал было 1 - 10^9 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	10.12.2011, 01:43
	neske, ссылку на задачи можете дать? 0