内容导读：导航目录:1、关于数学题目的思考问题2、想听大家对于一道密码设计的数学建模题3、黑客很厉害吗4、PASCAL算法知识题~~高分~紧急~5、计算机专业学习什么比较有用啊6、计算机***安全技术试题关于数...……
导航目录:
关于数学题目的思考问题
除了那些天才，数学在我们平常人眼里都是一门难学的科目，而且随着年级的增长越来越难。当考试时我们又发现数学分数怎么那么高，数学不好想考前几名没门，想考好中学没门，想考好高中没门，想考大学等着吧。现在我教大家一些学习数学的心得，希望对大家有所帮助。
一、认识我们可爱的数学
首先如果我现在说一句，我们周围的任何东西早晚都会可以用数学解释，你相信吗。你肯定不相信所以你还在抱怨学三角函数干什么，学微积分干什么？
数学是我们人类思维的表达形式，反映了我们对客观世界的理解，解释我们的客观世界。不管什么理论，只要还没有找到准确和谐的数学解释，我们就不能认为这个理论为真理，这就是数学的左右。所以数学有多重要，为什么那么高分了吧。
数学可以锻炼我们的思维，这一点有点假，但是我们还是要找个理由，不然你学什么都没动力。
二、对数学产生兴趣
对数学产生兴趣，不是每个人都能做到的，这是实情，但我们还是试着让自己喜欢上数学吧。
怎么才能对数学产生兴趣呢？我的经历告诉我，只有你欣赏数学或者与数学有关的东西了，你就逐渐喜欢上数学了
这可以通过下面几个途径实现
首先读几本著名数学家的传记（比如说陈景润如下图所示：）
，感受大家的风采，加深对数学的理解，当你欣赏某个大家了，你也就开始欣赏数学了。或者读写物理学家的事迹或者研究一下黑客的经历，如果有能力也可以试着学点黑客知识，你会发现，没了数学，啥都干不成，你就会拼命的学习数学。
其次读很多有关数学的小故事，感到好玩了才会有兴趣学习数学。
三、实际去学习数学知识
当我们坐在教室里面对厚厚的数学书，面对无限的数字加字幕很晕吧。
所以上课还是听课吧，多少听点。这样省点你的时间。
做题的技巧，做数学题不在多（但不能太少），而在精，当你拿到一份试卷，不要什么也不想直奔着题去了，做完了下一张。这样不行，首先你认真做完，然后认真听老师讲完，把自己错的全部该对，确定都学会了，自己再抄一份这个试卷，规定时间重做一遍，看看能不能得满分。如果还是有错的。
这时候就注意了，这些错的都是你不知道的知识点，继续研究好好研究，不怕时间不够。真的题不在多，而在于你都做会了。上边这一点是学习数学最棒的 *** 我感觉。
真心希望还在犹豫的朋友试一下。提高数学成绩不在是梦想。
想听大家对于一道密码设计的数学建模题
公钥密码又称为双钥密码和非对称密码，是1976年由Daffy和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：
W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654
单向陷门函数是满足下列条件的函数f：
(1)给定x，计算y=f(x)是容易的；
(2)给定y, 计算x使y=f(x)是困难的。
(所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实际意义。)
(3)存在δ，已知δ 时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。
注：1*. 仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ 称为陷门信息。
2*. 当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk。 f函数的设计者将δ 保密，用作解密密钥，此时δ 称为秘密钥匙，记为Sk。由于加密函数时公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。
3*.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。
Diffie和Hellman在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数。然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法。这个算法是基于有限域中计算离散对数的困难性问题之上的：设F为有限域，g∈ F是F的乘法群F*=F\{0}=g。并且对任意正整数x，计算gx是容易的；但是已知g和y求x使y= gx，是计算上几乎不可能的。这已问题称为有限域F上的离散对数问题。公钥密码学种使用最广泛的有限域为素域FP.
对Diffie-Hellman密钥交换协议描述：Alice和Bob协商好一个大素数p，和大的整数g，1gp，g更好是FP中的本原元，即FP*＝g。p和g无须保密，可为 *** 上的所有用户共享。
当Alice和Bob要进行保密通信时，他们可以按如下步骤来做：
(1)Alice送取大的随机数x，并计算
X=gx(mod P)
(2)Bob选取大的随机数x，并计算X = gx (mod P)
(3)Alice将X传送给Bob；Bob将X 传送给Alice。
(4)Alice计算K=(X )X(mod P);Bob计算K ＝（X) X (mod P),易见，K=K =g xx (mod P)。
由(4)知，Alice和Bob已获得了相同的秘密值K。双方以K作为加解密钥以传统对称密钥算法进行保密通信。
注：Diffie-Hellman密钥交换算法拥有美国和加拿大的专利。
3 RSA公钥算法
RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的（见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126)该算法的数学基础是初等数论中的Euler（欧拉)定理，并建立在大整数因子的困难性之上。
将Z/(n）表示为 Zn，其中n=pq; p,q为素数且相异。若
Z*n{g∈ Zn|(g,n)=1}，易见Z*n为 (n)阶的乘法群，且有 g (n)1(mod n)，而 (n)=(p-1)(q-1).
RSA密码体制描述如下：
首先，明文空间P＝密文空间C=Zn.(见P175).
A.密钥的生成
选择p,q，p,q为互异素数，计算n=p*q, (n)=(p-1)(q-1), 选择整数e使( (n),e)=1,1e (n)),计算d,使d=e-1(mod (n))),公钥Pk={e,n};私钥Sk={d,p,q}。
注意，当0Mn时,M (n) =1(mod n)自然有：
MK (n)+1M(mod n), 而ed 1 (mod (n)),易见(Me)d M(mod n)
B.加密 (用e,n)明文：Mn 密文：C=Me(mod n).
C.解密 (用d,p,q)
密文：C 明文：M=Cd（mod n)
注：1*, 加密和解密时一对逆运算。
2*, 对于0Mn时，若(M,n) ≠ 1，则M为p或q的整数倍，假设M=cp，由(cp,q)=1 有 M (q) 1(mod q) M (q) (p) 1(mod q)
有M (q) = 1+kq 对其两边同乘M=cp有
有M (q)＋1=M+kcpq=M+kcn于是
有M (q)＋1 M(mod n)
例子：若Bob选择了p=101和q＝113，那么，n=11413, (n)=100×112＝11200；然而11200＝26×52×7，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除（事实上，Bob不会分解φ(n)，而且用辗转相除法（欧式算法）来求得e，使（e, φ(n)=1)。假设Bob选择了e=3533，那么用辗转相除法将求得：
d=e -1 6597(mod 11200), 于是Bob的解密密钥d=6597.
Bob在一个目录中公开n=11413和e=3533, 现假设Alice想发送明文9726给Bob，她计算：
97263533(mod 11413)=5761
且在一个信道上发送密文5761。当Bob接收到密文5761时，他用他的秘密解密指数（私钥）d＝6597进行解密：57616597（mod 11413)=9726
注：RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知 (n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.
4 RSA密码体制的实现
实现的步骤如下：Bob为实现者
(1)Bob寻找出两个大素数p和q
(2)Bob计算出n=pq和 (n)=(p-1)(q-1).
(3)Bob选择一个随机数e(0e (n))，满足（e， (n)）＝1
(4)Bob使用辗转相除法计算d=e-1(mod (n))
(5)Bob在目录中公开n和e作为她的公开钥。
密码分析者攻击RSA体制的关键点在于如何分解n。若分
解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公
开的e，解出秘密的d。（猜想：攻破RSA与分解n是多项式
等价的。然而，这个猜想至今没有给出可信的证明！！！）
于是要求：若使RSA安全，p与q必为足够大的素数，使
分析者没有办法在多项式时间内将n分解出来。建议选择
p和q大约是100位的十进制素数。 模n的长度要求至少是
512比特。EDI攻击标准使用的RSA算法中规定n的长度为
512至1024比特位之间，但必须是128的倍数。国际数字
签名标准ISO/IEC 9796中规定n的长度位512比特位。
为了抵抗现有的整数分解算法，对RSA模n的素因子
p和q还有如下要求：
(1)|p-q|很大，通常 p和q的长度相同；
(2)p-1 和q-1分别含有大素因子p1和q1
(3)P1-1和q1-1分别含有大素因子p2和q2
(4)p+1和q+1分别含有大素因子p3和q3
为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定 e＝216＋1，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。 下面研究加解密算术运算，这个运算主要是模n的求幂运算。著名的“平方-和-乘法” *** 将计算xc(mod n)的模乘法的数目缩小到至多为2l，这里的l是指数c的二进制表示比特数。若设n以二进制形式表示有k比特，即k=[log2n]+1。 由l≤ k，这样xc(mod n)能在o(k3)时间内完成。（注意，不难看到，乘法能在o(k2)时间内完成。）
平方－和－乘法算法：
指数c以二进制形式表示为：
c=
Xc=xc0×（x2)c1×…×(x2t-1)ct-1
预计算： x2=xx
x4=x22=x2x2
.
.
.
x2t-1 =x2t-2*x2t-2
Xc计算：把那些ci=1对应的x2i全部乘在一起，便得xc。至
多用了t-1次乘法。请参考书上的177页，给出计算
xc(mod n)算法程序：
A=xc c=c0+c12+..+ct-12t-1= [ct-1,....,c1,c0]2
5 RSA签名方案
签名的基本概念
传统签名（手写签名）的特征：
（1）一个签名是被签文件的物理部分；
（2）验证物理部分进行比较而达到确认的目的。(易伪造)
（3）不容易忠实地“copy”!!!
定义： (数字签名方案）一个签名方案是有签署算法与验
证算法两部分构成。可由五元关系组（P,A,K,S,V）来刻化：
(1)P是由一切可能消息(messages)所构成的有限 *** ；
(2)A是一切可能的签名的有限 *** ；
(3)k为有限密钥空间，是一些可能密钥的有限 *** ；
(4)任意k ∈K，有签署算法Sigk ∈ S且有对应的验证算法Verk∈V,对每一个
Sigk:p A 和Verk:P×A {真，假} 满足条件：任意x∈ P,y∈ A.有签名方案的一个签名：Ver(x,y)= ｛
注：1*.任意k∈K, 函数Sigk和Verk都为多项式时间函数。
2*.Verk为公开的函数，而Sigk为秘密函数。
3*.如果坏人（如Oscar)要伪造Bob的对X的签名，在计算上是不可能的。也即,给定x，仅有Bob能计算出签名y使得Verk(x,y)＝真。
4*.一个签名方案不能是无条件安全的，有足够的时间，Oscar总能伪造Bob的签名。
RSA签名：n=pq,P=A=Zn,定义密钥 *** K={(n,e,p,q,d)}|n=pq,d*e1(mod (n))}
注意：n和e为公钥；p,q,d为保密的（私钥）。对x∈P, Bob要对x签名，取k∈K。Sigk(x) xd(mod n)y(mod n)
于是
Verk(x,y)=真 xye(mod n)
（注意：e,n公开；可公开验证签名(x,y)对错！！也即是否为Bob的签署）
注：1*.任何一个人都可对某一个签署y计算x=ek(y)，来伪造Bob对随机消息x的签名。
2*.签名消息的加密传递问题：假设Alice想把签了名的消息加密送给Bob，她按下述方式进行：对明文x，Alice计算对x的签名，y=SigAlice(x)，然后用Bob的公开加密函数eBob,算出
Z=eBob(x,y) ,Alice 将Z传给Bob，Bob收到Z后，之一步解密，
dBob(Z)=dBobeBob(x,y)=(x,y)
然后检验
VerAlice(x,y)= 真
问题：若Alice首先对消息x进行加密，然后再签名，结果
如何呢？Y=SigAlice(eBob(x))
Alice 将（z,y)传给Bob，Bob先将z解密，获取x;然后用
VerAlice检验关于x的加密签名y。这个 *** 的一个潜在问
题是，如果Oscar获得了这对（z,y)，他能用自己的签名来
替代Alice的签名
y=SigOscar(eBob(x))
(注意：Oscar能签名密文eBob(x)，甚至他不知明文x也能做。Oscar传送（z,y )给Bob,Bob可能推断明文x来自Oscar。所以，至今人么还是推荐先签名后加密。）
6.EIGamal方案
EIGamal公钥密码体制是基于离散对数问题的。设P
至少是150位的十进制素数，p-1有大素因子。Zp为有限域，
若α为Zp中的本原元，有Zp* ＝α。若取β∈Zp*=Zp\{0}，
如何算得一个唯一得整数a,（要求，0≤a≤ p-2)，满足
αa=β(mod p)
将a记为a=logαβ
一般来说，求解a在计算上是难处理的。
Zp*中的Egamal公钥体制的描述：设明文空间为P=Zp*,密文空
间为C=Zp*×Zp*,定义密钥空间K={(p, α,a, β )|β=αa(mod p)}
公开钥为：p, α ,β
秘密钥（私钥）：a
Alice 取一个秘密随机数k∈ Zp-1，对明文x加密
ek(x,k)=(y1,y2)
其中， y1=αk(mod p),y2=xβk(mod p)
Bob解密，
dk(y1,y2)=y2(y1α)-1(mod p)
注：1*.容易验证y2(y1α)-1=x(αa)k(αka)-1=x !!
2*.利用EIGamal加密算法可给出基于此的签名方案：
Alice 要对明文x进行签名，她首先取一个秘密随机数k作
为签名
Sigk(x,k)=( , )
其中 ＝αk(mod p), =(x-a )k-1(mod p-1)
对x, ∈Zp*和 ∈ Zp-1，定义Verk(x, ,)＝真等价于
βα＝αx(mod p)
要说明的是，如果正确地构造了这个签名，那么验证将
是成功的，因为
βα＝ αa αk (mod p)= αa+k (mod p)
由上面知道， ＝（x- a)k-1(mod p-1)可以推出
k=x- a(mod p-1)有a+kx(mod p)
所以 β ＝ αx (mod p)
该签名方案已经被美国NIST(国家标准技术研究所）确定为签名标准（1985）。
有关RSA方面的内容，请访问网址：
黑客很厉害吗
其实电影里面和流传的黑客，在很大程度上是被夸大了的。
可以说，没有100%黑客能破的机子。事实上，黑客在黑某个未知系统的时候，很大程度上有运气成分在里面。
首先，如果系统里存在已知的漏洞（未修复），那么，黑客的运气比较好，可以直接利用这些漏洞。
其次，如果系统比较完善，没有存在公开的漏洞，那么黑客需要自己不断尝试，就像做一个比较困难的数学题目一样。可能解出，也可能解不出。其中依靠黑客以往的功底（主要是 *** 和系统方面的知识，硬件倒是其次），还要依靠黑客的灵感和运气，真的就如同做高难度数学题。
至于已经中了木马或病毒的机子，不在考虑范围内。另外，黑客使用非电脑技术手段，也不在考虑范围内。
PASCAL算法知识题~~高分~紧急~
6.1 穷举策略的概念
所谓枚举法，指的是从可能的解的 *** 中一一枚举各元素， 用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。
有些问题可以用循环语句和条件语句直接求解，有些问题用循环求解时循环次数太多，无法编写程序，怎么办？下面是用“千军万马过独木桥，适者存”的方式实现穷举策略的。
6.2 典型例题与习题
例1.将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的 *** 产生出来的2n+1个二进制数都不相同。
例如，当n=2时，即22个0和22个1排成如下一圈：
比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，...可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明：
以n=4为例，即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数出现的可能性。
程序清单
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1; A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27
WHILE A[J]=1 DO J:=J-1;
( A[J]:=1 )
FOR I:=J+1 TO 27 DO ( A[i]:=0 )
FOR I:=0 TO 31 DO B[I]:=0;
FOR I:=1 TO 32 DO
BEGIN
( S:=0)
FOR K:=I TO I+4 DO S:=S*2+A[k];
( B[S]:=1 )
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF ( S=32 ) THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.
例2：在A、B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数=20，且每条路段上的距离均为一个整数)。
A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(更大距离=1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。
例如：下图所示是当N=1时的情况：
从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。
算法说明：本题采用穷举算法。
数据结构：N：记录A，B间路站的个数
数组D[I，0]记录第I-1个到第I路站间路段的个数
D[I，1]，D[I，2]，…记录每个路段距离
数组G记录可取到的距离
程序清单：
program CHU7_6;
var i,j,n,s:integer;
b:array[0..100] of integer;
d:array[0..100,0..20] of integer;
g:array[0..1000] of 0..1;
begin
readln(n);
for i:=1 to n+1 do
begin
readln(d[i,0]);
for j:=1 to d[i,0] do read(d[i,j]);
end;
d[0,0]:=1;
for i:=1 to n+1 do b[i]:=1;
b[0]:=0;
for i:=1 to 1000 do g[i]:=0;
while b[0]1 do
begin
s:=0;
for i:=1 to n+1 do
s:= s+d[i,b[i]];
g[s]:=1;j:=n+1;
while b[j]=d[j,0] do j:=j-1;
b[j]:=b[j]+1;
for i:=j+1 to n+1 do b[i]:=1;
end;
s:=0;
for i:=1 to 1000 do
s:=s+g[i];
writeln(s);readln;
end.
2.1 递归的概念
1.概念
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
如:
procedure a;
begin
.
.
.
a;
.
.
.
end;
这种方式是直接调用.
又如:
procedure b; procedure c;
begin begin
. .
. .
. .
c; b;
. .
. .
. .
end; end;
这种方式是间接调用.
例1计算n!可用递归公式如下:
1 当 n=0 时
fac(n)={n*fac(n-1) 当n0时
可编写程序如下:
program fac2;
var
n:integer;
function fac(n:integer):real;
begin
if n=0 then fac:=1 else fac:=n*fac(n-1)
end;
begin
write('n=');readln(n);
writeln('fac(',n,')=',fac(n):6:0);
end.
例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
设n阶台阶的走法数为f(n)
显然有
1 n=1
f(n)={2 n=2
f(n-1)+f(n-2) n2
可编程序如下：
program louti;
var n:integer;
function f(x:integer):integer;
begin
if x=1 then f:=1 else
if x=2 then f:=2 else f:=f(x-1)+f(x-2);
end;
begin
write('n=');read(n);
writeln('f(',n,')=',f(n))
end.
2.2 如何设计递归算法
1.确定递归公式
2.确定边界(终了)条件
练习:
用递归的 *** 完成下列问题
1.求数组中的更大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的更大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
2.3典型例题
例3 梵塔问题
如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'---',c)
else begin
move(n-1,a,c,b);
writeln(a,'---',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
例4 快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的 *** 处之直到每一个待处理的序列的长度为1, 处理结束.
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procedure quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]=x) and (ji) do j:=j-1;
if ji then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]=x) and (ij) do i:=i+1;
if ij then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if sj then quicksort(b,s,j);
if it then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.
3.1 回溯的设计
1.用栈保存好前进中的某些状态.
2.制定好约束条件
例1由键盘上输入任意n个符号;输出它的全排列.
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k0 do
begin
x[k]:=x[k]+1;
while (x[k]=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
例2.n个皇后问题:
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k0 do
begin
x[k]:=x[k]+1;
while (x[k]=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.
回溯算法的公式如下:
3.2 回溯算法的递归实现
由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。
上述例1的递归 *** 实现如下：
program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procedure input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procedure try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.
例2：n皇后问题的递归算法如下：
程序1：
program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procedure print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procedure try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.
程序2：
说明:当n=8 时有30条对角线分别用了l和r数组控制，
用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:
program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procedure output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if in then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.
7.1 贪心策略的定义
贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出更优值(或较优解)的一种解题 *** 。
其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是更优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部更优解，而许多问题自身的特性决定了该题运用贪心策略可以得到更优解或较优解。
例1：在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和更大。
本题可用贪心策略：选n次，每一次选相应行中的更大值即可。
例2：在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和更大。
本题用贪心策略不能得到更优解，我们以2×4的矩阵为例。 3 4 6
1 2 10
若按贪心策略求解，所得路径为：1,3,4,6；
若按动态规划法求解，所得路径为：1,2,10,6。
例3:设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解更佳方案,使得完成m项工作的时间最短?
本题不能用贪心算法求解:理由是若n=3,m=6 各作业的时间分别是11 7 5 5 4 7
用贪心策略解(每次将作业加到更先空闲的机器上)time=15,用搜索策略更优时间应是14,但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过15,给搜索提供了方便。
总之：
1. 不能保证求得的最后解是更佳的；
2. 只能用来求某些更大或最小解问题；
3. 能确定某些问题的可行解的范围，特别是给搜索算法提供了依据。
7. 2 贪心策略的特点
贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：
1、贪心选择性质：
所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似更佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
2、局部更优解：
我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了更优解，但能够保证局部更优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部更优解，但贪心策略比动态规划时间效率更高站用内存更少，编写程序更简单。
7.3 典型例题与习题
例4：背包问题：
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值更大，但不能超过总容量。 物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
分析：
目标函数： ∑pi更大
约束条件是装入的物品总重量不超过背包容量：∑wi=M( M=150)
（1）根据贪心的策略，每次挑选价值更大的物品装入背包，得到的结果是否更优？
（2）每次挑选所占空间最小的物品装入是否能得到更优解？
（3）每次选取单位容量价值更大的物品，成为解本题的策略。
程序如下：
program beibao;
const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;
procedure init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;
procedure make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;
begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.
例5：旅行家的预算问题：
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。
计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer"
若输入：
d1=275.6 c=11.9 d2=27.4 p=8 n=2
d[1]=102 p[1]=2.9
d[2]=220 p[2]=2.2
output
26.95
本问题的贪心策略是：找下一个较便宜的油站，根据距离确定加满、不加、加到刚好到该站。
程序如下:
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.waymaxway then
begin
init:=false;
exit
end;
init:=true;
end;
procedure buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s=maxway+zero) and (j=n-1) and (oil[i]^.value=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s=maxway+zero then
if (oil[i]^.over+zero=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.
例6:n个部件,每个部件必须经过先A后B两道工序。
以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？
输入：
5 部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9
输出：
34
1 5 4 2 3
本问题的贪心策略是A机器上加工短的应优先，B机器上加工短的应靠后。
程序如下：
program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procedure init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].ac[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procedure sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].mt then begin t:=c[j].m;k:=j end ;
if ki then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procedure playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procedure calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.
计算机专业学习什么比较有用啊
如今互联网行业飞跃发展，互联网技术百日新月异，就当前就业形势来说 IT行业是适合目前社会趋势的，社会也需要大量的 IT技术型人才，各行各业也需要，所以就业广泛。学互联度网的优势有：
1、电脑行业需求量大，工作很好找，而且工作环境也不错。
2、电脑行业的工作与社会接触都比较紧密，紧跟潮流，所以见识和思知想都会比较开放，也有利于以后自己发展。
3、学习电脑入手道比较快，学习难度不是很版大。
4、现在有些学校有一些技能加学历的政策 ,不过主要看你自己的选择，上大学虽说听起来好，但是很多大学生都是毕业即失业的，还不如趁早学习门技术，毕业就可以工作，选对了好的行业，以后的发展空也会很大的。可以去学习计算机 *** ，现在学 *** 就是不错的选择
计算机 *** 安全技术试题
1． 最有效的保护E-mail的 *** 是使用加密签字，如( B )，来验证E-mail信息。通过验证E-mail信息，可以保证信息确实来自发信人，并保证在传输过程没有被修改。
A． Diffie-Hellman
B． Pretty Good Privacy（PGP）
C． Key Distribution Center（KDC）
D． IDEA
2． 黑客要想控制某些用户，需要把木马程序安装到用户的机器中，实际上安装的是（B）
A． 木马的控制端程序
B． 木马的服务器端程序
C． 不用安装
D． 控制端、服务端程序都必需安装
3． 下列不属于包过滤检查的是（D）
A． 源地址和目标地址
B． 源端口和目标端口
C． 协议
D． 数据包的内容
4． *** 服务作为防火墙技术主要在OSI的哪一层实现（A）
A． 数据链路层
B． *** 层
C． 表示层
D． 应用层
5． 加密在 *** 上的作用就是防止有价值的信息在网上被( D本题答案说法不一个人认为是D)。
A． 拦截和破坏
B． 拦截和窃取
C． 篡改和损坏
D． 篡改和窃取
6． 按照可信计算机评估标准，安全等级满足C2级要求的操作系统是（D）
A． DOS
B． Windows XP
C． Windows NT
D． Unix
7． 下面关于口令的安全描述中错误的是（B和D说的都不是很正确。。）`
A． 口令要定期更换
B． 口令越长越安全
C． 容易记忆的口令不安全
D． 口令中使用的字符越多越不容易被猜中
8． 不对称加密通信中的用户认证是通过（B）确定的
A． 数字签名
B． 数字证书
C． 消息文摘
D． 公私钥关系
9． 对于IP欺骗攻击，过滤路由器不能防范的是( D ) 。
A．伪装成内部主机的外部IP欺骗
B．外部主机的IP欺骗
C．伪装成外部可信任主机的IP欺骗
D．内部主机对外部 *** 的IP地址欺骗
10．RSA加密算法不具有的优点是（D）
A．可借助CA中心发放密钥，确保密钥发放的安全方便
B．可进行用户认证
C．可进行信息认证
D．运行速度快，可用于大批量数据加密
11．PGP加密软件采用的加密算法（C）
A．DES
B．RSA
C．背包算法
D．IDEA
12．以下说法正确的是（D）
A．木马不像病毒那样有破坏性
B．木马不像病毒那样能够自我复制
C．木马不像病毒那样是独立运行的程序
D．木马与病毒都是独立运行的程序
13．使用防病毒软件时，一般要求用户每隔2周进行升级，这样做的目的是（C）
A．对付最新的病毒，因此需要下载最新的程序
B．程序中有错误，所以要不断升级，消除程序中的BUG
C．新的病毒在不断出现，因此需要用及时更新病毒的特征码资料库
D．以上说法的都不对
14．防火墙的安全性角度，更好的防火墙结构类型是（D）
A．路由器型
B．服务器型
C．屏蔽主机结构
D．屏蔽子网结构
剩下的由高人来补。