1.本书讨论的内容
设有一组N个数而要确定其中第K个最大者，称之为选择问题
一种解法
该问题的一种解法是将这N个数读进一个数组中，再通过某种简单的算法，以递减顺序将数组排序，然后返回位置K上的元素
//冒泡排序
#include <iostream>
using namespace std;
int main()
{
const int n = 10;
const int k = 5;
int arr[n];
int i,j,t;
for (i = 0; i < n; i++)
cin >> arr[i];
for (i = 0; i < n; i++)
{
for (j = 0; j < n-i-1; j++)
{
if (arr[j] < arr[j + 1])
{
t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
cout << arr[k - 1];
return 0;
}
另一种解法
稍微好一点的算法可以先把前K个元素读入数组(并以递减的顺序)对其排序，接着，将剩下的元素再逐个读入。当新元素被读到时，如果它小于数组中的第K个元素则忽略，否则就将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组，当算法终止时，位于第K个位置上的元素作为答案返回。
#include <iostream>
using namespace std;
int main()
{
const int k = 15;
int arr[k];
int i, j, t;
for (int i = 0; i < k; i++)
cin >> arr[i];
for (i = 0; i < k; i++)
{
for (j = 0; j < k-i-1; j++)
{
if (arr[j] < arr[j + 1])
{
t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
for (int i = 0; i < k; i++) //对K个值进行排序
{
cout << "arr[" << i << "] = ";
cout << arr[i] << endl;
}
cout << "Enter \'q\' to quit" << endl;
while(1) //插入剩下的元素
{
int n;
if (cin >> n)
{
for (i = 0; i < k; i++)
{
if (n > arr[i])
{
for (j = k-1; j > i; j--)
{
arr[j] = arr[j-1];
}
arr[i] = n;
break;
}
}
}
else
break;
}
for (int i = 0; i < k; i++)
{
cout << "arr[" << i << "] = ";
cout << arr[i] << endl;
}
}
虽然它们都能得出结果，但不认为是好的算法，在第七章内有另一种算法，对于第三种算法在合理的时间内能够处理的输入数据量而言，这两种算法是不切实际的。(Updating)
在许多问题当中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题。
如何估计程序的运行时间，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。彻底改进程序速度以及确定程序瓶颈的方法，使得我们能够找到大力优化的那些代码段。
2.数学知识复习
- 指数
- 对数
- 级数
- 模运算
- 证明方法
·归纳法 ·反证法
3.递归简论
当一个函数用它自己来定义时就称为是递归(recursive)的。
C提供的仅仅是遵循递归思想的一种企图，不是所有的数学递归函数都能有效的(或正确的)由C的递归模拟来实现。
F(0) = 0 且 F(X) = 2F(X-1) + X^2
#include <iostream>
using namespace std;
double F(double x)
{
if (x == 0) //处理基准情况
return 0;
if (x > 0)
return 2 * F(x -1) + x * x;
}
int main()
{
double x;
cout << "Pleas input x: " << endl;
cin >> x;
cout << "F(x) = " << F(x) << endl;
return 0;
}
F(X)函数中第一行和第二行处理基准情况(base case)，即此时函数的值可以直接算出而不用求助递归。C的递归函数若无基准情况，是毫无意义的。
递归的基本法则
- 1.基准情形(base case)
- 2.不断推进(making progress)
对于那些需要递归求解的情形，递归调用必须总能够朝着产生基准情形的方向推进。 - 3.设计法则(design rule)
假设所有的递归调用都能运行。 - 4.合成效益法则(compound interest rule)
在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
4.总结
对于面对大量输入的算法，它所花费的时间是一个判别其好坏的重要标准。速度是相对的。
