当前位置: 首页 > news >正文

【快速幂算法】快速幂算法讲解及C语言实现(递归实现和非递归实现,附代码)

快速幂算法

快速幂算法可用分治法实现

不难看出,对任意实数a和非负整数n,有:
a n = { 1 , n = 0 , a ≠ 0 0 , a = 0 ( a n 2 ) 2 , n > 0 , n 为偶数 ( a n 2 ) 2 ∗ a , n > 0 , n 为奇数 a^n = \begin{cases} 1, & n = 0, a\neq 0 \\ 0, & a = 0 \\ \left( a^\frac{n}{2} \right)^2, & n > 0, n \text{为偶数} \\ \left( a^\frac{n}{2} \right)^2*a, & n > 0, n \text{为奇数} \end{cases} an= 1,0,(a2n)2,(a2n)2a,n=0,a=0a=0n>0,n为偶数n>0,n为奇数
这里n/2是C语言中的整除计算,所以n为奇数时需要额外乘一个a
n=0可作为递归边界

递归实现

  • a如果等于0则返回0

  • n=0时作为递归边界返回1

  • n不等于0时,递归求 a n 2 a^\frac{n}{2} a2n的值,再根据n的奇偶性返回相应值

代码
double exp2(int a, int n){if (a == 0)return 0;if (n <= 0)return 1;else{int x = exp2(a, n/2);if (n % 2)return x * x *a;return x * x;}
}

时间复杂度为O(logn)

非递归实现

非递归实现的方法在于将指数n分解乘二进制,将对应二进制位为1的乘起来,就得到最终的结果

例:计算 3 93 3^{93} 393

93 = ( 1011101 ) 2 = 64 + 16 + 8 + 4 + 1 93=(1011101)_2=64+16+8+4+1 93=(1011101)2=64+16+8+4+1

3 93 = 3 64 ∗ 3 16 ∗ 3 8 ∗ 3 4 ∗ 3 3^{93}=3^{64}*3^{16}*3^{8}*3^{4}*3 393=36431638343

代码
  • 变量s存储当前计算结果,并最终作为返回值

  • 变量b存储当前数位的乘方值

  • 遍历n的每一个二进制位

    • n & 1判断指数当前的最后一位是否为1
    • 每次循环将指数n右移一位(除以2),并将b累乘一次,计算当前的乘方
double exp2(int a, int n) {double b, s = 1.0;b = a;while (n > 0) {if (n & 1) {s *= b;}n /= 2;b *= b;}return s;
}

因为n有logn+1个二进制位,只需要次计算就能得到 a n a^n an,时间复杂度为O(n)

测试
double exp2(int a, int n) {double b, s = 1.0;b = a;while (n > 0) {if (n & 1) {s *= b;}n /= 2;b *= b;}return s;
}
int main()
{cout << exp2(3, 93);return 0;
}

结果

在这里插入图片描述

在这里插入图片描述

结果正确

由于递归算法涉及到对栈的操作,一般建议使用非递归算法

相关文章:

【快速幂算法】快速幂算法讲解及C语言实现(递归实现和非递归实现,附代码)

快速幂算法 快速幂算法可用分治法实现 不难看出&#xff0c;对任意实数a和非负整数n&#xff0c;有&#xff1a; a n { 1 , n 0 , a ≠ 0 0 , a 0 ( a n 2 ) 2 , n > 0 , n 为偶数 ( a n 2 ) 2 ∗ a , n > 0 , n 为奇数 a^n \begin{cases} 1, & n 0, a\neq 0…...

3. 导入官方dashboard

官方dashboard&#xff1a;https://grafana.com/grafana/dashboards 1. 点击仪表板 - 新建 - 导入 注&#xff1a;有网络的情况想可以使用ID&#xff0c;无网络情况下使用仪表板josn文件 2. 在官方dashboard网页上选择符合你现在数据源的dashboard - 点击进入 3. 下拉网页选…...

怎么理解 Spring Boot 的约定优于配置 ?

在传统的 Spring 开发中&#xff0c;大家可能都有过这样的经历&#xff1a;项目还没开始写几行核心业务代码&#xff0c;就已经在各种配置文件中耗费了大量时间。比如&#xff0c;要配置数据库连接&#xff0c;不仅要在 XML 文件里编写冗长的数据源配置&#xff0c;还要处理事务…...

Dify 是什么?Dify是一个开源的LLM应用开发平台,支持快速搭建生成式AI应用,具有RAG管道、Agent功能、模型集成等特点

首先&#xff0c;Dify是一个开源的LLM应用开发平台&#xff0c;支持快速搭建生成式AI应用&#xff0c;具有RAG管道、Agent功能、模型集成等特点75。根据搜索结果&#xff0c;网页6详细对比了多个RAG和AI开发框架&#xff0c;包括MaxKB、FastGPT、RagFlow、Anything-LLM等。其中…...

数据预处理都做什么,用什么工具

数据预处理是数据分析、数据挖掘和机器学习中的关键步骤&#xff0c;其目的是将原始数据转换为适合后续分析或建模的格式。以下是关于数据预处理的主要内容及常用工具的详细介绍&#xff1a; 一、数据预处理的主要任务 数据预处理的主要任务包括以下几个方面&#xff1a; 数据…...

windows蓝牙驱动开发-在蓝牙配置文件驱动程序中接受 L2CAP 连接

L2CAP 服务器配置文件驱动程序会响应来自远程设备的传入逻辑链接控制和适应协议 (L2CAP) 连接请求。 例如&#xff0c;PDA 的 L2CAP 服务器配置文件驱动程序将响应来自 PDA 的传入连接请求。 接收传入 L2CAP 连接请求 1. 若要接收来自特定 PSM 的任何远程设备的传入 L2CAP 连…...

【原理图PCB专题】自制汉字转码工具,适配Allgero 17版本 Skill

众所周知,在使用Skill来编写Allegro控制脚本时如果程序的源码里是汉字,那么有可能会出现乱码。比如像下图这样的程序: 在Allegro中运行如下图所示: 那么如果我们需要让他转成正常的中文字符,就需要将字符转成GBK编码 打开自制小软件:中文与GBK编码互转V1…...

欧拉公式在信号处理中的魔法:调幅信号的生成与频谱分析

欧拉公式在信号处理中的魔法:调幅信号的生成与频谱分析 “数学不是枯燥的符号,而是宇宙的诗歌。” 当我们用欧拉公式解开调幅信号的频谱密码时,仿佛看到电磁波在时空中跳动的频率之舞。这篇博客将带你亲手触摸信号处理中的数学之美。 一、当欧拉公式遇见调幅信号:一场数学与…...

如何在Ubuntu中切换多个PHP版本

在Ubuntu环境下实现PHP版本的灵活切换&#xff0c;是众多开发者与系统管理员的重要技能之一。下面&#xff0c;我们将深入探讨如何在Ubuntu系统中安装、配置及管理多个PHP版本&#xff0c;确保您的开发环境随心所欲地适应各类项目需求。 开始前的准备 确保您的Ubuntu系统保持…...

基于opencv的HOG+角点匹配教程

1. 引言 在计算机视觉任务中&#xff0c;特征匹配是目标识别、图像配准和物体跟踪的重要组成部分。本文介绍如何使用 HOG&#xff08;Histogram of Oriented Gradients&#xff0c;方向梯度直方图&#xff09; 和 角点检测&#xff08;Corner Detection&#xff09; 进行特征匹…...

Linux线程概念与线程操作

Linux线程概念与线程操作 线程概念 前面提到进程程序代码和数据进程结构体&#xff0c;在线程部分就需要进一步更新之前的认识 进程实际上承担分配系统资源的基本实体&#xff0c;而线程是进程中的一个执行分支&#xff0c;是操作系统调度的基本单位 此处需要注意&#xff0…...

AI软件栈:LLVM分析(五)

数据流分析是编译优化、代码生成的关键理论。其数学基础是离散数学中的半格(Semi-Lattice)和格。半格与格不仅是编译优化和代码生成的重要理论基础,也是程序分析、验证及自动化测试的系统理论基础。 文章目录 格、半格与不动点格、半格与不动点 半格是指针对二元组 < S …...

Git指南-从入门到精通

代码提交和同步命令 流程图如下&#xff1a; 第零步: 工作区与仓库保持一致第一步: 文件增删改&#xff0c;变为已修改状态第二步: git add &#xff0c;变为已暂存状态 bash $ git status $ git add --all # 当前项目下的所有更改 $ git add . # 当前目录下的所有更改 $ g…...

Linux 文件系统挂载

系列文章目录 Linux内核学习 Linux 知识&#xff08;1&#xff09; Linux 知识&#xff08;2&#xff09; WSL Ubuntu QEMU 虚拟机 Linux 调试视频 PCIe 与 USB 的补充知识 vscode 使用说明 树莓派 4B 指南 设备驱动畅想 Linux内核子系统 Linux 文件系统挂载 文章目录 系列文章…...

Qt QSpinBox 总结

Qt5 QSpinBox 总结 1. 基本特性 用途&#xff1a;用于输入和调整整数值&#xff0c;支持通过上下箭头、键盘输入或编程方式修改值。 默认范围&#xff1a;0 到 99&#xff0c;可通过 setRange(min, max) 自定义。 步长控制&#xff1a;setSingleStep(step) 设置单步增减值&a…...

【OJ项目】深入剖析题目接口控制器:功能、实现与应用

《深入剖析题目接口控制器&#xff1a;功能、实现与应用》 一、引言 在在线编程平台或竞赛系统中&#xff0c;题目管理和提交是核心功能之一。QuestionController 类作为控制器层&#xff0c;承担着处理与题目相关的各种请求的重要职责&#xff0c;包括题目的增删改查、题目提…...

周考考题(学习自用)

1.查询student表中name叫张某的信息 select * from student where name张某; 2.写出char和varchar类型的区别 1&#xff09;char存储固定长度的字符串&#xff0c;varchar存储可变长度的字符串&#xff08;在实际长度的字符串上加上一个字节用于存储字符串长度&#xff09;&a…...

【matlab】大小键盘对应的Kbname

matlab中可以通过Kbname来识别键盘上的键。在写范式的时候&#xff0c;遇到一个问题&#xff0c;我想用大键盘上排成一行的数字按键评分&#xff0c;比如 Kbname(1) 表示键盘上的数字1&#xff0c;但是这种写法只能识别小键盘上的数字&#xff0c;无法达到我的目的&#xff0c;…...

LabVIEW与小众设备集成

在LabVIEW开发中&#xff0c;当面临控制如布鲁克OPUS红外光谱仪这类小众专业设备的需求&#xff0c;而厂家虽然提供了配套软件&#xff0c;但由于系统中还需要控制其他设备且不能使用厂商的软件时&#xff0c;必须依赖特定方法通过LabVIEW实现设备的控制。开发过程中&#xff0…...

Android 系统Service流程

主要用到的源码文件 /frameworks/base/core/java/android/app/ContextImpl.java 和ams通信。 /frameworks/base/services/core/java/com/android/server/am/ActivityManagerService.java 初始化Service,.管理服务 ActiveServices对象mServices /frameworks/base/services/core/…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...