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

c语言青蛙跳台阶

"青蛙跳台阶"问题是一个经典的动态规划问题,经常被用来解释动态规划的基本概念。问题的描述是:假设一只青蛙可以跳上1级或2级台阶,如果有n级台阶,那么青蛙有多少种跳法。

在C语言中,我们可以使用动态规划来解决这个问题。下面是一个示例代码:

  1. #include <stdio.h>
  2. long long frogJump(int n) {
  3.     if (n <= 2) {
  4.         return n;
  5.     }
  6.     long long dp[n+1];
  7.     dp[1] = 1;
  8.     dp[2] = 2;
  9.     for (int i = 3; i <= n; i++) {
  10.         dp[i] = dp[i-1] + dp[i-2];
  11.     }
  12.     return dp[n];
  13. }
  14. int main() {
  15.     int steps;
  16.     printf("请输入台阶数:");
  17.     scanf("%d", &steps);
  18.     printf("青蛙跳上%d级台阶的方法数为:%lld\n", steps, frogJump(steps));
  19.     return 0;
  20. }

在这个代码中,我们首先检查台阶数是否小于或等于2。如果是,我们直接返回台阶数,因为青蛙可以直接跳上去。如果不是,我们初始化一个数组dp,其中dp[i]表示跳上i级台阶的方法数。然后我们用一个循环来计算dp数组的值,最后返回dp[n],即跳上n级台阶的方法数。

这个问题的关键在于理解,青蛙跳上n级台阶的方法数等于跳上n-1级台阶和n-2级台阶的方法数的和。这是因为青蛙可以选择跳上一级台阶,或者跳上两级台阶。所以,我们用一个动态规划的思路来解决这个问题,即通过计算并保存每一级台阶的方法数,然后再利用这些保存的方法数来计算更高级台阶的方法数。

上述代码中的主函数首先从用户那里获取台阶数,然后调用frogJump函数来计算青蛙跳上这么多台阶的方法数,并将结果打印出来。

需要注意的是,由于我们使用了一个long long类型的数组来保存方法数,所以这个程序可以计算出相当大的台阶数的结果。然而,由于计算机资源的限制,如果台阶数过大,可能会导致溢出错误。为了避免这种情况,可以使用更复杂的算法来减少内存的使用,或者使用其他编程语言和工具来获取更准确的结果。

另外,如果你想在C语言中实现斐波那契数列,可以直接计算而不需要动态规划。对于n级台阶,就是斐波那契数列的第n项,可以通过递归或迭代的方式直接计算出来。以下是迭代的实现方式:

  1. #include <stdio.h>
  2. long long fibonacci(int n) {
  3.     if (n <= 0) {
  4.         return 0;
  5.     } else if (n == 1) {
  6.         return 1;
  7.     } else {
  8.         long long a = 0, b = 1;
  9.         for (int i = 2; i <= n; i++) {
  10.             long long temp = a + b;
  11.             a = b;
  12.             b = temp;
  13.         }
  14.         return b;
  15.     }
  16. }
  17. int main() {
  18.     int steps;
  19.     printf("请输入台阶数:");
  20.     scanf("%d", &steps);
  21.     printf("青蛙跳上%d级台阶的方法数为:%lld\n", steps, fibonacci(steps));
  22.     return 0;
  23. }

在这个代码中,我们用一个循环来计算斐波那契数列的第n项,然后返回结果。这种方法比动态规划的方法更简单,但是它需要更多的计算,特别是当n非常大的时候。

当然,还有更多的优化方式可以提高计算斐波那契数列的效率。例如,可以使用缓存来存储已经计算过的值,以避免重复计算。或者使用更高效的算法,例如快速幂算法。还可以使用更高效的编程语言和工具,例如Python的内置函数或者使用GPU进行并行计算。

另外,这个问题的实际应用不仅仅是计算斐波那契数列。它还可以被用来解决其他的问题,例如计算组合数或者解决旅行者问题。因此,可以根据具体的问题场景选择最合适的解决方法。

