《算法》（第4版）第1. 2章读书笔记

第一章 算法基础
我们使用Java语言来编写程序实现算法的原因：
1.程序是对算法的实例化阐述
2.可以通过运行程序了解算法性质
3.可以在程序中直接应用这些算法
对算法学习的恐惧主要来自自身语言基础的不扎实，但算法的学习其实与语言的基础无关，每个代码都可以用伪代码甚至中文来表示，如果把计算机语言比作一种工具，那算法就像使用工具的方法，这对程序员来说更加重要。
Java程序基本结构
1.原始数据类型
2.语句
3.数组
4.静态方法：静态方法可以封装并重用代码，使我们可以用独立的模块开发程序
5.字符串
6.标注输入/输出
7.数据抽象：数据抽象封装和重用代码，使我们可以定义非原始数据类型，进而支持面向对象编程

关于静态方法的三两事
方法封装了由一系列语句所描述的计算。

	
	

		定义静态方法。 甲方法封装了被定义为语句序列的计算。方法接受参数 （给定数据类型的值）并计算 某些数据类型的返回值或导致副作用。每个静态方法都由签名 和正文组成。
		

			
		

	

	

		调用静态方法。 对静态方法的调用是其名称后跟表达式，这些表达式在括号中指定参数值，以逗号分隔。调用方法时，其参数变量将使用调用中相应表达式的值进行初始化。一个返回语句会终止静态方法，控制返回给调用者。如果静态方法是计算值，则必须在return语句中指定该值。
	

	

		方法的属性。 Java方法具有以下功能：
		

			
			

				参数按值传递。 调用函数时，将完全计算参数值，并将结果值复制到参数变量中。这被称为pass by value。数组（和其他对象）引用也通过值传递：方法不能更改引用，但它可以更改数组中的条目（或对象的值）。
			

			

				方法名称可以重载。 如果类中的方法具有不同的签名，则它们可以具有相同的名称。此功能称为重载。
			

			

				方法具有单个返回值，但可能具有多个return语句。 Java方法只能提供一个返回值。一旦到达第一个return语句，控制就会返回到调用程序。
			

			

				方法可能有副作用。 方法可以使用关键字void作为其返回类型，以指示它没有返回值并产生副作用（消耗输入，产生输出，更改数组中的条目，或以其他方式更改系统的状态）。
			

		

	

	

		递归。 甲递归方法是，直接或间接地调用自身的方法。开发递归程序有三个重要的经验法则：
		

			
			

				递归有一个基本情况。
			

			

				递归调用必须解决 在某种意义上较小的子问题，以便递归调用收敛到基本情况。
			

			

				递归调用不应解决重叠的子问题。
			

		

	

	

		基本编程模型。 一个静态方法库是一组在Java类中定义的静态方法。Java编程的基本模型是通过创建静态方法库来开发一个解决特定计算任务的程序，其中一个方法名为main（）。
	

	

		模块化编程。 静态方法库支持模块化编程，其中一个库中的静态方法可以调用其他库中定义的静态方法。这种方法有许多重要的优点。
		

			
			

				使用合理大小的模块
			

			

				无需重新实现即可共享和重用代码
			

			

				替代改进的实施
			

			

				开发适当的抽象模型来解决编程问题
			

			

				本地化调试
			

		

	


典型静态方法实现
1.计算一个整数的绝对值
public static int abs(int x)
{
if(x<0) return -x;
else    return x;
}
2.计算一个数是否是素数
public static boolean isPrime(int N)
{
if(N < 2) return false;
for(int i = 2; i*i <= N; i++)
   if(N % i == 0) return false;
return true;
}
3.计算调和级数
public static double H(int N)
{
double sum = 0.0;
for(int i = 1;i <= N; i++)
   sum += 1.0 / i;
return sum;
}
静态方法的性质
1.方法的参数按值传递
2.方法名可以重载
3.方法只返回一个值
4.方法可以产生副作用

递归
编写递归代码最重要的三点
1.递归总有一个最简单的情况——方法的第一条总是一个包含return的条件语句
2。递归调用总是去尝试解决一个规模更小的子问题
3.递归调用的父问题和尝试解决的子问题之间不该有交集

二分查找的递归实现
public static int rank（int key, int[] a)
{ return rank(key, a, 0, a.length - 1);}
public static int rank(int key, int [] a, int lo ,int hi)
{
   if(lo > hi) return -1;
   int mid = lo + (hi - lo) / 2;
   if      (key < a[mid]) return rank(key, a, lo, mid - 1);
   else if (key > a[mid]) return rank(key, a, mid - 1, hi);
   else
}