कैसे की गणना करने के आपरेशन के कम से कम संख्या को खोजने के लिए एक्स^n

Question

यहाँ

एसीएम अंतर्राष्ट्रीय कॉलेजिएट प्रोग्रामिंग प्रतियोगिता एशिया क्षेत्रीय प्रतियोगिता, योकोहामा, 2006-11-05

से समस्या है

एक्स के साथ शुरू और बार बार x से गुणा, हम तीस गुणा साथ x^31 गणना कर सकते हैं:

x^2 = x * x, x^3 = x^2 * x, x^6 = x^3 * x^3, x^7 = x^6 *x, x^14 = x^7 * x^7 , 
x^15 = x^14 * x, x^30 = x^15 * x^15 , x^31 = x^30 * x 

एक प्रोग्राम लिखने की गणना करने के x^n गुणा और भाग द्वारा दिए गए सकारात्मक पूर्णांक n और के लिए x के साथ शुरू n<=200

के लिए

एन = 31 कम से कम #operations है n के लिए 6
आपरेशन के कम से कम संख्या को खोजने के लिए = 50 कम से कम # ऑपरेशंस 7

किसी भी विचार का स्वागत है।

Answer 1

इस देखें: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

कोई कुशल एल्गोरिथ्म है कि आप कदम की न्यूनतम संख्या प्राप्त करेंगे, और गतिशील प्रोग्रामिंग काम नहीं करता।

मुझे लगता है कि n एक ब्रूट फोर्स समाधान पास करने की अनुमति देने के लिए पर्याप्त छोटा है, हालांकि इसे अनुकूलित करने की आवश्यकता हो सकती है। क्या आप जानते हैं कि बल को कैसे बल देना है?