Exponentiation과 연결된 작업에 대한 더 나은 알고리즘

최근 경쟁에서 주어진 흥미로운 작업을 발견했지만 해결 방법은 작성자 솔루션이나 설명이 없습니다.Exponentiation과 연결된 작업에 대한 더 나은 알고리즘

작업은 다음과 같이 구성됩니다. 사용자에게 숫자 N이 주어지며 a^N (xor 연산이 아닌 n의 제곱으로)을 계산해야합니다. 여기서 a 또는 b를 곱하여 계산할 수 있습니다. 이전 결과. a^n을 계산하려면 계산해야 할 최소의 계산 수를 제공해야합니다.

예 :

N=27 
Then the answer is 6: 
a^2=a*a 
a^3=a^2*a 
a^6=a^3*a^3 
a^9=a^3*a^6 
a^18=a^9*a^9 
a^27=a^18*a^9

N의 한계는 다음과 같다 : N<=40000. 시간과 메모리 제한은 2s and 256MB입니다.

이 작업을 해결하는 좋은 방법은 무엇입니까?

미리 감사드립니다.

출처

2016-06-09 Ivan Ivanov

꼬리 재귀? 당신은 내 생각을 여기에 귀하의 답변을 찾을 수 있습니다 : http://stackoverflow.com/a/26691276 – RicardoVallejo

가능한 중복 [최소 추가 체인 지수] (http://stackoverflow.com/questions/7330752/minimal-addition-chain- exponentiation) –

@PaulHankin : 동의하지만이 문제는 실제로 문제를 설명하는 데 더 효과적이라고 생각합니다. –

이것은 간단한 해결책이지만 빠르지는 않습니다. 누군가가 조정할 수 있으면 좋겠습니까? 또는 문제 해결에 관심이있는 분에게.

#include<set> 
#include<iostream> 
using namespace std; 

int main(int argc, char** argv) 
{ 
    set<int> A, B; 
    A.insert(1); 
    int n = atoi(argv[1]), i; 
    for(i=1; A.find(n) == A.end(); i++) { 
     for(auto& a : A) for(auto& b : A) B.insert(a + b); 
     for(auto& c : B) A.insert(c); 
    } 
    cout << i << endl; 
}

는의를 n 번 calculaing하여 어떻게 내가 아는 수 있습니다 .. 다른 방법을 물어 보자? 매번 두 배가됩니다. 내가 빠진 것이 있습니까? 오직이 하나의 선으로 말했다 ,

while(pow(2, n)< atoi(argv[1])) n++; 
cout << n;

결과를 얻을 수 있습니다.

출처

2016-08-03 12:34:31 Parker

Exponentiation과 연결된 작업에 대한 더 나은 알고리즘

답변

관련 문제