返回课程

  由算法得出代码

  本系列一开头就说明了何谓程序,并说明由于CPU的世界和人们存在的客观物理世界的不兼容而导致根本不能将人编写的程序(也就是算法)翻译成CPU指令,但为了能够翻译,就必须让人觉得CPU世界中的某些东西是人以为的算法所描述的某些东西。如电脑屏幕上显示的图片,通过显示器对不同象素显示不同颜色而让人以为那是一幅图片,而电脑只知道那是一系列数字,每个数字代表了一个象素的颜色值而已。

  为了实现上面的“让人觉得是”,得到算法后要做的的第一步就是找出算法中要操作的资源。前面已经说过,任何程序都是描述如何操作资源的,而C++语言本身只能操作内存的值这一种资源,因此编程要做的第一步就是将算法中操作的东西映射成内存的值。由于内存单元的值以及内存单元地址的连续性都可以通过二进制数表示出来,因此要做的第一步就是把算法中操作的东西用数字表示出来。

  上面做的第一步就相当于数学建模——用数学语言将问题表述出来,而这里只不过是用数字把被操作的资源表述出来罢了(应注意数字和数的区别,数字在C++中是一种操作符,其有相关的类型,由于最后对它进行计算得到的还是二进制数故使用数字进行表示而不是二进制数,以增强语义)。接着第二步就是将算法中对资源的所有操作都映射成语句或函数。

  用数学语言对算法进行表述时,比如将每10分钟到车站等车的人的数量映射为一随机变量,也就前述的第一步。随后定此随机变量服从泊松分布,也就是上面的第二步。到站等车的人的数量是被操作的资源,而给出的算法是每隔10分种改变这个资源,将它的值变成按给定参数的泊松函数分布的一随机值。

  在C++中,前面已经将资源映射成了数字,接着就要将对资源的操作映射成对数字的操作。C++中能操作数字的就只有操作符,也就是将算法中对资源的所有操作都映射成表达式语句。

  当上面都完成了,则算法中剩下的就只有执行顺序了,而执行顺序在C++中就是从上朝下书写,而当需要逻辑判断的介入而改变执行顺序时,就使用前面的if和goto语句(不过后者也可以通过if后接的语句来实现,这样可以减少goto语句的使用,因为goto的语义是跳转而不是“所以就”),并可考虑是否能够使用循环语句以简化代码。即第三步为将执行流程用语句表示出来。

  而前面第二步之所以还说可映射成函数,即可能某个操作比较复杂,还带有逻辑的意味,不能直接找到对应的操作符,这时就只好利用万能的函数操作符,对这个操作重复刚才上面的三个步骤以将此操作映射成多条语句(通过if等语句将逻辑信息表现出来),而将这些语句定义为一函数,供函数操作符使用以表示那个操作。

  上面如果未明不要紧,后面有两个例子,都将分别说明各自是如何进行上述步骤的。

  排序给出三张卡片,上面随便写了三个整数。有三个盒子,分别标号为1、2和3。将三张卡片随机放到1、2、3这三个盒子中,现在要求排序以使得1、2、3三个盒子中装的整数是由小到大的顺序。

  给出一最简单的算法:称1、2、3盒子中放的卡片上的整数分别为第一、二、三个数,则先将第一个数和第二个数比较,如果前者大则两个盒子内的卡片交换;再将第一个和第三个比较,如果前者大则交换,这样就保证第一个数是最小的。然后将第二个数和第三个数比较,如果前者大则交换,至此排序完成。

  第一步:算法中操作的资源是装在盒子中的卡片,为了将此卡片映射成数字,就注意算法中的卡片和卡片之前有什么不同。算法中区分不同卡片的唯一方法就是卡片上写的整数,因此在这里就使用一个long类型的数字来表示一个卡片。

  算法中有三张卡片,故用三个数字来表示。前面已经说过,数字是装在内存中的,不是变量中的,变量只不过是映射地址而已。在这里需要三个long类型数字,可以借用定义变量时编译器自动在栈上分配的内存来记录这些数字,故可以如此定义三个变量long a1, a2, a3;来记录三个数字,也就相当于装三张卡片的三个盒子。

  

  第二步:算法中的操作就是对卡片上的整数的比较和交换。前者很简单,使用逻辑操作符就可以实现(因为正好将卡片上的整数映射成变量a1、a2和a3中记录的数字)。后者是交换两个盒子中的卡片,可以先将一卡片从一盒子中取出来,放在桌子上或其他地方。然后将另一盒子中的卡片取出来放在刚才空出来的盒子。最后将先取出来的卡片放进刚空出来的盒子。前面说的“桌子上或其他地方”是用来存放取出的卡片,C++中只有内存能够存放数字,因此上面就必须再分配一临时内存来临时记录取出的数字。

  第三步:操作和资源都已经映射好了,算法中有如果的就用if替换,由什么重复多少次的就用for替换,有什么重复直到怎样的就用while或do while替换,如上照着算法映射过来就完了,如下:

  void main()

  {

  long a1 = 34, a2 = 23, a3 = 12;

  if( a1 > a2 )

  {

  long temp = a1;

  a1 = a2;

  a2 = temp;

  }

  if( a1 > a3 )

  {

  long temp = a1;

  a1 = a3;

  a3 = temp;

  }

  if( a2 > a3 )

  {

  long temp = a2;

  a2 = a3;

  a3 = temp;

  }

  }

  上面就在每个if后面的复合语句中定义了一个临时变量temp以借助编译器的静态分配内存功能来提供临时存放卡片的内存。上面的元素交换并没有按照前面所说映射成函数,是因为在这里其只有三条语句且容易理解。如果要将交换操作定义为一函数,则应如下:

  void Swap( long *p1, long *p2 ) void Swap( long &r1, long &r2 )

  { {

  long temp = *p1; long temp = r1;

  *p1 = *p2; r1 = r2;

  *p2 = temp; r2 = temp;

  } }

  void main() void main()

  { {

  long a1 = 34, a2 = 23, a3 = 12; long a1 = 34, a2 = 23, a3 = 12;

  if( a1 > a2 ) if( a1 > a2 )

  Swap( &a1, &a2 ); Swap( a1, a2 );

  if( a1 > a3 ) if( a1 > a3 )

  Swap( &a1, &a3 ); Swap( a1, a3 );

  if( a2 > a3 ) if( a2 > a3 )

  Swap( &a2, &a3 ); Swap( a2, a3 );

  } }

  

  先看左侧的程序。上面定义了函数来表示给定盒子之间的交换操作,注意参数类型使用了long*,这里指针表示引用(应注意指针不仅可以表示引用,还可有其它的语义,以后会提到)。

  什么是引用?注意这里不是指C++提出的那个引用变量,引用表示一个连接关系。比如你有手机,则手机号码就是“和你通话”的引用,即只要有你的手机号码,就能够实现“和你通话”。

  再比如Windows操作系统提供的快捷方式,其就是一个“对某文件执行操作”的引用,它可以指向某个文件,通过双击此快捷方式的图标就能够对其所指的文件进行“执行”操作(可能是用某软件打开这个文件或是直接执行此文件等),但如果删除此快捷方式却并不会删除其所指向的文件,因为它只是“对某文件执行操作”的引用。

  人的名字就是对“某人进行标识”的引用,即说某人考上大学通过说那个人的名字则大家就可以知道具体是哪个人。同样,变量也是引用,它是某块内存的引用,因为其映射了地址,而内存块可以通过地址来被唯一表明其存在,不仅仅是标识。注意其和前面的名字不同,因为任何对内存块的操作,只要知道内存块的首地址就可以了,而要和某人面对面讲话或吃饭,只知道他的名字是不够的。

  应注意对某个东西的引用可以不止一个,如人就可以有多个名字,变量也都有引用变量,手机号码也可以不止一个。

  注意上面引入了函数来表示交换,进而导致了盒子也就成了资源,因此必须将盒子映射成数字。而前面又将盒子里装的卡片映射成了long类型的数字,由于“装”这个操作,因此可以想到使用能够标识装某个代表卡片的数字的内存块来作为盒子映射的数字类型,也就是内存块的首地址,也就是long*类型(注意不是地址类型,因为地址类型的数字并不返回记录它的内存的地址)。所以上面的函数参数类型为long*。

  下面看右侧的程序。参数类型变成long&,和指针一样,依旧表示引用,但注意它们的不同。后者表示它是一个别名,即它是一个映射,映射的地址是记录作为参数的数字的地址,也就是说它要求调用此函数时,给出的作为参数的数字一定是有地址的数字。所谓的“有地址的数字”表示此数字是程序员创建的,不是编译器由于临时原因而生成的临时内存的地址,如Swap( a1++, a2 );就要报错。之前已经说明,因为a1++返回的地址是编译器内部定的,就程序逻辑而言,其是不存在的,而Swap( ++a1, a2 );就是正确的。Swap( 1 + 3, 34 );依旧要报错,因为记录1 + 3返回的数字的内存是编译器内部分配的,就程序逻辑上来说,它们并没有被程序员用某块内存记录起来,也就不会有内存。

  一个很简单的判定规则就是调用时给的参数类型如果是地址类型的数字,则可以,否则不行。

  还应注意上面是long&类型,表示所修饰的变量不分配内存,也就是编译器要静态地将参数r1、r2映射的地址定下来,对于Swap( a1, a2 );就分别是a1和a2的地址,但对于Swap( a2, a3 );就变成a2和a3的地址了,这样是无法一次就将r1、r2映射的地址定下来,即r1、r2映射的地址在程序运行时是变化的,也就不能且无法编译时静态一次确定。

  为了实现上面的要求,编译器实际将会在栈上分配内存,然后将地址传递到函数,再编写代码以使得好像动态绑定了r1、r2的地址。这实际和将参数类型定为long*是一样的效果,即上面的Swap( long&, long& );和Swap( long*, long* );是一样的,只是语法书写上不同,内部是相同的,连语义都相同,均表示引用(虽然指针不仅仅只带有引用的语义)。即函数参数类型为引用类型时,依旧会分配内存以传递参数的地址,即等效于指针类型为参数。

  商人过河问题3个商人带着3个仆人过河,过河的工具只有一艘小船,只能同时载两个人过河,包括划船的人。在河的任何一边,只要仆人的数量超过商人的数量,仆人就会联合起来将商人杀死并抢夺其财物,问应如何设计过河顺序才能让所有人都安全地过到河的另一边。

  给出最弱却万能的算法——枚举法。坐船过河及划船回来的可能方案为一个仆人、一个商人或两个商人、两个仆人及一个商人一个仆人。

  故每次从上述的五种方案中选择一个划过河去,然后检查河岸两侧的人数,看是否会发生仆人杀死商人,如果两边都不会,则再从上述的五个方案中选择一个让人把船划回来,然后再检查是否会发生仆人杀死商人,如果没有就又重新从五个方案中选一个划过河,如上重复直到所有人都过河了。

  


  • 扫一扫 扫二维码继续学习