徐州市建设局交易网站,一般网站开发好的框架都有哪些,有一套源码做网站还差什么,个人小程序开发目录 一.快速幂
1.问题的引入
2.快速幂的介绍
3.核心思想
4.代码实现 2.猴子碰撞的方法数
1.题目描述
2.问题分析
3.代码实现 一.快速幂
1.问题的引入 问题:求解num的n次幂,结果需要求余7 对于这个问题我们可能就是直接调用函数pow(a,b)来直接求解a的b次幂问题,但是如果…目录 一.快速幂
1.问题的引入
2.快速幂的介绍
3.核心思想
4.代码实现 2.猴子碰撞的方法数
1.题目描述
2.问题分析
3.代码实现 一.快速幂
1.问题的引入 问题:求解num的n次幂,结果需要求余7 对于这个问题我们可能就是直接调用函数pow(a,b)来直接求解a的b次幂问题,但是如果求解的结果很大,超过的double的数值范围,我们要求对最终的结果求余7,我们如果直接调用pow()函数的话,求解出来的数已经超出了double的最大范围,根本无法求出,这个时候我们是否可以考虑在求解的过程中每一次的结果都求余7,而不是只在最终的结果求余7这样最终的结果肯定是小于7,一定不会超出最大的范围.
2.快速幂的介绍
快速幂:快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N),与朴素的O(N)相比效率有了极大的提高。
3.核心思想
例如计算,10的二进制为1010,相当于求解次方
3*3*3*3*3*3*3*3*3*3
(3*3)*(3*3*3*3*3*3*3*3)
*
相当于我们每次对10的二进制的每一个位置求权(如果是二进制这个位是1),则乘以当前的叠加的数,
例如进行求余的步骤 :
定义变量ans保存的结果 1010位10的二进制表达方式
1010的第一位为0,这个时候numnum*num; 二进制形式为:
1010的第二位为0,这个时候求权为1,ansans*num numnum*num;二进制形式为:
1010的第三位为0,这个时候numnum*num; 二进制形式为:
1010的第四位为1,这个时候求权为1,ansans*num* numnum*num; 4.代码实现
1.求余7的版本,返回数据类型为int的结果 public int quickPow(long num,int n){long ans1;long mod1000000007;while(n!0){if((n1)1)ans(ans*num)%mod;num num * num % mod;n1;}return (int)(ans%mod);} 2.不求余的版本,返回数据类型为long的结果 public long quickPow(long num,int n){long ans1;while(n!0){if((n1)1)ansans*num;num num * num;n1;}return ans;}2.猴子碰撞的方法数
1.题目描述 现在有一个正凸多边形其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。 每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是 顺时针方向的顶点 (i 1) % n 或逆时针方向的顶点 (i - 1 n) % n 。如果移动后至少有两个猴子位于同一顶点则会发生 碰撞 。 返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大请返回对 1097 取余后的结果。 注意每只猴子只能移动一次。 力扣: 力扣
2.问题分析
正难则反,题目问的是至少发生一次碰撞的移动次数,我们不妨把问题转换为求解猴子一次都不碰撞的次数,猴子一共有2的n次幂中跳跃的方式,求中有两种是一次都不碰撞的,一种是猴子全部顺时针进行跳跃,一种是猴子逆时针进行跳跃,所以猴子至少发生一次碰撞的次数猴子总共的移动次数-2
3.代码实现 public int monkeyMove(int n) {long ans1,a2;long mod1000000007;while(n!0){if((n1)1)ans(ans*a)%mod;a a * a % mod;n1;}return (int)((ansmod-2)%mod);}
