시간 제한을 제거하기 위해 내 코드를 어떻게 다르게 할 수 있습니까?

Question

질문은 : 8 자리 숫자의 티켓 스트립이 있습니다. 첫번째 티켓은 M 번, 마지막 N 번입니다. 크기 M과 N은 다음 관계를 충족시킵니다 : 10000000 ≤ M < N ≤ 99999999. 주어진 숫자 사이의 "운이 좋은"티켓의 수를 결정해야합니다. 첫 번째 네 자리의 합계가 마지막 네 자리의 합계와 같으면 티켓은 "행운"이라고 간주됩니다.

#include <iostream> 
#include <fstream> 
#include <iomanip> 
#include <stdlib.h> 
#include <stdio.h> 
using namespace std; 
int calcSumDigits(int n) 
{ 
    int sum=0; 
    while (n!=0) 
    { 
     sum+=n%10; 
     n/=10; 
    } 
    return sum; 
} 
int main(void) 
{ 
    int a,b,cnt=0,x,y; 
    cin>>a>>b; 
    for (int i=a;i<=b;i++) 
    { 
     x=i%10000; 
     y=(i-x)/10000; 
     if (calcSumDigits(x)==calcSumDigits(y)) cnt++; 
    } 
    cout<<cnt; 
    return 0; 
} 

결과를 잘 작성하지만이 결과를 제공하기 위해 프로그램에서 조금 시간이 오래 걸립니다 : 그리고 여기 내 코드입니다. 예를 들어 10000000에서 99999999까지 시도하면 4379055가 표시되지만 6 초 이상 걸린다

Answer 1

반올림을 단순화하기 위해 숫자의 각 반의 모든 순열에 의해 생성 된 두 합계를 비교하면됩니다. 숫자가 조금 벗어났습니다.

#include <iostream> 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
using namespace std; 
int calcSumDigits(int n) 
{ 
    int sum=0; 
    while (n!=0) 
    { 
     sum+=n%10; 
     n/=10; 
    } 
    return sum; 
} 
int SlowVersion(int a, int b) { 
    int cnt=0,x,y; 
    for (int i=a;i<=b;i++) 
    { 
     x=i%10000; 
     y=(i-x)/10000; 
     if (calcSumDigits(x)==calcSumDigits(y)) cnt++; 
    } 
    return cnt; 
} 
int main() 
{ 
    int lower; 
    int upper; 
    int original_lower; 
    int original_upper; 
    cout<<"enter lower:"; 
    cin>>original_lower; 
    cout<<"enter upper:"; 
    cin>>original_upper; 

    lower = original_lower - (original_lower%10000); 
    upper = original_upper + (9999 - (original_upper%10000)); 

    cout<<"to simplify the calculations the lower was changed to:" << lower << endl; 
    cout<<"to simplify the calculations the upper was changed to:" << upper << endl; 

    int cnt=0; 
    const int b=lower%10000; 
    const int a=(lower-b)/10000; 
    const int b_top=upper%10000; 
    const int a_top=(upper-b_top)/10000; 
    int a_sums[a_top-a]; 
    int b_sums[b_top-b]; 


    int counter = 0; 
    for (int i=a;i<=a_top;i++) 
    { 
     a_sums[counter] = calcSumDigits(i); 
     counter++; 
    } 
    counter = 0; 
    for (int x=b;x<=b_top;x++) 
    { 
     b_sums[counter] = calcSumDigits(x); 
     counter++; 
    } 

    int countera = 0; 
    int counterb = 0; 
    for (int i=a;i<=a_top;i++) 
    { 
     counterb = 0; 
     for (int x=b;x<=b_top;x++) 
     { 
      if (a_sums[countera]==b_sums[counterb]) cnt++; 
      counterb++; 
     } 
     countera++; 
    } 

    cnt = cnt - SlowVersion(lower,original_lower-1); 
    cnt = cnt - SlowVersion(original_upper+1,upper); 

    cout << "The total \"lucky numbers\" are " << cnt << endl; 

    cout << "a is " << a << endl; 
    cout << "b is " << b << endl; 
    cout << "a_top is " << a_top << endl; 
    cout << "b_top is " << b_top << endl; 
    system("PAUSE"); 
    return 0; 
} 

입력 사항을 입력하면 4379055 (동일한 결과가 나타납니다)가 발생하고 매우 빠르게 실행됩니다.