Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Количество чисел из диапазона, с повторяющимися разрядами
СообщениеДобавлено: 17 янв 2024, 09:42 
Не в сети
Начинающий
Зарегистрирован:
17 янв 2024, 09:21
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Не знаю насколько это задача школьного уровня, если вдруг что не так, прошу модераторов перенести в нужный раздел.
Итак, допустим у нас имеется 256 ячеек памяти в компьютере, в которых может храниться любое число от 1 до 2^256. Нужно узнать какое количество чисел, в этом диапазоне, являются числами с разрядами идущими подряд (не меньше 3 одинаковых разрядов подряд), нули тоже учитывать. рассчитать нужно для десятичных и шестнадцатиричных чисел.
т.е. если мы возьмем диапазон от 1 до 1000 в двоичном виде, то числа, которые нам нужно найти будут: 0001, 0002, 0003, 0004, 0005, 0006, 0007, 0008, 0009, 0111, 0222, 0333, 0444, 0555, 0666, 0777, 0888, 0999, 1000.
для шестнадцатиричного случая получим диапазон от 1 до 3Е8, следовательно и числа будут такими: 111, 222, 333, 444, 555, 666, 777, 888, 999, aaa, bbb, ccc, ddd
если диапазон маленький, то эту задачу можно решить простым перебором, но если диапазон большой, то проблема.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Количество чисел из диапазона, с повторяющимися разрядами
СообщениеДобавлено: 09 фев 2024, 12:34 
Не в сети
Продвинутый
Аватара пользователя
Зарегистрирован:
01 фев 2018, 07:40
Сообщений: 59
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 0

Добавить очки репутацииУменьшить очки репутации
Для решения этой задачи, можно воспользоваться математическим подходом. Давайте разберемся с каждым случаем по отдельности.

Десятичные числа:
Количество десятичных чисел с разрядами, идущими подряд, можно посчитать с помощью принципа включения-исключения. Для этого найдем количество чисел, у которых все разряды одинаковые, затем вычтем количество чисел, у которых все разряды, кроме первого, одинаковые, и так далее.

Количество чисел с одинаковыми разрядами равно 9 (от 1 до 9). Количество чисел с двумя одинаковыми разрядами равно [math]9 \times 9 = 81[/math] (каждый из 9 разрядов может быть от 1 до 9). Количество чисел с тремя одинаковыми разрядами равно [math]9 \times 9 \times 9 = 729[/math], и так далее.

Таким образом, общее количество десятичных чисел с разрядами, идущими подряд, равно сумме всех этих значений:

[math]9 + 81 + 729 + \ldots + 9 \times 9 \times 9 \times 9 = 9(1 + 9 + 9^2 + \ldots + 9^{n-1})[/math]

где [math]n[/math] - количество разрядов (в данном случае [math]n = 10[/math]).

Можно заметить, что это является геометрической прогрессией с первым членом 1 и знаменателем 9. Сумма такой прогрессии вычисляется по формуле:

[math]S_n = \frac{a_1(1 - r^n)}{1 - r}[/math]

где [math]S_n[/math] - сумма прогрессии, [math]a_1[/math] - первый член прогрессии, [math]r[/math] - знаменатель прогрессии, [math]n[/math] - количество членов прогрессии.

В нашем случае:

[math]S_{10} = \frac{1(1 - 9^{10})}{1 - 9} = \frac{1 - 9^{10}}{-8}[/math]

Таким образом, количество десятичных чисел с разрядами, идущими подряд, в диапазоне от 1 до [math]2^{256}[/math] будет равно [math]\frac{1 - 9^{10}}{-8}[/math].

Шестнадцатеричные числа:
Аналогично, количество шестнадцатеричных чисел с разрядами, идущими подряд, можно посчитать с помощью принципа включения-исключения.

Количество чисел с одинаковыми разрядами равно 15 (от 1 до 9 и от A до F). Количество чисел с двумя одинаковыми разрядами равно [math]15 \times 15 = 225[/math]. Количество чисел с тремя одинаковыми разрядами равно [math]15 \times 15 \times 15 = 3375[/math], и так далее.

Аналогично десятичному случаю, общее количество шестнадцатеричных чисел с разрядами, идущими подряд, будет равно:

[math]15 + 225 + 3375 + \ldots + 15 \times 15 \times 15 \times 15 = 15(1 + 15 + 15^2 + \ldots + 15^{n-1})[/math]

где [math]n[/math] - количество разрядов (в данном случае [math]n = 16[/math]).

Сумма геометрической прогрессии с первым членом 1 и знаменателем 15 будет:

[math]S_{16} = \frac{1(1 - 15^{16})}{1 - 15} = \frac{1 - 15^{16}}{-14}[/math]

Таким образом, количество шестнадцатеричных чисел с разрядами, идущими подряд, в диапазоне от 1 до [math]2^{256}[/math] будет равно [math]\frac{1 - 15^{16}}{-14})[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Количество чисел из диапазона, с повторяющимися разрядами
СообщениеДобавлено: 09 фев 2024, 16:51 
Не в сети
Гений
Зарегистрирован:
02 янв 2014, 21:56
Сообщений: 537
Cпасибо сказано: 62
Спасибо получено:
153 раз в 139 сообщениях
Очков репутации: 29

Добавить очки репутацииУменьшить очки репутации
MakarovDS, вы решили какую-то задачу, но она не совпадает с задачей, которую сформулировал testkorob.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Определить количество комбинаций диапазона до слова

в форуме Комбинаторика и Теория вероятностей

beats

5

1308

03 май 2015, 13:02

Количество шестизначных чисел

в форуме Комбинаторика и Теория вероятностей

Kalok

3

303

17 май 2020, 16:00

Количество шестизначных чисел

в форуме Дискретная математика, Теория множеств и Логика

greenpilot

2

214

19 дек 2019, 20:20

Количество перестановок чисел

в форуме Комбинаторика и Теория вероятностей

Vlad_ok

8

441

25 янв 2021, 09:44

Количество трёхзначных чисел

в форуме Комбинаторика и Теория вероятностей

Gagarin

11

1083

17 янв 2016, 01:42

Комбинаторика - количество n-разрядных чисел

в форуме Дискретная математика, Теория множеств и Логика

Claudia

5

573

12 июн 2017, 10:28

Найти количество простых чисел от 0 до N

в форуме Теория чисел

IvanPetrovPRO

4

825

03 фев 2019, 12:29

Совершенное количество простых чисел

в форуме Теория чисел

Ferma

0

194

01 дек 2019, 10:23

Бесконечное количество чисел-близнецов

в форуме Теория чисел

Foka

3

479

09 фев 2019, 15:50

Найти количество натуральных чисел

в форуме Теория чисел

Trek

6

1102

16 янв 2015, 21:20


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved