intpart在C语言中怎么运用,《数据结构和算法分析---C语言描述》读书笔记
一、绪论
1、导致递归的四个基本法则：
(1)基准情形：必须总有某些基准情形，它无须递归就能解出，这就好比数学归纳法中的第一步，证明基本情况
(2)不断推进：每一次递归调用都必须要使求解状况朝接近基准情形的方向推进
(3)设计法则：所有的递归调用都能运行
(4)合成效益法则：在求解一个问题时，切勿在不同的递归调用中做重复的工作，
例如斐波那契序列不符合这一条，
f(n)= f(n-1)+f(n-2)
而f(n-1) = f(n-2)+f(n-3)，这当中就和f(n)重复了，所以效率很低。
2、只使用处理I/O的printDigit函数编写一个过程以输出任意整数(可以是负数)
/*打印出一个整数*/
voidprintOut(intn)
{
/*该整数的中间数都以正数打出*/
if(abs(n) >= 10)
{
printOut(n/10);
printf("%d", abs(n%10));
} else//第一个数字按原样打出
printf("%d", n%10);
}
/*打印一个实数n，pointNum小数点位数*/
voidprintReal(doublen,intpointNum)
{
/*整数部分*/
intintPart, i, dicInt = 0;
/*小数部分*/
doubledicPart;
intPart = n;
dicPart = n - intPart;
/*打印整数部分*/
printOut(intPart);
if(pointNum > 0)
{
/*打印小数点*/
printf(".");
/*将小数部分转换为整数*/
for(i = 0; i
{
dicPart *= 10;
}
/*小数部分符号都弄为正数*/
dicInt = abs(dicPart);
/*打印出小数部分*/
printOut(dicInt);
}
}
3、
1.5证明：
(1)logX0成立
令f(x) = logX/X，只需证明f(X)在X>0时小于1即可然后求导，知道当X=2时取的最大值f(x)=f(2)=1/2<1
(2)log(A的B次方)=log(A*A*......A) [共有B个A相乘]
= logA+logA+logA+.......+logA 【共有B个logA相加】
= BlogA
1.6求下列各和：
a.采用等比数列的求和公式求得Sa
b.令和=Sb，则4*Sb -Sb=3*S=1+1/4+1/(4*4)+......=Sa
c.4*Sc-Sc = ......+(i*i-(i-1)*(i-1))/(4*4...共i-1个4相乘)+....=.....+(2*i-1)/(4*4...共i-1个4相乘)......=2*Sb-Sa
d.
1.7
(1+1/2+....1/N)-(1+1/2+.....1/(N/2))=logN-log(N/2)=log2.
1.8
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
2
4
8
6
2
4
8
6
2
4
8
6
2
4 2(100)=2(4)(25)
2(4)的尾数为6，则mod5为1,2(100)mod5也是1
1.9
a.数学归纳法
b.数学归纳法
1.10
a.S=2*(1+2+3+......+N)-N=2*(1+N)*N/2-N = N+N*N-N=N*N
b.数学归纳法
二、算法分析
1、
2、
法则一：如果T1(N)=O(f(N))且T2(N) = O(g(N))，那么：
T1+T2 = max(O(f(N)) ，O(g(N)))；
T1*T2 = O(f(N)*g(N))
法则二：
如果T(N)是一个k次多项式，则T(N) = Θ(N的k次方)
法则三：
对任意常数k，(logN)的k次方 = O(N)
3、当递归正常使用时，将其转换成为一个简单的循环结构是相当困难的。
4、求序列中最大子序列和的算法：
5、对数最常出现的规律概括为：
如果一个算法用常数时间(O(1))将问题的大小削减为其一部分，通常是1/2，那么算法就是O(logN)，另一方面，如果使用常数时间只是把问题减少为一个常数(如将问题减少1)，那么这种算法就是O(N)
对分查找的时间复杂度为：O(logN)
时间复杂度为：O(logN)
6、定理：
如果M>N,则M mod N < M/2
第七行还可以写成：
return Pow(X,N-1)* X;
但是不能写成：
return Pow(Pow(X,2),N/2)；
return Pow(Pow(X,2),N/2);
因为在N=2时，会产生无限循环，因为当N=2时，递归调用Pow中有一个是以2作为第二个参数。
同时，return Pow(X,N/2)*Pow(X,N/2);这种方式影响效率，因为产生两个递归调用。
2.1、按增长率排列 下列函数：
2/N,37，N的开方，N,NloglogN,NlogN,Nlog(N*N)，NlogN*logN，N(1.5)，N*N,N*N*logN，N*N*N，2(N/2)，2(N)
其中NlogN,Nlog(N*N)以相同的增长率增长
2.2、
a.成立
b.不
c.不成立
d.不成立
2.3对两个数同时求对数，然后洛必达法则
2.4
罗比达法则，应用k次，最后还是为0
2.5
Let PfOO (NO) = 1 whenNO is even, and NO whenNO is odd. Likewise, let gO(NO) = 1 whenNO isodd, and NO whenNO is even. Then the ratio PfOO (NO) / g O(NO) oscillates between 0 and ∞.
2.6
(1)O(N)
(2)O(N*N)
(3)O(N*N*N)
(4)O(N*N)
(5)O(N*N*N*N*N)
(6)O(N*N*N*N)
*****************************************************************************************************************************************************************************************
2013年5月16日更新
*****************************************************************************************************************************************************************************************
三、表、栈、队列
1、
*****************************************************************************************************************************************************************************************
2013年5月16日更新
*****************************************************************************************************************************************************************************************