最后,需要注意的是,虽然计算机科学在很大程度上已经解决了大规模计算的问题,但是仍然存在一些问题需要更复杂的算法或者更多的资源来解决。因此,即使是最先进的计算机科学技术,也有可能需要不断的改进和发展才能满足不断增长的计算需求。

相关文章:

c语言青蛙跳台阶

"青蛙跳台阶"问题是一个经典的动态规划问题&#xff0c;经常被用来解释动态规划的基本概念。问题的描述是&#xff1a;假设一只青蛙可以跳上1级或2级台阶&#xff0c;如果有n级台阶&#xff0c;那么青蛙有多少种跳法。 在C语言中&#xff0c;我们可以使用动态规划来…...

IntelliJ IDEA 2023.3 最新版如何试用?IntelliJ IDEA 2023.3 最新版试用方法

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

Java参数校验详解:使用@Valid注解和自定义注解进行参数验证

很多时候我们需要使用不少if、else等等逻辑判断及验证&#xff0c;这样在进行一些重复的参数校验会很麻烦&#xff0c;且以后要维护也会吃力。 而这样就可以使用javax.validation。验证&#xff08;Validation&#xff09;常见的验证操作包括验证数据的类型、格式、长度、范围、…...

多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测

多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测 目录 多维时序 | MATLAB实现BWO-CNN-BiGRU-Multihead-Attention多头注意力机制多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 MATLAB实现BWO-CNN-B…...

C++ 中的引用

文章目录 C 引用的应用1. 修改函数中传递的参数2. 避免复制大型结构3. for 循环中修改所有对象4. for 循环中避免复制对象 References vs Pointers引用的限制使用引用的优点练习Quesition 1Question 2Question 3Question 4Question 5Question 6 如果一个变量被声明为引用&#…...

MQ-Det: Multi-modal Queried Object Detection in the Wild

首个支持视觉和文本查询的开放集目标检测方法 NeurIPS2023 文章&#xff1a;https://arxiv.org/abs/2305.18980 代码&#xff1a;https://github.com/YifanXu74/MQ-Det 主框图 摘要 这篇文章提出了MQ-Det&#xff0c;一种高效的架构和预训练策略&#xff0c;它利用文本描述的…...

HarmonyOS应用开发初体验

9月25日华为秋季全场景新品发布会上&#xff0c;余承东宣布&#xff0c;全面启动鸿蒙原生应用&#xff0c;HarmonyOS NEXT开发者预览版将在2024年第一季度面向开发者开放。 最近鸿蒙开发可谓是火得一塌糊涂&#xff0c;各大培训平台都开设了鸿蒙开发课程。美团发布了鸿蒙高级工…...

《C++新经典设计模式》之第4章 策略模式

《C新经典设计模式》之第4章 策略模式 策略模式.cpp 策略模式.cpp #include <iostream> #include <memory> using namespace std;// if或switch分支不稳定&#xff0c;经常改动时&#xff0c;考虑引入算法独立到策略类中去实现// 依赖倒置原则 // 高层组件不应该依…...

【方法】PowerPoint“只读方式”如何取消?

PPT设置了以“只读方式”打开&#xff0c;可以保护文件无法编辑更改&#xff0c;那后续不需要保护了&#xff0c;或者想要编辑文件&#xff0c;要如何取消“只读方式”呢&#xff1f; 首先&#xff0c;我们要看看PPT设置的是哪种“只读方式”。 如果PPT设置的是无密码“只读方…...

MySQL数据库概念与实践

MySQL数据库概念与实践 1. 概念 MySQL是一种常用的关系型数据库管理系统&#xff0c;具有丰富的功能和广泛的应用。在本篇博客中&#xff0c;我们将介绍MySQL数据库的一些重要概念和相关知识。 存储引擎 存储引擎是MySQL数据库用于存储、更新和查询数据的技术实现方法。MyS…...

【ArcGIS Pro微课1000例】0052:基于SQL Server创建企业级地理数据库案例

文章目录 环境搭建创建企业级数据库连接企业级数据库环境搭建 ArcGIS:ArcGIS Pro 3.0.1Server.ecp:版本为10.7SQL Server:版本为SQL Server Developer 2019创建企业级数据库 企业级地理数据库的创建需要通过工具箱来实现。工具位于:数据管理工具→地理数据库管理→创建企业…...

