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

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

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

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

первая, это когда все числа начинают выписывать в ряд (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, ссылку на задачи можете дать?

Новые блоги и статьи Все статьи Все блоги /
Исключения в Java: советы, примеры кода и многое другое Javaican 18.05.2025 Исключения — это объекты, созданные когда программа сталкивается с непредвиденной ситуацией: файл не найден, сетевое соединение разорвано, деление на ноль. . . Список можно продолжать до бесконечности. . . .	Как сделать SSO (Single Sign-On) в C# приложении stackOverflow 18.05.2025 SSO — это механизм, позволяющий пользователю пройти аутентификацию один раз и получить доступ к нескольким приложениям без повторного ввода учетных данных. Вы наверняка сталкивались с ним, когда. . .	Kubernetes с Apache Flink для обработки данных в реальном времени Mr. Docker 17.05.2025 Kubernetes — это целая философия управления распределёнными приложениями. В отличие от "примитивных" решений вроде Docker Swarm, K8s (как его ласково называют в тусовке DevOps-инженеров) предлагает. . .	Использование декораторов в Python py-thonny 17.05.2025 Если вы когда-нибудь задумывались о том, как красиво расширить функциональность кода без лишней возни и дублирования, декораторы в Python — та самая волшебная палочка, которую вы искали. По сути, это. . .	Реализация многопоточных сетевых серверов на Python py-thonny 16.05.2025 Когда сталкиваешься с необходимостью писать высоконагруженные сетевые сервисы, выбор технологии имеет критическое значение. Python, со своей элегантностью и высоким уровнем абстракции, может. . .
C# и IoT: разработка Edge приложений с .NET и Azure IoT UnmanagedCoder 16.05.2025 Мир меняется прямо на наших глазах, и интернет вещей (IoT) — один из главных катализаторов этих перемен. Если всего десять лет назад концепция "умных" устройств вызывала скептические улыбки, то. . .	Гибридные квантово-классические вычисления: Примеры оптимизации EggHead 16.05.2025 Гибридные квантово-классические вычисления — это настоящий прорыв в подходах к решению сложнейших вычислительных задач. Представьте себе союз двух разных миров: классические компьютеры, с их. . .	Использование вебсокетов в приложениях Java с Netty Javaican 16.05.2025 HTTP, краеугольный камень интернета, изначально был спроектирован для передачи гипертекста с минимальной интерактивностью. Его главный недостаток в контексте современных приложений — это. . .	Реализация операторов Kubernetes Mr. Docker 16.05.2025 Концепция операторов Kubernetes зародилась в недрах компании CoreOS (позже купленной Red Hat), когда команда инженеров искала способ автоматизировать управление распределёнными базами данных в. . .	Отражение в C# и динамическое управление типами stackOverflow 16.05.2025 Reflection API в . NET — это набор классов и интерфейсов в пространстве имён System. Reflection, который позволяет исследовать и манипулировать типами, методами, свойствами и другими элементами. . .

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

	Определить, какая цифра стоит на заданном месте в последовательности 09.12.2011, 23:18. Показов 5425. Ответов 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