Посчитать количество чисел, содержащих единицу, на промежутке [1; N]
upd: загоняние в строку и подсчёт символов тоже не катит. Большие числа типа 10^9 должно считать быстро.
upd2: речь идёт о десятичном представлении числа.
Для проверки можно использовать это:
Слабо.
В лоб удобнее =)
И огромную переменную потребует.
достаточно посчитать количество чисел НЕ содержащих единицы. А это 9^N. Значит ответ 10^N-9^N.
А если еще минуту подумать, то будет как-то так:
Вот окончательная формула:
Надо посчитать кол-во чисел, содержащих единицу, в промежутке [1; 10].
10^10-10^9 = 9000000000. Over 9000. А на самом-то деле их там два (10 и 1).
> достаточно посчитать количество чисел НЕ содержащих единицы
подход хороший! а вот метод счёта лучше доопределить.
верно, что для всех чисел, содержащих в записи N знаков, будет . дальше как у вас. вот только число N задано несколько иначе.
>Надо посчитать кол-во чисел, содержащих единицу, в промежутке [1; 10].
то есть по твоему 101 и 111 — числа НЕ сожаржащие единицу?
Ты определись с условием-то.
>достаточно посчитать количество чисел НЕ содержащих единицы. А это 9^N. Значит ответ 10^N-9^N.
не понял.
Посчитаем кол-во единиц от 1 до N=11
Ответ: 4 (1, 10, 11)
10^11 — 9^11 = 68618940391
Промежуток [1; 10] это следующие числа: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Из них только 2 содержат единицу.
>Надо посчитать кол-во чисел, содержащих единицу, в промежутке [1; 10].
А ничего, что N — число разрядов?
Да и формула моя для промежутка [0; 10^N] работает. Доопределить легко.
> Ответ: 4 (1, 10, 11)
> Да и формула моя для промежутка [0; 10^N] работает.
И правда, похоже на то.
> камбинаторика?
насчёт А промолчу, но вообще нет, я сейчас вообще не в ВУЗе с весны.
млин! ну верный же он подход написал.
для числа N определяете число знаков в представлении M = log(N) (округление вниз)
значит число чисел [1, 1*10^M] будет вычислено по приведённой ранее формуле.
теперь берём k = (N/10^M) (вниз). очевидно, что столько раз без одного будет повторять ситуация, с 10^M — 9^M значений.
для старшего знака посчитали.
дальше для всех младших чисел в представлении повторяем процедуру. и да, предполагается, что запись будет в более чем 2-ой системе?
> и да, предполагается, что запись будет в более чем 2-ой системе?
В десятеричной. В двоичной было бы совсем просто :).
я просто про то, что формула обобщается на представление в любой системе счисления. только вместо 10 и 9=(10-1) будут A и A-1
> дальше для всех младших чисел в представлении повторяем процедуру.
поправка — если старшая цифра != 1. так?
зачем же. в любом случае. если старшая 1 — значит умножать на k — 1 не нужно (или просто на k).
1ABCD = 10000 + ABCD
для 10^4 вы посчитали. считаем для ABCD дальше
если первое число 1- тогда используем формулу и помним, что для любого числа, кроме 1 на этом месте, будет (A-1) таких чисел.
3ABCD = 10000 + 2* 10000 + ABCD Res = R + (3 — 1 ) * (R-1) + R2 + (A-1) (R2 -1) + R3 + (B-1) R3 + R4 + (C-1) R4 + R(D)
Блин, не вдупляю. Можешь разжевать?
Вот есть число 2146. Какие шаги надо сделать, чтобы получить результат?
>Да и формула моя для промежутка [0; 10^N] работает. Доопределить легко.
рекурсивно пройтись на уменьшение разрядности. То есть N-1 раз в итоге.
>Слабо вывести формулу?
А для непозиционной системы счисления,
например, для римских чисел «cлабо вывести формулу»? 🙂
Я правильно понял?
- dikiy(n) = exp(n*ln(10)) — exp(n*ln(9)) + 1 — число чисел с единичкой в промежутке [1; 10^n].
- dikiy2(n, m) = dikiy(n)*m — число чисел с единичкой в промежутке [1; m*10^n], где m<10.
только доопределять нужно корректно, т.е.
dikiy(n) = dikiy(n,1) = exp(n*ln(10)) — exp(n*ln(9)) + 1
dikiy2(n, m) = dikiy(n,1) + (m-1)*(dikiy(n,1) — 1)
> dikiy(n) = dikiy(n,1)
не понял, что за 2й параметр?
> что за 2й параметр?
да глючит меня. мне просто для подобия dikiy и dikiy2 нужно было. т.е. dikiy2 это такой невырожденный случай dikiy
всё нормально. или внутри функции разводить по значению параметра, или напрямую другую функцию вызывать.
int dikiy2( int n, int m) {
int val;
if( m == 1) { val = (int)( exp(n*ln(10)) — exp(n*ln(9)) + 1) ;
} else {
val = dikiy(n, 1);
val = val + (m-1) * (val -1);
}
return val;
}
погоди, для 2143 должно получиться dikiy(3,2)+143.
Выводит 937119. Хотя правильный ответ — 1468559. ЧЯДНТ?
сейчас подгоню. а что для 1е6 выдаёт?
dikiy(int n) правильно. я так понимаю, что косяк в том, что оно должно быть tmp + (m — 2) * (tmp — 1) + pow(10, n), щас попробую
Вот теперь правильно. Проблема была в том, что если у нас 2000000, то числа 1****** все содержат единицу. Так-то.
Кстати, я не понял, как вывели это самое exp(n * log(10)) — exp(n * log(9)).
так. метод индукции, дедукции, пофигу. единиц в представлении одной цифрой — одна штука в представлении двумя (10..99): первая единичка — таких 10, плюс по одной из каждых предыдущих переборов с первой из оставшихся 2. 9 — 8ми вариантов, значит 10..99 = 10 + 8. 1..99 = 18 + 1 представление 3мя (100. 999): первая единичка: 100, 8 на представление 2-мя (т.е. на 18) плюс 1 (представление 1). 1. 999 = 100 + 8*18 + 18 +1 = 100 + 9 * f(n-1) + 1
для представления f(N+1) 1*10^N = 1* f(N) + 9*f(N-1) +1 где-то такая рекурсивная функция у меня получилась. тогда F(ABCD) = F(1000) + (A-1)*F(100) + F(100) + (B-1) F(10) + F(10) + (C-1) F(1) + F(D) ну и можно упростить.
в каждой позиции может быть одно из 10 символов. 0..9
всего значит в N позициях может быть 10^N вариантов.
и мы знаем, что в позиции может быть или 1 или оставшиеся 9 символов.
размещая в N ячейках какой-либо из 9 символов, у нас будет 9^N комбинаций. значит разница между одним набором и другим такая, что в оставшихся вариантах будет присутствовать 10-ый символ.
10^N — 9^N в результате. чтобы не перегружать машины, можно вычислять экспоненциально (хотя толку от этого мало).