第一章引论

1. 选择问题（selection problem）

设有一组n个数而要确定其中的第k个最大者。我们称之为选择问题。
方法1：将这n个数读到一个数组里，再通过简单的算法，比如冒泡排序法，以递减顺序将数组排序，然后返回位置k上的元素。
方法2：可以先把前k个元素读入数组（以递减的顺序）对其进行排序。接着，将剩下的元素再逐个读入。当新元素被读到时，如果它小于数组中的第k个元素将被忽略，否则将数组的一个元素挤出数组。当算法终止时，位于第k个位置上的元素作为答案返回。
因为有更好的算法，故此处不实现

2. 字谜问题

解决一个流行的字谜，输入是由一些字母和单词的二维数组组成。目标是要找出字谜中的单词，这些单词可能是水平、垂直、或沿对角线以任何方式放置的。作为例子下表中所示的字谜由单词“this”,”two”,”fat”和“that”组成。单词this从(1,1)开始，并延伸至(1,4)，单词two从(1,1)到(3,1)，fat从(4,1)到(2,3)，that从(4,4)到(1,1)。

	1	2	3	4
1	t	h	i	s
2	w	a	t	s
3	o	a	h	g
4	f	g	d	t

方法1：对单词表中的每一个单词，我们检查每个有序三元组（行，列，方向），验证是否有单词存在。

方法2：对每一个有序四元组（行，列，方向，字符数）我们可以测试所指的单词是否在单词表中。
因为有更好的算法，故此处不实现

3. 递归的基本法则

基准情况（base case），也就是递归的终止条件。
不断推进(making progress)，若用递归求解问题，则此问题需要朝着基准情况不断的前进。

若递归函数嵌套相同参数的同样的递归函数，此时形成一个循环，就违反了此原则。
此外，有些情况下，并不能归到基准情况，此时递归也是不正确的。比如：
下面是一个递归函数的例子：

int 
F(int x){
  if(x==0)
    return 0;
  else 
    return 2*F(x-1)+x*x;
}

下面是一个无终止递归函数的例子：（因为并不是所有的情况都归到基准情况）

int 
Bad(unsigned int N){
  if(N==0)
    return 0;
  else 
    return Bad(N/3+1)+N/1;
}

合成效益法则（compound interest rule），对于同一问题，切勿出现重复计算的工作，否则将极大的影响效率，比如：递归求解的菲波那切数列。

4. 模运算

同余问题

若N可以整除 A-B，那么我们说 A与B 模 N 同余（congruent），记做 A≡B(mod N)。
也就是说A和B关于N的余数相同。
用此方法可以方便的解决习题 1.8

取模的等价运算

N%10=N-[N/10]*10。([x]意为小于或等于x的最大整数) //因为公式输入问题，有些不标准，但是大概这个意思

习题

说明

有些题目涉及到数学证明，有些比如C语言的文件操作，不太常用，故而不写出。
更多的习题答案可以参考：
数据结构与算法分析（2）算法效率问题引入与递归简论
 数据结构与算法分析—c语言描述_课后答案.pdf

1.3 只适用处理IO的PrintDigit 函数，编写一个过程以输出任意实数（可以是负的）

首先，我们看到输出的是任意实数，所以我们可以用 double 型的变量来表示。
再者，要明确 PrintDigit 函数是只处理单个数字（非负）并将其输出到终端，也就是说处理的数字范围是 0<=N<10.
还有，若一个数用 double 类型表示，比如 double x=8.1 ，由于计算机的存储特性，则 x 在计算机中不一定是 8.1，还有可能是一个接近 8.1 的数，比如 8.09999999..，所以我们需要通过某种方式抵消这种误差，不影响我们问题的解决。详细见：只使用I/O的PrintDigit函数，编写一个过程以输出任意实数

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
void PrintDigit(int n)
{
    cout<<n;
}
//DcePlaces 指的是有几位小数
double RoundUp(double N, int DecPlaces) // 用于消除存储误差
{
    int i;
    double AmountToAdd=0.5;
    for(i=0;i<DecPlaces;i++)
        AmountToAdd/=10;
    return N+AmountToAdd;
}
int IntPart(double N)//取实数的整数部分
{
    return (int)N;
}
double DecPart(double N)//取实数的小数部分
{
    return N-(int)N;
}
void PrintFractionPart(double FractionPart, int DectPlaces)
{
    int i,Adigit;
    for (i = 0; i < DectPlaces; i++)//对于小数部分的打印
    //将小数部分一个接一个的移入整数位，一次仅仅移入一个，然后调用 PrintDigit 进行打印
    //而不是根据小数位数一次性的将所有的小数部分都移入整数部分，进行打印的原因是：
    //避免不必要的递归
    {
        FractionPart*=10;
        Adigit=IntPart(FractionPart);
        PrintDigit(Adigit);
        FractionPart=DecPart(FractionPart);
    }
}
void PrintOut(unsigned int n)//递归的打印，契合 PrintDigit 函数的限制条件
{
    if(n>=10)
        PrintOut(n/10);
    PrintDigit(n%10);
}
void PrintReal(double N, int DecPlaces)
{
    int IntergerPart;
    double FractionPart;
    if(N<0)//对于负数的处理
    {
        putchar('-');
        N=-N;
    }
    N=RoundUp(N, DecPlaces);
    IntergerPart=IntPart(N); FractionPart=DecPart(N);
    PrintOut(IntergerPart);
    if(DecPlaces>0)
        putchar('.');
    PrintFractionPart(FractionPart, DecPlaces);
}
int main()
{
    PrintReal(-8.101,3);
    cout<<endl;
    return 0;
}