当前位置: 首页 > 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;从入门到调优…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用

Linux 内存管理调试分析&#xff1a;ftrace、perf、crash 的系统化使用 Linux 内核内存管理是构成整个内核性能和系统稳定性的基础&#xff0c;但这一子系统结构复杂&#xff0c;常常有设置失败、性能展示不良、OOM 杀进程等问题。要分析这些问题&#xff0c;需要一套工具化、…...