C/C++

Помогите пожалуйста ускорить код

Есть код на с++ при работе с числами больше миллиона он работает больше чем 1 секунда где то на 0.1 надо чтобы он работал менее чем за секунду
#include <iostream>
#include <thread>
using namespace std;
bool f(int n) {
while (n) {
if (n & 1) return false;
n /=10;
}
return true;
}
int main() {
float a, b;
int count = 0, i;
cin >> a >> b;
for (i = a; i <= b; i++)
if (f(i)) count++;
cout << count;
}
АЗ
Алексей Зотов
163
Тут естественнее сразу применить перечислительную комбинаторику для поиска количеств чётных цифр. Например, n-значных натуральных чисел с чётными цифрами ровно 4·5ⁿ/5. Надо найти номера нижней и верхней границ диапазона в списке чисел с чётными цифрами соответствующей значности (если они сами чётные, а если нет, то и этот случай надо программно обработать), посчитать сколько таких чисел не меньших чем а и не больше чем b, после чего прибавить количество чисел соответствующих значностей, лежащих между значностями чисел а и b. Как-то так. А этот код зачем ускорять? Его лучше сразу сдать в утиль, хотя, впрочем, float надо всего лишь заменить на int и тогда всё должно работать очень быстро если n всего-то где-то порядка миллиона..
ИТ
Илья Топовский
29 440
Лучший ответ
Какую задачу решает этот код?
Зачем переменные a,b типа float?
Orhan Aslanov
Orhan Aslanov
58 065
Алексей Зотов Этот код считает количество чисел у которых в десятичной записи все цифры четные. я сделал флоат для того чтобы немного ускорить работу кода
инклуд Иострим
юсинг намеспасе стд;

int Fee( int& i)
{
static short mas[20];
int n = i;
short dig = 0;
while (n) { *(mas+dig) = n % 2; dig++; n /= 10;}
for (int j = dig - 1; j >= 0; j--)
if (mas[j]) { i += pow(10, j); return 0; }
i++;

return 1;
}

int main()
{
int a=1, n=100000000, count = 0;
for (int i=a; i<=n;)
count+=Fee(i);
cout << count;
}

Некоторые идеи в этом коде.
Логика такая:
Число разбивается на разряды. Если высший разряд нечетный - значит все комбинации ниже него можно смело пропустить. К примеру подается число 1000. 1 - нечетная, значит 1000 вариантов можно пропустить. И так далее.
Алгоритм правильно считает, от 1 до N. Уже устал сегодня доделывать избегание ошибки, если нижнее число уже со старшим нечетным разрядом. К примеру если первое число будет 1500, то пропустится все равно 1000 и счет будет с 2500 с потерей результатов от 2500 до 2999. Но думаю там элементарщина какая-то.
Скорость конская.
Danil Valchun
Danil Valchun
51 411
Danil Valchun int first(int& i)
{
short masa[20]{};
int n = i;
int diff = 0;
short dig = 0;
while (n) { *(masa + dig) = n % 10; dig++; n /= 10; }
n = i;
for (int j = dig - 1; j >= 0; j--)
if (masa[j]%2)
return (masa[j] + 1)* pow(10, j) - n;
else
n = n - masa[j] * pow(10, j);
return 0;
}

int main()
{
int a, n, count = 0;
cin >> a >> n;
a = a + first(a); //вот та самая поправочка
for (int i=a; i<=n;)
count+=Fee(i); //функция из кода выше
cout << count;
}
Danil Valchun first(x) - возвращает приращение для корректной работы алгоритма.
first(1500) = 500, и первое число будет сразу 2000
first(2766) = 34, счет будет с 2800 и т. д.
Danil Valchun до 1'000'000'000 считает за 0,46 секунд а с полным перебором - за 17 секунд.
Danil Valchun #include < iostream >
using namespace std;

int variants(int t)
{
if (!t) return 1;
int count = 0;
int n = t;
int n10 = 1;
int dig = 0;
while (n) { dig++; n /= 10; n10 *= 10; }
n10 /= 10; n = t;
do
{
count += (n / n10 + 1) / 2 * pow(5, dig - 1);
if (n / n10 % 2) break;
n = n - (n / n10) * n10;
if (!n) { count++; break; }
n10 /= 10;
dig--;

} while (n > 0);
return count;
}

int main()
{
int a, b, count = 0;
cin >> a >> b;
cout << variants(b) - variants(a) + !a;
}

//мгновенный алгоритм
Вот так сделай:

#include<stdio.h>

int f(int n)
{
while(n)
{
if(n & 1) return 0;
n/=10;
}
return 1;
}

int main()
{
int a, b, count = 0;
printf("Enter a: ");scanf("%d",&a);
printf("Enter b: ");scanf("%d",&b);
for (int i = a; i <= b; i++)
if (f(i)) count++;
printf("\n%d",count);
return 0;
}
Виктор Рыбаков
Виктор Рыбаков
37 945
Orhan Aslanov Ага. Надо только переписать на Си, и программа ускорится 100 раз :-)
Алексей Зотов как сделать чтобы эти 2 числа считывалась в 1 строке?
int i = float a это как?
Алексей Рязанцев
Алексей Рязанцев
21 700
Orhan Aslanov Это он так ускоряет код :-)
Вам уже надавали советов, лучшего я не придумаю.

Ну и до кучи: открепите потоки iostream от потоков stdio и отвяжите cin от cout. Программа будет меньше дёргать консоль.
Mansur Makhmudov
Mansur Makhmudov
16 172

Похожие вопросы