>

도전 :

와이즈 비즈

이 코드를 더 빨리 만들려면 어떻게해야합니까? 현재로서는 3 초를 초과합니다.

Suppose you are inhabitant of a planet where 1, 7, and 9 are lucky digits. A lucky number for you is a number that contains only your lucky digits in it. For ex: 1, 79, 911, 9917 etc., are lucky, where as 5, 172, 93, 170 are not. Given a integer N, count the number of lucky numbers in the range 1 to N.
[Constraints : 1 ≤ N ≤ 10^12. Time limit : 3s]

#include<stdio.h> #include<time.h> int lucky(long long int num) { while(num>0) { if(!(num%10==1 || num%10==7 || num%10==9)) return 0; num = num/10; } return 1; } int main() { clock_t tic = clock(); long long int num,i,count = 0; scanf("%lld",&num); for(i=1;i<=num;i++) { count += lucky(i); } printf("%lld\n",count ); clock_t toc = clock(); printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC); return 0; }
  • 답변 # 1

    이 문제의 비결은 각 숫자를 확인하지 않아야한다는 것입니다. 시간이 너무 오래 걸립니다.

    내가 알아 차린 중요한 것은 세 자리 숫자 만 있다는 것입니다. N이 10이면 3 자리 숫자가 있기 때문에 3 자리 숫자가 있습니다. N이 100이면 운이 좋은 숫자의 3 * 3 조합이 있기 때문에 12 개의 행운의 숫자가 있습니다. 하지만 '01'과 '07', '09'는 1, 7, 9로 쓰니까 총 12 개입니다.

    N의 각 자리를 보면 문제를 더 빨리 해결할 수 있습니다.

    이 표를 살펴보면 행운의 숫자를 모두 N = 1000까지 썼습니다.

     1     7     9 = 3
     11    17    19 
     71    77    79
     91    97    99 = 12
    111   117   119 
    171   177   179 
    191   197   199 
    711   717   719 
    771   777   779 
    791   797   799 
    911   917   919 
    971   977   979 
    991   997   999 = 39
    
    

    행운이 2, 7, 9 인 N = 1000을 취합니다.

    이것은 쉽다. 1000은 모든 3 자리 숫자 (3 + 3 ^ 2 + 3 ^ 3)를 기록한다는 의미입니다. 첫 번째 숫자는 운이 좋은 숫자와 일치하지 않으므로 완료되었습니다.

    운이 좋은 숫자 1, 7, 9를 갖는

    N = 1000은 설명하기가 좀 더 어렵다 : 첫째, N은 4 자리 숫자이기 때문에 3 자리 숫자를 모두 얻는다. 다음으로, 첫 번째 숫자는 운이 좋은 숫자이므로 다음 숫자로 할 수있는 모든 점수를 매겨 야합니다. 그러나 다음 숫자는 운이 좋은 숫자보다 크지 않기 때문에 해당 점수는 0입니다.

    행운의 숫자로

    N = 1150 : 다시, 4 자리 숫자로 39를 얻습니다. 다음으로 150 점을 얻지 만 3 자리 숫자로 무료 점수를받지는 않습니다. 150의 첫 번째 숫자는 행운의 숫자이지만 행운의 숫자보다 크지 않기 때문에 두 자리의 행운 숫자의 0 배를 얻습니다. 그러나 0. 50은 5로 시작합니다. 5는 1보다 크지 만 7보다 작으므로 1 * 1의 운이 좋은 숫자의 양을 얻습니다. N = 1150, 점수는 42입니다.

    N = 1750 :

    4 자리 숫자로 39 포인트 (3 + 3 ^ 2 + 3 ^ 3)

    1은 행운의 숫자보다 크지 않으므로 0 * 3 ^ 3

    1은 행운의 숫자이므로 다음 숫자로 계속하십시오

    750은 7, 7로 시작합니다. 7은 1보다 크지 만 7 또는 9보다 크지 않으므로 1 * 3 ^ 2 = 9 포인트입니다.

    7은 운이 좋은 숫자이므로 다음 숫자로 계속하십시오

    50은 5로 시작하고 5는 1보다 크지 만 7 또는 9보다 크지 않으므로 여기서 1 * 3 ^ 1 = 3 포인트

    총 39 + 0 + 9 + 3. = 51로 만듭니다.

    N = 11 :

    2 자리 (3) 인 경우 3 점

    1은 행운의 숫자보다 크지 않으므로 0 * 3

    1은 행운의 숫자이므로 다음 숫자로 계속하십시오

    마지막 숫자이므로 마지막 숫자는 1 포인트 이상입니다.이 경우에는 '1'이므로 1 포인트입니다

    N = 11, 4, 행운의 숫자입니다.

    N = 2000 :

    4 자리 숫자로 39 포인트 (3 + 3 ^ 2 + 3 ^ 3)

    2는 1 자리 숫자보다 크므로 1 * (3 ^ 3) = 27

    2는 행운의 숫자가 아니므로 끝납니다

    39 + 27 = 66을 만듭니다.

    확인할 테이블이 있습니다 :

      1     7     9 = 3
      11    17    19 
      71    77    79
      91    97    99 = 12
     111   117   119 
     171   177   179 
     191   197   199 
     711   717   719 
     771   777   779 
     791   797   799 
     911   917   919 
     971   977   979 
     991   997   999 = 39
    1111  1117  1119 - 3
    1171  1177  1179 - 6
    1191  1197  1199 - 9
    1711  1717  1719 - 12
    1771  1777  1779 - 15
    1791  1797  1799 - 18
    1911  1917  1919 - 21
    1971  1977  1979 - 24
    1991  1997  1999 = 27 + 39 = 66
    
    

    왜이게 문제가 되나요?

    방금 설명한이 알고리즘은 약 $$O (log n) \ $입니다. 즉, N = 1000은 N = 1 인 경우 4 배가 걸립니다. N = 10 ^ 12는 N = 1 인 경우 12 배가 걸립니다.

    알고리즘은 각 숫자를 확인하므로 \ $O (n) \ $입니다. 즉, N = 1000은 N = 1 인 경우 1,000 배 (1000)가 걸립니다. 즉, 높은 경우에는 N = 10 ^ 12이므로 코드가 1.000.000.000.000 배 더 오래 걸리므로 코드가 너무 오래 걸립니다. N = 1보다 완료해야합니다.

  • 답변 # 2

    코드를 개선하는 데 도움이되는 몇 가지 사항이 있습니다. 먼저 이미 작성한 코드에 대한 의견을 언급 한 다음 더 나은 알고리즘을 제시하겠습니다.

    bool 사용적절한 곳에

    lucky 의 리턴 값  아마도 bool 해야합니다   int 대신 . 줄을 추가하여 쉽게 변경할 수 있습니다

    #include <stdbool.h>
    
    

    그런 다음 bool 를 리턴하도록 루틴을 변경하십시오. .

    서명 된 것과 서명되지 않은 것에주의하십시오

    문제 설명으로 num  1보다 작을 수 없으므로 long long unsigned 로 선언해야합니다.   long long int 보다는  부정적 일 수 있습니다.

    더 많은 공백 사용

    이 대신 코드를 훨씬 더 읽기 쉽게 할 수 있습니다 :

    for(i=1;i<=num;i++)
    
    

    다음과 같이 쓸 수 있습니다 :

    for(i = 1; i <= num; i++)
    
    

    추가 공백은 읽기 쉽고 이해하기 쉽습니다.

    I/O에서 계산 분리

    와이즈 비즈  루틴은 입력과 출력을 모두 수행하며 행운의 숫자를 계산하는 주요 계산에 실질적으로 관여합니다. 해당 기능이 다음과 같이 분리되어야한다고 주장합니다.

    main
    
    

    알고리즘 만 시간

    현재 프로그램에서 타이밍이 수행되는 방식에는 사용자가 숫자를 입력하는 데 걸리는 시간과 알고리즘 시간이 포함됩니다. 인간의 가변성은 시간이 알고리즘에만 해당되는 경우보다 그러한 데이터를 덜 유용하게 만듭니다.

    와이즈 비즈 제거   unsigned countLucky(long long unsigned num) { unsigned count = 0; for(long long unsigned i = 1; i <= num; i++) { count += lucky(i); } return count; } 의 끝에서

    C99부터 컴파일러는 자동으로 return 0 에 해당하는 코드를 생성합니다.   main 의 끝에서명시 적으로 작성할 필요가 없습니다.

    더 나은 알고리즘

    기존 코드는 가장 빠르지는 않지만 분명히 맞다는 점에서 큰 이점이 있습니다. 이를 사용하여 다른 방법을 확인하고 타이밍 비교에이 방법을 사용할 수 있습니다. 여기에서이 검토가 끝날 때까지 코드의 단계별 개선을 보여 드리겠습니다.

    테스트 장치 쓰기

    여러 버전의 코드를 작성하고 비교할 수 있습니다. 이를 수행하는 좋은 방법은 다음과 같은 구조와 매크로를 사용하는 것입니다.

    return 0
    
    

    이제 다양한 테스트를 쉽게 수행하고 모든 대체 알고리즘을 실행할 수 있습니다 :

    main
    
    

    문제에 대해 신중히 생각하십시오

    다른 사람들이 지적했듯이, \ $O (\ log n) \ $의 순서로 실행 시간을 만드는 방법이 있습니다. 아직 설명되지 않은 것은 실제로 그것이 정확하고 효율적인 알고리즘으로 어떻게 변환되는지입니다. 그렇게 말하면, 우리가 그렇게 할 수있는 방법이 있습니다.

    먼저 한 자리 숫자의 경우 다음과 같은 간단한 구조에서 답을 얻을 수 있습니다.

    typedef struct {
        unsigned (*fn)(long long unsigned num);
        const char *name;
    } counttest;
    #define TEST(x) { x, #x }
    
    

    또한 행운의 숫자를 다음과 같이 열거 할 수 있습니다 :

    int main()
    {
        const counttest test[] = {
            TEST(countLucky),
            TEST(countLucky2),
        };
        const size_t tests = sizeof(test)/sizeof(test[0]);
        long long unsigned num;
        scanf("%llu",&num); 
        for (size_t i=0; i < tests; ++i) {
            clock_t tic = clock();
            unsigned count = test[i].fn(num);
            clock_t toc = clock();
            printf("%u\n%s: ",count, test[i].name);
            printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
        }
    }
    
    

    ... 등등. 3 자리 1 자리 행운의 숫자, 9 2 자리 행운의 숫자, 27 3 자리 행운의 숫자 등이 있습니다. 따라서 \ $3 ^ n \ $\ $n \ $자리 숫자가 있습니다. \ $n + 1 \ $자릿수의 숫자에 대해서는 각각 \ $\ sum_ {k = 1} ^ {n} 3 ^ k = \ fra {3} {2} (3 ^ n-1) \ $입니다. 그런 다음 고려해야 할 유일한 부분은 주어진 숫자보다 작거나 같은 \ $n \ $자리 숫자의 수입니다.

    좀 더 구체적으로 만들려면 숫자 157을 고려하십시오. 위의 차트에서 157이 119와 171 사이에 있음을 알 수 있습니다. 계산하면 운이 좋은 숫자가 15보다 작거나 같다는 것을 알 수 있습니다 157.

    즉, 157은 3 자리 숫자이므로 \ $\ frac {3} {2} (3 ^ 2-1) = 12 \ $2 자리 행운의 숫자는 157보다 작습니다. 그러나 많은 3 자리 행운의 숫자는 \ $\ le 157 \ $입니다. 위 표의 추가 열에서 짐작할 수 있듯이 각 행운의 숫자를 기본 3 숫자로 간주 할 수 있습니다. 그런 다음 \ $\ le 157 \ $에 해당하는 3 진수를 찾으면됩니다. 우리는 입력 알고리즘을거의다음의 알고리즘에 의해 밑수 3으로 변환 할 수 있음을 관찰함으로써 그렇게 할 수 있습니다 :

    static const int k[10] = { 
     // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
        0, 1, 1, 1, 1, 1, 1, 2, 2, 3 
    };
    
    

    이 문제는 100과 같은 숫자가 이미 가장 낮은 3 자리 운이 적은 숫자보다 작 으면 합계에 0을 기여해야하지만 숫자가 112이면 정확히 1 3이라는 것입니다 운이 좋은 숫자보다 작습니다. 본질적으로, 우리는 변환하는 동안 더 높은 자릿수에서 "빌리기"를 고려해야합니다. 완벽하게 작동하고 올바른 코드 버전은 다음과 같습니다.

    lucky base-3
      1      0
      7      1
      9      2 
     11     00
     17     01
     19     02
     71     10
     77     11
     79     12
     91     20
     97     21
     99     22
    111    000
    117    001
    119    002
    171    010
    177    011
    179    012
    191    020
    197    021
    199    022
    711    100
    717    101
    719    102
    771    110
    777    111
    779    112
    791    120
    797    121
    799    122
    911    200
    917    201
    919    202
    971    210
    977    211
    979    212
    991    220
    997    221
    999    222
    
    

    나는 호너의 법칙을 사용하여 지수를 일련의 곱셈으로 바꿨습니다. 이렇게하면 코드가 상대적으로 효율적이고 부동 소수점 루틴이 필요하지 않습니다.

    결과

    내 컴퓨터에서 위 코드를 비교 한 것입니다 :

    m = base-3 equivalent of first digit
    for each remaining digit "d"
        m = 3 * m + base-3 equivalent of next digit
    
    

    보시다시피, 두 버전 모두 동일한 답변을 제공하지만 새 버전은 \ $5 \ mu \ text {s} \ $미만으로 답변을 반환합니다.

  • 답변 # 3

    왜 운이 좋은 숫자를 쌓고 결과를 세지 않습니까? 1, 7 및 9는 실제로 운이 좋은 숫자라는 것을 알고 있습니다. 결과가

    이러한 방식으로 숫자를 구성하고 결과를 계산할 수 있습니다 ...

  • 답변 # 4

    \ $n \ $는 \ $N \ $의 자릿수로 결정하십시오. \ $O (\ ln N) \ $시간

    \ $l_ {n-1} \ $는 \ $n-1 \ $자리를 가진 \ $N \ $보다 작은 행운의 숫자이고 \ $l_ {n} \ $는 \ $n \ $자리의 \ $N \ $보다 작은 행운의 숫자. 최종 답변은

    $$l = l_ {n} + l_ {n-1}. $$

    \ $n-1 \ $자리의 모든 행운의 숫자는 \ $N \ $보다 작습니다. 세어 보자. \ $k \ $숫자가있는 숫자 (즉, \ $k-1 \ $0 앞에 오는 숫자) 만 고려하면 각 \ $k \ $위치에 대해 행운의 숫자를 선택하면됩니다. 따라서 \ $3 ^ k \ $가능성이 있습니다. \ $k \ $의 각 값에 대해 이렇게하면 다음과 같이됩니다.

    $$l_ {n-1} = \ sum_ {k = 1} ^ {n-1} 3 ^ k = \ frac12 (3 ^ n-3) $$

    반복 된 제곱을 통해 \ $O (\ ln n) \ $시간으로 계산할 수 있습니다.

    이제 \ $N_ $보다 작은 \ $n \ $자리를 가진 행운의 숫자 인 \ $l_n \ $를 세어 보자. 우리는 \ $N \ $보다 작은 \ $n-1 \ $숫자를 세어야합니다. 이 AFAIK에는 닫힌 수식이 없으므로 대신 간단한 재귀 알고리즘을 사용합니다 (위의 경우 계산을 사용함).

    static const int MAXBUF =  20;
    unsigned countLucky2(long long unsigned num) 
    {
        static const int k[10] = { 
         // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
            0, 1, 1, 1, 1, 1, 1, 2, 2, 3 
        };
        char buff[MAXBUF];
        int digits = snprintf(buff, MAXBUF, "%llu", num);
        if (digits < 0) {
            return 0;  // encoding error
        }
        --digits;
        unsigned count = 1;
        int d = buff[0]-'0';
        int m = k[d]-1;
        bool borrow = (d != 1 && d != 7 && d != 9);
        for (int i=1; i <= digits; ++i) {
            int d = buff[i]-'0';
            count *= 3;
            if (borrow) {
                m = 3*m + 3;
            } else {
                m = 3*m + k[d];
                borrow = (d != 1 && d != 7 && d != 9);
            } 
        }
        return count + m;
    }
    
    

    기본적으로 \ $N \ $의 맨 앞자리 (\ $d \ $라고 부름)가 운이 아닌 숫자 인 경우 \ $d \ $보다 작은 행운의 자릿수를 곱하면됩니다. 특정 자릿수를 가진 행운의 숫자의 수에 대해 위에서 계산 된 공식의 1 또는 2) 배. \ $d \ $가 행운의 숫자이면 \ $d \ $로 시작하는 행운의 숫자를 고려해야합니다. 이는 $$N \ $보다 작거나 같지 않을 수 있습니다. 따라서 우리는 재귀합니다. 런타임은 \ $N \ $의 자릿수이므로 \ $O (\ ln N) \ $입니다.

    두 부분의 결과를 합쳐서 최종 답변을 얻으십시오.

  • 답변 # 5

    다른 답변은 이미 문제를 해결할 수 있음을 보여주었습니다. 실제로 계산하지 않을 때 \ $O (log N) \ $와 \ $O (N) \ $를 비교 숫자이지만 1, 7, 9의 가능한 조합 수를 합산 다른 길이의. 다른 사람의 단순화를 찾을 때 접근 방식은 문제를 변형시키는 데 많은 도움이된다는 것을 알게되었습니다. 기본 3 자리 숫자로 작업 할 수 있습니다.

    이 알고리즘을 생각해 냈습니다 :

    <올>

    \ $m \ $를 최대 ₩ $m \ $로 찾아 \ $m \ leq N \ $을 찾으십시오. 행운의 숫자. \ $d \ $가 이것의 십진수 수를 나타내도록하라 번호.

    다음 매핑에 따라 숫자를 바꾸어 \ $m \ $를 변환하십시오.

    \ $\ {\;1 \ 오른쪽 화살표 0, \;\;7 \ 오른쪽 화살표 1, \;\;9 \ 오른쪽 화살표 2;\} \ $

    결과를 ​​기수 3으로 처리하고 기수 3을 \ $d \ $로 구성되어 있습니다.

    3 단계 후에 이미 결과를보고 있습니다. 그러나 당신은 다시 기본 10으로 변환하고 싶을 수도 있습니다.

    1 단계에서 숫자가 손실 될 수 있습니다 (예 : N 10의 거듭 제곱입니다. 숫자를 확인하여 \ $m \ $를 쉽게 찾을 수 있습니다. 왼쪽에서 오른쪽으로 \ $N \ $. 숫자가 아닌 숫자를 만나면 행운의 숫자, 다음 행운의 숫자로 줄이고 나머지를 설정하십시오. 해당 숫자를 줄일 수없는 경우 (0) 줄일 수있는 숫자를 찾을 때까지 왼쪽을 찾으십시오 (7 또는 9). 하나를 찾으면 대신 이것을 줄이고 모든 후속 설정 하나를 찾지 못하면 (첫 번째 숫자는 1) 첫 번째 숫자를 생략하고 나머지 모든 숫자를 9로 설정하십시오.

    설명

    아마도 이것을 이해하는 가장 쉬운 방법은 예제를 보는 것입니다. \ $N = 775_ {10} \ $를 보자. 다음으로 운이 적은 숫자는 \ $771_ {10} \ $입니다. 매핑에 따르면 \ $110_3 \ $로 변환됩니다. 이거 어떻게 도움? 모든 삼항 수가 \ $110_3 \ $보다 낮다면 그들은 우리에게 \ $771_ {10} \ $보다 작은 다른 3 자리 행운의 숫자를줍니다. 매핑을 다시 뒤집 으면 예 : \ $012_3 \ $는 \ $179_ {10} \ $. \ $000_3 \ $도 3 자리 행운을 나타냅니다. 번호, 즉 \ $111_ {10} \ $입니다. 이것이 바로 우리가 수정해야하는 이유입니다 추가하여 \ $110_3 \ $의 중간 결과

    1과 2 만있는 행운의 숫자도 빠졌습니다 숫자. \ $010_3 \ $한 자리와 \ $100_3 \ $두 자리 행운이 있습니다 번호. 따라서 우리는 중간에 \ $111_3 \ $를 추가 할 수 있습니다. \ $110_3 \ $의 결과는 우리가 놓친 모든 숫자를 보충합니다. 첫 번째 단계 . \ $221_3 = 25_ {10} \ $을 얻습니다.

    157 15 countLucky: Elapsed: 0.000003 seconds 15 countLucky2: Elapsed: 0.000003 seconds 11118888 3333 countLucky: Elapsed: 0.117209 seconds 3333 countLucky2: Elapsed: 0.000003 seconds 1234567890 36084 countLucky: Elapsed: 12.574423 seconds 36084 countLucky2: Elapsed: 0.000004 seconds 9876543210 82011 countLucky: Elapsed: 250.884767 seconds 82011 countLucky2: Elapsed: 0.000005 seconds

관련 자료

  • 이전 java - 암호화 및 해독
  • 다음 스칼라의 비슷한 2 클래스는 리팩토링해야합니다