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

【C++】每日一题 50 Pow(x,n)

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,x^n )。

当需要计算x的n次幂时,可以使用递归或者迭代的方式来实现。

#include <iostream>double myPow(double x, int n) {if (n == 0) {return 1.0;} else if (n < 0) {return 1.0 / (x * myPow(x, -(n + 1)));} else {double half = myPow(x, n / 2);if (n % 2 == 0) {return half * half;} else {return x * half * half;}}
}int main() {double x = 2.0;int n = 10;std::cout << x << " raised to the power of " << n << " is: " << myPow(x, n) << std::endl;return 0;
}

在这个函数中,我们首先处理n为0和n为负数的情况,然后使用递归的方式计算x的n次幂。如果n为偶数,则将问题分解为计算x的n/2次幂,然后将结果相乘;如果n为奇数,则将问题分解为计算x的(n-1)/2次幂,然后将结果相乘,并额外乘以x。这样递归下去,直到n减小为0时返回1,从而完成了整数次幂的计算。

注意如果将这行代码

return 1.0 / (x * myPow(x, -(n + 1)));

替换为

 return 1.0/myPow(x,-n);


x =
1.00000
n =
-2147483648
时会溢出。
这个错误发生在对 -2147483648(即 INT_MIN)进行取反操作时。在 C++ 中,对 INT_MIN 进行取反会导致溢出,因为 INT_MIN 的绝对值大于 INT_MAX,无法表示为有符号整数的正值。
当 n 为 -2147483648 时,原始的代码中的 myPow(x, -n) 将会调用 myPow(x, 2147483648),这个值超出了 int 类型的范围,导致了溢出错误。
为了解决这个问题,要不需要将 n 强制转换为长整型 long long 类型,以避免溢出。
要不通过(x * myPow(x, -(n + 1)))处理使其不溢出

时间复杂度分析:

当 n 为正数时,我们可以通过递归将指数减半,因此时间复杂度为 O(logn),因为每次递归我们将指数减半。
当 n 为负数时,我们同样可以通过递归将指数加一减半,因此时间复杂度也为 O(logn)。

空间复杂度分析:

递归调用会使用栈空间,因此考虑递归的深度。由于每次递归将指数减半,所以递归的深度最多为 logn,因此空间复杂度为 O(logn)。
因此,经过修改后的 myPow 函数的时间复杂度为 O(logn),空间复杂度也为 O(logn)。这意味着无论是时间开销还是空间开销,随着指数的增长,都是以对数级别的速度增加的。

相关文章:

【C++】每日一题 50 Pow(x,n)

实现 pow(x, n) &#xff0c;即计算 x 的整数 n 次幂函数&#xff08;即&#xff0c;x^n &#xff09;。 当需要计算x的n次幂时&#xff0c;可以使用递归或者迭代的方式来实现。 #include <iostream>double myPow(double x, int n) {if (n 0) {return 1.0;} else if (…...

HG/T 6088-2022 透水道路用涂料检测

透水混凝土是指由水泥、矿物掺合料、骨料、外加剂及水等主要材料经拌合形成的&#xff0c;具有透水功能的混凝土材料&#xff0c;用于其表面的涂料称为透水道路用涂料。 HG/T 6088-2022透水道路用涂料检测项目&#xff1a; 测试指标 测试方法 有害物质限量 GB 38468 在容器…...

linux定时清理docker日志脚本

Linux 定时清理 Docker 日志的脚本与配置指南 在使用 Docker 容器化应用程序时,日志文件可能会迅速增长,占用大量磁盘空间。为了保持系统的稳定性和高效运行,定期清理 Docker 日志文件是必要的。本文将介绍如何编写一个 Linux 脚本来清理 Docker 日志文件,并通过 cron 定时…...

ROS学习笔记(16):夹缝循迹

0.前言 在笔记的第15期对巡墙驾驶的原理进行了简单讲解&#xff0c;而这期我们来讲一下夹缝循迹&#xff0c;也常被叫follow the gap&#xff0c;也更新一些概念。 1.探索式路径规划与避障 1.概念 无预先建图的路径规划叫探索式路径规划&#xff0c;例如巡墙循迹和夹缝循迹&…...

【MySQL精通之路】SQL语句(3)-锁和事务语句

目录 1.START TRANSACTION、COMMIT和ROLLBACK语句 2.无法回滚的语句 3.导致隐含COMMIT的语句 4.SAVEPOINT、ROLLBACK TO SAVEPOINT和RELEASE SAVEPOINT语句 5.LOCK INSTANCE FOR BACKUP和UNLOCK INSTANCE语句 6.LOCK TABLE和UNLOCK TABLES语句 6.1 表锁获取 6.2 表锁释放…...

211大学计算机专业不考408,新增的交叉专业却考408!南京农业大学计算机考研考情分析!

南京农业大学信息科技学院可追溯至1981年成立的计算中心和1985年筹建的农业图书情报专业。1987年设立了农业图书情报系&#xff0c;1993 年农业图书情报系更名为信息管理系&#xff0c;本科专业名称也于1999年更名为信息管理与信息系统专业。1994年计算中心开始招收计算机应用专…...

