算法概念:
# 一个有限指令集
#接受一些输入(有些情况下不需要输入)
#产生输出
#一定在有限步骤之后终止
#每一条指令必须
#有充分明确的目标,不可以有歧义
#计算机能处理的范围之内
#描述应不依赖于任何一种计算机语言以及具体的实现手段
如下选择排顺序描述:
void SelectionSort (int List[], int N ) { /*将N个整数List[0]。。。List[N-1]进行非递减排序 */ for (i=0; i<N; i++) { Minposition = ScanForMin(List, i ,N-1); /*从List[]到L实体【n-1]中找最小元,并将其位置赋值给MiniPosition*/ Swap( List[i],List[MinPosition] ); /*将未排序部分最小值换到有序部分的最后位置*/ } }
前面讲述的是算法的基础,下面将解决最大子列和问题:
问题描述:给定N个整数的序列{A1,A2,A3,....,An},求函数 f( i , j ) = max{第 i 到 j 的序列和} 的最大值。
#include<stdio.h> #include<stdlib.h> /*----------------------------- ---------最大子列和问题-------- --- 给定N个整数的序列{A1,A2,A3,....,An}, --- 求函数 f( i , j ) = max{第 i 到 j 的序列和} --- 的最大值。 如:[1,2,4,5,-2,4,5,2,1,9,0,3] -------------------------------*/ //算法一书暴力算法,每次需要重头算起,时间复杂度O(N^3) int MaxSubseqSum1(int A[],int N) { int ThisSum,MaxSum=0; int i, j, k; for( i = 0; i < N; i++ ) {/*i是子列左端位置*/ for( j = i; j < N; j++ ){/* j 是子右端的位置*/ ThisSum=0; /* ThisSum是从A[i]到A[j]的子列和*/ for( k = i; k <= j; k++ ) { ThisSum += A[k]; if( ThisSum > MaxSum ) /*如果当前子列和大于已记录的最大子列和则更新记录*/ MaxSum = ThisSum; } } } return MaxSum; } //利用上次算出的i到j的值,直接加上当前值即可,时间复杂度O(N^2) int MaxSubseqSum2(int A[],int N) { int ThisSum,MaxSum=0; int i,j; for( i = 0; i < N; i++ ) {/*i是子列左端位置*/ ThisSum=0; /* ThisSum是从A[i]到A[j]的子列和*/ for( j = i; j < N; j++ ){/* j 是子右端的位置*/ ThisSum += A[j]; if( ThisSum > MaxSum ) /*如果当前子列和大于已记录的最大子列和则更新记录*/ MaxSum = ThisSum; } } return MaxSum; } //分而治之 int MaxSubseqSum3(int A[],int N) { int ThisSum=0,MaxSum=0; int i; for( i = 0; i < N; i++) { ThisSum += A[i]; if( ThisSum > MaxSum ) MaxSum = ThisSum; else if( ThisSum < 0 ) ThisSum = 0; } return MaxSum; } int main(){ int N,A[100000]; int i,t; //输入数组长度 scanf("%d",&N); //输入数据 if( N <= 0 || N > 100000) { printf("Input Array Length Invalid \n "); exit(0); } for(i = 0; i < N ; i++ ){ scanf("%d",&A[i]); } printf("%d",MaxSubseqSum3(A,N)); return 0; }
相关推荐
3.1 分布式文件系统 3.3 HDFS相关概念 3.4 HDFS体系结构 3.5 HDFS存储原理 3.6 HDFS数据读写过程 3.7 HDFS编程实践 3
中国大学MOOC浙江大学数据结构课程(陈越)____数据结构作业(内含所有作业)
大连理工大学数据结构课后习题答案1—4章,课堂上老师布置的题基本都包括了
第1讲 C++语言概述 第2讲 信息的表示与存储 第3讲 程序中数据的表示 第4讲 运算符与表达式 第5讲 顺序结构的程序设计 第6讲 选择结构的程序设计 第7讲 循环结构的程序设计 第8讲 循环结构的设计 第9讲 函数的定义和...
内容介绍:包含该书的2个版本:版本1只有1-9章(带目录完整版)+版本2包含全12章,但目录只有简单的章节号;还包含配套的习题解析+相关讲义/代码/图片(讲义及代码等为下载链接,可自取)。 注:网上目录详细的版本...
中国大学MOOC上浙大的《数据结构》课程第一章线性表顺序存储实现的代码。 包含线性表初始化、输入、输出、插入、查找、删除等函数
第一章 Python环境与操作 3 第二章 数据与表达 3 第三章 基本语句应用 3 第四章 字符串 3 第五章 组合数据类型 6 第六章 输入与输出 6 第七章 控制与结构 9 第八章 函数 6 等
也许对于数据结构的学习涉及的内容比较少,没有动态规划,图论也只是讲了很基础的东西,字符串中KMP弄的过于复杂(对比于acm)。但是瑕不掩瑜,对于绝大部分内容真的讲的超级清楚,完美的图解,就像单步调试一样,也许...
写在前面这里记录着一个跨行菜鸟的成长路程,希望能从一只菜鸟开始,慢慢成长!:-) 如果您对我的努力表示认可或者和我一样也有同样的经历,能不能动下小手点个star、watch或者fork,这是对我最大的鼓励,鞠躬! : ) ...
第一部分 初识Python语言 第1章 程序设计基本方法 第2章 Python程序实例解析 第二部分 深入Python语言 第3章 基本数据类型 第4章 程序的控制结构 第5章 函数和代码复用 第6章 组合数据类型 第7章 文件和数据格式化 ...
《小甲鱼-带你学C带你飞》第一季的一些代码 3.PAT真题: 牛客网:PAT真题练兵场-乙级; PAT甲级真题练习 4.书籍练习题: PTA习题:浙大版《数据结构(第2版)》题目集; 《C++ Primer 5th》课后练习; 5.PTA习题: ...
7-1 计算 11+12+13+…+m (30分) 输入一个正整数m(20<=m<=100),计算 11+12+13+…+m 的值。 输入格式: 在一行输入一个正整数m。 输出格式: 在一行中按照格式“sum = S”输出对应的和S. 输入样例: 在这里给出一...
ARM 体系结构数据类型及堆栈操作实验在第 2 讲的时候,我假设同学们是已经把指令集学完了的,但在 mooc 的课程学习中,我用慕课堂出的讨论题,从很多复制粘贴
中国大学MOOC上浙大的《数据结构》课程第一章线性表链式存储实现的代码。 包链表创建、插入、删除、排序、反序、查找等链表基本操作
熟悉任何语言的基础编程的学生可以跳过此第一门课程 数据结构与算法 算法课程以Java授课。 如果学生需要学习Java,则应首先参加本课程 资料库 单变量微积分 线性代数 多变量微积分 统计与概率 数据科学工具与方法 ...
版的数据结构和算法的个人实现。 我真的很喜欢这个在线 mooc,因为我在台湾的时候就知道了。 感谢Coursera,我可以在线享受这个精彩的算法课程,无需支付任何费用。 我在 2019 年花了很多时间。 在我开始这门课程...
终端统一: 铭飞MCMS支持PC与MOBILE皮肤定制,同时使用MS团队移动JS插件,轻松实现手机多屏幕适配,想想看你发布的信息第一时间在PC上展示又能在手机上展示,这是件多么幸福的事情,数据统一、平台统一、终端统一是MS团队...
主题:数据结构,算法,Java 评论:演讲速度有点太慢,所以我不得不以1.25倍至1.5倍的速度运行以节省时间。 一切都很好地解释了,即使是对于新手来说,这门课程也非常友好。 实际上,我为此签了名只是为了在Java编程...
建立了用于分析前17个HarvardX和MITx课程的方法(Ho等人,HarvardX和MITx:在线公开课程的第一年),然后根据查看,探索和认证的子群体描述了课程注册人人口统计数据。 解决了课程中学生活动的多样性,以及学生与...
建立了用于分析前17个HarvardX和MITx课程的方法(Ho等人,HarvardX和MITx:在线公开课程的第一年),然后根据查看,探索和认证的子群体描述了课程注册人人口统计数据。 解决了课程中学生活动的多样性,以及学生与...