- 递归
- 斐波那契数列
- 青蛙跳台阶问题
- 链表倒序打印
- 分治法
- 二分查找/折半查找 Binary Search
- 题目1：快速幂
- 题目2：如何判断一个数是否为2的次幂
指在函数的定义中使用函数自身的方法。（在栈区消耗空间）
- 特点：
- ① 必须可以分解成若干个规模较小，但是与原问题形式相同的子问题。并且这些子问题可以用完全相同的解决思路来进行解决。
- ② 递归问题的演化过程是一个把原问题从大到小进行拆解的过程，并且会有一个明确的终点。最后从这个临界点开始，把小问题的答案原路返回，原问题便得以解决。
- 步骤：
- ① 确定函数功能
- ② 找出递归结束的条件
- ③ 函数的主体（函数等价关系式）
f(1) = 1; f(2) = 1; f(n) = f(n-1) + f(n-2)
#include -
经调试观察，50以上就巨慢了 因为函数调用的次数以等比数列疯狂增长
-
优化思路：保存已经计算过的结果，下次可以直接进行调用，加快计算。
-
继续优化：
实际上，递归并不是唯一的解决方式，甚至也不是最好的方式，原因也正在于递归的特性：递归问题的演化过程是一个把原问题从大到小进行拆解的过程，并且会有一个明确的终点。最后从这个临界点开始，把小问题的答案原路返回，原问题便得以解决。
基于以上，这是一个从大到小又从小返回到大得到结果的过程，那直接从小到大得到结果不是更快？同时，递归基于栈，实际上是消耗空间的，而从小到大利用循环的思路进行计算，已经计算过的小的都没有意义了，所以实际上所需要的空间也并不多，时间消耗为O(n)，遍历一次，空间消耗为O(1)，三个变量（i-2，i-1，i）即可。
#includeunsigned int Fibonacci2(unsigned int n){ if (n == 2 || n == 1) return 1; if (n == 0) return 0; unsigned int fn; unsigned int fn_1 = 1; unsigned int fn_2 = 1; unsigned int i; for (i = 3; i <= n; i++) { fn = fn_1 + fn_2; fn_2 = fn_1; fn_1 = fn; } return fn; } int main() { unsigned int nResult1 = Fibonacci2(50); printf("%u\n",nResult1); return 0; }
-
问题：一次性可以跳1个台阶，也可以一次性跳2个台阶，那么n级台阶一共有多少种跳法？
-
规律类似于Fibonacci数列，代码如下：
递归做法： public static int jump(int n){ if (n==0) return 0; if (n==1) return 1; if (n==2) return 2; return jump(n-1)+jump(n-2); } 非递归做法： public static int jump2(int n){ if (n==0) return 0; if (n==1) return 1; if (n==2) return 2; int n1=1; int n2=2; int count=2; while (count++<=n){ int tmp=n1; n1=n2; n2=tmp+n2; } return n2; }
升级版问题：一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
-
当n = 1 时， 只有一种跳法，即1阶跳：Fib(1) = 1;
当n = 2 时， 有两种跳的方式，一阶跳和二阶跳：Fib(2) = Fib(1) + Fib(0) = 2;
当n = 3 时，有三种跳的方式，第一次跳出一阶后，后面还有Fib(3-1)种跳法；
第一次跳出二阶后，后面还有Fib(3-2)中跳法；第一次跳出三阶后，后面还有Fib(3-3)种跳法，
因此Fib(3)=Fib(2)+Fib(1)+Fib(0)=4;
…当n = n 时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法；
第一次跳出二阶后，后面还有Fib(n-2)中跳法
…
第一次跳出n阶后, 后面还有Fib(n-n)中跳法.Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+…+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+…+Fib(n-1)
又因为Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+…+Fib(n-2)
两式相减得：Fib(n)-Fib(n-1)=Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 2
public int Jump3(int n) {
if (n <= 1) {
return 1;
} else {
return 2 * Jump3(n - 1);
}
}
进阶版问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法？
- 先列多项式：
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-m)
f(n-1) = f(n-2) + f(n-3) + … + f(n-m) + f(n-m-1)
化简得：f(n) = 2f(n-1) - f(n-m-1) - 代码如下：
public static int Jump4(int n,int m ) {
//当大于m的时候是上面的公式
if(n > m){
return 2*Jump4(n-1, m)-Jump4(n-1-m, m);
}
//当小于等于m的时候就是和n级的相同了
if (n <= 1) {
return 1;
} else {
return 2 * Jump4(n - 1,n);
}
}
PS：倒序打印和倒置是不一样的，前者链表结构不变，只是倒序打印，后者链表结构发生改变，方向进行变化了。
-
方案：
-
入栈出栈
- 时间O(n)；空间O(n)
-
递归（下一个≠NULL，打印下一个，再打印本节点）
-
时间O(n)；空间O(n)
-
代码如下：
void ReversePrint(List *pHead){ if (pHead == NULL) return; ReversePrint(pHead->pNext); printf("%d\t",pHead->nValue); }
-
-
利用数组（链表节点值加入数组，倒序遍历数组）
- 时间O(n)；空间O(n)
-
头插法倒置链表，然后遍历，完成后再倒置复原链表就行
- 三次遍历 时间O(n) ；无空间消耗 空间O(1)
-
-
定义：
把一个大规模、高难度的问题分解为若干个小规模、低难度的小问题，再将多个小问题的解合并成大问题的解。（大数据集上优势明显）
-
需要用分治法进行解决的问题的特性：
- 问题难度随着数据规模的缩小而降低
- 能够分解成小规模的问题
- 解可以合并
- 子问题的解相互独立
-
二分是典型的分治法其中的一个处理方法，快排和归并也都是分治法的运用。
-
二分查找的前提：必须有序
-
代码：
//二分查找代码实现 #include//递归方式 int BinarySearch(int arr[],int nBegin,int nEnd,int nNum){ if(arr == NULL || nBegin > nEnd) return -1; //int nMid = (nBegin + nEnd)/2; //不知道给定的数据是多大，如果很大的话，相加可能会超出int的上限出现问题，所以要进行优化 int nMid = nBegin + (nEnd - nBegin)/2; if (arr[nMid] == nNum) { return nMid; } if (arr[nMid] > nNum) { //左侧 return BinarySearch(arr, nBegin, nMid-1, nNum); }else { //右侧 return BinarySearch(arr, nMid+1, nEnd, nNum); } } //循环方式 int BinarySearch1(int arr[],int nBegin,int nEnd,int nNum){ if(arr == NULL || nBegin > nEnd) return -1; int nMid; //找到中间位置，比较 while (nBegin <= nEnd) { nMid = nBegin + (nEnd-nBegin)/2; if (arr[nMid] == nNum) { return nMid; }else if (arr[nMid] > nNum) { //左侧 nEnd = nMid - 1; }else { //右侧 nBegin = nMid + 1; } } return -1; } int main() { int arr[] = {1,2,3,4,5,6,7,8}; int nIndex = BinarySearch(arr,0,sizeof(arr)/sizeof(arr[0])-1,4); int nIndex2 = BinarySearch1(arr,0,sizeof(arr)/sizeof(arr[0])-1,5); printf("%d\n%d\n",nIndex,nIndex2); return 0; }
快速计算一个数字的n次方
-
确定奇偶（n%2 == 1 为奇数）
- 奇： x ∗ x ( n − 1 ) / 2 ∗ x ( n − 1 ) / 2 x* x^{(n-1)/2} * x^{(n-1)/2} x∗x(n−1)/2∗x(n−1)/2
- 偶： x n / 2 ∗ x n / 2 x^{n/2} * x^{n/2} xn/2∗xn/2
-
代码：
#includeint FastPower(int nNum,int n){ if (n == 0) return 1; if (n == 1) return nNum; if (n%2 == 1) { //奇数 return nNum*FastPower(nNum,n-1); }else { //偶数 int nValue = FastPower(nNum, n/2); return nValue*nValue; } } int main(){ int nResult = FastPower(2, 7); printf("%d\n",nResult); return 0; } - 2的50次方用上述的代码运行后得到0，因为int存不下这么大的数发生了截断。
- 取余+除法：先取余，如果==0，再使用除法
- int类型的数字最大也就32次方，就直接乘法然后判断每次乘完和这个数比较就行
- 二进制里是否只有一个1（原二进制数和原二进制数减1进行&运算是否得到0，即 n&(n-1) == 0）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）