`
peizhiinfo
  • 浏览: 1417373 次
文章分类
社区版块
存档分类
最新评论

最小乘法次数

 
阅读更多

题目描述:

给你一个非零整数,让你求这个数的n次方,每次相乘的结果可以在后面使用,求至少需要多少次乘。

如24:2*2=22(第一次乘),22*22=24(第二次乘),所以最少共2次。

211:2*2=22(第一次乘),22*22=24(第二次乘)24*24=28(第三次乘)28*22=210(第四次乘)210*21=211(第五次乘)所以最少共5次。

输入

第一行m表示有m(1<=m<=100)组测试数据;

每一组测试数据有一整数n(0<n<=10000);

输出

输出每组测试数据所需次数s;

样例输入

3

2

3

4

样例输出

1

2

2

解题方法:

每次寻找小于等于n的最大的2k的值,如11,先找23=8,然后以此类推。

则可以转换为二进制计算。

其算法类似于把一个十进制数转换为二进制。只要把最高位1转换的次数记下来,再加上这个二进制其它为1的位的个数。例如:
(14)10=(1110)2
最高位的1需要转换3次,所以计算14次方需要3+2(其它为1的位数)=5次。
(100)10=(1100100)2
最高位的1需要转换6次,所以计算100次方需要6+2(其它为1的位数)=8次。

此算法关键在于最高位1转换的次数。(2倍增长是速度最快!)只要算出最高位的1,则低位的1已经被全部算出。因为最高位的1是通过1+1=2 2+2=4 4+4=8 8+8=16……算出来的,则最高位转换次数算出后,其他为1的位只是在使用的时候加一次。(二分思想)

代码如下:



分享到:
评论

相关推荐

    矩阵链相乘的最小乘法次数及乘法方式

    用动态规划策略求矩阵链相乘的最小乘法次数及乘法方式

    动态规划之矩阵连乘问题Python实现方法

    如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 例如: A1={30×35} ; A2={35×15} ;A3={15×5} ;A4={5×10} ;A5={10×20} ;A6={20×25} ; 结果为:((A1(A2A3))((A4A5)A6)) ...

    动态规划四个经典问题的c++实现

    四种经典动态规划:钢条切割求最大收益问题、矩阵链相乘求最小乘法次数问题、最长公共子序列问题、求最小的搜索代价的最优二叉搜索树的c++代码实现。 对应blog

    最小二行乘法 C++和Python实现源码带注释+数据分析报告

    在使用SOR方法求解正则方程组时,由于松弛因子选择不当,使得达到精度要求所进行的迭代次数很大,为了能够较快的达到精度要求,多次改变了松弛因子的取值,在经过多次修改取值后发现当松弛因子取值为1.36时相对较快...

    MATCHAIN 矩阵求和的最少次数

    输入:矩阵个数n和该n个矩阵的行数和列数 输出:该n个矩阵相乘的最小次数 过程:通过动态构建M表,来找到最小次数

    Python-多元线性回归方程比较最小二乘法与梯度下降法

    最小二乘法是先将方程自变量与因变量化为系数矩阵X,再求该矩阵的转置矩阵(X1),接着求矩阵X与他的转置矩阵的X1的乘积(X2),然后求X2的逆矩阵。最后整合为系数矩阵W,求解后分别对应截距b、a1、和a2。可见计算一...

    矩阵连乘 动态规划.cpp

    给定n个矩阵{A1,A2,…,An},其中,Ai与Ai+1是可乘的,(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的次数最小

    联合CMA+DDLMS盲均衡算法 (2009年)

    该算法在捕获阶段同时利用恒模算法和面向判决的最小均方算法(DDLMS)的误差对系数进行更新,在不增加乘法运算次数条件下提高了均衡的性能。对该算法进行了理论分析,并针对正交幅度调制信号进行了仿真。结果证明,该...

    矩阵连乘积的动态规划算法设计.pdf

    矩阵连乘积的动态规划算法设计;确定n个矩阵连乘积 A_1 A_2 A_3…A_n 的计算次序,使得按照这一次序计算矩阵连乘积,需要的"数乘"次数最小。

    2018-2019-2《算法设计与分析A》复习提纲 -总.docx

    复习提纲 第1章: 算法的重要问题类型 第2章 算法的分析框架,包括输入规模的度量、运行时间的度量、增长次数、最优最差及平均效率等知识...Prim算法、Kruskal算法,注意算法和构造最小生成树的方法,包括算法分析等。

    辨识方法的计算效率(1):递推算法 (2012年)

    算法的计算量可用其乘法运算次数和加法运算次数表示(除法作为乘法对待,减法作为加法对待).一次乘法运算或一次加法运算称为一个flop,即一次浮点运算.作为“辨识方法的计算效率7’系列3篇连载论文的第1篇,主要了...

    coding-puzzle:编码难题

    将字符串a转换为字符串b的最小插入和删除次数 最长重复子序列 字符串a的最大子序列的长度,它是b中的子序列 子序列模式匹配 计算b中String a子序列的数量 最大回文子序列 最长回文子串 回文子串计数 字符串中使其...

    c_wp486-deep-learning-int8.pdf

    在 INT8 深度学习每秒运算次数 (OPS) 上相比其它 FPGA,能实现 1.75 倍的峰值 解决方案级性能。由于深度学习推断可以在不牺牲准确性的情况下使用较低位精 度,因此需要高效的 INT8 实现方案。 赛灵思的 DSP 架构和库...

    矢量量化原理与应用(图像视频压缩丛书)

    2乘法次数度量法 二、投影法 三、超立方体法 四、最小最大法 一、矢量量化在图像编码中的应用 1设计任务要求 2方案选择 3设计步骤 4实验结果 二、矢量量化在语音编码中的应用 1VQLPC声码器 2语音波形编码器的硬件...

    多项式拟合程序 过程辨识

    这个时候你不知道该一元函数的最高次数是多少,即不知道未知数系数a1,a2,...,a(n+1)的个数。在这里显然要先假设一个n的值,再来算出这些系数值:有n+1个未知数系数要求,就得有n+1对(x,y)的值,这样可以精确算出唯一...

    Introduction_to_Algorithms:一些我自己的代码

    计算矩阵相乘的最小次数以及输出如何相乘 最优二叉查找树: 求最优二叉查找树的期望搜索代价 排序: 为一些排序的算法:快排、随机化快排、堆排序、选择排序、冒泡排序、插入排序等 最大公共子序列相关: 为最大公共...

    基于FPGA的DSC高速译码器设计及实现

    采用易于FPGA实现的归一化最小和算法,通过选取合适的归一化因子,将乘法转化成移位和加法运算。在高斯白噪声信道下,仿真该译码算法得出最佳的译码迭代次数,并结合Xilinx XC7VX485T资源确定量化位数。然后基于该...

    高斯顺序消去法matlab代码-massey-generator:根据用户输入的数据生成Massey方法的MATLAB代码

    Massey方法是一种线性最小二乘数值方法,用于在给定过去比赛数据集的情况下为球员/球队生成排名。 为了计算这些梅西排名,它考虑到了比赛的获胜次数和得分。 该页面将帮助创建MATLAB脚本来运行并获得排名。 您可以从...

Global site tag (gtag.js) - Google Analytics