第一章算法的基本概念
第一章算法的基本概念
1.1 引言
算法设计与分析在计算机科学与技术中的地位
算法（Algorithm）一词的由来。
1.1.1 算法的定义和特征
欧几里德算法：
算法1.1欧几里德算法
输入：正整数m,n
输出：m,n的最大公因子
1. int euclid(int m,int n)
2. {
3. int r;
4. do {
5. r = m % n;
6. m = n;
7. n = r;
8. } while(r)
9. return m;
10. }
一、算法的定义：
定义1.1算法是解某一特定问题的一组有穷规则的集合。
二、算法的特征：
1．有限性。算法在执行有限步之后必须终止。
2．确定性。算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。
3．输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。算法的输入是从特定的对象集合中抽取的。
4．输出。一个算法有一个或多个输出，这些输出，和输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。
1
5．能行性。算法的能行性指的是算法中有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。
1.1.2 算法设计的例子，穷举法
一、穷举法，是从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解。
二、例
例1.1百鸡问题。
“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”
a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程：
b
+c
a（1.1.1）
+
100
=
b
a（1.1.2）
+
+c
5=
100
3/
3
c（1.1.3）
%=
3
1。第一种解法：
a、b、c的可能取值范围：0 ~ 100，对在此范围内的，a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。
把问题转化为用n元钱买n只鸡，n为任意正整数，则方程（1.1.1）、（1.1.2）变成：+（1.1.4）
n
a=
+
c
b
3
+3/
5（1.1.5）
+
c
n
b
a=
算法1.2百鸡问题
输入：所购买的三种鸡的总数目n
输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]
1. void chicken_question(int n,int &k,int g[],int m[],int s[])
2. {
3. int a,b,c;
4. k = 0;
5. for (a=0;a<=n;a++)
6. for (b=0;b<=n;b++)
7. for (c=0;c<=n;c++) {
8. if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) {
9. g[k] = a;
10. m[k] = b;
11. s[k] = c;
12. k++;
13. }
2
14. }
15. }
16. }
17. }
执行时间：外循环：1
n次，
+
中间循环：)1
+n
?
n次，
)1
(+
(
内循环：)1
?
+n
n次。
+
n
)1
)1
(
(
?
(+
当100
n时，内循环的循环体执行次数大于100万次。
=
2。第二种解法：
公鸡只数：~
05/n
母鸡只数：~
03/n
母鸡只数：b
-
=。
n
c-
a
算法1.3改进的百鸡问题
输入：所购买的三种鸡的总数目n
输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[]
1. void chicken_problem(int n,int &k,int g[],int m[],int s[])
2. {
3. int i,j,a,b,c;
4. k = 0;
5. i = n / 5;
6. j = n / 3;
7. for (a=0;a<=i;a++)
8. for (b=0;b<=j;b++) {
9. c = n – a – b;
10. if ((5*a+3*b+c/3==n)&&(c%3==0)) {
11. g[k] = a;
12. m[k] = b;
13. s[k] = c;
14. k++;
15. }
16. }
17. }
18. }
执行时间：外循环：1
n
5/+
内循环：)1
?
+n
n
3/
(+
(
)1
5/
3
当100
21=
34
?次。
n时，内循环的循环体的执行次数为714
=
对某类特定问题，在规模较小的情况下，穷举法往往是一个简单有效的方法。
例1.2货郎担问题。
n个城市，分别用1到n的数字编号，问题归结为在有向赋权图>
G,中，寻找一
= V 条路径最短的哈密尔顿回路。其中，} ,2,1 ) , (表示城市 j i∈ =，表示城市顶点，边E V {n i到城市j的距离，n ,2,1 ,=。 j i 图的邻接矩阵C：表示各个城市之间的距离，称为费用矩阵。 数组T：表示售货员的路线，依次存放旅行路线中的城市编号。 售货员的每一条路线，对应于城市编号n 2,1的一个排列。n个城市共有!n个排列， 采用穷举法逐一计算每一条路线的费用，从中找出费用最小的路线，便可求出问题的解。 算法1.4 穷举法版本的货郎担问题 输入：城市个数n,费用矩阵c[][] 输出：旅行路线t,最小费用min 1. void salesman_problem(int n,float &min,int t[],float c[][]) 2. { 3. int p[n],i = 1; 4. float cost; 5. min = MAX_FLOAT_NUM; 6. while (i <= n!) ( 7. 产生n个城市的第i个排列于p; 8. cost = 路线p的费用； 9. if (cost < min) { 10. 把数组p的内容拷贝到数组t； 11. min = cost; 12. } 13. i++; 14. } 15. } 执行时间：while循环执行!n次。 表1.1 算法1.4的执行时间随n的增长而增长的情况 4 5 1.1.3 算法的复杂性分析 问题：效率和方法。 问题一：如何设计算法，算法的设计方法。 问题二：如何分析算法，算法的复杂性分析。 用算法的复杂性来衡量算法的效率。算法的时间复杂性和算法的空间复杂性。算法的时间复杂性越高，算法的执行时间越长；反之，执行时间越短。算法的空间复杂性越高，算法所需的存储空间越多；反之越少。 1.2 算法的时间复杂性 一、算法复杂性的度量？ 二、如何分析和计算算法的复杂性？ 1.2.1 算法的输入规模和运行时间的阶 一、算法的输入规模和运行时间 令百鸡问题的第一、二两个算法，其最内部的循环体每执行一次，需1μs 时间。 100=n 的内循环次数 时间 10000=n 的内循环次数 时间 第一个算法 100万次 1s 3 10000 11天零13小时 第二个算法 714次 714μs )13/10000()15/10000(+?+ 6.7秒 202=n 选择排序需6.4天 合并排序需20秒 算法的执行时间随问题规模的增大而增长的情况。 二、算法运行时间的评估 不能准确地计算算法的具体执行时间 不需对算法的执行时间作出准确地统计（除非在实时系统中） 1、计算模型：RAM 模型（随机存取机模型）、图灵机模型等 2、初等操作：所有操作数都具有相同的固定字长；所有操作的时间花费都是一个常数时间间隔。算术运算；比较和逻辑运算；赋值运算，等等； 例：输入规模为n ，百鸡问题的第一个算法的时间花费，可估计如下： 33221)1(4)1(16)1()1(21)1(21)(++++++++++++≤n n n n n n n T 2769632023+++=n n n （1.1.6） 可把)(1n T 写成： 0)(13 1*1>≈c n c n T （1.1.7） 6 这时，称)(*1n T 的阶是3n 。 百鸡问题的第一个算法的时间花费： ) 13/()15/()4103()13/()15/(215/)15/(21221)(2+?+?+++ +?+?++++?++++≤n n n n n n n T 2815 16115192++= n n （1.1.8） 同样，随着n 的增大，)(2n T 也可写成： 0)(22 2*2>≈c n c n T （1.1.9） 这时，称)(*2n T 的阶是2n 。把)(*1n T 和)(*2n T 进行比较，有： n c c n T n T 2 1 *2*1)(/)(= （1.1.10） 当n 很大时，21/c c 的作用很小。 3、算法时间复杂性的定义： 定义1.2 设算法的执行时间)(n T ，如果存在)(*n T ，使得： 0) ()()(lim *=-∞→n T n T n T n （1.1.11） 就称)(*n T 为算法的渐近时间复杂性。 表1.2表示时间复杂性的阶为n n n n n n n 2,,,log ,,log 32，当16432,,2,2 =n 时，算法的渐近运行时间。这里假定每一个操作是s n 1。 表1.3表示对不同时间复杂性的算法，计算机速度提高后，可处理的规模2n 和1n 的关系。 表1.2 不同时间复杂性下不同输入规模的运行时间 7 n ：纳秒 μ：微秒 ms ：毫秒 s ：秒 h ：小时 d ：天 y ：年 c ：世纪 表1.3 计算机速度提高10倍后，不同算法复杂性求解规模的扩大情况 4、多项式时间算法和指数时间算法。 1.2.2 运行时间的上界，O 记号 一、O 记号的定义： 定义1.3 令N 为自然数集合，+R 为正实数集合。函数f ：+→R N ，函数g ：+→R N ，若存在自然数0n 和正常数c ，使得对所有的0n n ≥，都有)()(n cg n f ≤，就称函数)(n f 的阶至多是))((n g O 。 因此，如果存在)(/)(lim n g n f n ∞ →，则： ∞≠∞ →) () (lim n g n f n 即意味着： ))(()(n g O n f = 含义：)(n f 的增长最多象)(n g 的增长那样快。称))((n g O 是)(n f 的上界。 二、例：百鸡问题的第二个算法，由式（1.1.8）有： 2815161 1519)(22++≤n n n T 取0n =28，对0n n ≥?，有： n n n n T ++≤ 151611519)(22 n n 1517615192+= 2 215 1761519n n +≤ 213n = 令13=c ，并令2)(n n g =，有： 8 )()(22n cg cn n T =≤ 所以，)())(()(22n O n g O n T ==。 这时，如果有一个新算法，其运行时间的上界低于以往解同一问题的所有其它算法的上界，就认为建立了一个解该问题所需时间的新上界。 1.2.3 运行时间的下界，Ω记号 一、Ω记号的定义： 定义1.4 令N 为自然数集合，+R 为正实数集合。函数f ：+→R N ，函数g ：+→R N ，若存在自然数0n 和正常数c ，使得对所有的0n n ≥，都有)()(n cg n f ≥， 就称函数)(n f 的阶至少是))((n g Ω。 因此，如果存在)(/)(lim n g n f n ∞ →，则： 0) () (lim ≠∞ →n g n f n 即意味着： ))(()(n g n f Ω= 含义：)(n f 的增长至少象)(n g 那样快。表示解一个特定问题的任何算法的时间下界。 二、例：百鸡问题的第二个算法第11、12、13、14行，仅在条件成立时才执行，其执行次数未知。假定条件都不成立，这些语句一次也没有执行，该算法的执行时间至少为： ) 13/()15/()103()13/()15/(215/)15/(21221)(2+?+?++ +?+?++++?++++≥n n n n n n n T 245 43 2++ =n n 2n ≥ 当取0n = 1时，0n n ≥?，存在常数1=c ，2)(n n g =，使得： )()(22n cg n n T =≥ 三、结论1.1 )(n f 的阶是))((n g Ω，当且仅当)(n g 的阶是))((n f O 。 1.2.4 运行时间的准确界，Θ记号 百鸡问题的第二个算法，运行时间的上界是213n ，下界是2n ，这表明不管输入规模如何变化，该算法的运行时间都界于2n 和213n 之间。这时，用记号Θ来表示这种情况，认为这个算法的运行时间是)(2n Θ。Θ记号表明算法的运行时间有一个较准确的界。 一、Θ记号的定义如下： 定义1.5 令N 为自然数集合，+R 为正实数集合。函数f ：+→R N ，函数g ：+→R N ，若存在自然数0n 和两个正常数210c c ≤≤，使得对所有的0n n ≥，都有： )()()(21n g c n f n g c ≤≤ 9 就称函数)(n f 的阶是))((n g Θ。 因此，如果存在)(/)(lim n g n f n ∞ →，则： c n g n f n =∞ →) () (lim 即意味着： ))(()(n g n f Θ= 其中，c 是大于0的常数。 二、例： 例1.3 常函数4096)(=n f 。 令0n = 0，4096=c ，使得对)(n g = 1，对所有的n 有： )(14096)(n cg n f =?≤ ∴ )1())(()(O n g O n f == )(14096 )(n cg n f =?≥ ∴ )1())(()(Ω=Ω=n g n f 。 )()()(n cg n f n cg ≤≤ ∴ )1()(Θ=n f 。 例1.4 线性函数25)(+=n n f 。 令0n = 0，当0n n ≥时，有n n g c ==)(,51，使得： )(5)(1n g c n n f =≥ ∴ )())(()(n n g n f Ω=Ω=。 令0n = 2，当0n n ≥时，有：n n g c ==)(,62 n n n f +≤5)( n 6= )(2n g c = ∴ )())(()(n O n g O n f ==。 同时，有： )()()(21n g c n f n g c ≤≤ ∴ )()(n n f Θ=。 例1.5 平方函数238)(2++=n n n f 。 令0n = 0，当0n n ≥时，有21)(,8n n g c ==，使得： )(8)(12n g c n n f =≥ ∴ )())(()(2n n g n f Ω=Ω=。 令0n = 2，当0n n ≥时，有：22)(,12n n g c == n n n n f ++≤38)(2 212n ≤ )(2n g c = ∴ )())(()(2n O n g O n f ==。 同时，有： )()()(21n g c n f n g c ≤≤ ∴ )()(2n n f Θ=。 结论1.2 令： 0)(0 111>++++=--k k k k k a a n a n a n a n f 10 则有：)()(k n O n f =，且)()(k n n f Ω=，因此，有：)()(k n n f Θ=。 例1.6 指数函数225)(n n f n +?=。 令0n = 0，当0n n ≥时，有n n g c 2)(,51==，使 )(25)(1n g c n f n =?≥ ∴ )2())(()(n n g n f Ω=Ω=。 令0n = 4，当 0n n ≥ 时，有：n n g c 2)(,62== n n n f 225)(+?≤ n 26?≤ )(2n g c = ∴ )2())(()(n O n g O n f ==。 同时，有： )()()(21n g c n f n g c ≤≤ ∴ )2()(n n f Θ=。 例1.7 对数函数2log )(n n f =。 因为： n n l o g 2l o g 2= 令0n = 1，11=c ，32=c ，n n g log )(=，有： )(log 2)(21n g c n n g c ≤≤ ∴ )log (log 2n n Θ=。 结论1.2’ 对任何正常数k ，都有：)log (log n n k Θ= 例1.8 函数∑== n j j n f 1 log )( ∑∑==≤n j n j n j 1 1 log log n n log = 令0n = 1，11=c ，n n n g log )(=，有： )(log 1 1 n g c j n j ≤∑= ∴ )log ())((log 1 n n O n g O j n j ==∑= 另一方面，假定n 是偶数， ∑ ∑ ==≥ 2 /1 1 2 log log n j n j n j =2log 2n n )1log (2 -=n n )2log log (4 -+= n n n 11 因此，令0n = 4，4/12=c ，n n n g log )(=，对所有的0n n ≥，都有： n n j n j log 41 log 1 ≥∑= )(2n g c = ))((n g Ω= )log (n n Ω= 因此，有： )(log )(1 1 2n g c j n g c n j ≤≤ ∑= 所以， )log ())((log 1 n n n g j n j Θ=Θ=∑= 结论1.2’’ )l o g (!l o g n n n Θ=。 1.2.5 复杂性类型和o 记号 一、复杂性的分类 定义1.6 令R 是函数集合F 上的一个关系，F F R ??，有 {}))(()(|,n g n f F g F f g f R Θ=∧∈∧∈><= 则R 是自反、对称、传递的等价关系，它诱导的等价类，称阶是)(n g 的复杂性类型的等价类。 所有常函数的复杂性类型都是)1(Θ； 所有线性函数的复杂性类型都是)(n Θ； 所有的2阶多项式函数的复杂性类型都是)(2n Θ，如此等等。 例： 4096)(=n f ， 23)(+=n n g ， ? 0n = 1，1365=c ，? 0n n ≥，有 )()(n cg n f ≤。 ∴)())(()(n O n g O n f ==。 又： 02 34096lim )()(lim =+=∞→∞ →n n g n f n n ∴))(()(n g n f Ω≠，则：))(()(n g n f Θ≠。 ∴ 4096)(=n f 和23)(+=n n g 是属于不同复杂性类型的函数。 例： n n =2log )l o g (!l o g n n n Θ= )log (!log n n cg n ≤ 由 n n n log < ? 00≥n ，0≥c ，? 0n n ≥ 有!2cn n ≤ ∴ )!(2n O n = 12 021222lim !2lim =????=∞→∞→n n n n n ∴ )!(2n n Ω≠ n 2和!n 是属于不同复杂性类型的函数。 例： )log (!log n n n Θ= n n n n log 2log 22 >= )2(!2n O n = )!(22 n O n ≠。 这两个函数也是属于不同复杂性类型的函数。 二、o 记号的定义 定义1.7 令N 为自然数集合，+R 为正实数集合。函数f ：+→R N ，函数g ：+→R N ，若存在自然数0n 和正常数c ，使得对所有的0n n ≥，都有 )()(n cg n f < 就称函数)(n f 是))((n g o 。 由此，如果存在)(/)(lim n g n f n ∞→，则 0) () (lim =∞ →n g n f n 即意味着 ))(()(n g o n f = 结论1.3 ))(()(n g o n f = 当且仅当 ))(()(n g O n f =而))(()(n f O n g ≠。 复杂性类型体系：用偏序关系)()(n g n f 表示))(()(n g o n f =。 2 2!2log log log log 124/3n n n n n n n n n n n 1.3 算法的时间复杂性分析 1.3.1 循环次数的统计 一、循环次数表示乘以一个常数因子的运行时间 例1.9 计算多项式： 0111)(a x a x a x a x P n n n n ++++=-- Horner 法则改写： 011))(()(a x a x a x a x P n n ++++=- 算法1.5 计算多项式 输入：存放多项式系数的数组A[],实数x,多项式的阶n 输出：多项式的值 1. float polynomial(float A[],float x,int n) 2. { 3. int i; 4. float value; 5. for (i=n;i>0;i--) { 13 6. value = A[i] * x + A[i-1]; 7. return value; 8. } 1c ：循环控制变量i 赋初值所花费的单位时间 2c ：变量i 的测试及递减、以及值value 的计算所花费的单位时间 算法的执行时间)(n T 为： n c c n T 21)(+= )(n Θ= 例1.10 把数组中n 个元素由小到大进行排序。 算法1.6 冒泡算法 输入：数组A[],元素个数n 输出：按递增顺序排序的数组A[] 1. template 2. void bubble(Type A[],int n) 3. { 4. int i,k; 5. for (k=n-1;k>0;k--) { 6. for (i=0;i 7. if (A[i] > A[i+1]) { 8. swap(A[i],A[i+1]); 9. } 10. } 11. } 12. } 13. void swap(Type &x,Type &y) 14. { 15. Type temp; 16. temp = x; 17. x = y; 18. y = temp; 19. } c ：辅助操作的执行时间 c ：循环体的平均执行时间 算法总的执行时间)(n T 为： c c n n n T +++-+-=)1)2()1(()( 14 c n n c +-= )1(2 )(2n Θ= 例1.11 选手的竞技淘汰比赛。 有k n 2=位选手进行竞技淘汰比赛，最后决出冠军的选手。假定用如下的函数： BOOL comp(Type mem1,Type mem2) 模拟两位选手的比赛，若1mem 胜则返回TRUE ，否则返回FALSE 。 并假定可以在常数时间c 内完成函数comp 的执行。 算法1.7 竞技淘汰比赛 输入：选手成员group[],选手个数n 输出：冠军的选手 1. Type game(Type group[],int n) 2. { 3. int j,i = n; 4. while (i>1) { 5. i = i / 2; 6. for (j=0;j 7. if (comp(group[j+i],group[j]); 8. group[j] = group[j+i]; 9. } 10. return group[0]; 11. } 因为k n 2=，第4行的while 循环的循环体共执行k 次。 在每一次执行时，第6行的for 循环的循环体，其执行次数分别为1,,4/,2/ n n ， 函数comp 可以在常数时间内完成。 算法的执行时间)(n T 为： n n n n n T +++= 42)( )214121(k n +++= )211(k n - = 1-=n )(n Θ= 例1.12 对n 张牌进行n 次洗牌，洗牌规则如下：在第k 次洗牌时（n k 1=），对第i 15 张牌（k n i /1 =）随机地产生一个小于n 的正整数d ，互换第i 张牌和第d 张牌的位置。 算法1.8 洗牌 输入：牌A[],牌的张数n 输出：洗牌后的牌A[] 1. template 2. void shuffle(Type A[],int n) 3. { 4. int i,k,m,d; 5. random_seed(0); 6. for (k=1;k<=n;k++) { 7. m = n / k ; 8. for (i=1;i<=m;i++) { 9. d = random(1,n); 10. swap(A[i],A[d]); 11. } 12. } 13. } 函数random_seed ：为随机数发生器产生随机数种子，需常数时间 函数random ：产生一个1到n 之间的随机数，需常数时间 第6行开始的for 循环的循环体共执行n 次。 第8行开始的内部for 循环的循环体，其执行次数依次为： ??????n n n n n /,3/,2/, 算法的执行时间)(n T 为内部for 循环的循环体的执行次数乘以一个常数时间，因此，有： ∑ =?? ????= n i i n n T 1 )( 因为： ∑∑ ∑ ===≤?? ? ???≤-n i n i n i i n i n i n 1 1 1 )1( 由调和级数的性质，有： 1ln 1 )1(ln 1 +≤≤ +∑ =n i n n i 因此： 16 1log log 1log ) 1(log 1 +≤≤ +∑=e n i e n n i 所以： n n n e i n n n n e n i +≤?? ????≤-+∑ =log log 1)1(log log 1 1 由此得出： )log ()(n n n T Θ= 1.3.2 基本操作频率的统计 一、基本操作的定义 定义1.8 算法中的某个初等操作，如果它的最高执行频率，和所有其它初等操作的最高执行频率，相差在一个常数因子之内，就说这个初等操作是一个基本操作。 初等操作的执行频率，可正比于任何其它操作的最高执行频率 基本操作的选择，必须反映出该操作随着输入规模的增加而变化的情况 二、用基本操作的执行频率估计算法的时间复杂性 例1.13 合并两个有序的子数组 假定A 是一个具有m 个元素的整数数组，给定三个下标：r q p ,,, m r q p <≤≤≤0，使得][p A ~][q A ，]1[+q A ~][r A 分别是两个以递增顺序排序的子数组。把这两个子数组按递增顺序合并在][p A ~][r A 中。 算法1.9 合并两个有序的子数组 输入：整数数组A[],下标p,q,r,元素个数m 。A[p]~A[q]及A[q+1]~A[r]已按递增顺序排序 输出：按递增顺序排序的子数组A[p]~A[r] 1. void merge(int A[],int p,int q,int r,int m) 2. { 3. int *bp = new int[m]; /* 分配缓冲区,存放被排序的元素 */ 4. int i,j,k; 5. i = p; j = q + 1; k = 0; 6. while (i<=q && j<=r) { /* 逐一判断两子数组的元素 */ 7. if (A[i]<=A[j]) /* 按两种情况,把小的元素拷贝到缓冲区*/ 8. bp[k++] = A[i++]; 9. else 10. bp[k++] = A[j++]; 11. } 12. if (i==q+1) /* 按两种情况,处理其余元素 */ 17 13. for (;j<=r;j++) 14. bp[++] = A[j++];; /* 把A[j]~A[r]拷贝到缓冲区 */ 15. else 16. for (;i<=q;i++) 17. bp[++] = A[i++]; /* 把A[i]~A[q]拷贝到缓冲区 */ 18. k = 0; 19. for (i=p;i<=r;i++) /* 最后,把数组bp 的内容拷贝导A[p]~A[r] */ 20. A[i++] = bp[k++]; 21. delete bp; 22. } p i q j r A A while 循环的循环次数、for 循环的循环次数未知 基本操作的选择： 1、数组元素的赋值操作作为基本操作，操作频率：n 2， 1）、随输入规模的增大而增加 2）、执行频率与其它操作的执行频率相差一个常数因子 算法的时间复杂性为)(n Θ。 2 、数组元素的比较操作作为基本操作 令两个子数组的大小分别为1n 和 2n ，其中，n n n =+21。 合并两个数组时，数组元素的比较次数，最少为1n ，最多为1-n 次。 图1.1 合并两个有序数组时,元素比较次数最少的情况 图1.2 合并两个有序数组时,元素比较次数最多的情况 如果合并两个大小接近相同的有序数组，例如??2/1n n =，??2/2n n =， 数组元素的比较操作，操作频率：2/n 满足上述1）2）。算法的时间复杂性仍然是)(n Θ。 例1.14 菜园四周种了n 棵白菜，并按顺时针方向由1到n 编号。收割时，从编号1开 始，按顺时针方向每隔两棵白菜收割一棵，直到全部收割完毕为止。按收割顺序列出白菜的编号。 数组A：存放白菜的编号，初值为n, ,1 。当白菜被收割后，从数组中删去相应元素数组B：按收割顺序存放被收割白菜的编号 算法1.10收割白菜 输入：白菜棵数n 输出：按收割顺序存放白菜编号的数组B[] 1. void reap(int B[],int n) 2. { 3. int i,j,k,s,t; 4. int *A = new int[n]; 5. j = 0; k = 3; s = n; 6. for (i=0;i 7. A[i] = i + 1; 8. while (j 9. t = s; s = 0; 10. for (i=0;i 11. if (--k!=0) 12. A[s++] = A[i]; /* 未被收割的白菜 */ 13. else { 14. B[j++] = A[i]; k = 3; /* 被收割的白菜 */ 15. } 16. } 17. } 18. delete A; 19. } while循环for循环的循环次数未知 基本操作的选择：14行的赋值操作需要执行n次，12行的赋值操作，需要执行n 2次算法的运行时间为) 。 (n 1.3.3 计算步的统计 一、计算步 定义1.9计算步是一个语法或语义意义上的程序段，该程序段的执行时间与输入实例无关。 例： 18 flag=(a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0); a=b; 和输入规模无关。连续200个乘法操作可为一个计算步，n次加法不能作为一个计算步计算步所表示的计算量，可能有很大的差别。 二、计算步的统计 把全局变量count嵌入实现算法的程序中，每执行一个计算步，count就加1。算法运行结束时，count的值，就是算法所需执行的计算步数。 随着输入实例的不同，按这种方式统计出来的计算步数也不同。它有助于了解算法的执行时间随输入实例的变化而变化的情况。如果输入实例的规模增大10倍，所需执行的计算步数也增加10倍，就可以认为运行时间随着n的增大而线性增加。 1.3.4 最坏情况和平均情况 一、影响运行时间的因素 问题规模的大小、输入的具体数据（除算法的性能外） 例1.15用插入法对n个元素的数组A，按递增顺序进行排序。 算法1.11 用插入法按递增顺序排序数组A 输入：n个元素的整数数组A[],数组元素个数n 输出：按递增顺序排序的数组A[] 1. void insert_sort(int A[],int n) 2. { 3. int a,i,j; 4. for (i=1;i 5. a = A[i]; 6. j = i – 1; 7. while (j>=0 && A[j]>a) { 8. A[j+1] = A[j]; 9. j--; 10. } 11. A[j+1] = a; 12. } 13. } j j +1 i 19 1.初始数组已按递增顺序排列，执行时间既是) (n O的，也是) (n Ω，所以，是) (n Θ的。 2.初始数组按递减顺序排列，每一个元素1 1,] [- ≤ ≤n i i A，都和它前面的i个元素进行比较，则整个算法执行的元素比较次数为： ∑-= -= 1 1 )1 ( 2 1 n i n n i 在这种情况下，算法的执行时间是) (2n O的，也是) (2n Ω的，所以是) (2n Θ的。 二、算法时间复杂性的三种分析 最坏情况的分析、平均情况的分析、和最好情况的分析。 1.3.5 最坏情况分析 下界和上界不一致的情况： 例 1.16 对已经排序过的、具有n个元素的数组A，检索是否存在元素x。当n是奇数时，用二叉检索算法检索；当n是偶数时，用线性检索算法检索。 算法1.12 分别采用线性检索算法和二叉检索算法进行检索的算法 输入：给定n个已排序的元素的数组A[],及元素x 输出：若x = A[j],1≤j≤n,输出j,否则输出0 1. int linear_search(int A[],int n,int x); 2. int binary_search(int A[],int n,int x); 3. int serach(int A[],int n,int x) 4. { 5. if ((n%2)==0) 6. return linear_search(A,n,x); 7. else 8. return binary_search(A,n,x); 10. } 这个算法在n是偶数时，调用线性检索算法进行检索；在n是奇数时，调用二叉检索算法进行检索。线性检索算法如下： 算法1.13 线性检索算法 输入：给定n个已排序过的元素的数组A[],及元素x 输出：若x = A[j],0≤j≤n-1,输出j,否则输出-1 1． int linear_search(int A[],int n,int x); 2． { 3． int j = 0; 4． while (j 20 一、选择题 1．以下关于算法的说法正确的是() A．描述算法可以有不同的方式，可用形式语言也可用其它语言 B．算法可以看成按照要求设计好的有限的确切的计算序列，并且这样的步骤或序列只能解决当前问题 C．算法过程要一步一步执行，每一步执行的操作必须确切，不能含混不清，而且经过有限步或无限步后能得出结果 D．算法要求按部就班地做，每一步可以有不同的结果 [答案] A [解析]算法可以看成按照要求设计好的有限的确切的计算序列，并且这样的步骤或计算序列能够解决一类问题．算法过程要求一步一步执行，每一步执行的操作，必须确切，只能有惟一结果，而且经过有限步后，必须有结果输出后终止，描述算法可以有不同的语言形式，如自然语言、框图语言及形式语言等． 2．使用计算机解题的步骤由以下几部分构成 ①寻找解题方法②调试运行 ③设计正确算法④正确理解题意 ⑤编写程序 正确的顺序为() A．④①③②⑤B．④①③⑤② C．④③②①⑤D．④①②③⑤ [答案] B 3．下列叙述能称为算法的个数为() ①植树需要运苗、挖坑、栽苗、浇水这些步骤； ②顺序进行下列运算：1＋1＝2,2＋1＝3,3＋1＝4，…，99＋1＝100； ③从枣庄乘火车到徐州，从徐州乘飞机到广州． ④3x >x ＋1； ⑤求所有能被3整除的正数，即3,6,9,12，…. A ．2 B ．3 C ．4 D ．5 [答案] B [解析] ①②③是算法，④⑤不是，故选B. 4．下列各式中S 值不可以用算法求解的是( ) A ．S ＝1＋2＋3＋4 B ．S ＝12＋22＋32＋…＋1002 C ．S ＝1＋12＋…＋110000 D ．S ＝1＋2＋3＋4＋… [答案] D [解析] 由算法的有限性知，D 不正确，而A 、B 、C 都可以通过有限步骤操作，输出确定结果，故选D. 5．结合下面的算法： 第一步，输入x . 第二步，判断x 是否小于0，若是，则输出x ＋2，否则执行第三步． 第三步，输出x －1. 当输入的x 的值为－1,0,1时，输出的结果分别为( ) A ．－1,0,1 B ．－1,1,0 C ．1，－1,0 D ．0，－1,1 [答案] C 第四章力法 一、是非题（“是”打√，“非”打） 1、图（a）所示超静定结构，力法求解时，所有副系数全为零的基本结构如图（b）所示（除BC杆EI=∞外，其余各杆EI=C）。（） 2、图（a）所示超静定结构，AC杆端剪力可由图（b）所示脱离体 用静力平衡条件直接求出。（） 3、图（a）所示超静定梁M图与图（b）所示静定梁M图相同。（） 4、图（a）所示超静定梁在均布荷载作用下的M图与图（b）所示静定梁M图图乘的结果不等于其与图（c）所示静定梁的M图的图乘结果。（） 5、图示结构中，去掉其中任意两根支座链杆后余下部分都可作为力法计算的基本体系。（） 6、图示结构中，去掉其中任意两根支座链杆后余下部分都可作为力法计算的基本体系。（） 7、图示两结构，对应点内力相同。 8、图示两结构，对应点内力相同。 9、图示两结构，对应点内力相同。（） 10、图示结构，其力法典型方程的自由项,。（） 11、图（a）所示结构，用力法求解时，可取图（b）做基本系。（） 12、图（a）所示结构，用力法求解时可取图（b）做基本系。（） 13、超静定结构在支座移动作用下一定会有内力产生。（） 14、图示结构在支座C垂直向下移动时结构的内力全为零。（） 15、对于超静定桁架，如果在结构外荷载及结构材料不变的情况下增加某些杆件的截面积，则指定处所的位移一定会减小（）。 16、某超静定梁，截面的高度为h，线膨胀系数为α，EA=常数，EI=常数。图（a）中梁上、下面的温度均升高50℃，图（b）中梁上面的温升为30℃，梁下面的温升为70℃。两种情况下梁的内力一样（）。 17、图（a）与图（b）所示结构在支座C处的反力关系为不超过。 ( ) 18、图（a）所示结构（不计杆长变化）用力法求解时可采用图（b）所示结构进行计算。（） 19、图示对称结构受对称荷载（不计杆长变化），则B支座的约束反力 0。( ) 算法的概念的教学设计 杭二中分校海玲 一．容和容解析 算法是规则系统一种循序渐进解决问题的过程，尤指一种为在有限步骤解决问题而建立的可重复应用的计算过程。（概念的涵广义） 在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题。（概念的涵狭义） 算法概念这一节，立足于用自然语言描述解决问题过程中的明确顺序，是实现用程序框图、程序语言的表示方式的基础。（容及在本章的地位） 算法的思想方法几乎贯穿整个高中数学课程的所有章节，如解三角形、数学归纳法、数学建模等．本节的容能为以后学习本章程序框图、基本算法语句以及选修1-2第四章“框图”容奠定基础．由于程序框图体现的是算法的思想，故其思想方法可运用到数学的各个领域之中．（在学科中地位）算法也是数学及其应用的重要组成部分，算法是连接人和计算机的纽带。是计算机科学的基础，利用计算机解决问题需要算法。首先研究解决问题的算法的自然语言表达，再把算法转化为程序，所以本节课学习用自然语言进行算法设计是使用计算机解决具体问题的一个极为重要的环节。（体现其应用性） 二．目标和目标解析 本节课通过对解决具体问题的过程与步骤的分析，让学生体会算法的思想，了解算法的含义。具体目标为： 1．要求学生了解算法的含义，体会算法的思想。 2．在分析实例的基础上了解算法的基本特征。 3．能够用自然语言描述一些具体问题的算法。 本节课教学重点通过实例让学生体会算法思想，会用自然语言表达一些具体问题的算法.三．教学问题诊断 本节算法对学生来说并不陌生。生活中很多问题是按照指定的要求一步步解决的；小学的四则混合运算所遵循的先乘除、后加减的规则，括号的处理规则等，都是学生最初接触到的算法实例。初中学习的方程组的解法等，也是算法的典型体现。高中学习的必修1中求函数零点的二分法的解题步骤、必修5中线性规划的解题规律等更成了算法的经典问题。还有数列的求和、质数的判定、最大公约数和最小公倍数的求法等，都涉及到算法。同时，在其他学科、甚至生活中也离不开算法。 算法的实质是将人的思维过程处理成计算机能够一步一步执行的步骤，进而转化为一步一步执行的程序。这种处理问题的方式，学生以往有一些经验，如教师对某些题型总结的较为固定的解题步骤。不过这种经验并没有得到应有的升华。只有在完整地学习了算法后，学生才能把这些知识提升到新的高度来认识。算法是对解题方案的准确而完整的构造性的描述。算法并不是容易理解和掌握的容。教学难点是对算法概念的理解和对算法的描述，尤其是对循环问题的递归语言表达，由于学生初次接触，更加难以掌握。 教师可以首先通过实际生活中的生动有趣的例子帮助学生了解算法的含义，明白算法是规则系统一种循序渐进解决问题的过程。在此基础上通过引导学生在具体情境之下回顾特殊的二元一次方程组的求解，自然展示求解的“步骤”，从而帮助学生进一步明白算法是在有限步骤解决问题而建立的可重复应用的计算过程，并能够编成计算机可以执行的程序让计算机执行并解决问题的。 在建立了算法的概念以后，教师可以通过进一步介绍学生熟悉的例子，并尝试着让学生自己举算法的例子，帮助学生进一步领会算法的思想。 接着通过例1和例2设计算法，帮助学生学会用自然语言描述算法，质数的判断是学生小学就 基本概念 1、统计的含义：统计工作、统计资料、统计学 2、社会经济统计学的特点：数量性、社会性、综合性 3、统计工作的职能：统计信息职能、统计咨询职能、统计监督职能 4、统计工作过程：统计调查、统计整理、统计分析 5、统计调查的质量要求：准确性、全面性、及时性、有效性 6、专门调查的方法：普查、重点调查、典型调查、抽样调查 7、统计调查的方法：直接观察法、报告法、采访法、通讯法、实验调查法、网上调查法 8、次数分布的主要类型：钟型分布、U型分布、J型分布 9、统计表的结构，从组成要素看，由总标题、横行与纵栏标题、指标数值等三部分组成 10、统计表的结构，从内容上看，由主词、宾词两部分构成 11、统计分析方法：综合指标、动态数列、统计指数、相关回归、抽样推断 12、综合指标从它的作用和方法特点的角度可概括为三类：总量指标、相对指标、平均指标 13、相对指标的种类：计划完成相对指标、结构相对指标、比例相对指标、比较相对指标、强度相对指标、动态相对指标 14、平均指标的种类：算术平均数、调和平均数、几何平均数、众数、中位数 15、测定标志变动度的主要方法：全距、四分位差、平均差、标准差、离散系数 16、动态数列按构成其指标数值的性质不同分为：绝对数动态数列、相对数动态数列、平均数动态数列 17、动态数列的水平分析指标：发展水平、平均发展水平、增长量、平均增长量 18、动态数列的速度分析指标：发展速度、增长速度、平均发展速度、平均增长速度 19、测定长期趋势常用的主要方法：间隔扩大法、移动平均法、最小平方法 20、指数按其反映指标性质不同分为：数量指标指数和质量指标指数 21、指数按其表现形式不同分为：综合指数、平均指数、平均指标对比指数 22、相关关系按其方向不同分为:正相关和负相关 23、相关关系按其涉及因素多少分为：单相关和复相关 24、相关关系按其形式不同分为：直线相关和曲线相关 25、抽样调查的组织形式：简单随机抽样、类型抽样、等距抽样、整群抽样、多阶段抽样 26、总体参数的抽样估计方法为点估计和区间估计。 统计分析 1．某市某“五年计划”规定计划期最末一年甲产品产量应达到75万吨，假定每天产量相等，实际生产情况如下表所示（单位：万吨）。试计算该市甲产品产量五年计划完成程度和提前完成计划的时间。 第一年第二年第三年 56 58 62 第四年一季二季三季四季 16 17 18 18 第五年一季二季三季四季 19 19 20 23 型题 ．在实际工作中，同质是指（）．被研究指标地非实验影响因素均相同．研究对象地测量指标无误差．被研究指标地主要影响因素相同．研究对象之间无个体差异．以上都对 ．变异是指（） ．各观察单位之间地差异 ．同质基础上，各观察单位之间地差异．各观察单位某测定值差异较大．各观察单位有关情况不同．以上都对 ．统计中所说地总体是指（）．根据研究目地确定地同质地全部个体．根据地区划分地研究对象地全体文档来自于网络搜索 ．根据时间划分地研究对象地全体 ．随意想象地研究对象地全体 ．根据人群划分地研究对象地全体 ．统计中所说地样本是指（） ．从总体中随意抽取一部分 ．有意识地选择总体中地典型部分 ．依照研究者地要求选取有意义地一部分 ．从总体中随机抽取有代表性地一部分 ．以上都不是 ．统计学上地系统误差、测量误差、抽样误差在实际工作中（）．均不可避免 ．系统误差和测量误差不可避免 ．测量误差和抽样误差不可避免 ．系统误差和抽样误差不可避免 ．只有抽样误差不可避免 ．抽样误差指地是（） ．个体值和参数值之差 ．个体值和样本统计量值之差 ．样本统计量值和参数值之差 ．不同地总体参数之差 ．以上都不是 ．随机测量误差使调查结果（） ．大部分偏高 ．大部分偏低 ．统一偏高或偏低 ．存在误差且该误差无规律性 ．存在误差但该误差有一定地规律性 ．抽样误差使调查结果（） ．大部分偏高 ．大部分偏低 ．统一偏高或偏低 ．存在误差且该误差无规律性 ．存在误差但该误差有一定地规律性 ．系统误差使调查结果（） ．大部分偏高 ．大部分偏低 ．统一偏高或偏低 ．存在误差且该误差无规律性 ．存在误差但该误差有规律性文档来自于网络搜索 ．统计学中可以根据（）地分布规律，对总体进行统计学推断．误差．过失误差 ．系统误差 ．随机测量误差 ．随机抽样误差 ．时间资料为（） ．名义测度资料 ．等级测度资料 ．循环测度资料 ．区间测度资料 ．比值测度资料 ．某地年来地气温（℃）资料为（） ．名义测度资料 ．等级测度资料 ．循环测度资料 ．区间测度资料 ．比值测度资料 ．分析资料时，下列哪项不作为统计分析方法选择地根据（）．研究设计地目地 ．研究设计地方案 ．资料地类型 ．资料地分布类型 ．前人地分析结果 ．小概率事件是指（是随机事件发生地概率）( ) ．≤ ．≤ . ≤ . ≤ ．＜文档来自于网络搜索 型题 ．某医生欲研究各种生化指标与糖尿病地关系，测量病人地血糖、血压、胆固醇，这些资料为（) ．名义测度资料 ．等级测度资料 ．循环测度资料 ．区间测度资料 力法的基本概念 一、超静定结构和超静定次数 1．超静定结构的概念 ①几何构造方面：有多余约束的几何不变体系。 ②力学解答方面：方程的个数少于未知力的个数。 2．超静定次数的确定 去掉多余约束使超静定结构成为静定结构，所去掉的多余约束数目，就是超静定次数。 一般地， *切断链杆（或支杆）是去掉了一个约束，相应一个约束力； *拆开一个铰（或固定铰支座）是去掉了两个约束，相应两个约束力；*切端刚结点（或固定支座）是去掉了三个约束，相应三个约束力；*刚结点变为铰结点，是去掉了一个约束，相应一个约束力； ① ②③ 二、力法的基本结构和多余未知力 1．超静定结构经过去掉多余约束后，变为静定结构，这个静定结构称为力法的基本结构。去掉的多余约束所对应的约束力，称为力法的多余约束力。基本结构、荷载与多余未知力合称基本体系。 2．基本结构的形式不唯一。 一般地，基本结构和多余未知力同时产生。选取时，应使计算简单为前提。 前例题与练习中，给出了每个结构的部分基本结构和相应的多余未知力。 三、力法原理 1．基本假设：弹性小变形 2．确定超静定次数，选取恰当的基本体系 3．位移协调条件的确定（即，补充方程的建立） 4．计算柔度系数（单位未知力产生的位移），建立力法方程 5．结构内力的叠加公式 6．作内力图 示例1 P P L X L 基本体系 解：1）一次超静定结构，取基本体系如图所示。 2）基本思路 超静定结构用平面三个平衡方程是不够的。注意到原结构在荷载作用下的内力和变形是唯一确定的，特别地，支座反力也是确定的。因此，如果设X是支座反力，则原结构的内力与变形就与基本体系（其结构是静定的）在荷载P和支座反力X共同作用下的内力与变形等价。这样，原超静定结构的计算就转化为静定结构的计算。 问题是，X是未知的。需要考虑位移协调条件，即，补充方程。显然，基本体系中，B端是自由端；而原超静定结构中却是有支座的。要保证是等价关系，就必须保证基本体系在P和X共同作用下，在B 端的竖向位移是零。其办法是： 在基本结构中，按叠加法把P和X的共同作用分别作用在基本结构上， ①荷载P作用下，在B端产生的竖向位移的计算 P P L P=1 PL M P图L M 图 刑法基本概念整理 第一章：刑法的绪论 1.刑法：即一个国家规定犯罪、刑事责任和刑罚的法律。 具体些说，刑法是掌握政权的阶级即统治阶级，为了维护本阶级政治上的统治和经济上的利益，根据自己的意志，规定哪些行为是犯罪和应负刑事责任，并给犯罪人以何种刑罚处罚的法律。 2.广义刑法：一切规定犯罪、刑事责任和刑罚的法律规范总称，包括刑法典、单行刑事法律和非刑事法律中的刑事责任条款(附属刑法规范)。 3.狭义刑法：系统规定犯罪、刑事责任和刑罚的刑法典。 4.刑法的渊源：刑法典、单行刑法、附属刑法 5.刑法典：是以国家名义颁布的、系统规定犯罪及刑法的法律，是刑法的最主要存在形式。 6.单行刑法：国家以决定、规定、补充说明、条例等名称颁布的，规定某一类犯罪及刑罚或者刑法的某一事项的法律。 7.刑法的性质：内容上——（1）调整范围的广泛性，从国家安全、公共安全、经济秩序到公民个人的人身权利、财产权利都有所涉及 （2）调整对象的特定性：针对最严重的违法行为 （3）调整手段的严厉性：刑罚是国家最严厉的强制方法 形式上——（1）刑法是基本法（2）刑法是实体法（3）刑法是公法 8.刑法的目的：就在于惩罚犯罪，保护人民。保护法益 9.刑法的任务：就是用刑罚同一切犯罪行为作斗争，保护人民，打击敌人，为社会主义建设事业服务。 10.刑法的机能：就是刑法在社会生活中应当具备的作用，它是实现刑法目的和任务的手段。（1）保护法益机能（2）保障人权机能（3）规制行为机能 11.谦抑思想：就是不应当将所有的违法行为都作为刑法的处罚对象，作为刑法处罚对象的只能是那些不得不予以刑罚处罚的行为。 12.刑法规范：是以禁止、处罚犯罪行为为内容的罪刑规范。（包括行为规范和裁判规范）如刑法规定有盗窃罪、遗弃罪，其中所蕴含的规范就是：不得盗窃、义务者必须抚养没有独立生活能力的人。 13.刑法的体系：是指刑法典的组成和结构。我国刑法是采用编、章、节、条、款、项的结构来编排的。我国刑法典分为①总则②分则③附则。 14.刑法解释：是对刑法规定用语的意义进行说明，是赋予刑法规范特定含义的思维或者实践过程。 分类：（1）主体不同 立法解释——全国人大代表大会及其常务委员会对刑法规定所做的解释 司法解释——由最高人民法院和最高人民检察院就审判和检查工作中具体应用的法律解释（2）方法不同 文理解释——亦称文意解释或者文法解释，是根据刑法条文的文词字句进行的字面解释。论理解释——指参酌立法背景、目的、沿革及其他相关事项，对刑法规定做逻辑分析，阐明刑法用语真实含义的解释方法。 （当然解释）——指刑法没有明文规定的事项，但依事物属性、处罚目的以及当然的道理，推论刑法所没有明文规定的事项，但要在刑法规定适用范围之内。 （扩大解释）（限定解释） 第六部分法律——第二十六章法的一般原理 第六部分法律 第二十六章法的一般原理 本章知识点 【知识点一】法的概念、本质和基本特征 【知识点二】法律规则的逻辑构成和分类 【知识点三】法的制定和法律解释 【知识点四】法的功能和效力 【知识点一】法的概念、本质和基本特征 建议关注法的类型、本质、基本特征。 （一）法的概念 1.法是由一定物质生活条件决定的，体现统治阶级意志，由国家制定或认可并由国家强制力保证实施的，以维护、巩固和发展一定的社会关系和社会秩序为目的的具有普遍效力的行为规范体系。 2.法的类型 （二）法的本质 1.法的阶级性：法反映的是整个统治阶级的整体利益和共同意志。 2.法的国家意志性：只有通过合法的程序，上升为国家意志的那部分统治阶级意志才能成为法。 3.法的物质制约性：法最终决定于构成物质关系的社会物质生活条件。 （三）法的基本特征 1.法是一种特殊的社会规范：特殊强制性。 2.法由国家制定或认可。 3.法以权利和义务为内容。 4.法由国家强制力保证实施：是法区别于其他社会规范的重要标志。 5.法在国家权利管辖范围内普遍有效，具有普遍性。 6.法是具有严格程序规定的规范。 【经典例题】 【例题·单选题】（2016年）根据马克思主义的观点，法的本质可以概括为阶级性、国家意志性和物质制约性等多个方面，但作为一种上层建筑，法最终决定于（）。 A.社会物质生活条件 B.统治阶层的意志 C.国家的意志 D.多数公民的意志 『正确答案』A 『答案解析』本题考查法的本质。法最终决定于构成物质关系的社会物质生活条件。 【知识点二】法律规则的逻辑构成和分类 建议关注法律规则和法律条文的区别、法律规则的分类。 （一）法律规则的逻辑构成 【例如】酒类经营者不得向未成年人销售酒类商品，并应在经营场所显著位置予以明示，违反规定的，给予警告，责令改正；情节严重的，处两千元以下罚款。 2.法律规则与法律条文的区别 （1）法律规则是法律条文的内容，法律条文是法律规则的表现形式。 （2）并不是所有的法律条文都直接规定法律规则。 （3）不是每一个法律条文都完整地表述一个规则或只表述一个法律规则。 【例如】当事人协商一致，可以变更合同。 （二）法律规则的分类 第一节法律的基本概念 一、法律的基本概念 （一）法或法律的定义： 法的定义：法是反映统治阶级意志的，由国家制定或认可并以国家强制力保证实施的行为规范总和。 “法律”，通常那广义和狭义两种含义以上使用。 广义的“法律”通“法”同义。 狭义的法律，是指拥有立法权的国家机关依照法定程序和颁布的规范性文件。 在我国，由全国人大和全国人大常委会制定和颁布的规范性文件，称为法律。 （二）法的特征 法的特征：指区别于其他社会规范所持有的属性。 特征：1、法是由国家制定或认可的规范。制定或认可是国家创造法的两种形式。 2、法是有国家强制力保证实施的规范。 3、法是制定人们权利和义务的规范。 4、法具有普遍约束力的规范。 （三）法的本质 法的本质：指法的质的规定性，是法的内在、基本的物质精神因素的总和，是法存在的基础和发展变化的决定力量。 要点：1、法是统治阶级意志的体现。 2、法的内容是统治阶级的物质生活条件所决定的。经济基础对法具有决定作用。 二、法律价值和法律理念 （一）法律的价值 首先：法具有服务性价值，它确认和保护、发展对统治阶级有利的社会关系和社会秩序，它确立规则，使资源得到合理的分配。其次：法本身还具有权利和义务相一致的价值、相对稳定相的价值、是国家权力运用公开化的价值等。只有当法律符合或能够满足人们的需要时，法律才有价值可言。 （二）法律的理念 法律的理念是对法律的本质、精神、基本原则和运行机制的理性认识和价值取向上的意识形态，它基于某种基本的法律制度而产生。 依法治国是社会主义法治的核心内容，执法为民是社会主义法治的本质要求，公平公正是社会主义法治的价值追求，服务大局是社会主义法治的重要使命。 三、法律的形式和体系 （一）法律的形式 国家机关制定的各种规范性文件是法律的主要形式。 规范性文件：国家机关在其权限范围内，按照法定程序制定和颁 日志吕品吕品的日志当前日志返回日志首页? 较新一篇/ 较旧一篇 分享 1. 统计学：收集处理分析解释数据并从数据中得出结论的科学。 2. 描述统计：研究数据收集处理汇总图表描述概括与分析等统计方法。 3. 推断统计：研究如何利用样本数据来推断总体特征的统计方法。 4. 分类数据：只能归于某一类别的非数字型数据。 5. 顺序数... 如果你也考统计学~~~~~网上搜索到的统计学基本概念~~~~~ 2011-05-28 12:06 | (分类:默认分类) 1. 统计学：收集处理分析解释数据并从数据中得出结论的科学。 2. 描述统计：研究数据收集处理汇总图表描述概括与分析等统计方法。 3. 推断统计：研究如何利用样本数据来推断总体特征的统计方法。 4. 分类数据：只能归于某一类别的非数字型数据。 5. 顺序数据：只能归于某一有序类别的非数字型数据。 6. 数值型数据：按数字尺度测量的观察值。 7. 观测数据：通过调查或观测而收集到的数据。 8. 实验数据：在实验中控制实验对象而收集到的数据。 9. 截面数据：在相同或近似相同的时间点上收集的数据。 10. 时间序列数据：在不同时间上收集到的数据，这类数据按时间顺序收集到的。 11. 抽样调查：从总体中随机抽取一部分单位作为样本进行调查，根据样本调查结果来推断总体特征的数据收集方法。 12. 普查：为特定目的而专门组织的全面调查。 13. 总体：包含所研究的全部个体（数据）的集合。 14. 样本：从总体中抽取的一部分元素的集合。 15. 样本容量：也称样本量，是构成样本的元素数目。 16. 参数：用来描述总体特征的概括性数字度量。 17. 统计量：用来描述样本特征的概括性数字度量。 18. 变量：说明现象某种特征的概念。 19. 分类变量：说明事物类别的一个名称。 20. 顺序变量：说明事物有序类别的一个名称。 第七章医学统计学的基本概念和步骤 A1型题 1．在实际工作中，同质是指( ) A．被研究指标的非实验影响因素均相同 B．研究对象的测量指标无误差 C．被研究指标的主要影响因素相同 D．研究对象之间无个体差异 E．以上都对 2．变异是指( ) A．各观察单位之间的差异 B．同质基础上，各观察单位之间的差异 C．各观察单位某测定值差异较大 D．各观察单位有关情况不同 E．以上都对 3．统计中所说的总体是指( ) A．根据研究目的确定的同质的全部个体 B．根据地区划分的研究对象的全体 C．根据时间划分的研究对象的全体 D．随意想象的研究对象的全体 E．根据人群划分的研究对象的全体 4．统计中所说的样本是指( ) A．从总体中随意抽取一部分 B．有意识地选择总体中的典型部分 C．依照研究者的要求选取有意义的一部分 D．从总体中随机抽取有代表性的一部分 E．以上都不是 5．统计学上的系统误差、测量误差、抽样误差在实际工作中( ) A．均不可避免 B．系统误差和测量误差不可避免 C．测量误差和抽样误差不可避免 D．系统误差和抽样误差不可避免 E．只有抽样误差不可避免 6．抽样误差指的是( ) A．个体值和参数值之差 B．个体值和样本统计量值之差 C．样本统计量值和参数值之差 D．不同的总体参数之差 E．以上都不是 7．随机测量误差使调查结果( ) A．大部分偏高 B．大部分偏低 C．统一偏高或偏低 D．存在误差且该误差无规律性 E．存在误差但该误差有一定的规律性 8．抽样误差使调查结果( ) A．大部分偏高 B．大部分偏低 C．统一偏高或偏低 D．存在误差且该误差无规律性 E．存在误差但该误差有一定的规律性 9．系统误差使调查结果( ) A．大部分偏高 B．大部分偏低 C．统一偏高或偏低 D．存在误差且该误差无规律性 E．存在误差但该误差有规律性 10．统计学中可以根据( )的分布规律，对总体进行统计学推断 A．误差 B．过失误差 C．系统误差 D．随机测量误差 E．随机抽样误差 11．时间资料为( ) A．名义测度资料 B．等级测度资料 C．循环测度资料 D．区间测度资料 E．比值测度资料 12．某地30年来的气温(℃)资料为( ) A．名义测度资料 B．等级测度资料 C．循环测度资料 D．区间测度资料 E．比值测度资料 13．分析资料时，下列哪项不作为统计分析方法选择的根据( ) A．研究设计的目的 B．研究设计的方案 C．资料的类型 D．资料的分布类型 E．前人的分析结果 14．小概率事件是指(P是随机事件发生的概率)( ) A．P≤O．05 B．P≤0．5 C．P≤0．1 D．P≤0．20 E．P<0．08 15．某医生欲研究各种生化指标与糖尿病的关系，测量病人的血糖、血压、胆固醇，这些资 法律的基本概念 (1) 一、绪论 研究法学的方法和研究别种科学是一样的。先把那根本上的原理彻底悟会了，其他的枝叶问题就可不劳思索，迎刃而解。比方代数、几何、物理、化学都有确定的公式和定例；学者根据那种公式和定例就可解释各种变化无定的问题。要是没有那种公式和定例，就要觉得头绪纷纭，顿时无从着手，怎能造出一种科学的统系呢？但其间有一异点就是代数、几何、物理、化学都属于自然科学；那自然境界上的现象如影随形，都有定理可以推测。法律学并非自然科学，乃是一种精神界的科学，??乃是社会科学之一部分。精神是一样活动的东西，吾人难以捉摸，其变化亦复神妙非常，与天然现象大不相同。要在精神界的科学上作个公式下个定例，那个公式和定例断乎不能如八八六十四和H2 O=H2O的呆板且绝对。何以故呢？因为人的精神是自由的，海阔天空没有人可以捉摸得到，想做什么就要做什么。那“想做什么”是个因，那“就要做什么”是个果；因既活动，果亦不免随了活动。所以自然界只有现象，精神界则有事业。自然科学的问题是“究是怎样？”其答案是个发明，其所证明的是“有因必有果”；精神界科学的问题是“应是怎样”？其答案是个创作，其所奉为信条的是“有志就成”。万物的进化是在天演；人事的进化是在猛进。宇宙间惟有人心是最灵活，既难束缚又难察量。那自然的“光”“热”“电”虽然奇妙，然还可以用各种科学艺器来确定他的度数；人心的 “光”“热”“电”（知、情、意）那是更属奇妙了，没有什么科学仪器可以用了来察量其度数。照这样说，那人的心理果为一种不可研究的东西吗？人心既不能研究，精神界上的科学就没有什么公式和定例之可言了！那又不然的。人心虽不能用有形的仪器来推察，却可用无形的仪器考查他一下。在精神界上的科学，我们所用以察量短长，评判是非的仪器都是无形的；虽然无形，其真确和稳妥倒不让那有形的仪器。法律学既是精神界科学之一部，自然亦有一种无形仪器??即是标准。标准拿定了，就不难再造公式和定例。 二、法律的标准 从前孔子曾经说过：“礼云礼云！玉帛云乎哉？乐云乐云！钟鼓云乎哉？”现在我也要依样葫芦说句话：“法云法云！条文云乎哉？”玉帛是礼的用，非礼的体；钟鼓是乐的器，非乐的本；条文是法的骸，非法的魂。所谓“体”所谓“本”所谓“魂”，都是标准之别名。礼的标准可以用一“敬”来代表他；乐的标准可以用一“和”字来代表他；法的标准却用个“理”字来代表他。所以“敬”、“和”、“理”是治礼、乐、法的人所用以察量短长，评判是非的利器；靠了那种利器，善恶真假即可一辨而知。天下固有不敬的礼，不和的乐，不合理的法。但便是礼其所礼，乐其所乐，法其所法，并不是我心目中的礼、乐、法了。这种礼乐法，即使能够冒着礼乐法的名横行一世，那也不过是暂时的。以历史的眼光看来，却是无足重轻，在不足挂齿之例。现在休论礼乐，且先以法学讲来并与海内外学者讨论一下。 方才不说法的标准是个“理”字吗？这个理字先要讲得明明白白才可免得有隔靴搔痒的毛病。中国宋明诸儒为了这个理字，质难辩论，曾用了一番苦工。但其结果真理愈弄愈涩，门户之见亦愈弄愈多，说来亦觉可怜得很。清代诸儒以为前车可鉴就起了一个大反动！这个反动在中国思想界至今尚占势力。欧美十八、九世纪诸法家亦想专恃一个理字来解决一切法学上问题。现在 第1章算法的基本概念 计算机系统中的任何软件，都是由大大小小的各种程序模块组成，它们按照特定的算法来实现，算法的好坏直接决定了所实现软件性能的优劣。用什么方法来设计算法，所设计算法需要什么样的资源，需要多少运行时间、多少存储空间，如何判定一个算法的好坏……在实现一个软件时，这些都是必须予以解决的。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个的具体算法来实现。因此，算法设计与分析是计算机科学与技术的一个核心问题。 1.1 引言 “算法”这一术语是从Algorithm翻译而来的，但直到1957年，西方著名的《韦伯斯特新世界词典》也未将其收录其中。据西方数学史家的考证，古代阿拉伯的一位学者写了一部名著——《Kitāb al-jabr Wa’lmuqāb J la》（《复原和化简的规则》），作者的署名是Abū‘Abd Allāh Muhammad ibn Mūsa al-Khwārizmī。从字面上看，其含义是“穆罕默德（Muhammad）的父亲，摩西（Moses）的儿子，Khwārizm地方的人”。后来，这部著作流传到了西方，结果从作品名称中的al-jabr派生出Algebra（代数）一词；从作者署名中的al-Khwārizmī派生出Algorithm一词。随着时间的推移，Algorithm这个词的含义已变得面目全非了，成了本书要讨论的内容——算法。 1.1.1 算法的定义和特征 欧几里得曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里得所描述的这个过程被称为Euclides Algorithm for gcd，国内将其翻译为“求最大公因子的欧几里得算法”，Algorithm（算法）这一术语在学术上具有了现在的含义。下面通过一个例子来认识一下该算法。 算法1.1欧几里得算法 输入：正整数m,n 输出：m,n的最大公因子 1. int euclid(int m,int n) 2. { 3. int r; 4. do { 法律基本概念 本套试卷满分为:56您的得分是:0 1、2008年10月全国人大常委会对《消防法》进行了修订，2009年4月，某省人 大常委会通过《实施〈中华人民共和国消防法〉办法》，对实施《消防法》作 出了具体规定。关于该办法，下列说法正确的是（）。 A.该办法属于对《消防法》的立法解释 B.该办法属于《消防法》的下位法，按照法律高于法规的原则其效力较低 C.该办法属于对《消防法》的变通或补充规定 D.该办法对《消防法》进行了体系解释 【正确答案:】B【答题结果:】未答【您的得分:】0 2、马克思曾说：“社会不是以法律为基础，那是法学家的幻想。相反，法律 应该以社会为基础。法律应该是社会共同的，由一定的物质生产方式所产生的 利益需要的表现，而不是单个人的恣意横行。”根据这段话所表达的马克思主 义法学原理，下列说法正确的是（）。 A.强调法律以社会为基础，这是马克思主义法学与其他派别法学的根本区别 B.法律在本质上是社会共同体意志的体现 C.在任何社会，利益需要实际上都是法律内容的决定性因素 D.特定时空下的特定国家的法律都是由一定的社会物质生活条件所决定的 【正确答案:】D【答题结果:】未答【您的得分:】0 3、剥夺公民政治权利只能由（）规定。 A.地方性法规 B.法律 C.行政法规 D.部门规章 【正确答案:】B【答题结果:】未答【您的得分:】0 4、下列有关法律后果、法律责任、法律制裁和法律条文等问题的表述正确的是（）。 A.任何法律责任的设定都必定是正义的实现 B.法律后果不一定是法律制裁 C.承担法律责任即意味着接受法律制裁 D.不是每个法律条文都有法律责任的规定 【正确答案:】D【答题结果:】未答【您的得分:】0 5、下列关于法律责任的说法不正确的是（）。 A.法律责任的归结讲求责任法定原则、公正原则、效益原则 B.法律责任的免除即无责任 C.法律责任体现了国家的强制力 D.法律责任产生的主要原因是违法与违约 【正确答案:】B【答题结果:】未答【您的得分:】0 6、把法律划分为根本法和普通法的主要依据是（）。 A.适用范围不同 B.制定和表达的方式不同 C.制定和实施的主体不同 D.规定的内容、法律地位和制定的程序不同 【正确答案:】D【答题结果:】未答【您的得分:】0 7、下列由全国人大常委会裁决的法律冲突是（）。 A.同一机关制定的法律，新的规定与旧的规定不一致的 B.法律之间对同一事项的新的一般规定与旧的特别规定不一致的 C.同一机关制定的法律，特别规定与一般规定不一致的 D.行政法规之间对同一事项的新的一般规定与旧的特别规定不一致的 【正确答案:】B【答题结果:】未答【您的得分:】0 8、我国《立法法》规定行使国家立法权的机关是（）。 A.全国人大和地方人大 B.全国人大和国务院 C.全国人大及其常委会 D.全国人大及其常委会、国务院及其各部委 【正确答案:】C【答题结果:】未答【您的得分:】0 9、根据马克思主义法学的基本观点，下列表述正确的是（）。 A.法在本质上是社会成员公共意志的体现 B.法既执行政治职能，也执行社会公共职能 C.法最终决定于历史传统、风俗习惯、国家结构、国际环境等条件 D.法不受客观规律的影响 【正确答案:】B【答题结果:】未答【您的得分:】0 10、下列有关行政法规和规章的说法正确的是 第一章算法的基本概念 1.1 引言 算法设计与分析在计算机科学与技术中的地位 算法（Algorithm）一词的由来。 1.1.1 算法的定义和特征 欧几里德算法： 算法1.1欧几里德算法 输入：正整数m,n 输出：m,n的最大公因子 1. int euclid(int m,int n) 2. { 3. int r; 4. do { 5. r = m % n; 6. m = n; 7. n = r; 8. } while(r) 9. return m; 10. } 一、算法的定义： 定义1.1算法是解某一特定问题的一组有穷规则的集合。 二、算法的特征： 1．有限性。算法在执行有限步之后必须终止。 2．确定性。算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。 3．输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。算法的输入是从特定的对象集合中抽取的。 4．输出。一个算法有一个或多个输出，这些输出，和输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。 1 5．能行性。算法的能行性指的是算法中有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。 1.1.2 算法设计的例子，穷举法 一、穷举法，是从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解。 二、例 例1.1百鸡问题。 “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？” a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程： b +c a（1.1.1） + 100 = b a（1.1.2） + +c 5= 100 3/ 3 c（1.1.3） %= 3 1。第一种解法： a、b、c的可能取值范围：0 ~ 100，对在此范围内的，a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。 把问题转化为用n元钱买n只鸡，n为任意正整数，则方程（1.1.1）、（1.1.2）变成：+（1.1.4） n a= + c b 3 +3/ 5（1.1.5） + c n b a= 算法1.2百鸡问题 输入：所购买的三种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[],m[],s[] 1. void chicken_question(int n,int &k,int g[],int m[],int s[]) 2. { 3. int a,b,c; 4. k = 0; 5. for (a=0;a<=n;a++) 6. for (b=0;b<=n;b++) 7. for (c=0;c<=n;c++) { 8. if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) { 9. g[k] = a; 10. m[k] = b; 11. s[k] = c; 12. k++; 13. } 2 1．什么叫算法？简述算法的基本特性。 2．如何评价一个算法？简述空间复杂性和时间复杂性的概念。 3．试分析下列各程序段的时间复杂性。 （1）i=1; （2） for(i=1; i<=m; i++) （3） x=n; /*n>1*/ k=0; for(j=1; j<=n; j++) y=0; n=100; A[i][j] = i * j; while(x>=(y+1)*(y+1)) do{k = k + 10 * i; y = y + 1; i++; }while(i ! 100); 4.简述下列概念：数据、数据元素、数据类型、数据结构； 5．简述数据的逻辑结构、数据的存储结构和数据运算的概念。 6．线性表可用顺序表和单链表作为存储结构。试问： （1） 两种存储表示各有哪些主要优缺点？ （2） 如果有n 个表同时并存，且处理过程中个表的长度会动态发生变化，表的 总数也可能自动变化，在此情况下应选用哪种存储表示？为什么？ （3） 若表的总数基本稳定，且很少进行插入和删除，但要求以最快速度存取表 中元素，这时应采用哪种存储表示？为什么？ 7.设ha 和hb 分别是两个带表头结点的升序单链表的表头指针。试设计一个算法将这两个链表合并成为一个降序单链表。要求结果链表仍使用原来两个链表的结点空间而不另开辟其他存储空间，表中允许出现重复数据。 8.设有一个线性表12(,,,)n L a a a = ，试分别在顺序表和单链表两种存储表示方式下，各设计一个将线性表L 逆置的算法，要求不重新开辟存储空间。所谓逆置是指将线性表中的元素次序颠倒过来，即成为11(,,,)n n L a a a -'= 。 9. 设有一个栈，元素的进栈次序依次为A, B, C, D, E. 试问能否得到下面的出栈序列？若能请写出操作序列，若不能请说明原因。 (1) C, E, A, B, D (2) C, B, A, D, E (3) D, C, A, B, E (4) A, C, B, E, D (5) A, B, C, D, E (6) E, A, B, C, D 10. 何谓队列的上溢现象？解决它有哪些方法？分别简述其工作原理。 11．试写一个算法，它借助栈逆置一个单链表。 12．已知一棵树边的集合为{ 统计学基本概念和步骤一、统计学中的几个基本概念 总体根据研究目的确定的、同质的全部研究对象（严格地讲，是某项观察值的集合）如研究2008年中国60岁以上的老人血清总胆固醇含量，测定值的全部构成了一个总体 样本随机化的原则从总体中抽出的有代表性的观察单位组成的子集称作样本，如DM患者中随机抽取有代表性一组患者构成样本 抽样误 差 由于随机抽样所造成的某变量值的统计量和总体参数之间存在的差异 变量数值变 量 变量值是定量的，表现为数值大小的变化，有度量衡单位。（计量 资料）如：身高（cm）、体重（kg） 分类变 量 变量值是定性的，表现为互不相容的类别或属性。（计数资料） 如：性别分男女两类 有序数 据 半定量数据或等级资料，临床疗效可分为治愈、显效、好转、无效 四级，尿糖（-、+、++、+++） 概率描述随机事件（如发病）发生可能性大小的度量为概率，常用P表示。在0和1之间，P≤0.05的随机事件，通常称作小概率事件，即事件发生的可能性很小 同质和变异同质除了实验因素外，影响被研究指标的非实验因素相同变异是在同质的基础上被观察个体之间的差异 参数和统计 量 总体的统计指标称为参数，样本的统计指标称为统计量统计设计统计工作最关键的一步，整个研究工作的基础 数据整理对数据质量进行的检查，考虑数据分布及变量转换，检查异常值和数据是否符合特定的统计分析方法要求等 统计描述描述及总结一组数据的重要特征，其目的是使实验或观察得到的数据表达清楚并便于分析 统计推断由样本数据的特征推断总体特征的方法 A.等级资料 B.计数资料 C.计量资料 D.分别变量 E.参数因素 在统计学中，数值变量构成 在统计学中，分类变量构成 在统计学中，有序数据构成 『正确答案』C；B；A 下列不属于计量资料的是 A.体重（kg） B.血型（A、B、O、AB型） C.身高（cm） D.每天吸烟量（1－5支） E.白细胞（个/L） 『正确答案』B 定量资料的统计描述 （一）考什么？ （1）集中趋势指标 （2）离散趋势指标 （3）正态分布的特点与面积分布规律 （二）最重点是什么？ 正态分布的集中趋势和离散趋势的指标 （三）最难点的是什么？ 概念和正态分布的特点与面积分布规律1-1-1 算法的概念
第四章 力 法
算法的概念的教学设计说明
统计学基本概念
第七章 医学统计学的基本概念和步骤
力法的基本概念
刑法基本概念整理
法的概念、本质和基本特征
法律 -法律的基本概念
统计学基本概念
第七章医学统计学的基本概念和步骤
法律的基本概念 (1)汇总
第1章算法的基本概念
2014基本法的概念
第一章算法的基本概念
什么叫算法简述算法基本特性。
统计学基本概念和步骤