Посчитать количество чисел, содержащих единицу, на промежутке [1; N]

Для проверки можно использовать это:

#include <iostream>

inline bool valueContainsOne(int n)
{
    do {
        if (n % 10 == 1) {
            return true;
        }
    } while (n /= 10);
    return false;
}

int main()
{
    int x;
    do {
        std::cout << "Enter fucking positive number: ";
        std::cin >> x;
    } while (x < 1);
    int result = 0;
    for (; x >= 1; --x) {
        if (valueContainsOne(x)) {
            ++result;
        }
    }
    std::cout << "Your answer is " << result << ", dumbass." << std::endl;
}

Слабо.
В лоб удобнее =)

def count(n)
  buff = ""
  (n+1).times do |x|
    buff << x.to_s
  end
  return buff.count("1")
end

И огромную переменную потребует.

достаточно посчитать количество чисел НЕ содержащих единицы. А это 9^N. Значит ответ 10^N-9^N.

А если еще минуту подумать, то будет как-то так:

def count(n)
  c = 0
  (n+1).times do |x|
    c += x.to_s.count("1")
  end
  return c
end

камбинаторика?

Вот окончательная формула:

k=exp(Nln(10))-exp(Nln(9)).

Программисты, блин )

Надо посчитать кол-во чисел, содержащих единицу, в промежутке [1; 10].

10^10-10^9 = 9000000000. Over 9000. А на самом-то деле их там два (10 и 1).

> достаточно посчитать количество чисел НЕ содержащих единицы

подход хороший! а вот метод счёта лучше доопределить.

верно, что для всех чисел, содержащих в записи N знаков, будет ... дальше как у вас. вот только число N задано несколько иначе.

>Надо посчитать кол-во чисел, содержащих единицу, в промежутке [1; 10].

то есть по твоему 101 и 111 - числа НЕ сожаржащие единицу?

Ты определись с условием-то.

exp(10*ln(10))-exp(10*ln(9)) = 6513215599.00000000021795629708

ЧЯДНТ?

>достаточно посчитать количество чисел НЕ содержащих единицы. А это 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

> k=exp(Nln(10))-exp(Nln(9)).

exp(Nln(10))-exp(Nln(9))+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;
}

dikiy2(3,2)+dikiy2(2,1)+dikiy2(1,4)+(???)

для 2143

result(2143) = dikiy(3,2)+dikiy2(2,1)+dikiy2(1,4)+lol(3)

lol(n) = (n==0? 0 : 1)

так?

погоди, для 2143 должно получиться dikiy(3,2)+143...

#include <iostream>
#include <cmath>

using namespace std;

/// Количество чисел с единичкой в промежутке [1; 10^n]
int dikiy(int n)
{
    return exp(n * log(10)) - exp(n * log(9)) + 1;
}

/// Количество чисел с единичкой в промежутке [1; m*10^n]
int dikiy(int m, int n)
{
    int tmp = dikiy(n);
    return tmp + (m - 1) * (tmp - 1);
}

int main()
{
    int result = dikiy(2, 6);
    
    cout << "2*10^6 has " << result << " ones." << endl;
}

Выводит 937119. Хотя правильный ответ — 1468559. ЧЯДНТ?

сейчас подгоню. а что для 1е6 выдаёт?

dikiy(int n) правильно... я так понимаю, что косяк в том, что оно должно быть tmp + (m - 2) * (tmp - 1) + pow(10, n), щас попробую

/// Количество чисел с единичкой в промежутке [1; m*10^n]
int dikiy(int m, int n)
{
    if( m == 1) {
        /// Количество чисел с единичкой в промежутке [1; 10^n]
        return exp(n * log(10)) - exp(n * log(9)) + 1;
    } else {
        double tmp = dikiy(1, n);
        return tmp + (m - 2) * (tmp - 1) + pow(10,n) - 1;
    }
}

Вот теперь правильно. Проблема была в том, что если у нас 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 в результате. чтобы не перегружать машины, можно вычислять экспоненциально (хотя толку от этого мало).

exp( n ln(10)) = exp ( ln (10^N)) = 10 ^N.

#include <iostream>
#include <cmath>
#include <cassert>

using namespace std;

/// Количество чисел с единичкой в промежутке [1; m*10^n]
int dikiy(int m, int n)
{
    assert(m >= 0);
    assert(n >= 0 && n < 10);
    if(m == 0) {
        return 0;
    } else if(n == 0) {
        return 1;
    } else if(m == 1) {
        return exp(n * log(10)) - exp(n * log(9)) + 1;
    } else {
        double tmp = dikiy(1, n);
        return tmp + (m - 2) * (tmp - 1) + pow(10,n) - 1;
    }
}

/// Количество чисел с единичкой в промежутке [1; x]
int fuckingFunc(int x)
{
    assert(x > 0);
    int result = 0;
    for (int i = log10(x); i >= 0; --i) {
        int tmp = x/pow(10,i);
        x -= tmp*pow(10,i);
        result += dikiy(tmp, i);
        if (tmp == 1) {
            /* если текущая цифра -- 1, добавляем остаток к результату и всё,
             * ведь при реальном счёте всё в остатке начиналось бы на 1 */
            result += x;
            break;
        }

    }
    return result;
}

int main()
{
    int x;
    do {
        cout << "Enter fucking positive number: ";
        cin >> x;
    } while(x < 1);
    
    int result = fuckingFunc(x);
    
    cout << "Your answer is " << result << ", dumbass." << endl;
}

Вот. Работает. Насчёт if (tmp == 1) пояснить, или и так понятно? Всем спасибо!.

Я уже на баяне поиграл, а вы все задачу насилуете :)

Определим цифры числа K как k_n,... по убыванию разряда. Также обозначим как Kтогда количество чисел без единиц в диапазоне от [0..K]


f(K)={

(k_n-1)*9^(n-1)+f(K-k_n*10^(n-1)), if k_n≥2;
//f(K), if k_n=0; за ненадобностью
9^(n-1), if k_n=1;
k_n, if n=1

}

по-моему, это в программе выше и написанно.

чето она большая сильно.

ой, неправильно прочитал твою формулу. А как там понимать k_n? В смысле сумму формулы для каждого n прогонять?

>ой, неправильно прочитал твою формулу. А как там понимать k_n? В смысле сумму формулы для каждого n прогонять?

я ж написал: k_n - это цифра числа. Например для 262 k_3=2, k_2=6, k_1=2)

да, но что подставлять в качестве n? или имелось в виду сумму для n = 1..max_n?