算法设计和分析1( 算法问题求解基础)

news/2024/6/24 7:37:18/文章来源:https://blog.csdn.net/qq_53682472/article/details/137275392

chapter1 算法问题求解基础

1.1算法概述

1.什么是算法

  1. 算法—用计算机实现的问题求解方法。
  2. 5个特征
    (1)输入:0或多个
    (2)输出:至少一个
    (3)确定性:算法每一条指令都有明确的定义
    (4)能行性:算法每一条指令必须足够基本,可以用=已实现的基本运算执行有限次来实现。
    (5)有穷性:有限步骤后终止
  3. 描述方法
    大白话、流程图、伪代码、程序设计语言

例1 计算两个整数的最大公约数(辗转相除法==欧几里得算法、连续整数检测算法)
用于计算两个整数m和n(0<=m<n)的最大公约数gcd(m,n).其计算过程是重复下列等式,直到n mod m=0.
gcd(m,n)=gcd(n mod m,m)
例如gcd(24,60)=gcd(12,24)=gcd(0,12)=12

程序1-1 欧几里得递归算法 (递归调用函数)

#include<iostream>
#include<algorithm>
using namespace std;//欧几里得递归算法void Swap(int &a,int &b)//用于交换两个数的函数,其实有内置的swap函数,注意要变量的引用
{int c=a;a=b;b=c;
}
int RGcd(int m,int n)//0<=m<n
{if(m==0)return n;return  RGcd(n%m,m);
}
int Gcd(int m,int n)
{if(m>n)Swap(m,n);return RGcd(m,n);
}
int main()
{int m,n;cin>>m>>n;cout<<Gcd(m,n);return 0;}

