Как найти количество чисел в промежутке
Перейти к содержимому

Как найти количество чисел в промежутке

  • автор:

Найти количество чисел из заданного промежутка, в которых есть цифра Х

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

Найти количество чисел из промежутка [N; К], в которых есть цифра Х.

Лучшие ответы ( 1 )

94731 / 64177 / 26122

Регистрация: 12.04.2006

Сообщений: 116,782

Ответы с готовыми решениями:

Найти количество простых чисел не больше N, в записи которых есть хоть одна четная цифра
Здравствуйте! Есть число N.Нужно найти количество простых чисел не больше N в записи которых есть.

Вводятся числа a и b. Найти количество чисел в диапазоне [a;b], у которых последняя цифра равна 7.
Помогите пожалуйста с программой. Задание: Вводятся числа a и b. Найти количество чисел в диапазоне.

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

2620 / 1735 / 916

Регистрация: 16.10.2013

Сообщений: 5,045

Записей в блоге: 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
#include using namespace std; int find(int arr[], int start, int end, int x){ int count = 0; for (int i = start; i  end; i++){ count += (arr[i] == x) ? 1 : 0; } return count; } int main() { int arr[10] = {1, 399, 2, 399, 3, 399, 4, 399, 5, 6}; // будем искать число 399 int count = find(arr, 0, 9, 399); // проверим на всем интервале cout  "count: "  count  endl; count = find(arr, 1, 5, 399); // проверим на интервале от 1 до 5 (. 399, 2, 399, 3, 399. ) cout  "count: "  count  endl; return 0; }

Как посчитать количество чисел-палиндромов в большом промежутке?

Нужно посчитать количество палиндромов в промежутке от a до b. Решается легко, если промежуток — до 10000 Но, как решить задачу, где нужно найти количество палиндромов в промежутке от 1.026.376 до 10**15 (квадриллиона)? И желательно за быстрое время. Перебором слишком долго, может есть какие-то формулы, где можно просто числа брать, не проверяя каждое на палиндромность?

Отслеживать
15.5k 31 31 золотой знак 19 19 серебряных знаков 29 29 бронзовых знаков
задан 19 мая 2023 в 16:15
21 2 2 бронзовых знака

Для суммы последовательных палиндромов можно вывести формулы без прямого суммирования всех палиндромов. Решение будет примерно за k или k^2, где k число цифр верхней границы.

19 мая 2023 в 16:55

сопоставьте заголовок вопроса с текстом, пожалуйста. сейчас из заголовка следует, что вам нужна сумма, а из текста вопроса — количество чисел.

19 мая 2023 в 18:32

@n1tr0xs, я разбился в лепёшку и решил для суммы. Гм. (Количество идёт в качестве бесплатного приложения).

19 мая 2023 в 18:33
@n1tr0xs, поменял название, простите!
20 мая 2023 в 15:33

Добавьте в вопрос код вашего решения. Не важно что оно медленное, важно чтобы оно было. Иначе вопрос закроют.

20 мая 2023 в 15:35

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

f(k) — число чисел-палиндромов из k разрядов. Тогда

Девятка отвечает за цифры старшего разряда — от единицы до девяти. Степень десятки — за остальные разряды из старшей половины числа.

g(k) — число чисел-палиндромов из не более чем k разрядов. Тогда

  • g(2k) = 2·10 k — 2;
  • g(2k + 1) = 11·10 k — 2.

Доказывается по индукции (g(n + 1) = g(n) + f(n + 1)).

h(n) — число чисел-палиндромов не более n. Я покажу на примере как его можно сосчитать быстро. Пусть n = 345678. Разобъём все палиндромы не более n на группы:

 ? - палиндромы длины один. Их f(1) ?? - палиндромы длины два. Их f(2) . - палиндромы длины три. Их f(3) . - палиндромы длины четыре. Их f(4) . - палиндромы длины пять. Их f(5) 1. 1 - таких палиндромов 100 (все палиндромные цифровые строки длины 4) 2. 2 - тоже самое (первые цифры от единицы до 3 - 1) 30??03 - таких палиндромов 10 (все палиндромные цифровые строки длины 2) 31??13 - тоже самое 32??23 - тоже самое 33??33 - тоже самое (вторые цифры от нуля до 4 - 1) 340043 - такой палиндром один (все палиндромные цифровые строки длины 0) 341143 - тоже самое 342243 - тоже самое 343343 - тоже самое 344443 - тоже самое (третьи цифры от нуля до 5 - 1) 345543 - такой палиндром один, но надо отдельно проверить что он не больше n 

Получается такая программа:

def ps_count(k): """ число палиндромных строк длины k """ return 10 ** ((k + 1) // 2) def p_count_10p(k): """ число чисел-палиндромов не более k разрядов """ return 10 ** ((k + 1) // 2) + 10 ** (k // 2) - 2 def p_count(n): """ число чисел-палиндромов не более n """ if n == 0: return 0 digits = tuple(map(int, str(n))) m = len(digits) # короткие палиндромы c = p_count_10p(m - 1) for i in range((m + 1) // 2): # палиндромы вида ABC. CBA c += (digits[i] - (0 if i > 0 else 1)) * ps_count(m - 2 * (i + 1)) if digits[:m // 2 - 1::-1]  
echo 1026376 1_000_000_000_000_000 | python pcount.py 109997973 

Программа работает за логарифмическое время. Её можно переделать для расчёта суммы палиндромов. Первоначально так и было, но вопрос изменился и ответ упростился.

Нахождение количества чисел между двумя натуральными числами

Данный калькулятор определяет количество натуральных числел между двумя натуральными числами.

РУКОВОДСТВО

Введите в каждое поле по одному натуральному числу и нажмите кнопку "Рассчитать"

ТЕОРИЯ

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

Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна?

Здравствуйте.
Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.

Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.
Программа получает два натуральных числа A и B, не превосходящих 10^9, A Программа должна вывести одно число - количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.

Решение, что приходит на ум: два цикла (цикл в цикле) - В первом перебираем сами числа, а во втором цифры каждого числа.

Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)

Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого - путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).

Кстати, странно, что у таких чисел еще нет названия 🙂

Заранее благодарен, Артем.

  • Вопрос задан более трёх лет назад
  • 15964 просмотра

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *