【云+社区年度征文】1到100求和学算法之循环的秘密

1 引言

Pascal之父尼古拉斯·沃斯因提出著名公式“算法+数据结构=程序”而荣获1984年计算机领域的最高奖项-图灵奖。通过这个公式,可以发现算法对于程序设计的重要性。然而算法思想的学习异常抽象,而且往往虽然理解了算法的思想却难以应用其解决实际问题。

1.1 互联网算法文章现状

互联网的出现让我们获取知识变得比以往任何时候都要便捷,面对海量的信息,甚至经常会出现信息过载的情况。同样,互联网上也有非常多的文章来介绍各种算法。通过阅读互联网介绍算法的部分文章,发现存在以下问题:

(1) 算法文章的质量参差不齐。随着互联网技术的快速发展,进入2.0时代后,让每一位互联网用户都成为了内容的创造者。利用百度搜索引擎输入“算法”后,会出现来自几乎所有互联网用户撰写的文章,虽然搜索引擎本身已经为我们做了一定的筛选和排名,但是受限于算法文章撰写作者水平自身的水平,导致文章质量差异较大。

(2) 算法思想的描述晦涩难懂。算法思想本身是高度抽象,部分算法较为复杂,因此给学习者带来一定的困难。现有文章大多是照搬教材等不同来源的内容,些许的文章增加案例帮助学习者理解,文章的同质化现象较为严重。一个复杂的算法思想需要用简单的语言表达出来,并且能够让学习者理解。做到这一点的前提是文章作者对算法本身有较深的理解,熟悉一定的教学技巧,同时还要了解学习者在学习时的心理,经过各种转化,最后能够用简单的语言表达出来,这所有的一切都需要一定的沉淀和积累才能做到。

(3) 不同算法文章选取的问题背景均不同,读者需要花费较多的时间来了解背景知识。现有的个别文章虽然采用案例的方式帮助读者更好理解算法思想,但是不同算法选取的案例不同,部分案例较为复杂不便于理解,且无法形成算法体系。读者在学习的时候,需要不停切换各种算法问题场景,容易造成算法学习的分散,无法形成聚焦,导致算法学习效率较低。

1.2 算法文章撰写思路

为了有效应对上述挑战,提出以下两种方式进行算法学习文章的撰写。

本系列文章选取1到100求和问题,尝试从不同角度加以分析,介绍常见算法思想。1到100求和是一个非常简单的问题,同时也是程序设计语言初学者都会遇到的一个问题,因此该案例的选取具有较强的通用性,读者不必花费太多的时间和精力去了解案例的背景知识,而专注于算法思想本身。一个问题通常有N种解法,针对1到100求和这个问题,从不同角度加以分析,应用不同的算法思想解决这个问题,最终实现“一个问题、多种算法”的学习。

本系列文章由主线和辅线两个部分组成。主线围绕1到100求和问题开展多种算法思想的阐述。辅线将对主线涉及到的一些关键知识点进行补充介绍,帮助读者了解更多的细节。之所以采用主线、辅线两种方式分开的原因在于,该方式能够帮助读者更好的聚焦算法本身,如果读者已经了解并熟悉该部分内容,则可以跳过并继续后续阅读,反之可以阅读辅线文章以帮助其更好的了解细节。

1.3 特色和亮点

首次提出了“一个问题、多种算法”的算法学习路径。让读者将主要的时间和精力聚焦在不同算法思想的学习和理解上,最大程度上减少案例背景知识的学习。选取的问题简单、通俗易懂,能够帮助大家快速熟悉背景知识,尽早的投入到算法本身的学习。

从不同角度深入研究和探讨同一个问题,在学习算法的同时,掌握多种分析问题的方法。除了知识的传授之外,更加注重算法能力的培养,帮助读者在掌握算法思想后能够灵活应用其解决实际问题,而不仅仅是停留在知识学习的层面。

2 循环的秘密

循环结构是程序设计三大结构的重点和难点,几乎所有的算法的设计都使用了循环结构。程序语言为什么需要循环结构?没有循环结构会给程序设计带来哪些问题?如何利用循环结构求解1到100求和问题,本节将带领读者一起探索循环的秘密。

2.1 仅依赖变量定义和加法运算符实现求和

1到100求和问题几乎是所有编程语言初学者都会接触到的一个问题,其定义如下,编程实现:

1 + 2 + ··· + 100 = ?

限制条件:仅依赖变量定义和加法运算符两个知识点。

程序设计初学者在学习完变量的定义之后,紧接着学习了加减乘除等运算符。仅有这些知识是否可以实现1到100求和问题?

1到100求和问题定义的是1到100共一百个整数的求和,其问题规模n=100,如何缩小问题规模,简化问题求解。如果将问题规模n缩小到两个整数的求和,即1+2=?