利用java8 的 CompletableFuture 优化 Flink 程序,性能提升 50%

你好&#xff0c;我是 shengjk1&#xff0c;多年大厂经验&#xff0c;努力构建 通俗易懂的、好玩的编程语言教程。 欢迎关注&#xff01;你会有如下收益&#xff1a; 了解大厂经验拥有和大厂相匹配的技术等 希望看什么&#xff0c;评论或者私信告诉我&#xff01; 文章目录 一…...

香橙派 AIpro综合体验及AI样例运行

香橙派 AIpro综合体验及AI样例运行 环境&#xff1a; 香橙派版本&#xff1a; AIpro(8TOPSINT8) OS : Ubuntu 22.04.3 LTS(GNU/Linux 5.10.0 aarch64) (2024-03-18) 远程服务端1&#xff1a;OpenSSH 8.9p1 远程服务端2&#xff1a;TightVNC Server 1.3.10 远程客户端&#xf…...

通过域名接口申请免费的ssl多域名证书

来此加密已顺利接入阿里云的域名接口&#xff0c;用户只需一键调用&#xff0c;便可轻松完成域名验证&#xff0c;从而更高效地申请证书。接下来&#xff0c;让我们详细解读一下整个操作过程。 来此加密官网 免费申请SSL证书 免费SSL多域名证书&#xff0c;泛域名证书。 首先&a…...

【JAVA WEB实用与优化技巧】如何自己封装一个自定义UI的Swagger组件,包含Swagger如何处理JWT无状态鉴权自动TOKEN获取

目录 一、Swagger 简介1. 什么是 Swagger&#xff1f;2. 如何使用 Swagger3. Springboot 中swagger的使用示例1. maven 引入安装2. java配置 二、Swagger UI存在的缺点1.不够方便直观2.请求的参数没有缓存3.不够美观4.如果是JWT 无状态登录&#xff0c;Swagger使用起来就没有那…...

理解大语言模型(二)——从零开始实现GPT-2

相关说明 这篇文章的大部分内容参考自我的新书《解构大语言模型&#xff1a;从线性回归到通用人工智能》&#xff0c;欢迎有兴趣的读者多多支持。 本文涉及到的代码链接如下&#xff1a;regression2chatgpt/ch11_llm/char_gpt.ipynb1 本文将讨论如何利用PyTorch从零开始搭建G…...

SSH远程登录时常见问题解决

SSH时出现WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! 问题解决——SSH时出现WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! 翻译过来就是 警告&#xff1a;远程主机标识已更改&#xff01; 此报错是由于远程的…...

工业级3D开发引擎HOOPS:创新与效率的融合!

在当今这个技术日新月异的时代&#xff0c;3D技术已成为推动各行各业发展的重要力量。从工程设计到游戏开发&#xff0c;从虚拟现实到增强现实&#xff0c;3D技术的应用无处不在&#xff0c;它极大地丰富了我们的生活和工作。而在这样的背景下&#xff0c;HOOPS作为一个强大的3…...

IDEA创建Spring Boot项目

1 打开新建项目界面 如图1&#xff0c;打开IDEA&#xff0c;点击菜单栏的File->New->Project&#xff0c;打开新建项目界面。 图1 新建项目 2 填写项目信息 在新建项目界面点击左侧工具栏的Spring Initializr选项&#xff0c;进行Spring Boot项目信息的填写&#xff…...

mysql实战——xtrabackup全量备份/增量备份及恢复

一、测试前准备 mysql数据库 端口3306数据文件目录 /data/mysql/3306/data 安装目录/usr/lcoal/mysql配置文件/etc/my.cnf 创建数据库 testXtra 创建备份目录 备份目录/data/backup/备份恢复数据文件目录/data/mysql/3307/data备份恢复配置文件/etc/my_3307.cnf 二、开始…...

探索演进:了解IPv4和IPv6之间的区别

探索演进&#xff1a;了解IPv4和IPv6之间的区别 在广阔的互联网领域中&#xff0c;设备之间的通信依赖于一组独特的协议来促进连接。前景协议中&#xff0c;IPv4&#xff08;Internet 协议版本 4&#xff09;和 IPv6&#xff08;Internet 协议版本 6&#xff09;是数字基础设施…...

Python 实现Word (DOC或DOCX)与TXT文本格式互转

目录 引言 安装Python库 使用Python将Word转换为TXT文本格式 使用Python将TXT文本格式转换为Word 引言 Word文档和TXT文本文件是日常工作和生活中两种常见的文件格式&#xff0c;各有其特点和优势。Word文档能够保留丰富的格式设置&#xff0c;如字体、段落、表格、图片等…...

anaconda install on CentOS 7

参考&#xff1a; CentOS 7安装conda并配置环境 CentOS 7安装conda并配置环境_centos conda-CSDN博客...

git管理Codeup云效平台

HTTPS方式实现Git命令 1.进入项目路径&#xff0c;如 cd demo&#xff0c;与此同时&#xff0c;在Codeup平台创建一个空仓库repo&#xff0c;获取空仓库的https协议地址&#xff0c;例如 https://codeup.aliyun.com/xxxx/xxxx/xxx.git。 2.在demo项目下执行 git init命令初始化…...

