Как заставить мою программу работать быстрее?

Question

Я попытался запустить этот код, но в несколько раз превысил лимит времени, как я могу сократить время?

Мне нужно понять, что я использовал в своей программе, для чего время занимает много, как некоторые функции и т. Д. Я понимаю, улучшая итерацию и сложность, я могу сократить время выполнения, но не помогло. Help

Программа проста, я беру точку а и точку b и вычисляю числа всех чисел палиндрома.

#include<stdio.h> 
int ifpalin(int g) 
{ 
    int rev=0; 
    int tmp=g; 
    while(tmp>0) 
    { 
     rev=rev*10+(tmp%10); 
     tmp=tmp/10; 
    } 
    if(rev==g) 
     return 1; 
    else 
     return 0; 
} 
int findpalin(int a1,int b1) 
{ 
    int sm=0; 
    for(int i=a1;i<=b1;i++) 
    { 
     if (ifpalin(i)==1) 
     sm++; 
    } 
    printf("%d",sm); 
    printf("\n"); 
    return 0; 
} 
int main() 
{ 
int a,b,n; 
    scanf("%d",&n); 
    for(int i=0;i<n;i++) 
    { 
     scanf("%d",&a); 
     scanf("%d",&b); 
     findpalin(a,b); 
    } 
    return 0; 
} 

Answer 1

 
In ifpalin 
Convert the number to string 
Reverse the string 
Compare with the original 
If equal then it's a palindrome 

См How to reverse an std::string?

Answer 2

Ваш int ifpalin(int g) fnction, для каждого заданного г, может выполняться параллельно, потому что кажется, как различные входные данные для этой функции, не оказывает никакого влияния на другие данные. вы можете запустить эту функцию параллельно.

В функции int findpalin(int a1,int b1) есть цикл for, который имеет порядок сложности N, здесь вы можете запускать свои потоки. (каждый поток, работает функция ifpalin). Конечно, необходим хороший план параллелизма. Вы можете запустить эту функцию в некоторой логической связке и агрегировать результаты.

С другой стороны, любой тест должен выполняться в режиме деблокирования.

Надеюсь, это поможет.

Извините, если мое письмо на английском плохо, и , пожалуйста, исправьте меня.

Answer 3

Ваш код уже довольно эффективен (как реализация вашего алгоритма, который может быть улучшен). Эти проблемы хотят, чтобы вы нашли «неочевидный», но более эффективный алгоритм. I.e., в этом конкретном случае вы не должны проверять каждое число между a и b.

Здесь есть другое решение, то есть вы можете «знать» количество палидромов напрямую. Подумайте о it'like этом:

С одной цифрой, есть 10 palidromes [0, ..., 9],

С двумя цифрами, есть 9 палиндромов [11, ..., 99].

С тремя цифрами существует 9 возможностей, где первая и последняя цифры равны [1, ..., 9]. Для жизнеспособного палиндрома, середина также должна быть палиндром. Поскольку середина имеет одну цифру, мы знаем, что здесь есть 10 возможностей для палиндромов, и поэтому у нас есть 9 * 10 = 90 палиндромы с 3 цифрами.

С четырьмя цифрами мы получили 9 * 10 (теперь также разрешены двузначные палиндромы, 00) и с 5 цифрами 9 * 100 (3-значный p, начиная с 0 разрешенных).

Таким образом, вы можете получить формулу для n-значных чисел. Затем вы можете напрямую вывести число для больших полос между a и b и только беспокоиться о том, какое количество цифр имеет значение и сколько чисел было потеряно в начале и конце из-за а и b не 10^(n-1) и 10^n - 1