定义两个变量a1和a2,再利用加法运算符即可求解。伪码如下:

a1 = 1
a2 = 2
sum = a1+a2

既然学会了两个整数的求和,采取相似思路,可以将问题规模进一步扩大到100个整数。

定义a1, a2, ..., a100共100个变量保存1到100这100个,然后直接相加。

a1 = 1
a2 = 2
···
a100 = 100
sum = a1 + a2 + ··· +a100
(上面两处省略号并非程序语言关键词,而是由于空间有限故省略)

至此,仅依赖变量定义和加法运算符两个知识点就可以完成1到100求和问题的求解。

本节介绍了程序设计初学者在仅仅学习变量定义和加法运算符两个知识点后如何求解1到100求和问题,通过缩小问题规模采用以此类推的方式进行求解。当问题规模缩小后,就可以快速完成求解。

解题方法1:对于规模较大的问题,采取适当的方式减小问题规模,先求解规模较小的问题,然后采用以此类推的方式来求解规模较大的问题。

如何缩小问题规模?1到100求和问题的问题规模非常易于发现,问题规模缩小后,无论是1到2求和还是1到100求和本质上是一样的。但是有些问题的问题规模却不好定义。后续文章将针对该问题进行深入的探讨。

另外虽然本文算法完成了对1到100求和问题的求解,但是存在哪些问题呢?

2.2 使用尽可能少的变量实现求和

上一节分析了仅依赖变量定义和加法运算符两个知识点完成1到100求和,虽然能够实现目标,然而仔细分析却发现存在较大问题。文中描述的算法需要定义a1,a2,···,a100共100个变量才能实现加法求和,如此大规模的变量定义是否有必要,如果没有必要如何减少变量定义的个数?

2.2.1 是否有必要定义这么多的变量

前面提出了两个问题,首先来分析第一个问题,是否有必要定义这么多的变量呢?要想搞清楚这个问题,前提是要弄明白什么是变量,变量的本质是什么。

所谓变量名就是计算机内存地址的一个别名,如下图所示左侧为内存地址,右侧为其对应的变量名。设整型变量int占用的内存大小为4个字节,内存地址起始位置为0x1000的单元此时有整数1,起始位置0x1004的单元存有整数2。通过计算机编程的方式如何访问得到这两个整数,最简单的方式就是直接通过内存地址来访问得到,但是这种方式要求开发者需要时刻牢记程序中每一个变量的起始地址,而且需要知道这个变量的类型。如果程序涉及的变量很少,这种简单暴力的方式可行,但是对于实际应用开发时,动辄成千上万的变量,这种方法就行不通。如何让开发者快速的访问和改变每一个变量的值,成为研究者的重点。

与其让开发者牢记毫无规律的纯数字,不然让开发者给这串数字取一个有意义的别名,通过别名实现快速存取指定内存单元的数据。

图 1 变量与内存地址的对应关系

理解了变量的本质以后,可以发现定义变量的目的是该变量对应的内存单元数据在程序运行期间会发生多次变化,这正体现了变量的“变”字。而与之相对应的是不变量即常量,整个程序运行期间内存单元的值不会发生任何改变。

算法 仅依赖变量定义和加法运算符实现求和

定义a1, a2, ..., a100共100个变量保存1到100这100个,然后直接相加。
a1 = 1
a2 = 2
···
a100 = 100
sum = a1 + a2 + ··· +a100
(上面两处省略号并非程序语言关键词,而是由于空间有限故省略)

有了上面分析之后,回到最初提出的问题。结合算法1和其对应的内存单元关系进行分析,前面100行变量的定义和赋值,本质是将1到100这100个整数存储在对应的内存单元。最后一行代码利用CPU的运算器不断的从a1到a100的内存单元取整数实现累加,最后将得到的结果存储在a100对应的内存单元(后面文章将分析CPU执行此操作的具体流程,如感兴趣,欢迎持续关注)。

遗留问题:CPU是如何实现sum=a1+a2+a3这行代码的加法?

图 2 算法1对应的内存单元

通过对算法执行流程的分析发现,程序运行期间,a1到a100对应的这100个内存单元并未发生任何的变化,自始至终始终维持着刚开始的初值。这与变量的本质不符,且浪费了较多的内存单元。

至此,可以得出结论,算法1定义的这些变量,没有充分体现变量的本质,带来了内存单元空间的大量浪费。

关于引言中提出的第二个问题,如何减少变量定义的个数呢?需要定义多少个变量来实现目标呢。

2.2.2 如何减少变量定义的个数

上一节分析了没有必要定义a1,a2,···,a100这100个变量,其根本原因在于定义的这些变量在程序运行期间,这些变量对应的内存单元没有发生任何的改变,其本质为常量。既然没有必要定义这么多的变量,那如何减少变量定义的个数呢?本文一起来探索实现这一目标的做法。