深度学习——第3章 Python程序设计语言(3.7 matplotlib库)

3.7 matplotlib库 目录 1 matplotlib库简介 2 pyplot的plot函数 3 matplotlib基础绘图函数示例 数据可视化有助于深度理解数据。 本节介绍绘制图形的基本方法。 1. matplotlib库简介 matplotlib官网 1.1 matplotlib库概述 matplotlib是Python优秀的数据可视化第三方库&a…...

【数据分析实战】酒店行业华住集团门店分布与评分多维度分析

文章目录 1. 写在前面2. 数据集展示3. 多维度分析3.1 门店档次多元化&#xff1a;集团投资战略观察3.1.1 代码实现3.1.2 本人浅薄理解 3.2 门店分布&#xff1a;各省市分布概览3.2.1 代码实现3.2.2 本人浅薄理解 3.3 门店分级评分&#xff1a;服务水平的多维度观察3.3.1 代码实…...

近期Chrome浏览器 不知哪个版本升级后原先http强制跳转到https,导致服务端302强制跳转到http也没反应

关于Chrome更新http强制跳转到https解决方法 近期Chrome浏览器 不知哪个版本升级后原先http强制跳转到https&#xff0c;导致服务端302强制跳转到http也没反应一、F12检查加载的Response Headers中有没有Non-Authoritative-Reason二、找了资料后得到解决方案&#xff1a;三、找…...

【scikit-learn基础】--『数据加载』之样本生成器

除了内置的数据集&#xff0c;scikit-learn还提供了随机样本的生成器。通过这些生成器函数&#xff0c;可以生成具有特定特性和分布的随机数据集&#xff0c;以帮助进行机器学习算法的研究、测试和比较。 目前&#xff0c;scikit-learn库&#xff08;v1.3.0版&#xff09;中有2…...

基于 ESP32-S3 的 Walter 开发板

Walter 是一款基于 ESP32-S3 且拥有 5G LTE 连接功能的新型开源开发套件。 近日&#xff0c;比利时公司 DPTechnics BV 推出了一款基于乐鑫 ESP32-S3 且拥有 5G LTE 连接功能的新型开源开发套件。该套件即将在 Crowd Supply 平台上发布&#xff0c;您可以点击此处了解详情。 无…...

Gitlab+GitlabRunner搭建CICD自动化流水线将应用部署上Kubernetes

文章目录 安装Gitlab服务器准备安装版本安装依赖和暴露端口安装Gitlab修改Gitlab配置文件访问Gitlab 安装Gitlab Runner服务器准备安装版本安装依赖安装Gitlab Runner安装打包工具安装docker安装java17安装maven 注册Gitlab Runner 搭建自动化部署准备SpringBoot项目添加一个Co…...

待做-待补充-每个节点做事,时间,以及与角度的关系

文章目录 纲领1.是否可以通过遍历一遍二叉树得到答案2.是否可以通过两颗子树相同问题的答案推导出树的答案(形式为递归)无论哪种思维模式&#xff0c;都需要思考:单独一个二叉树节点&#xff0c;它需要做什么事情&#xff1f;需要在什么时候做 后序判断问题是否和子树相关&…...

液态二氧化碳储存罐远程无线监测系统

二氧化碳强化石油开采技术&#xff0c;须先深入了解石油储层的地质特征和二氧化碳的作用机制。现场有8辆二氧化碳罐装车&#xff0c;每辆罐车上有4台液态二氧化碳储罐&#xff0c;每台罐的尾部都装有一台西门子S7-200 smart PLC。在注入二氧化碳的过程中&#xff0c;中控室S7-1…...

kafka学习笔记--安装部署、简单操作

本文内容来自尚硅谷B站公开教学视频&#xff0c;仅做个人总结、学习、复习使用&#xff0c;任何对此文章的引用&#xff0c;应当说明源出处为尚硅谷&#xff0c;不得用于商业用途。 如有侵权、联系速删 视频教程链接&#xff1a;【尚硅谷】Kafka3.x教程&#xff08;从入门到调优…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...