Как определить количество чисел из заданного диапазона таких, у которых три соседних разряда одинаковые?

@kelod · Регистрация: 17.01.2013

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

например у нас есть диапазон чисел от 0 до 9999999999999999
как определить сколько чисел в этом диапазоне, таких, у которых три соседних разряда одинаковые, т.е.
0000000000000111
0000000000001110
0000000000011100
0000000000111000
...
0000000000000555
0000000000005550
0000000000055500
0000000000555000
...
0099900000000000
0999000000000000
9990000000000000
другие разряды разумеется могут быть и не нулевыми и вообще не одинаковые
как это вообще посчитать, не перебирая числа?

Комментарий модератора

Правила форума, пункт 4.3. Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят.
Правила форума, пункт 4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие результаты получены.

@Red white socks · 12.01.2024, 16:59

Проще вычислить обратную задачу: найти количество чисел, у которых никакой символ не идёт 3 раза подряд.
Также будем считать числа без нулей. С нулями можно посчитать аналогично, но общая идея для демонстрации размывается.
Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(k)$ - количество таких k-значных чисел.
Пусть также $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(k)$ - количество искомых чисел,у которых первые 2 цифры не совпадают, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_2(k)$ - у которых первые 2 цифр совпадают.
Тогда
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f(k) = f_1(k) + f_2(k)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f_2(k+1) = f_1(k)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(k+1) = 8(f_1(k)+f_2(k))$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(1) = 9, \,\, f_2(1) = 0$
Оставив только одну функцию, получаем
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(k) = 8(f_1(k-1)+f_1(k-2))$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f(k) = f_1(k) + f_1(k-1)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(1) = 9, \,\, f_1(0) = 0$

Добавлено через 2 минуты
Для подсчета с нулями потребуется в одну из указанных формул добавить пару слагаемых и чуть изменить начальные условия.

@mihailm · 12.01.2024, 17:54

Red white socks, не совсем понятно, что хочет ТС исходя из его примеров. После 0000000000001110 например идет 0000000000011100, а там есть числа 0000000000001111 и 0000000000001112 они что не подходят?
А три нуля рядом это не "три соседних разряда одинаковые" что ли?

kelod, задачу нормально поставьте

@Red white socks · 12.01.2024, 18:24

mihailm, тут возможны вариации трактовки условия, но главная идея решения остается та же.
ТС остается доработать напильником под свои условия.

Добавлено через 4 минуты
Первые две строчки задают вроде однозначно, а уж как подходящие числа упорядочивать - дело вкуса.

@kelod · 12.01.2024, 22:58 **[ТС]**

mihailm, все числа подходят, лишь бы три цифры были бы подряд, т.е. число 4359996810002467 тоже подходит и три нуля рядом это тоже подходит, и больше 3 одинаковых чисел тоже подходит
Red white socks, извините, но я почти ничего не понимаю в том что вы написали

@mihailm · 13.01.2024, 16:44

kelod, а здесь 0000000000000123 есть три соседних разряда одинаковые?

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

Red white socks, извините, но я почти ничего не понимаю в том что вы написали

понятно, что учиться нужно, например по книге Белоусов А.И. и др. - Элементы комбинаторики, МГТУ - 2012

@kelod · 15.01.2024, 23:20 **[ТС]**

mihailm, да, там есть одинаковые разряды

Новые блоги и статьи Все статьи Все блоги /
Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .	Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .
Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .	Dispose и Finalize в C# stackOverflow 12.06.2025 Работая с C# больше десяти лет, я снова и снова наблюдаю одну и ту же историю: разработчики наивно полагаются на сборщик мусора, как на волшебную палочку, которая решит все проблемы с памятью. Да,. . .	Повышаем производительность игры на Unity 6 с GPU Resident Drawer GameUnited 11.06.2025 Недавно копался в новых фичах Unity 6 и наткнулся на GPU Resident Drawer - штуку, которая заставила меня присвистнуть от удивления. По сути, это внутренний механизм рендеринга, который автоматически. . .	Множества в Python py-thonny 11.06.2025 В Python существует множество структур данных, но иногда я сталкиваюсь с задачами, где ни списки, ни словари не дают оптимального решения. Часто это происходит, когда мне нужно быстро проверять. . .	Работа с ccache/sccache в рамках C++ Loafer 11.06.2025 Утилиты ccache и sccache занимаются тем, что кешируют промежуточные результаты компиляции, таким образом ускоряя последующие компиляции проекта. Это означает, что если проект будет компилироваться. . .

@Red white socks 4522 / 1898 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.01.2024, 16:59
	Проще вычислить обратную задачу: найти количество чисел, у которых никакой символ не идёт 3 раза подряд. Также будем считать числа без нулей. С нулями можно посчитать аналогично, но общая идея для демонстрации размывается. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(k)$ - количество таких k-значных чисел. Пусть также $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(k)$ - количество искомых чисел,у которых первые 2 цифры не совпадают, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_2(k)$ - у которых первые 2 цифр совпадают. Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(k) = f_1(k) + f_2(k)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_2(k+1) = f_1(k)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(k+1) = 8(f_1(k)+f_2(k))$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(1) = 9, \,\, f_2(1) = 0$ Оставив только одну функцию, получаем $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(k) = 8(f_1(k-1)+f_1(k-2))$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(k) = f_1(k) + f_1(k-1)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?f_1(1) = 9, \,\, f_1(0) = 0$ Добавлено через 2 минуты Для подсчета с нулями потребуется в одну из указанных формул добавить пару слагаемых и чуть изменить начальные условия. 1

@mihailm 1692 / 1130 / 296 Регистрация: 05.10.2014 Сообщений: 5,506
	12.01.2024, 17:54
	Red white socks, не совсем понятно, что хочет ТС исходя из его примеров. После 0000000000001110 например идет 0000000000011100, а там есть числа 0000000000001111 и 0000000000001112 они что не подходят? А три нуля рядом это не "три соседних разряда одинаковые" что ли? kelod, задачу нормально поставьте 0

@Red white socks 4522 / 1898 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	12.01.2024, 18:24
	mihailm, тут возможны вариации трактовки условия, но главная идея решения остается та же. ТС остается доработать напильником под свои условия. Добавлено через 4 минуты Первые две строчки задают вроде однозначно, а уж как подходящие числа упорядочивать - дело вкуса. 0

@kelod 11 / 11 / 0 Регистрация: 17.01.2013 Сообщений: 504
	12.01.2024, 22:58 [ТС]
	mihailm, все числа подходят, лишь бы три цифры были бы подряд, т.е. число 4359996810002467 тоже подходит и три нуля рядом это тоже подходит, и больше 3 одинаковых чисел тоже подходит Red white socks, извините, но я почти ничего не понимаю в том что вы написали 0

@kelod 11 / 11 / 0 Регистрация: 17.01.2013 Сообщений: 504
	15.01.2024, 23:20 [ТС]
	mihailm, да, там есть одинаковые разряды 0