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

> имелось в виду сумму

имелась в виду сумма

n - это порфдок числа (количество знакомест)

Для K=32414: n = 5, а k_n = 4, так?

n=5, а k_n=3.

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

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

using namespace std;

/// Количество чисел БЕЗ единички в промежутке [1; K]
int dikiy2(int K)
{
    assert(K > 0);
    int n = int(log10(K))+1;
    int k_n = K/pow(10,n-1);
    if (k_n >= 2) {
        return (k_n-1)*9^(n-1)+dikiy2(K-k_n*pow(10,n-1));
    }
    if (k_n  == 1) {
        return pow(9, n-1);
    }
    if (n == 1) {
        return k_n;
    }
    assert(false);
    return 1;
}

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

Иногда считает правильно, иногда нет, иногда assert'ит...

все. баг выхода поправил. вот программа для bc:

define bestpow(a) {i=0; while(a-10^i>=0) { i=i+1 }; return i-1; }

define f(k) { if(bestpow(k)<=0) {if (k==0) return 1; return k}; if(int(k/10^bestpow(k))>=2) return ((int(k/10^bestpow(k))-1)*9^bestpow(k)+f(k-int(k/10^bestpow(k))*10^bestpow(k))); if (int(k/10^bestpow(k))==1) return (9^bestpow(k));}

Вывод:

f(200) 82

f(201)
82

f(202)
83

f(453634)
205276

f(10^9)
387420489

f(16)
9

f(19)
9
f(10)
9
f(11)
9

для удобоваримости:

define f(k)

{

if(bestpow(k)<=0)
{
if (k==0) return 1;
return k
}

if(int(k/10^bestpow(k))>=2)
return ((int(k/10^bestpow(k))-1)*9^bestpow(k)+\
f(k-int(k/10^bestpow(k))*10^bestpow(k)));

if (int(k/10^bestpow(k))==1)
return (9^bestpow(k));

}

Есессно можно намного короче, если взять calc, а не bc.

>n = int(log10(K))

муаххах. вот это я затупил к ночи глядя :) начал bestpow мутить какой-то вместо этого )

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

using namespace std;

int bestpow(int a)
{
    int i = 0;
    while(a - pow(10, i) >= 0) {
        i = i + 1;
    }
    return i - 1;
}

/// Количество чисел БЕЗ единички в промежутке [1; k]
int f(int k)
{
    if(bestpow(k) <= 0) {
        if(k == 0) {
            return 1;
        } else {
            return k;
        }
    }
    
    if(int(k / pow(10, bestpow(k))) >= 2) {
        return (int(k / pow(10, bestpow(k))) - 1) * pow(9, bestpow(k))
               + f(k - int(k / pow(10, bestpow(k))) * pow(10, bestpow(k)));
    }
    
    if(int(k / pow(10, bestpow(k))) == 1) {
        return pow(9, bestpow(k));
    }
}

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

Тоже работает, спасибо

тока ж замени bestpow на то, что у тебя сначала было. А то препод на тебя будет смотреть как на дурака :) Я затупил конкретно с этой функцией )

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

мне вот интересно, решаема ли он без ветвлений?

тебе лучше знать, тем более я щас пива нажратый и вообще ничё не понимаю :)

>тебе лучше знать, тем более я щас пива нажратый и вообще ничё не понимаю :)

Да я тоже не математик, а баянист :)

Так что не факт )

Я бы поискал критерий наличия в числе единицы - функцию, которая возвращает единицу, если единица в числе имеется. Или нет таковой. А потом можно попробовать её проинтегрировать, если я, конечно, не упоролся.

Господи.

пусть число N = a b_1 b_2 b_3... b{n-1}

Легко находим n-1 значное число с 1

Далее надо найти все возможные {n-1} значные числа с учетом b_1..b{n-1}, если а == 1, иначе все {n-1} значные числа

и сложить

> мне вот интересно, решаема ли он без ветвлений?

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

> Господи

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

покажете пример? на основании вашего описания алгоритма?

>Далее надо найти все возможные {n-1} значные числа с учетом b_1..b{n-1}, если а == 1, иначе все {n-1} значные числа

и сложить

а теперь смотрим на http://www.linux.org.ru/jump-message.jsp?msgid=5864969&cid=5866832

о господи. а по русски писать писать не умеем?

Или на языке математики?

покажете пример? на основании вашего описания алгоритма?

хм. вроде любой справится. Или нет?

> вроде любой справится. Или нет?

вот именно о нет я и говорил. что лично до меня вот так сформулированный алгоритм не дал бы ничего. т.е. пришлось бы или долго ещё думать и додумывать (т.е. доопределять алгоритм) или с умным видом зависать.

плохо позависай для тренировки