⑴ 那些书籍可以很好练计算机编程的思维
最着名的是高德纳的《计算机编程的艺术》(The Art of Computer Programming,Donald E.Knuth),网络一下看看吧,很容易找的,就算去买一套实体书也很值得,里面对于数学的要求有点高。至少目前看来,这套书很了不起。或者多去有关开发者的网站逛逛,看看别人的言论和经验总结也是不错的路子,比如csdn之类的网站。
忽然想起来,还有本科普名着,是北大中文系翻译的,叫《哥德尔,艾舍尔和巴赫,集异璧之大成》,难度要小太多,里面融合数学,禅宗,音乐,绘画以及计算机科学于一体,对于计算机思维也有很大启示意义。
⑵ 学习java的书籍
1、《深入理解计算机系统》
从c语言到汇编语言到硬件再到操作系统,写得非常好。是一本能帮助深入理解计算机系统的书。基本上把这本书吃透面试操作系统的大部分问题都不是问题。
2、《算法导论(第三版)》
被很多acmer coder奉为学算法的经典之作,但不太适合初学者,因为它这本书很多内容只提供了伪代码,而没有具体实现。但可以从这本书学数据结构和算法好,因为日后的编程语言对实现而言实际上并没有特别大的障碍,只是适合与不适合的选择罢了,而把想法转换成编程语言才是对算法知识的考验。如果不想太过深入的话可以忽略掉第四部分(高级设计和分析技术)第五部分(高级数据结构)和第七部分(算法问题选编),你会发现书其实比你想象中薄很多噢!
3、《计算机网络:自顶向下方法》
软件学院的计算机网络教材,非常适合初学者,里面将计算机网络从顶层到底层逐章分析了一遍,如果能够结合一些实验来辅助理解会更好,因为里面的讲解比较抽象。
4、《STL源码剖析》
如果你是经常用c++刷算法题的同学,那么一定经常用STL的各种集合, vector, set, stack, queue等等。它们的实现原理,在源码面前,完全没有秘密。
5、《图解HTTP》
日本人着的介绍HTTP协 议的书,对理解HTTP协 议的一些细节有非常大的帮助,插画也很多,感觉就像看漫画一样,很容易理解的。
6、《TCP/IP详解卷一》
这本书能把枯燥的知识讲得很细致,强烈推荐这本,看完相应章节后大概能够明白为什么TCP/IP要这么设计了。面试的时候经常问到三次握手和四次挥手,还有各种状态的转移, TIME_WAIT的时间为什么是2*MSL······
7、《UNIX网络编程卷一:套接字联网API(第三版)》
中文版快800页,不过我只看了一些章节,这本书也是把TCP/IP的细节讲得很深很深,此外还有非常重要的基本套接字编程,就是写网络程序的时候那些bind, accept, listen, send, receive函数之类的,内容非常多,但是这些是理解多路复用模型所需要掌握的······select/poll/epoll这些系统调用解决了什么问题?事件机制能不能理解?就看这本书的前六章了。
⑶ 计算机科学与技术,大二了,我该学些什么呢,现在只会写几行代码
我不是大神,事实上我还是大一呢。我已经学了C,正在学C++,我也是一头雾水。再好多看些相关书籍。我给你推荐些。我只看了一点就受益无穷。求采纳。
计算机经典教材
目录
1 前言
2 Mathematics (数学)
3 Data Structures & Algorithms (数据结构、算法)
4 Compiler (编译原理)
5 Operating System (操作系统)
6 Database (数据库)
7 C (C 语言)
8 C++ (C++ 语言)
9 Object-Oriented (面向对象)
10 Software Engineering (软件工程)
11 UNIX Programming (UNIX编程)
12 UNIX Administration (UNIX系统管理)
13 Networks (网络)
14 Windows Programming (Windows 编程)
15 Other (其它)
前言
推荐原则:
宁缺勿滥,决不混进糟粕 (好书不一定对所有人都合适,但对于它的目标读者群来说,一定是好书)。
选书原则:
有国外的,不看国产的
有原版的,不看翻译的
看大师的作品
看书原则:
不要看C、C++、java……今天听说C好,就跑去学C。明天听说java好,就跑去学java,最后你什么也学不到。因为不管什么语言,永远不要忘记语言的本质。语言只是一种工具,它的作用就是完成你的工作。不管把
C 的语法学得如何透彻,也不管把 C 的
trick用的如何精妙,这都不能表示你会编程。要学会如何分析问题,如何设计程序,如何用一种具体的语言来实现。如果你只会做最后一步,你只是一个编码者(coder),还不是一个程序员(programmer)。做一个programmer,不要做coder。总之,不要为了学语言而去学语言(除非你是个语言学家)。
不要放弃对基础知识的学习。所谓基础知识,一般都有一个特点,那就是:它们可能看起来没用,但如果你忽视它们的话,总有一天你会后悔莫及。所以,如果不想以后再后悔的话,就在今天多花点时间。
不管学什么东西,学之前先弄明白自己要学的是什么东西,它有什么用,在你已经学和以后的发展方向中,它处于什么位值。如果这些都不明白,就好比在茫茫的丛林里面四处乱撞,就算能出去,也一定会走很多弯路。
对于软件工程之类的东西,不象 C
语言有着严格的标准,最好的办法就是兼收并蓄,能看的都看,然后(最重要的)在此之上形成自己的思想(不然就什么都白看了)。
尽信书不如无书。书里写的只不过是写书的人认为正确的观点而已。学习前人的知识和经验,在此基础上形成自己的知识结构、观点和思维方式,才是学习的真正目的。
一。Mathematics (数学)
书名(英文):Discrete Mathematics and Its Applications (Fifth Edition)
书名(中文):离散数学及其应用 (第五版)
原作者:Kenneth H.Rosen
书名(英文):Concrete Mathematics : A Foundation for Computer Science
(Second Edition)
书名(中文):具体数学:计算机科学基础 (第2版)
原作者:Ronald L. Graham / Donald E. Knuth / Oren Patashnik
二。Data Structures & Algorithms (数据结构、算法)
书名(英文):Data Structures and Algorithm Analysis in C, Second Edition
书名(中文):数据结构与算法分析--C语言描述 (第二版)
原作者:Mark Allen Weiss
大凡国外的数据结构教科书,都有一个共同的特点,就是他们的第一章都不是讲的数据结构,而是软件工程的基本原则。我个人认为这是十分必要的,特别是对于大
多数没有接触过程序设计的同学来说,在数据结构这个可以说是第一次接触程序设计的课程中能学习到基本的软件工程原则,对于以后的学习是十分有好处的。写一
个乱七八糟的程序出来还不如什么都不写。在我看来,这本书有两个优点:一:将软件工程的基本原则贯穿全书,二:简单,容易理解。对于初学者,这本书无疑是
非常合适的。mufasa
书名(英文):Data Structures & Program Design In C (Second Edition)
书名(中文):数据结构与程序设计 C 语言描述 (第二版)
原作者:Robert Kruse / C.L. Tondo / Bruce Leung
书名(英文):Data Structures with C++ Using STL (Second Edition)
书名(中文):数据结构C++语言描述描述—应用标准模版库 (第二版)
原作者:William Ford, William Topp
书名(英文):Introction to Algorithms (Second Edition)
书名(中文):算法导论 (第二版)
原作者:Thomas H. Cormen / Charles E. Leiserson / Ronald L. Rivest /
Clifford Stein
书名(英文):The Art of Computer Programming, Volume 1 : Fundamental
Algorithms (Third Edition)
书名(中文):计算机程序设计艺术 第1卷 基本算法 (第3版)
原作者:Donald E. Knuth
书名(英文):The Art of Computer Programming, Volume 2 : Seminumerical
Algorithms (Third Edition)
书名(中文):计算机程序设计艺术 第2卷 半数值算法 (第3版)
原作者:Donald E. Knuth
书名(英文):The Art of Computer Programming, Volume 3 : Sorting and
Searching (Second Edition)
书名(中文):计算机程序设计艺术 第3卷 排序和查找 (第2版)
原作者:Donald E. Knuth
三。Compiler (编译原理)
书名(英文):Compilers: Principles, Techniques, and Tools
书名(中文):编译原理、技术与工具
原作者:Alfred V. Aho / Ravi Sethi / Jeffrey D. Ullman
书名(英文):Advanced Compiler Design and Implementation
书名(中文):高级编译器设计与实现
原作者:Steven S. Muchnic
书名(英文):Modern Compiler Implementation in C
书名(中文):现代编译原理--C语言描述
原作者:Andrew W.Appel / Maia Ginsburg
四。Operating System (操作系统)
书名(英文):Operating System Concepts (Sixth Edition)
书名(中文):操作系统概念 (第六版)
原作者:Abraham Silberschatz / Peter Baer Galvin / Greg Gagne
书名(英文):Operating Systems : Design and Implementation (Second
Edition)
书名(中文):操作系统:设计及实现 (第二版)
原作者:Andrew S. Tanenbaum / Albert S. Woodhull
翻译者:王鹏、尤晋元、朱鹏、敖青云
书名(英文):The Design and Implementation of the 4.4BSD Operating System
书名(中文):4.4BSD操作系统设计与实现
原作者:Marshall Kirk McKusick / Keith Bostic / Michael J. Karels / John
S.Quarterman
书名(英文):The Design and Implementation of the FreeBSD Operating System
书名(中文):FreeBSD操作系统设计与实现
原作者:Marshall Kirk McKusick / George V. Neville-Neil
翻译者:张辉
书名(英文):The Design of The UNIX Operating System
书名(中文):UNIX操作系统设计
原作者:Maurice J.Bach
书名(英文):UNIX Internals : The New Frontiers
书名(中文):UNIX系统内幕
原作者:Uresh Vahalia
书名(英文):UNIX Systems for Modern Architectures
书名(中文):现代体系结构上的UNIX系统--内核程序员的SMP和Caching技术
原作者:Curt Schimmel
翻译者:张辉
书名(英文):Lions' Commentary on UNIX 6th Edition with Source Code
书名(中文):莱昂氏UNIX源代码分析
原作者:John Lions
书名(英文):Distributed Systems : Principles and Paradigms
书名(中文):分布式系统:原理与范例
原作者:Andrew S.Tanenbaum / Maarten van Steen
五.Database (数据库)
书名(英文):An Introction to Database Systems, Eighth Edition
书名(中文):数据库系统导论 (第八版)
原作者:C. J.Date
书名(英文):Database System Concepts, Fourth Edition
书名(中文):数据库系统概念 (第四版)
原作者:Abraham Silberschat / Henry F.Korth / S.Sudarshan
六。C (C 语
书名(英文):The C Programming Language, Second Edition
书名(中文):C程序设计语言,第二版
原作者:Brian W. Kernighan / Dennis Ritchie
书名(英文):The Art and Science of C : A Library-Based Introction to
Computer Science
书名(中文):C语言的科学和艺术
原作者:Eric S.Roberts
书名(英文):Programming Abstractions in C : A Second Course in Computer
Science
书名(中文):C程序设计的抽象思维
原作者:Eric S.Roberts
书名(英文):Expert C Programming
书名(中文):C专家编程
原作者:Andrew Koenig
书名(英文):C Traps and Pitfalls
书名(中文):C陷阱与缺陷
原作者:Andrew Koenig
七。C++ (C++ 语言)
书名(英文):C++ Primer, Third Edition & Forth Edition
书名(中文):C++ Primer (第三版、第四版)
原作者:Stanley B.Lippman / Josée LaJoie / Barbara E.Moo
翻译者:李师贤、蒋爱军、梅晓勇、林瑛
平心而论,这本书的第三版并不适合入门,但是第四版适合。所以第四版的出现并不意味着第三版就失去了其价值。在我看来最好的办法就是买一本第四版的中文版和一本第三版的英文版。中文版用来入门,英文版用来作参考手册。mufasa
书名(英文):The C++ Programming Language, Special Edition
书名(中文):C++ 程序设计语言 (特别版)
原作者:Bjarne Stroustrup
书名(英文):Inside the C++ Object Model
书名(中文):深度探索 C++ 对象模型
原作者:Stanley B. Lippman
书名(英文):Effective C++, Thrid Edition
书名(中文):Effective C++ (第三版)
原作者:Scott Meyers
书名(英文):More Effective C++
书名(中文):More Effective C++
原作者:Scott Meyers
翻译者:侯捷
书名(英文):Thinking in C++, Second Edition
书名(中文):C++编程思想 (第二版)
原作者:Bruce Eckel
书名(英文):Thinking in C++, Volume 2 : Practical Programming
书名(中文):C++编程思想 第2卷:实用编程技术
原作者:Bruce Eckel / Chuck Alison
书名(英文):Ruminations on C++ : A Decade of Programming Insight and
Experience
书名(中文):C++沉思录
原作者:Andrew Koenig / Barbara Moo
八。Object-Oriented (面向对象)
书名(英文):Object-Oriented Analysis and Design with Applications, Second
Edition
书名(中文):面向对象分析与设计 (第二版)
原作者:Grady Booch
书名(英文):Object-Oriented Modeling and Design with UML,Second Edition
书名(中文):UML面向对象建模与设计 (第二版)
原作者:Michael Blaha / James Rumbaugh
翻译者:车皓阳、杨眉
书名(英文):Object-Oriented Software Construction (Second Edition)
书名(中文):面向对象软件构造 (第二版)
原作者:Bertrand Meyer
书名(英文):Design Patterns : Elements of Reusable Object-Oriented
Software
书名(中文):设计模式:可复用面向对象软件的基础
原作者:Erich Gamma / Richard Helm / Ralph Johnson / John Vlissides
九。Software Engineering (软件工程)
书名(英文):Software Engineering (7th Edition)
书名(中文):软件工程 (第七版)
原作者:Ian Sommerville
书名(英文):Software Engineering : A Practitioner's Approach (Fifth
Edition)
书名(中文):软件工程:实践者之路 (第5版)
原作者:Roger S. Pressman
书名(英文):Software Engineering : Theory and Practice (Second Edition)
书名(中文):软件工程:理论与实践 (第二版)
原作者:Shari Lawrence Pfleeger
书名(英文):The Mythical Man-Month
书名(中文):人月神话
原作者:Frederick Phillips Brooks
书名(英文):Software Architecture : Perspectives On an Emerging Emerging
Discipline
书名(中文):软件体系结构:一门初露端倪学科的展望
原作者:Mary Shaw / David Garlan
十。UNIX Programming (UNIX编程)
书名(英文):Advanced Programming in the UNIX Environment, Second Edition
书名(中文):UNIX 环境高级编程 (第二版)
原作者:W.Richard Stevens / Stephen A.Rago
翻译者:尤晋元、张亚英、戚正伟
书名(英文):The UNIX Programming Environment
书名(中文):UNIX 编程环境
原作者:Brianw. Kernighan
书名(英文):UNIX Network Programming, Volume 1 : The Sockets Networking
API (Third Edition)
书名(中文):UNIX 网络编程 卷1:套接字联网API (第三版)
原作者:W. Richard Stevens / Bill Fenner / Andrew M. Rudoff
书名(英文):UNIX Network Programming Volume 2 : Interprocess
Communications (Second Edition)
书名(中文):UNIX 网络编程 卷2:进程间通信 (第2版)
原作者:W. Richard Stevens
书名(英文):The Art of UNIX Programming
书名(中文):UNIX 程序设计艺术
原作者:Eric Raymond
UNIX Administration (UNIX系统管理)
书名(英文):UNIX System Administration Handbook (Third Edition)
书名(中文):UNIX系统管理技术手册 (第三版)
原作者:Evi Nemeth / Garth Snyder
书名(英文):Linux Administration Handbook
书名(中文):Linux系统管理技术手册
原作者:Evi Nemeth / Garth Snyder / Trent R.Hein
书名(英文):UNIX Unleashed (Fourth Edition)
书名(中文):UNIX 技术内幕 (第四版)
原作者:Robin Anderson / Andy Johnston
书名(英文):UNIX:The Textbook
书名(中文):UNIX操作系统教程
原作者:Syed Mansoor Sarwar / Robert Koretsky / Syed Aqeel Sarwar
书名(英文):Unix Backup & Recovery
书名(中文):UNIX 备份与恢复
原作者:W.Curtis Preston
十一。Networks (网络)
书名(英文):Computer Networks (Fourth Edition)
书名(中文):计算机网络 (第4版)
原作者:Andrew S. Tanenbaum
书名(英文):TCP/IP Illustrated, Volume 1 : The Protocols
书名(中文):TCP/IP 详解 卷1:协议
原作者:W. Richard Stevens
书名(英文):TCP/IP Illustrated, Volume 2 : The Implementation
书名(中文):TCP/IP详解 卷2:实现
原作者:Gary R. Wright / W. Richard Stevens
书名(英文):TCP/IP Illstrated, Volume 3 : TCP for Transactions, HTTP,
NNTP, and the UNIX Domain Protocols
书名(中文):TCP/IP详解 卷3:TCP事务协议、HTTP、NNTP和UNIX域协议
原作者:W. Richard Stevens
书名(英文):Internetworking with TCP/IP Vol I : Principles, Protocols,
and Architecture (Third Edition)
书名(中文):TCP/IP 网络互连技术 卷1:原理、协议和体系结构 (第3版)
原作者:Douglas E. Comer
书名(英文):Internetworking with TCP/IP Vol II : Design, Implementation,
and Internals (Second Edition)
书名(中文):TCP/IP 网络互连技术 卷2:设计与实现 (第2版)
原作者:Douglas E. Comer / David L. Stevens
书名(英文):Internetworking with TCP/IP Vol III : Client-Server
Programming and Applications, BSD Socket Version (Second Edition)
书名(中文):TCP/IP 网络互连技术 卷3:客户服务器编程和应用BSD套接字版 (第2版)
原作者:Douglas E. Comer / David L. Stevens
书名(英文):Internetworking with TCP/IP Vol III : Client-Server
Programming and Applications, Windows Sockets Version
书名(中文):TCP/IP 网络互连技术 卷3:客户服务器编程和应用Windows套接字版
原作者:Douglas E. Comer / David L. Stevens
十二。Windows Programming (Windows 编程)
书名(英文):Inside Microsoft Windows 2000 (Third Edition)
书名(中文):Microsoft Windows 2000 技术内幕 (第3版)
原作者:David A.solomon Mark E.Russinovich
书名(英文):Programming Windows (Fifth Edition)
书名(中文):Windows 编程 (第5版)
原作者:Charles Petzold
书名(英文):Programming Applications for Microsoft Windows
书名(中文):Microsoft Windows 应用程序设计
原作者:Jeffrey Richter
书名(英文):Programming with Microsoft Visual C++ .NET (Sixth Edition)
书名(中文):Visual C++.NET 技术内幕 (第6版)
原作者:George Shepherd / David Kruglinski
书名(英文):Dissecting MFC
书名(中文):深入浅出MFC
原作者:侯捷
十三。Other (其它)
书名(英文):Computer Systems : A programmer' s Perspective
书名(中文):计算机系统
原作者:Randal E. Bryant / David R. O'Hallaron
书名(英文):Pattern Classification (Second Edition)
书名(中文):模式分类 (第2版)
原作者:Richard O. Duda / Peter E. Hart / David G. Stork
书名(英文):Code Complete 2
书名(中文):代码大全第2版
原作者: Steve McConnell
书名(英文):Programming Pearls (2nd Edition)
书名(中文):编程珠玑第2版
原作者: Jon Bentley
别人给我推荐的,我只看过一两本。
⑷ Adroid Studio 提示Error:(2) Error retrieving parent for item: No resource found that matches
《C Primer Plus》《Head First Java》
⑸ 求C++ 网络编程最好的书籍 谢谢了
学习编程基础也很重要的,路要一步一步地走。不要老是想到看一本书就成为高手。我给你推荐一些书吧,你可以选一些看。其中很多都是经典之作。C++是以C为基础的,所以你最好看一下C语言,网络方面,《计算机网络》和《TCP/IP详解》是必看的。望采纳。
1、算法
计算机程序设计艺术-------Donald.E.Knuth----------算法“倚天屠龙”双剑
算法导论-----------------Thomas H. Cormen--------算法“倚天屠龙”双剑
离散数学及其应用----------Kenneth H.Rosen
具体数学—计算机科学基础--------Donald.E.Knuth
2、数据结构
数据结构 C++
数据结构算法与应用
3、C语言
C程序设计语言(第2版·新版)---C语言“倚天屠龙双剑”---Brian W.Kernighan“C语言之父”
C Primer Plus中文版(第五版)--------C语言“倚天屠龙双剑”---Stephen Prata
C程序设计(第三版)---------------------------谭浩强
C语言大全(第四版)---------------------------HERBERT SCHILDT
C语言接口与实现:创建可重用软件的技术-------------DAVID R.HANSON
C语言参考手册(原书第5版)--------------------------Samuel P.Harbison
C程序设计教程---------------------------------H.M.Deitel/P.J.Deitel
C陷阱与缺陷-----------------------------------Andrew Koenig
5、C++
C++程序设计语言(特别版)---c++八大金刚----Bjarne Stroustrup“C++之父”
C++ Primer (第3版)中文版----c++八大金刚---Stanley B.Lippman
C++ Primer (第4版)中文版----c++八大金刚---Stanley B.Lippman
C++标准程序库—自修教程与参考手册--c++八大金刚--Nicolai M.Josuttis
C++语言的设计和演化-----c++八大金刚----Bjarne Stroustrup“C++之父”
深度探索C++对象模型---c++八大金刚----Stanley B.Lippman
Essential C++中文版---c++八大金刚---Stanley B.Lippman
Effective C++中文版 2nd Edition-----c++八大金刚------Scott Meyers
More Effective C++中文版----c++八大金刚------Scott Meyers
C++编程思想(第2版) 第1卷:标准C++导引--------Bruce Eckel
C++编程思想(第2版)第2卷:实用编程技术 --------Bruce Eckel
C++程序设计--------------------------谭浩强
C++ 程序设计教程(第2版)--------------钱能
C++ Primer Plus(第五版)中文版---Stephen Prata
6、操作系统
深入理解计算机系统(修订版)-------RANDAL E.BRYANT
计算机操作系统(第六版)
7、编译原理
跟我一起写makefile
《编译原理技术和工具》------- Alfred ------- 龙书
《现代编译原理-C语言描述》 ----------- Andrew W. Appel ----------- 虎书
《高级编译器设计与实现》 ----------- Steven S.Muchnick ----------- 鲸书
8、网络
计算机网络第四版中文版-----------Andrew S.Tanenbaum -------网络编程三剑客
TCP/IP详解3卷本--------------------Richard Stevens----网络编程三剑客
UNIX网络编程2卷本--------------------Richard Stevens----网络编程三剑客
用TCP/IP进行网际互联-----------Douglas E. Comer
高级TCP/IP编程-------------------Jon C. Snader
C++网络编程-----------------------Douglas Schmidt
UNIX环境高级编程(第2版)--------------------Richard Stevens
9、Linux
Linux内核设计与实现
Linux内核完全注释
LINUX内核分析及编程
⑹ C语言如何从大到小排序呢
给你提供几个比较简单的算法思路。
首先纠正一下,你要排序的对象不要存在单个变量里,要存在数组里,这样才能用循环的方式取用。
插入排序
如果你打过牌,这种排序你就一定能理解。从未排序的部分取出一个元素来,然后插入到已经排好序的部分。就这样一个一个的查入。
2.选择排序
从未排序的部分选出最大(最小)的一个放在已排好序的部分的最后。然后重复此步骤。
3.归并排序
排一个很长的序列可能比较麻烦,我就把他们分成两份,把他们分别排好,然后再把他们接起来,接起来就很简单了。而这两个怎么排呢,我再把他们分别分成两个……这就要用到递归了。
总结一下,前两个时间复杂度是平方,后一个是n*logn 。还有很多其他排序方法,其中冒泡排序比较费时但是很好写,如果你不是想知其所以然,直接网络冒泡套用一下就行。
如果想系统的学习算法,推荐你读算法导论,就是那本很厚的。讲的很好。
⑺ 如何从零开始学编程
在你学习编程之前思考一下你的目标,当你有最终目标时道路会更加的清晰。那么,你想要写什么?网站?游戏?iOS或者Android应用?或是你是想自动化完成一些乏味的任务让你有更多的时间看窗外的风景?也许你只是想更具有就业竞争力找个好工作。所有的这些都是有价值的目标,这些目标都是你编程学习推动力的一部分,没有推动力的人,是无法在略显枯燥的漫长学习之旅中走远的。
不要浮躁
Badprogrammingiseasy.EvenDummiescanlearnitin21days.,meswithit.
不管是在线下还是线上的书店,满目都是《21天学通Java》这种速成书目,它们都承诺在很短一段时间内就让你能够学会相关技术。MatthiasFelleisen在他的着作HowtoDesignPrograms,SecondEdition一书中明确指出了这种“速成”的趋势并予以了以上的讽刺。
所谓的“捷径”或者说“银弹”是不存在的,智者说过,精通某个东西需要10年或10000个小时,也就是汉语中的“十年磨一剑”,所以不用着急,功不唐捐。
培养兴趣
ionbythepublic,butbecauseitisfuntoprogram.
_LinusTorvalds
沉醉于编程,编程更是为了兴趣。兴趣是推动力的不竭源泉,保持这种充满兴趣的感觉,以便于你能将其投入到你的10年/10000小时的编程时间中。编程很有趣,那是探索的喜悦。那是创造的喜悦。看到自己亲手完成的作品显示在屏幕上很有趣。有人为你的代码而惊叹很有趣。有人在公共场合称赞你的产品、邻居使用你的产品、以及在媒体上讨论你的产品很有趣。编程应该十分有趣,若并非如此,就找出导致编程无趣的问题,然后解决之。
在这里对于初学者有两个大坑:
如果初学者们只与预先构建好的“发动机和组件”接触(没有理解和思考它们构造的原理),这会严重限制他们在将来构建这些东西的能力,并且在诊断解决问题时无从下手。
第二个坑没有第一个那么明显:幼稚的“整体论”方法有些时候会显得很有效,这有一定的隐蔽性与误导性,但是一两年过后(也许没那么长),当你在学习路上走远时,再想回过头来“补足基础”会有巨大的心理障碍,你得抛弃之前自己狭隘的观念,耐心地缓步前进,这比你初学时学习基础知识困难得多。
但腊敏茄也不能矫枉过正,陷入还原论的大坑,初学时便一心试图做宏大的理论,这样不仅有一切流于理论的危险,枯燥和乏味还会让你失去推动力。这种情况经常发生在计算机科班生身上。
为了更好理解,可以将学习编程类比为学习厨艺:你为了烧得一手好菜买了一些关于菜谱的书,如果你只是想为家人做菜,这会是一个不错的主意,你重复菜谱上的步骤也能做出不赖的菜肴,但是如果你有更大的野心,真的想在朋友面前露一手,做一些独一无二的美味佳肴,甚至成为“大厨”,你必须理解这些菜谱背后大师的想法,理解其中的理论,而不仅仅是一味地实践。但拿猛是如果你每天唯一的工作就是阅读那些厚重的理论书籍,因为缺乏实践,你只会成为一个糟糕的厨子,甚至永远成为不了厨子,因为看了几天书后你就因为枯燥放弃了厨艺的学习。
总之,编程是连接理论与实践的纽带,是计算机科学与计算机应用技术相交融的领域。正确的编程学习方法应该是:通过自顶而下的探索与项目实践,获得编程直觉与推动力;从自底向上的打基础过程中,获得最重要的通用方法并巩固编程思想的理解。
作为初学者,应以后者为主,前者为轮察辅。
启蒙
“学编程应该学哪门语言?”这经常是初学者问的第一个问题,但这是一个错误的问题,你最先考虑的问题应该是“哪些东西构成了编程学习的基础”?
编程知识的金字塔底部有三个关键的部分:
算法思想:例如怎样找出一组数中最大的那个数?首先你得有一个maxSoFar变量,之后对于每个数
语法:我怎样用某种编程语言表达这些算法,让计算机能够理解。
系统基础:为什么while(1)时线程永远无法结束?为什么int*foo(){intx=0;return&x;}是不可行的?
启蒙阶段的初学者若选择C语言作为第一门语言会很困难并且枯燥,这是因为他们被迫要同时学习这三个部分,在能做出东西前要花费很多时间。
因此,为了尽量最小化“语法”与“系统基础”这两部分,建议使用python作为学习的第一门语言,虽然Python对初学者很友好,但这并不意味着它只是一个“玩具”,在大型项目中你也能见到它强大而灵活的身影。熟悉Python后,学习C语言是便是一个不错的选择了:学习C语言会帮助你以靠近底层的视角思考问题,并且在后期帮助你理解操作系统层级的一些原理,如果你只想成为一个普通(平庸)的开发者你可以不学习它。
下面给出了一个可供参考的启蒙阶段导引,完成后你会在头脑中构建起一个整体框架,帮助你进行自顶向下的探索。
完成Codecademy的Python部分。这只是热身部分,尽快完成它,因为你永远只是在浏览器里,你不会学到如何搭建开发环境。在Codecademy这类的编程学习网站学到的那点儿东西,哪怕你只想做一个小的不能再小的项目,你都不知道该从哪儿开始。
完成MIT6.00.1x(中文化)(如果你英语不过关,完成麻省理工学院公开课:计算机科学及编程导论。MOOC是学习编程的一个有效途径。虽然该课程的教学语言为Python,但作为一门优秀的导论课,它强调学习计算机科学领域里的重要概念和范式,而不仅仅是教你特定的语言。如果你不是科班生,这能让你在自学时开阔眼界;课程内容:计算概念,python编程语言,一些简单的数据结构与算法,测试与调试。支线任务:
完成Python核心编程
完成HarvardCS50(如果你英语不过关:完成哈佛大学公开课:计算机科学cs50。同样是导论课,但这门课与MIT的导论课互补。教学语言涉及C,php,JavaScript+SQL,HTML+CSS,内容的广度与深度十分合理,还能够了解到最新的一些科技成果,可以很好激发学习计算机的兴趣。支线任务:
阅读《编码的奥秘》
完成《C语言编程》
[可选]如果你的目标是成为一名Hacker:阅读Hacker'sDelight
PS:如果教育对象还是一个孩子,以下的资源会很有帮助:
5-8岁:TurtleAcademy
8-12岁:PythonforKids
12岁以上:MITScratch或KhanAcademy
入门
结束启蒙阶段后,初学者积累了一定的代码量,对编程也有了一定的了解。这时你可能想去学一门具体的技术,诸如Web开发,Android开发,iOS开发什么的,你可以去尝试做一些尽可能简单的东西,给自己一些正反馈,补充自己的推动力。但记住别深入,这些技术有无数的细节,将来会有时间去学习;同样的,这时候也别过于深入特定的框架和语言,现在是学习计算机科学通用基础知识的时候,不要试图去抄近路直接学你现在想学的东西,这是注定会失败的。
那么入门阶段具体该做些什么呢?这时候你需要做的是反思自己曾经写过的程序,去思考程序为什么(Why)要这样设计?,思考怎样(How)写出更好的程序?试图去探寻理解编程的本质:利用计算机解决问题。
设想:
X=用于思考解决方案的时间,即“解决问题”部分
Y=用于实现代码的时间,即“利用计算机”部分”
编程能力=F(X,Y)(X>Y)
要想提高编程能力,就得优化X,Y与函数F(X,Y),很少有书的内容能同时着重集中在这三点上,但有一本书做到了——(SICP)《计算机程序的构造和解释》,它为你指明了这三个变量的方向。在阅读SICP之前,你也许能通过调用几个函数解决一个简单问题。但阅读完SICP之后,你会学会如何将问题抽象并且分解,从而处理更复杂更庞大的问题,这是编程能力巨大的飞跃,这会在本质上改变你思考问题以及用代码解决问题的方式。此外,SICP的教学语言为Scheme,可以让你初步了解函数式编程。更重要的是,他的语法十分简单,你可以很快学会它,从而把更多的时间用于学习书中的编程思想以及复杂问题的解决之道上。
PeterNorvig曾经写过一篇非常精彩的SICP书评,其中有这样一段:
Touseananalogy,ifSICPwereaboutautomobiles,,howtheyarebuilt,andhowonemightdesignfuel-efficient,safe,.highway,justlikeeveryoneelse.
如果你是文中的前者,阅读SICP将成为你衔接启蒙与入门阶段的关键点
虽然SICP是一本“入门书”,但对于初学者还是有一定的难度,以下是一些十分有用的辅助资源:
):由上文提到的Google研究主管PeterNorvig主讲,教学语言为Python,内容有一定难度。
HowtoDesignPrograms,SecondEdition:HtDP的起点比SICP低,书中的内容循循善诱,对初学者很友好,如果觉得完成SICP过于困难,可以考虑先读一读HtDP。
UCBerkeleySICP授课视频以及SICP的两位作者给Hewlett-Packard公司员工培训时的录像(中文化项目)
ComposingPrograms:一个继承了SICP思想但使用Python作为教学语言的编程导论(其中包含了一些小项目)
SICP解题集:对于书后的习题,作为初学者应尽力并量力完成。
完成了这部分学习后,你会逐步建立起一个自己的程序设计模型,你的脑子里不再是一团乱麻,你会意识到记住库和语法并不会教你如何解决编程问题,接下来要学些什么,在你心里也会明朗了很多。这时候才是真正开始进行项目实践,补充推动力的好时机。
关于项目实践:对于入门阶段的初学者,参与开源项目还为时过早,这时候应该开始一些简单的项目,诸如搭建一个网站并维护它,或是编写一个小游戏再不断进行扩展,如果你自己的想法不明确,MegaProjectList中选取项目。总之,务必在这时拿下你项目实践的第一滴血。
与此同时,别忘了继续打好根基。为了将来的厚积薄发,在下面这几个方面你还要继续做足功课(注意:下面的内容没有绝对意义上的先后顺序):
计算机系统基础
有了之前程序设计的基础后,想更加深入地把握计算机科学的脉络,不妨看看这本书:《深入理解计算机系统》ComputerSystemsAProgrammer'sPerspective。这里点名批评这本书的中译名,其实根本谈不上什么深入啦,这本书只是CMU的“计算机系统导论”的教材而已。CMU的计算机科学专业相对较偏软件,该书就是从一个程序员的视角观察计算机系统,以“程序在计算机中如何执行”为主线,全面阐述计算机系统内部实现的诸多细节。
如果你看书觉得有些枯燥的话,可以跟一门Coursera上的MOOC:TheHardware/SoftwareInterface,这门课的内容是CSAPP的一个子集,但是最经典的实验部分都移植过来了。同时,可以看看TheCProgrammingLanguage,回顾一下C语言的知识。
完成这本书后,你会具备坚实的系统基础,也具有了学习操作系统,编译器,计算机网络等内容的先决条件。当学习更高级的系统内容时,翻阅一下此书的相应章节,同时编程实现其中的例子,一定会对书本上的理论具有更加感性的认识,真正做到经手的代码,从上层设计到底层实现都了然于胸,并能在脑中回放数据在网络->内存->缓存->CPU的流向。
此外,也是时候去接触UNIX哲学了:KISS-KeepitSimple,Stupid.在实践中,这意味着你要开始熟悉命令行界面,配置文件。并且在开发中逐渐脱离之前使用的IDE,学会使用Vim或Emacs(或者最好两者都去尝试)。
阅读《UNIX编程环境》
阅读《UNIX编程艺术》
折腾你的UN*X系统
数据结构与算法基础
如今,很多人认为编程(特别是做web开发)的主要部分就是使用别人的代码,能够用清晰简明的方式表达自己的想法比掌握硬核的数学与算法技巧重要的多,数据结构排序函数二分搜索这不都内置了吗?工作中永远用不到,学算法有啥用啊?这种扛着实用主义大旗的“码农”思想当然不可取。没有扎实的理论背景,遭遇瓶颈是迟早的事。
数据结构和算法是配套的,入门阶段你应该掌握的主要内容应该是:这个问题用什么算法和数据结构能更快解决。这就要求你对常见的数据结构和算法了熟于心,你不一定要敲代码,用纸手写流程是更快的方式。对你不懂的数据结构和算法,你要去搜它主要拿来干嘛的,使用场景是什么。
供你参考的学习资源:
《算法导论》:有人说别把这本书当入门书,这本书本来就不是入门书嘛,虽说书名是IntroctiontoAlgorithms,这只不过是因为作者不想把这本书与其他书搞重名罢了。当然,也不是没办法拿此书入门,读第一遍的时候跳过习题和证明就行了嘛,如果还觉得心虚先看看这本《数据结构与算法分析》
CourseraAlgorithms:DesignandAnalysis[Part1]&[Part2]:Stanford开的算法课,不限定语言,两个部分跟下来算法基础基本就有了;英语没过关的:麻省理工学院公开课:算法导论
入门阶段还要注意培养使用常规算法解决小规模问题的能力,结合前文的SICP部分可以读读这几本书:《编程珠玑》,《程序设计实践》
编程语言基础
.,.Additionally,,
-ThePragmaticProgrammer
此外还要知道,学习第n门编程语言的难度是第(n-1)门的一半,所以尽量去尝试不同的编程语言与编程范式,若你跟寻了前文的指引,你已经接触了:“干净”的脚本语言Python,传统的命令式语言C,以及浪漫的函数式语言Scheme/Racket三个好朋友。但仅仅是接触远远不够,你还需要不断继续加深与他们的友谊,并尝试结交新朋友,美而雅的Ruby小姑娘,Hindley-Milner语言家族的掌中宝Haskell都是不错的选择。但有这么一位你躲不开的,必须得认识的大伙伴—C++,你得做好与他深交的准备:
入门:C++Primer
[可选]进阶:
高效使用:EffectiveC++
深入了解:《深度探索C++对象模型》;C++Templates
研究反思:TheDesignandEvolutionofC++;对于C++这个NecessaryEvil,看这本书可以让你选择是成为守夜人还是守日人。
现实是残酷的,在软件工程领域仍旧充斥着一些狂热者,他们只掌握着一种编程语言,也只想掌握一种语言,他们认为自己掌握的这门语言是最好的,其他异端都是傻X。这种人也不是无药可救,有一种很简单的治疗方法:让他们写一个编译器。要想真正理解编程语言,你必须亲自实现一个。现在是入门阶段,不要求你去上一门编译器课程,但要求你能至少实现一个简单的解释器。
供你参考的学习资源:
《程序设计语言-实践之路》:CMU编程语言原理的教材,程序语言入门书,现在就可以看,会极大扩展你的眼界,拉开你与普通人的差距。
Coursera编程语言MOOC:课堂上你能接触到极端FP(函数式)的SML,中性偏FP的Racket,以及极端OOP(面向对象)的Ruby,并学会问题的FP分解vsOOP分解、ML的模式匹配、Lisp宏、不变性与可变性、解释器的实现原理等,让你在将来学习新语言时更加轻松并写出更好的程序。
:热热身,教你写一个简单的浏览器——其实就是一个javascript和html的解释器,完成后的成品还是很有趣的;接下来,试着完成一个之前在SICP部分提到过的项目:用Python写一个SchemeInterpreter
其他
编程入门阶段比较容易忽视的几点:
学好英语:英语是你获取高质量学习资源的主要工具,但在入门阶段,所看的那些翻译书信息损耗也没那么严重,以你自己情况权衡吧。此外英语的重要性更体现在沟通交流上,LinusTorvalds一个芬兰人,一口流利的英语一直是他招募开发者为Linux干活的的法宝,这是你的榜样。
学会提问:学习中肯定会遇到问题,首先应该学会搜索引擎的“高级搜索”,当单靠检索无法解决问题时,去StackOverflow或知乎提问,提问前读读这篇文章:Whathaveyoutried?
不要做一匹独狼:尝试搭建一个像这样简单的个人网站,不要只是一个孤零零的About页面,去学习Markdown与LaTeX,试着在Blog上记录自己的想法,并订阅自己喜欢的编程类博客。推荐几个供你参考:JoelonSoftware,PeterNorvig,CodingHorror
小结
以上的内容你不应该感到惧怕,编程的入门不是几个星期就能完成的小项目。期间你还会遇到无数的困难,当你碰壁时试着尝试“费曼”技巧:将难点分而化之,切成小知识块,再逐个对付,之后通过向别人清楚地解说来检验自己是否真的理解。当然,依旧会有你解决不了的问题,这时候不要强迫自己——很多时候当你之后回过头来再看这个问题时,一切豁然开朗。
此外不要局限与上文提到的那些材料,还有一些值得在入门阶段以及将来的提升阶段反复阅读的书籍。ThePragmaticProgrammer就是这样一本程序员入门书,终极书。有人称这本书为代码小全:从DRY到KISS,从做人到做程序员,这本书教给了你一切,你所需的只是遵循书上的指导。
后记
如果你能设法完成以上的所有任务,恭喜你,你已经真正实现了编程入门。这意味着你在之后更深入的学习中,不会畏惧那些学习新语言的任务,不会畏惧那些“复杂”的API,更不会畏惧学习具体的技术,甚至感觉很容易。当然,为了掌握这些东西你依旧需要大量的练习,腰还是会疼,走路还是会费劲,一口气也上不了5楼。但我能保证你会在思想上有巨大的转变,获得极大的自信,看老师同学和csdn的眼光会变得非常微妙,虽然只是完成了编程入门,但已经成为了程序员精神世界的高富帅。不,我说错了,即使是高富帅也不会有强力精神力,他也会怀疑自己,觉得自己没钱就什么都不是了。但总之,你遵循指南好好看书,那就会体验“会当凌绝顶”的感觉。
首先要想学编程,选一门合适的计算机语言就十分重要了,怎么去选择就显得尤为重要了,这要根据自己的兴趣爱好及每个语言的特性来选择,比如说PHP适合做web开发,易学习,易上手,非常流行的一门计算机语言了,我个人比较推荐php语言。
java可以做web开发,做安卓app开发也用的是java,在学习程度上上可能比php稍微难上手一点,不过也是没问题的,如果对java感兴趣可以尝试一下。
python是目前比较火的一门语言了,比较适合做人工智能领域,另外写网络爬虫类的程序,用python也是非常合适的了,看个人兴趣来选择了。
c,c++,c#这些语言就不推荐给了,特别是c#,已经是比较过时的一门语言了,即使学习好了,也不太适合去找工作,c与c++并不是十分适合初学者来学习,因此也是没必要进行考虑了,还有一些更小众的语言,更是没有必要去考虑,因此关于语言的学习就从上面3种语言去选择一门自己所感兴趣的吧!
研发搭建环境
如果选择好计算机语言,那么接下来就是研发环境的搭建了,因为只有研发环境搭建好了,才可以进行后续的编程工作,比如说PHP,那么就从网络上搜一下如何安装PHP环境,能搜出一些简单的教程,初学者按照教程一步一步来,顶多半天时间就可以把研发环境装好了,如果是java,就需要先安装jdk,进行环境变量的配置等,网上也有相关的教程,也是十分容易的,相信大家只要按照教程来做,都可以很轻易的把研发环境搭建起来的
选好视频和书籍,辅助学习。既然是零基础学习,就需要进行系统的学习,而不是到处网络零基础的知识点进行学习。
代码练习
跟随教程一个一个章节的进行学习,需要注意的一点就是不能只是去看,那样不行,要对每一个章节的知识点要亲自用代码敲一遍,运行一下试试效果才行,这样才能提高自己的动手能力,才开始会觉得有一点生疏,慢慢的就会熟练起来,逐渐会增加编程的兴趣。这个过程就是需要反复的进行练习,大量的代码练习才行。这个过程是5步中最关键的阶段了,重在代码亲自练习,对编程中有的章节不明白的地方,千万不要放过去,可以在网上找一些相关的编程交流群,参加进去,在线上咨询一些过来人,也许就可以轻松帮你解决疑问了,对你的学习十分帮助,并且整个过程也都是免费的。
项目实战
如果说基础教程都按部就班的都实践过一遍了,那么你就有一定的编程的基本功了,那么自己就可以尝试着做一些小项目,把学到的知识给串起来,进入项目实战阶段,比如说自己设计一个学生管理系统,并把它完成,如果不了解怎么设计,可以去网上搜索。慢慢就有思路了。
我也在学习这方面,视频书籍看过不少,最推荐的还是北京尚学堂的学习资料,Java.300集,Python400集,都是很经典的入门基础教程,而且是结合项目学习的,很有意思,干货满满,还都是免费的,推荐你可以去看看,相信可以带你走进变成的世界。
从零开始学编程,第一关就是要选择你所要学习的编程语言。面对着琳琅满目的编程语言,初学者常常一筹莫展,拿不定主意,不知该选哪
⑻ 动态规划 最长公共子序列 过程图解
首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。
这里给出一个例子:有两个母串
cnblogs
belong
比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列。最长公共子序列(Longest Common Subsequence,LCS),顾名思义,是指在所有的子序列中最长的那一个。
子串是要求更严格的一种子序列, 要求在母串中连续地出现 。
在上述例子的中,最长公共子序列为blog(cnblogs,belong),最长公共子串为lo(cnblogs, belong)。
给一个图再解释一下:
如上图,给定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原有的元素序列所得到的结果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。
它的子串示例:{c,d,e,f} 即连续元素c,d,e,f组成的串是给定序列的子串。同理,{a,b,c,d},{g,h}等都是它的子串。
这个问题说明白后,最长公共子序列(以下都简称LCS)就很好理解了。
给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。
s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}
求解LCS问题,不能使用暴力搜索方法。 一个长度为n的序列拥有 2的n次方个子序列,它的时间复杂度是指数阶 ,太恐怖了。解决LCS问题,需要借助动态规划的思想。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。 为了避免大量的重复计算,节省时间,我们引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。
解决LCS问题,需要把原问题分解成若干个子问题,所以需要刻画LCS的特征。
设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质:
如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;
如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0,a1,…,a(m-1)”和“b0,b1,…,bn”的一个最长公共子序列;
如果am!=bn,则若zk!=bn,蕴涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n-1)”的一个最长公共子序列。
有些同学,一看性质就容易晕菜,所以我给出一个图来让这些同学理解一下:
以我在第1小节举的例子(S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}),并结合上图来说:
假如S1的最后一个元素 与 S2的最后一个元素相等,那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。
假如S1的最后一个元素 与 S2的最后一个元素不等(本例子就是属于这种情况),那么S1和S2的LCS就等于 : {S1减去最后一个元素} 与 S2 的LCS, {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。
假设Z=<z1,z2,⋯,zk>是X与Y的LCS, 我们观察到
如果Xm=Yn,则Zk=Xm=Yn,有Zk−1是Xm−1与Yn−1的LCS;
如果Xm≠Yn,则Zk是Xm与Yn−1的LCS,或者是Xm−1与Yn的LCS。
因此,求解LCS的问题则变成递归求解的两个子问题。但是,上述的递归求解的办法中, 重复的子问题多,效率低下。改进的办法——用空间换时间,用数组保存中间状态,方便后面的计算。这就是动态规划(DP)的核心思想了。
DP求解LCS
用二维数组c[i][j]记录串x1x2⋯xi与y1y2⋯yj的LCS长度,则可得到状态转移方程
以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。我们借用《算法导论》中的推导图:
图中的空白格子需要填上相应的数字(这个数字就是c[i,j]的定义,记录的LCS的长度值)。填的规则依据递归公式,简单来说:如果横竖(i,j)对应的两个元素相等,该格子的值 = c[i-1,j-1] + 1。如果不等,取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化该表:
S1的元素3 与 S2的元素5 不等,c[2,2] =max(c[1,2],c[2,1]),图中c[1,2] 和 c[2,1] 背景色为浅黄色。
继续填充:
至此,该表填完。根据性质,c[8,9] = S1 和 S2 的 LCS的长度,即为5。
本文S1和S2的最LCS并不是只有1个,本文并不是着重讲输出两个序列的所有LCS,只是介绍如何通过上表,输出其中一个LCS。
我们根据递归公式构建了上表,我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
c[8][9] = 5,且S1[8] != S2[9],所以倒推回去,c[8][9]的值来源于c[8][8]的值(因为c[8][8] > c[7][9])。
c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去,c[8][8]的值来源于 c[7][7]。
以此类推,如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,这里请都选择一个方向(之后遇到这样的情况,也选择相同的方向)。
这就是倒推回去的路径,棕色方格为相等元素,即LCS = {3,4,6,7,8},这是其中一个结果。
如果如果遇到S1[i] != S2[j] ,且c[i-1][j] = c[i][j-1] 这种存在分支的情况,选择另一个方向,会得到另一个结果。
即LCS ={3,5,7,7,8}。
构建c[i][j]表需要Θ(mn),输出1个LCS的序列需要Θ(m+n)。
参考:
https://blog.csdn.net/hrn1216/article/details/51534607
https://blog.csdn.net/u012102306/article/details/53184446