Количество "единичек"

[Serge_Bliznykov]

Сообщение от boomeer

Тут я. Но последний раз за сегодня =)
Придумал такое решение.
От каждой цифры числа, кроме числа единиц, которая больше 1 отнимаем 1. Умножаем это число на 9. Складываем все + число единиц числа. Теперь от n+1 отнимем это число. Вуаля.
n=29 таким образом 1*9 + 9 = 18. Вычтите из n+1, и получаем 12
5394=9*9*9*4+2*9*9+8*9+4=5395-3154=2241
для 100: 1*9*9=81; 101-81=20
Писал сумбурно, если что завтра поясню как решал)

Здорово! Непонятно, как Вы пришли к такому решению - но оно вроде бы работает!!

[Obey-Kun]

ещё можно находить позицию самой левой единицы в числе и пропускать соответствующее число чисел, нарастив счётчик на их количество.

[NiCola999]

Этот расчёт мой комп делает за 100 секунд.
Результат 80000000.

для числа
100000000
правильный ответ 56 953 280

и "лобовой" алгоритм (пост #32) его находит за 5 секунд

56953280

real	0m5.785s
user	0m5.260s
sys	0m0.216s

Сообщение от boomeer...

тоже не очень понял =)

[Serge_Bliznykov]

для числа
100000000
правильный ответ 56 953 280

угу. согласен.
и по формуле boomeer тоже работает:
100000001 - 9*9*9*9*9*9*9*9 = 56953280

[Smitt&Wesson]

Хорошо.

Проверим на алгоритме из поста 32
для 100 = 20
для 200 = 119
для 1000 = 272
Как мы видим, идёт накопление ошибки в сторону уменьшения.
Теперь посчитаем вручную:

[kaljan775]

нука, а если через файлы

#include <fstream>
#include <iostream>

unsigned long Schet(unsigned long &N);
{
	ofstream out("numbers.txt");
	for (unsigned long i=1;i<=n;i++)
		out<<i;
	out.close();
	unsigned long s=0;
	ifstream input("numbers.txt");
	while(!(input.eof()))
		(input.get()==49)?s++:0;
	return s;
}

int main(){
unsigned long N;
cout<<"Введите N";
 cin>>N;
cout<<Schet(N);
}

а, как считать скорость выполнения программы?

[Smitt&Wesson]

Не, через файлы ещё медленнее получается.
Я выложил более детальную таблицу для проработки.
Кому интересно посмотрите. Кстати, мой "лобовой" алгоритм (пост 41), хоть и не самй шустрый, но зато работоспособный. Работает в любом диапазоне чисел.
Его можно использовать как проверочный для нахождения математической формулы. К сожелению я не математик, а аналитик (есть разница), так что дерзайте.

[boomeer]

Моя формула провалилась... Например для 16 выдает 2

[Serge_Bliznykov]

Smitt&Wesson, что-то не могу врубится, а что даёт выложенная Вами таблица? Поясните, пожалуйста... Или это просто набор исходных данных для дальнейшего анализа? Но тогда зачем подсчёт и суммирование количества чисел?

Как мы видим, идёт накопление ошибки в сторону уменьшения.

и это поясните, пожалуйста.. Какое накопление, какой ошибки?...

Сообщение от boomeer

Моя формула провалилась... Например для 16 выдает 2

ну вот... а я так в неё верил..
тогда расскажите, как Вы к ней пришли?..


кстати, по поводу формул.
Мне кажется, что я знаю как можно построить вычисление достаточно быстро. но нечестно!
достаточно посчитать, сколько чисел в диапазонах десяток, сотен, тысяч и т.д. т.е. 10^I
сохранить эти значения, а потом использовать их в вычислениях. вроде бы там получается не очень сложно...

[boomeer]

Sorry for english but i'm writing from mobile. I add a new rule. If you encounter a 1 you do the count for that digit (rest to the power of 9) but then are finished.