题目122：找出计算幂的最高效方法
本帖最后由 欧拉计划 于 2016-8-22 23:16 编辑Efficient exponentiation
The most naive way of computing n15 requires fourteen multiplications:
n × n × ... × n = n15
But using a "binary" method you can compute it in six multiplications:
n × n = n2
n2 × n2 = n4
n4 × n4 = n8
n8 × n4 = n12
n12 × n2 = n14
n14 × n = n15
However it is yet possible to compute it in only five multiplications:
n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15
We shall define m(k) to be the minimum number of multiplications to compute nk; for example m(15) = 5.
For 1 ≤ k ≤ 200, find ∑ m(k).
题目：
计算 n15 的最朴素的算法要 14 次乘法
n × n × ... × n = n15
如果采用分治的方法，你可以只要六次乘法就完成这一工作：
n × n = n2
n2 × n2 = n4
n4 × n4 = n8
n8 × n4 = n12
n12 × n2 = n14
n14 × n = n15
然而，只用 5 次乘法的方法也是存在的：
n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15
我们定义 m(k) 为计算 nk 所需的乘法的最少次数，比如 m(15)=5。
对于 1 ≤ k ≤ 200, 求 m(k) 的和。
解答：
#coding:utf-8
L = 201
ways = [[*L] for i in range(L)]
ways = []
for i in range(2,L):
for eachway in ways:
for p in eachway:
n = i + p
if n < L:
if min(]) > min(]) + 1:
ways = [ + eachway]
elif min(]) == min(]) + 1:
ways += [ + eachway]
print (sum([(min(])-1) for x in range(2,201)]))
答案：
1582 //应用带路径的广搜
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int nN = 200;
int m;//记录最短路径长度
queue<vector<int> > q;//带路径的广搜队列
int main(void)
{
for (int i = 1; i <= nN; ++i)
m = i - 1;
vector<int> v;//记录搜索的路径
v.push_back(1);
q.push(v);
while (!q.empty())
{
vector<int> v0 = q.front();
q.pop();
for (int i = 0; i < (int)v0.size(); ++i)//扩展下一个节点
{
int k = v0.back();
k += v0;
if (k <= nN)//检查数据的有效性
{
if (v0.size() <= m)//找到更短的路径
{
m = v0.size();
v = v0;
v.push_back(k);
q.push(v);
}
}
}
}
int nS = 0;
for (int i = 1; i <= nN; ++i)
{
cout << i << ": " << m << endl;
nS += m;
}
cout << nS << endl;
return 0;
}
答案：1582
页:
[1]