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

[boomeer]

написал код, но в промежутках [20..99] [200..999] он не работает правильно. Ищу ошибку. Для 10^9 считает 0.104 секунды. Ответ 612579512

[NiCola999]

 но в промежутках [20..99] [200..999] он не работает правильно.

в этом промежутке можно лобовой запускать, мгновенно всё посчитает

[boomeer]

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

 но в промежутках [20..99] [200..999] он не работает правильно.

в этом промежутке можно лобовой запускать, мгновенно всё посчитает

[2000..9999] тоже не верно =) и тд

[NiCola999]

[2000..9999] тоже не верно =) и тд

на этом промежутке тоже быстро , вообще у меня (1...10^8) лобовой алг. за 5 сек считает, а 1...10^9 уже за 1 мин =)

[Smitt&Wesson]

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

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

Поясняю. Таблица показывает сколько единичек содержится в определённом диапазоне чисел. Если записать в линейку получим:

диапазон от 0-9 = содер 1 единичку. Далее:

0 - 9 = 1
10 - 19 = 11
20 - 99 = 8
100 - 109 = 11
110 - 119 = 21 т.е. 10 единиц старшего разряда + 11 единиц двух младших
120 - 129 = 11
130 - 139 = 11
140 - 149 = 11
150 - 159 = 11
160 - 169 = 11
170 - 179 = 11
180 - 189 = 11
190 - 199 = 11
200 - 219 = 12
220 - 299 = 8
300 - 399 = 20
400 - 499 = 20
500 - 599 = 20
600 - 699 = 20
700 - 799 = 20
800 - 899 = 20
900 - 999 = 20

Теперь просуммируем все полученные результаты:

1+11+8+11+21+8*11+12+8+20*7 = 300

Это и есть число входящих в этот диапазон единичек.
А вот этот расклад не верен.

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

N= 10 комбинаций : 2
N= 100 комбинаций : 20
N= 1000 комбинаций : 272
N= 10000 комбинаций : 3440
N= 100000 комбинаций : 40952
N= 1000000 комбинаций : 468560
N= 10000000 комбинаций : 5217032
N= 100000000 комбинаций : 56953280
N= 1000000000 комбинаций : 612579512

Как из этого примера видно, уже в диапазоне от 0 до 1000 получилось число 272 которое меньше чем при ручном счёте (300) на целых 28 единиц.
А дальше идёт накопление этой ошибки, так в диапазон от 0 до 100000000 мой алгоритм показывает 80000000, а этот 5217032.

[NiCola999]

Smitt&Wesson

это вы не верно считаете, от 1 до 1000 ровно 272 числа с единицами

я еще раз вам повторяю, мы считаем не общее кол-во единиц в числах от 1 до n, а кол-во чисел содержащих единицы. Ваш ответ всё равно не верен, от 1 до 1000 ровно 301 единица

[Obey-Kun]

Народ, всё просто! Все числа больше или равны единицы содержат единицу в своей двоичной записи. То есть ответ — N. :D

[NiCola999]

это шутка? =) в двоичной системе согласен =)

[Акоб]

#include<iostream.h>

int stepen(int x)
{
	int s = 1;
	for(; x >= 1; x--)
		{
			s = s * 10;
		}
	return s;
}




int main()
{
	
	int Buff[10] = {0,1,19,271,3439,40951,468559,5217031,56953279,612579511};
	int N,j,h = 0,n = 0;
	cin>>N;
	j = N;
	

	while(j >= 1)
	{
		j = j / 10;
		h++;
	}


	j = N;
	j = j / stepen(h - 1);
	if(h == 1)
		{
			n = 1;
			cout<<n<<endl;
			return 0;
		}
	
	while(h != 0) 
	{
		if(j == 1)
			{
				if(N % stepen(h - 1) == 0)
					{
						n = n + Buff[h - 1] + 1;
						cout<<n<<endl;
						return 0;
					}
					
				n = n + (N % stepen(h - 1)) + Buff[h - 1] + 1;
				cout<<n<<endl;
				return 0;
			}
		else
			if(j != 0)
			{
				n = n + (j - 1) * Buff[h - 1] + stepen(h - 1);
			}
		N = N % stepen(h - 1);
		j = N;
		h--;
		j = j / stepen(h - 1);
	}
	cout<<n<<endl;


	return 0;
}

не очень красивое решение,но...
как время работы высчитать?

[NiCola999]

на 10^9 выдает неверный ответ:
612579513

правильный
612579512