Pycharm最新安装教程(最新更新时间2024年5月27日)

ps&#xff1a;本教程Pycharm安装&#xff0c;最新更新时间&#xff1a;2024年5月27日&#xff0c;公众号持续更新关注公众号防失联哦 Pycharm 再次更新了一个小版本。又回到老话题&#xff0c;2023.3.2这个版本是否还能安装&#xff0c;笔者也亲测了一下。还是沿用本站之前的…...

TVA在汽车零部件焊接点检测中的实操启示录(3)

TVA系统在汽车零部件焊接点检测的落地&#xff0c;并非简单的“设备安装调试”&#xff0c;而是一个涉及流程优化、人员适配、技术衔接的系统工程。不少企业技术主管因忽视落地全流程管控&#xff0c;出现“系统安装后无法正常运行”“员工不会操作”“检测流程与生产流程脱节”…...

忍者像素绘卷惊艳效果:同一角色在横/竖/方三画幅下的电影感构图适配

忍者像素绘卷惊艳效果&#xff1a;同一角色在横/竖/方三画幅下的电影感构图适配 1. 像素艺术的新境界 忍者像素绘卷是一款基于Z-Image-Turbo深度优化的图像生成工作站&#xff0c;它将传统忍者文化与现代像素艺术完美结合。这款工具最令人惊叹的特点之一&#xff0c;是能够为…...

Windows下OpenClaw安装教程:一键部署Kimi-VL-A3B-Thinking镜像

Windows下OpenClaw安装教程&#xff1a;一键部署Kimi-VL-A3B-Thinking镜像 1. 为什么选择OpenClawKimi-VL组合 上周我在整理电脑上的图片素材时&#xff0c;突然冒出一个想法&#xff1a;如果能有个AI助手帮我自动分类这些图片&#xff0c;还能根据内容生成描述文字该多好。经…...

利用快马AI快速生成Android Studio天气预报应用原型

最近在尝试开发一个简单的天气预报应用&#xff0c;发现用传统方式从零开始搭建Android项目框架特别耗时。特别是Gradle配置和各种依赖项的引入&#xff0c;经常要反复调试。后来尝试了InsCode(快马)平台&#xff0c;发现它的AI生成功能能极大提升原型开发效率&#xff0c;这里…...

⚔️ 易经+人性+数学·三位一体终极博弈|算法裁判·话语权殖民·三色审计逻辑链闭环 v2.0|UID9622

《道德经》第三十六章&#xff1a;“将欲夺之&#xff0c;必固予之。” —— 先给你一把裁判的椅子&#xff0c;再告诉你&#xff0c;坐上去的人才有资格说话。&#x1f9ed; 这篇文章在干嘛⚔️ 这不是针对任何人的。 这是一场博弈论的推演——用易经的智慧、人性的逻辑、数学…...

Lenovo Legion Toolkit开源硬件管理工具完全指南:从问题诊断到系统优化

Lenovo Legion Toolkit开源硬件管理工具完全指南&#xff1a;从问题诊断到系统优化 【免费下载链接】LenovoLegionToolkit Lightweight Lenovo Vantage and Hotkeys replacement for Lenovo Legion laptops. 项目地址: https://gitcode.com/gh_mirrors/le/LenovoLegionToolki…...

利用快马平台快速原型:基于17.100.c.cm的网络设备配置界面搭建指南

最近在做一个网络设备管理的小工具&#xff0c;需要快速验证一个配置界面的原型。正好发现了InsCode(快马)平台这个神器&#xff0c;用它不到半小时就搞定了基础功能&#xff0c;特别适合像我这样想快速验证想法的开发者。下面分享下具体实现过程&#xff1a; 界面布局设计 首先…...

5分钟掌握usbipd-win:Windows USB设备跨平台共享神器

5分钟掌握usbipd-win&#xff1a;Windows USB设备跨平台共享神器 【免费下载链接】usbipd-win Windows software for sharing locally connected USB devices to other machines, including Hyper-V guests and WSL 2. 项目地址: https://gitcode.com/gh_mirrors/us/usbipd-w…...

告别IPA安装困境:App-Installer如何实现iOS应用部署革命

告别IPA安装困境&#xff1a;App-Installer如何实现iOS应用部署革命 【免费下载链接】App-Installer On-device IPA installer 项目地址: https://gitcode.com/gh_mirrors/ap/App-Installer 你是否曾遇到这样的情况&#xff1a;急需安装一个第三方iOS应用&#xff0c;却…...

墨语灵犀33语种翻译准确率实测:专业领域术语覆盖能力报告

墨语灵犀33语种翻译准确率实测&#xff1a;专业领域术语覆盖能力报告 1. 引言&#xff1a;当古典美学遇见现代翻译技术 在全球化交流日益频繁的今天&#xff0c;语言翻译工具已经成为我们工作学习中不可或缺的助手。然而&#xff0c;大多数翻译工具都停留在功能实用层面&…...