算法 1 两个整数的求和

sum = 0
a1 = 1
a2 = 2
sum = a1 + a2

关于1到100求和问题,截至到目前,主要的工作有:首先介绍了两个整数的求和算法1,然后以此类推到100个整数的求和算法2,接着分析了没有必要定义a1到a100这100个变量。

算法 2 仅依赖变量定义和加法运算符的1到100的求和

a1 = 1
a2 = 2
···
a100 = 100
sum = a1 + a2 + ··· +a100
(上面两处省略号并非程序语言关键词,而是由于空间有限故省略)

关于算法2,再做一些深入的分析,对其进行优化。首先定义变量sum用来保存最后的求和结果。注意这里定义的变量sum,意味着程序执行期间,sum的值会多次发生改变,最后一次改变后,得到的值就是最终的结果。算法2是一次性将a1到a100全部加到sum中,将一次性的行为变更为逐步累加的过程,即每一次加一个整数到sum中,这样每一次加法操作后,sum变量的值就会改变,符合变量的定义。从第一个整数开始,共执行100步操作,每次加一个整数,第100步执行加法完成后就得到最终的结果,如算法3所示。

算法 3 仅依赖变量定义和加法运算符的1到100求和(改进版)

sum = 0
a1 = 1
sum = sum + a1
a2 = 2
sum = sum + a2
···
a100 = 100
sum = sum +a100
(上面省略号并非程序语言关键词,而是由于空间有限故省略)

算法2算法3,看似微小的变化,其体现的算法思想完全不一样。算法2是一次性的操作,而算法3是一次性的操作拆分成了很多微小的步骤,这体现了一种分解的思路,从而使得问题的理解更加深刻了。实现了这种分解之后,如何实现引言最初提出的减少变量定义的个数呢?

要想改进算法,前提是要对其进行认真的分析,发现规律。通过对算法3的分析,可以发现如下的规律:

ai = i
sum = sum + ai
(i = 1,2,···,100)

这个规律是否可以做进一步的优化呢?通过观察发现,ai=i这行代码没有改变i的值,ai和i之间存在冗余,可以直接用i来替代,改进后的模式如下所示:

sum = sum + i
i = 1,2,···,100

经过优化后的模式比之前更简洁和直观。对于i从1到100,这样的模式需要重复一百次。如何设计算法让这样的模式能够重复执行100次成为下一步分析的关键。

2.2.3 使用循环结构减少变量定义个数

这样的一个问题经过抽象后就是,对于编程语言而言,如何实现一个有限长度固定模式的重复。其中模式存在两种情况,其一是模式是常量,其二是模式中有变化的地方。举例如下:

(1) 重复打印100次“hello,world”字符串。这种模式中不存在变化的地方,都为常量,每一次的重复都是一成不变的。

(2) 重复打印i,其中i=1,2,···,100。这种情况下,每一次的重复,对于i都是变化的。

循环结构是解决这一重复问题的利器。一般情况下编程语言会提供for、while和do...while三种循环结构,其中for是最基础同时也是最重要的结构。

sum = 0
for i = 1 to 100:
   sum = sum + i

重复执行sum = sum + i 共计100次,而且每一次执行的时候,改变i的值,如第1次执行的时候,i=1,第2次执行的时候,i=2,以此类推。这样就完成了模式的重复。

至此,1到100求和问题,只使用了i和sum两个变量就完成了求和。1到100求和是编程初学者都会接触到的一个问题,选择这样的一个问题作为分析的对象,重点不在于如何解决这个问题,如何编程实现1到100求和,而是一步一步严谨的分析过程。试想假如编程语言没有提供循环结构,你该如何解决这个问题呢?

3 总结

本文首先介绍了1到100求和算法文章撰写的缘由及思路,接着分析了仅依赖变量定义和算法运算符两个知识点如何实现求和,随后深入分析了没有必要定义a1,a2,···,a100这100个变量其本质为常量,接下来介绍了如何利用循环结构消除重复。通过一步步细致甚微的分析,让读者充分感受到循环的秘密,分析的过程中一直引导读者思考,假如没有循环,你应该如何解决这个问题。

本站文章资源均来源自网络,除非特别声明,否则均不代表站方观点,并仅供查阅,不作为任何参考依据!
如有侵权请及时跟我们联系,本站将及时删除!
如遇版权问题,请查看 本站版权声明
THE END
分享
二维码
海报
【云+社区年度征文】1到100求和学算法之循环的秘密
Pascal之父尼古拉斯·沃斯因提出著名公式“算法+数据结构=程序”而荣获1984年计算机领域的最高奖项-图灵奖。通过这个公式,可以发现算法对于程序设计的重要性...
<<上一篇
下一篇>>