程序1-2 欧几里得迭代算法(循环

#include<bits/stdc++.h>
using namespace std;int Gcd(int m,int n)
{if(m==0)return n;if(n==0)return m;if(m>n)swap(m,n);//n中保存大的数while(m>0){int rem=n%m;n=m;m=rem;}return n;
}
int main()
{int m,n;cin>>m>>n;cout<<Gcd(m,n);return 0;}

连续整数检测算法
最大公约数定义:能够同时整除它们的最大正整数。因此最大公约数小于或等于两数中的较小者。t=min{m,n},然后检查t能否整除m和n ,若能,即为解;否则t–,继续检测

#include<bits/stdc++.h>
using namespace std;int Gcd(int m,int n)
{if(m==0)return n;if(n==0)return m;int t=m>n?n:m;while(m%t ||n%t)t--;return t;
}
int main()
{int m,n;cin>>m>>n;cout<<Gcd(m,n);return 0;}

2.为什么学习算法

重要重要重要
一个受过良好的计算机科学知识训练的人知道如何处理算法,即构造算法、操纵算法、理解算法和分析算法。算法远不只是为了编写好的计算程序,它是一种具有一般意义的智能工具,必定有助于对其他学科的理解。

1.2 问题求解方法

软件开发的过程----使用计算机求解问题的过程。
计算机解题的核心任务----设计算法

1.问题和问题求解

问题----与希望的目标不一致

2.问题求解过程

  1. 理解问题
  2. 设计方案
  • 何处着手,类似问题
  • 一些特殊示例进行分析
  1. 实现方案
  2. 回顾复查
  • 评估:改进、简化和推广

3.系统生命周期

系统生命周期:软件工程将软件开发和维护过程分成若干阶段。分析(做什么)、设计(如何做)、编码、测试和维护

1.3 算法设计和分析

1.算法问题求解过程

精确算法、启发式算法(可能更有效,但未必是最优解)

2.如何设计算法

学习基本算法
如合并排序和快速排序都可以视为分治法产生的排序算法,但二者是不同的算法。

3.如何表示算法

自然语言、流程图、伪代码、程序设计语言等,(下面主要用c/c++来描述)

4.如何确认算法

算法确认:对于所有的合法术后如,都能在有限时间输出预期结果。
算法证明:使用数学方法

5.如何分析算法

执行时间和所需空间

1.4 递归和归纳

重复性计算
(1)递归
(2)迭代
归纳法和递归关系密切,可以用归纳法证明递归算法的正确性。

1.递归

递归定义:直接或间接引用自身的定义方法。包括基础情况和递归部分

例1-1 斐波那契数列

F0=0,F1=1;
Fn=Fn-1+Fn-2;

需要注意的是,递归实现的斐波那契数列在计算过程中会存在大量的重复计算,效率较低。如果需要计算较大的斐波那契数列,建议使用迭代或动态规划的方法,可以避免重复计算,提高效率。

long Fib(int n)
{if(n<=1)return n;else return Fib(n-1)+Fib(n-2);
}

2.递归算法示例

例1-2 逆序输出整数的各位数 设有正整数n=12345,现希望逆序输出54321.
设k位整数为d1d2…dk,要得到dkdk-1…d1可以分两步:
(1)首先输出dk
(2)然后输出由前k-1位组成的正整数d1d2…dk-1

得到下面的递归程序

#include<bits/stdc++.h>
using namespace std;void PrintDigit(unsigned int n)
{cout<<n%10;if(n>=10)PrintDigit(n/10);
}
int main()
{unsigned int n;cin>>n;PrintDigit(n);return 0;
}

例1-3 汉诺塔问题
假定有三个塔座:x,y,z,在塔座上有n个直径不同的圆盘,它们按直径大小从小到大编号为1,2,…,n。现要求将x塔座上的n个圆盘移动到y上,并按相同的顺序叠排。移动时:
(1)每次只能移动一个圆盘
(2)圆盘可以加到塔座x、y、z中任意一个之上
(3)任何时刻都不能将一个较大的圆盘放在较小的圆盘之上

假定圆盘从小到大编号为1-n,移动圆盘的算法可以粗略地描述如下:
(1)以y为中介,将前n-1个圆盘从x移到z上
(2)将第n个圆盘移到y上
(3)以x为中介,将z上的n-1个圆盘移到y上

#include<bits/stdc++.h>
using namespace std;
enum tower{A='X',B='Y',C='Z'};
void Move(int n,tower x,tower y)
{//将第n个圆盘从x移到y的顶部cout<<"The disk "<<n<<" is moved from "<<char(x)<<" to top of tower "<<char(y)<<endl;
}
void Hanoi(int n,tower x,tower y,tower z)//将n个圆盘从x->y,z作为中介
{if(n){Hanoi(n-1,x,z,y);Move(n,x,y);Hanoi(n-1,z,y,x);}
}
int main()
{Hanoi(3,A,B,C);return 0;}

输出如下

The disk 1 is moved from X to top of tower Y
The disk 2 is moved from X to top of tower Z
The disk 1 is moved from Y to top of tower Z
The disk 3 is moved from X to top of tower Y
The disk 1 is moved from Z to top of tower X
The disk 2 is moved from Z to top of tower Y
The disk 1 is moved from X to top of tower Y

例1-4 产生各种可能的排列
给定n个自然数,{0,1,2,…n-1}的集合。设计一个算法,输出该集合所有可能的排列(permutation).n个自然数的集合有n!个不同的排列。

介绍一种求此问题的简单递归算法。

由四个自然数组成的排列通过以下方式构造:
(1)以0 开头,紧随其后为{1,2,3}的各种排列
(2)以1 开头,紧随其后为{0,2,3}的各种排列
(3)以2 开头,紧随其后为{0,1,3}的各种排列
(4)以3 开头,紧随其后为{0,1,2}的各种排列
语句(1)中“紧随其后为{1,2,3}的各种排列”实质上是求比原始问题少一个数的排列生成问题。相当于原题目,这是一个同类子问题,但规模小一些。意味着可用递归求解

template <class T>void Perm(T a[],int k,int n)
{if(k=n-1){for(int i=0;i<n;i++)//输出一种排列cout<<a[i]<<" ";}elsefor(int i=k;i<n;i++){T t=a[k];a[k]=a[i];a[i]=t;//产生{a[k],...a[n-1]}各种排列Perm(a,k+1,n);t=a[k];a[k]=a[i];s[i]=t;//产生{a[k+1],...a[n-1]}各种排列}
}

本章小结

递归是强有力的算法算法结构。

习题

1.写一个递归算法和一个迭代算法计算二项式系数。 Cnm=Cn-1m+Cn-1m-1=n!/m!(n-m)!

递归法

#include<bits/stdc++.h>
using namespace std;
int Combine(int m,int n)
{if(m==0||m==n)return 1;//注意递归出口,是一个确定的值else return Combine(m,n-1)+Combine(m-1,n-1);
}int main()
{int m,n;cin>>m>>n;cout<<Combine(m,n);return 0;}

迭代法是不是用一个数组保存结果呀,然后依次计算。

2.S是有n个元素的集合,S的幂集是S的所有可能的子集组成的集合。例如,S={a,b,c},S的幂集={{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.写一个递归函数,以S为输入,输出S的幂集。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034830.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

高效学习方法:冥想背诵,看一句念一句,再每个词分析位置及语法等合理性,忘记哪个词再看猜下为什么会忘,跟自己的表达哪里不一样。

原则&#xff1a;易学则易行&#xff0c;则效果最好。《易经》 你提到的这种学习方法结合了多种记忆和理解技巧&#xff0c;可以帮助提高学习效率。下面是对这种方法的一个详细解释和一些建议&#xff1a; 冥想背诵&#xff1a;通过冥想来集中注意力&#xff0c;可以帮助你在没…

学习vue3第十二节(组件的使用与类型)

1、组件的作用用途 目的&#xff1a; 提高代码的复用度&#xff0c;和便于维护&#xff0c;通过封装将复杂的功能代码拆分为更小的模块&#xff0c;方便管理&#xff0c; 当我们需要实现相同的功能时&#xff0c;我们只需要复用已经封装好的组件&#xff0c;而不需要重新编写相…

神经网络:梯度下降法更新模型参数

作者&#xff1a;CSDN _养乐多_ 在神经网络领域&#xff0c;梯度下降是一种核心的优化算法&#xff0c;本文将介绍神经网络中梯度下降法更新参数的公式&#xff0c;并通过实例演示其在模型训练中的应用。通过本博客&#xff0c;读者将能够更好地理解深度学习中的优化算法和损…

如何从文本数据中提取子列表

提取文本数据中的子列表可以通过各种方式实现&#xff0c;具体取决于文本数据的结构和提取子列表的条件。例如&#xff1a;使用字符串操作和条件判断、使用正则表达式、使用自然语言处理工具、使用自定义解析器等几种模式&#xff0c;那么对于在日常使用中会有那些问题呢 &…

EasyExcel 模板导出excel、合并单元格及单元格样式设置。 Freemarker导出word 合并单元格

xls文件&#xff1a; 后端代码&#xff1a; InputStream filePath this.getClass().getClassLoader().getResourceAsStream(templateFile);// 根据模板文件生成目标文件ExcelWriter excelWriter EasyExcel.write(orgInfo.getFilename()).excelType(ExcelTypeEnum.XLS).withTe…

python批量转化pdf图片为jpg图片

1.把pdf图片批量转为jpg&#xff1b;需要注意的是&#xff0c;需要先安装poppler这个软件&#xff0c;具体安装教程放在下面代码中了 2.代码 #poppler安装教程参考&#xff1a;https://blog.csdn.net/wy01415/article/details/110257130 #windows上poppler下载链接&#xff1a…

基于ssm端游账号销售管理系统论文

摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对端游账号销售信息管理混乱&#xff0c;出错率高&#xff0c;信息安全…

乐观锁解决超卖问题

3.6 乐观锁解决超卖问题 修改代码方案一、 VoucherOrderServiceImpl 在扣减库存时&#xff0c;改为&#xff1a; boolean success seckillVoucherService.update().setSql("stock stock -1") //set stock stock -1.eq("voucher_id", voucherId).eq(&q…

31-5 命令执行漏洞 - RCE漏洞利用

环境准备:构建完善的安全渗透测试环境:推荐工具、资源和下载链接_渗透测试靶机下载-CSDN博客 一、打开pikachu靶场 二、远程命令执行利用 正常情况下这一关卡就是个ping命令,我们只能输入个 ip 靶场就就会ping 这ip 但是我们可以用管道符拼接来执行其他命令,详细可以看我…

Flutter 开发学习笔记(1):第一个简单的Flutter项目(上)

文章目录 前言相关链接初始化项目设置键盘映射建议使用AnLink链接物理机。 项目配置日志打印官方案例添加依赖主函数更换添加最简单的按钮Flutter 项目结构Flutter项目入口Flutter的MyApp函数 更新视图直接修改浅拷贝父节点数据思考 修改布局子节点重构子节点布局重构多次扩展布…

Github 2024-04-02Python开源项目日报 Top10

根据Github Trendings的统计,今日(2024-04-02统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目10系统设计指南 创建周期:2507 天开发语言:Python协议类型:OtherStar数量:241693 个Fork数量:42010 次关注人数:241693 人贡献…

Intellij IDEA / Android studio 可持续开发笔记

Intellij 的Java/安卓工具链有着一种不可持续性&#xff0c;这种不可持续性体现在多个方面。 首先是不可持续运行。IDEA 使用时间越长&#xff0c;内存占用越大&#xff0c;从不主动释放。运行时间越长&#xff0c;日志越多&#xff0c;从不主动清理。 然后是不完整的开源&am…

【SQL Server】1. 认识+使用

1. 创建数据库的默认存储路径 C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Microsoft SQL Server 2008 R2 当我们选择删除数据库时&#xff0c;对应路径下的文件也就删除了 2. 导入导出数据工具的路径 3. 注册数据库遇到的问题 ??? 目前的问题就是服务器新建…

【Qt】使用Qt实现Web服务器(九):EventSource+JSON实现工业界面数据刷新

1、效果 效果如下,实时刷新温度、湿度 2、源码 2.1 index.html <html><body> <!-- 页面布局,本人对HTML标签不熟悉,凑合看吧 --> <div><label for

Oracle基础-PL/SQL编程 备份

1、PL/SQL简介 PL/SQL块结构 约定&#xff1a;为了方便&#xff0c;本文后面把PL/SQL简称PL。 PL程序都是以块&#xff08;BLOCK&#xff09;为基本单位&#xff0c;整个PL块分三部分&#xff1a;声明部分&#xff08;使用DECLARE开头&#xff09;、执行部分(以BEGIN开头)和异…

【JavaEE初阶系列】——synchronized原理及优化(偏向锁,轻量级锁,自旋锁,锁消除,锁粗化)

目录 &#x1f6a9;synchronized锁特性详细解说 &#x1f6a9;加锁工作过程(锁升级) &#x1f388;偏向锁 &#x1f388;轻量级锁(自适应的自旋锁) &#x1f388; 重量级锁 &#x1f6a9;其他的优化操作 &#x1f388;锁消除 &#x1f388;锁粗化 &#x1f388;相关面…

JavaScript动态渲染页面爬取——Selenium的使用

JavaScript动态渲染页面爬取 JavaScript动态渲染得页面不止Ajax一种。例如&#xff0c;有些页面的分页部分由JavaScript生成&#xff0c;而非原始HTML代码&#xff0c;这其中并不包含Ajax请求。还有类似淘宝这种页面&#xff0c;即使是Ajax获取的数据&#xff0c;其Ajax接口中…

LeetCode题练习与总结:螺旋矩阵

一、题目描述 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a; 输入&#xff1a;ma…

C#手术麻醉信息系统源码,技术框架:Vue,Ant-Design+百小僧开源框架

C#手术麻醉信息系统源码&#xff0c;技术框架&#xff1a;Vue&#xff0c;Ant-Design百小僧开源框架 手术麻醉系统主要用于在手术过程中监测和控制患者的状态&#xff0c;确保手术的顺利进行并保障患者的生命安全。该系统通过一系列先进的医疗设备和技术&#xff0c;为手术患者…

on-my-zsh 命令自动补全插件 zsh-autosuggestions 安装和配置

首先 Oh My Zsh 是什么? Oh My Zsh 是一款社区驱动的命令行工具&#xff0c;正如它的主页上说的&#xff0c;Oh My Zsh 是一种生活方式。它基于 zsh 命令行&#xff0c;提供了主题配置&#xff0c;插件机制&#xff0c;已经内置的便捷操作。给我们一种全新的方式使用命令行。…