严教算法
1. 与操作系统有关的一些经典算法
哦 ,kmp算法就是一种经典算法.KMP算法
一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
完全掌握KMP算法思想
学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。
如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。)
严老的《数据结构》79页讲了基本的匹配方法，这是基础。
80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。
我们继续往下看：
现在讨论一般情况。
假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’
现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较
此时，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我们得到关系式
‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：(k<j),
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比较)
匹配串： P(1) p(2) …… p(k-1) p(k)
现在我们把前面总结的关系综合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比较)
P(1) p(2) ……. p(k-1) p(k)
由上，我们得到关系：
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。
你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！
附：
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //递推计算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
补上个Pascal的KMP算法源码
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procere get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;
Write(s = );
Readln(str_s);
Write(t = );
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( Found , str_t, in , str_s, at , int_i, . );
end
else
Writeln( Cannot find , str_t, in , str_s, . );
END.
index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0
2. 身心严教什么意思
我的理解是，严格要求，方正教育。身，指身教，即以身作则，言传身教的意思；心，指心里、品性、精神方面，即心性的塑造，理想情操的熏陶培养。严教就是从身心两方面严格教育。
3. 三国杀张菖蒲为啥那么贵
张菖蒲这个武将的出现，可以说是三国杀武将的技能更新的又一次尝试，把技能的主动权交给了别人，同时还增加了智力在游戏中的重要性：善谋者，得天下。
张昌蒲这个武将非常有意思的一点就是其强度完全由队友的水平决定，甚至由敌人的水平决定。张昌蒲本人所能控制的也就是回合外留什么牌，以及对哪个队友发动【严教】。
游戏特色
三国杀作为一款原创桌上游戏，有别于其他桌面游戏的最主要特色，就是身份（势力、阵营）系统。
身份场中共有4种身份：主公、反贼、忠臣、内奸。主公和忠臣的任务就是剿灭反贼，清除内奸；反贼的任务则是推翻主公。内奸则要在场上先清除除主公以外的其他人物（包括其他内奸），最后单挑主公。
游戏开始时每个玩家随机抽取一张身份牌，抽到主公的玩家，要将自己的身份牌明示。其他人的身份牌不能被其他玩家看到。
国战场共有4种势力：魏、蜀、吴、群和一种特殊身份：野心家。四种势力的任务是消灭其他势力的所有角色和所有野心家；野心家与身份场的内奸相似，即必须除掉所以其他人（包括其他野心家），不过无顺序要求。
4. 严教不如身教，身教不如境教是什么意思
严厉、严格的教导，树立榜样，以身作则，境，是指孩子生活、成长的环境。
“严教不如身教，身教不如境教”的意思是孩子是父母的影子，孩子是父母的翻版。为了培养孩子的品德，做父母亲的行为要自慎，应该处处做孩子的表率。孩子好的和坏的行为都是父母教育影响的结果。
家长是孩子的第一任老师，要在孩子的成长过程中，树立正确的人生观和价值观，让孩子懂得：什么是是，什么是非，什么可为，什么不可为，让孩子懂得爱，懂得感恩，懂得给予。
(4)严教算法扩展阅读：
关于以身作则的几则话语：
其身正，不令而行；其身不正，虽令而不行。——《论语·子路》
其全句义为：孔子说：“自我品行端正了，即使不发布命令，老百姓也会去实行；若自身不端正，即使发布命令，老百姓也不会服从。”
2.圣人处无为之事行不言之教。——《道德经》
“圣人行不言之教”要求人们，特别是从事教育的人们，要注重以身作则，身教胜于言教，实践胜于雄辩，同时还要学会因材施教，或言或不言，视学生禀赋而行。
5. 严教的利与弊
严教的利是孩子很规矩，遵守一切规则，善于忍耐一切不公平和委屈。害处是不能建立和谐的
亲子关系
，家长与孩子无法沟通，孩子缺乏自信，没有闯劲。
6. 考研<<数据结构>>哪些算法比较重要是不是严的那本书上所有的算法都要掌握!
不是！
★计算机研究生法的考察主要以线性表 +排序（结合）为主 排序（结合）为主 排序（结合）为主 ,其 他知识算法只要求理解，不会在考研试中出现。之是 他知识算法只要求理解，不会在考研试中出现。之是 他知识算法只要求理解，不会在考研试中出现。之是 以线性表 +排序知识为依托，更重要的是考察算法思想 排序知识为依托，更重要的是考察算法思想 。你是 。你是 怎样用线性表 +排序解决问题的，思 想对了才能拿工具做。而排序解决问题的，思 想对了才能拿工具做。而排序解决问题的，思 想对了才能拿工具做。而想的融会贯通则是建 立在对线性表 +排序知识的熟练程度上 。所 以建议多做这方面的工作，在熟练掌握线性表 以建议多做这方面的工作，在熟练掌握线性表 +排序知识的基础 上，多锻炼算法的思想。
★数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 数据结构：小题目理 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 解知识最重要；大题目图 /查找 和算法， 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 算法最重要。中，思想只正确程 序写，基本上就能得到 一半以的分数。当然在考场想序写，基本上就能得到 一半以的分数。当然在考场想序写，基本上就能得到 一半以的分数。当然在考场想的方法 就是最好， 时间复杂度和空能最优好不能就写想到的 。所以 。所以 数据结构的 复习，最重要是算法思想数据结构的 复习，最重要是算法思想训
7. 严教苛求的意思
严教，指严格教诲。
苛求，拼音是kē qiú，意思是过严地要求。
8. 计算教学中如何正确处理算理和算法的关系
计算的算理是指计算的理论依据，通俗地讲就是计算的道理。算理一般由数学概念、定律、性质等构成，用来说明计算过程的合理性和科学性。计算的算法是计算的基本程序或方法，是算理指导下的一些人为规定，用来说明计算过程中的规则和逻辑顺序。
算理和算法既有联系，又有区别。算理是客观存在的规律，主要回答“为什么这样算”的问题；算法是人为规定的操作方法，主要解决“怎样计算”的问题。算理是计算的依据，是算法的基础，而算法则是依据算理提炼出来的计算方法和规则，它是算理的具体体现。算理为计算提供了正确的思维方式，保证了计算的合理性和可行性；算法为计算提供了便捷的操作程序和方法，保证了计算的正确性和快速性。算理和算法是计算教学中相辅相成、缺一不可的两个方面。
处理好算理与算法的关系对于突出计算教学核心，抓住计算教学关键具有重要的作用。当前，计算教学中“走极端”的现象实质上是没有正确处理好算理与算法之间关系的结果。一些教师受传统教学思想、教学方法的支配，计算教学只注重计算结果和计算速度，一味强化算法演练，忽视算理的推导，教学方式“以练代想”，学生“知其然，不知其所以然”，导致教学偏向“重算法、轻算理”的极端。与此相反，一些教师片面理解了新课程理念和新教材，他们把过多的时间用在形式化的情境创设、动手操作、自主探索、合作交流上，在理解算理上大做文章，过分强调为什么这样算，还可以怎样算，却缺少对算法的提炼与巩固，造成学生理解算理过繁，掌握算法过软，形成技能过难，教学走向“重算理、轻算法”的另一极端。
如何正确处理算理与算法的关系，防止“走极端”的现象，广大数学教师在教学实践中进行了有益的探索，取得了许多成功经验。比如，“计算教学要寻求算理与算法的平衡，使计算教学‘既重算理，又重算法”“把算理与算法有机融合，避免算理与算法的‘硬性对接’”“引导学生在理解算理的基础上自主地生成算法，在算法形成与巩固的过程中进一步明晰算理”“计算教学要让学生探究并领悟算理，及时抽象并掌握算法，力求形成技能并学会运用”等等，这些观点对于计算教学少走弯路、提高计算教学质量具有重要作用。
对此，笔者认为，处理计算教学中算理与算法的关系还应注意以下五点：一是算理与算法是计算教学中有机统一的整体，形式上可分，实质上不可分，重算法必须重算理，重算理也要重算法；二是计算教学的问题情境既为引出新知服务，体现“学以致用”，也为理解算理、提炼算法服务，教学要注意在“学用结合”的基础上，以理解算理，掌握算法，形成技能为主；三是算理教学需借助直观，引导学生经历自主探索、充分感悟的过程，但要把握好算法提炼的时机和教学的“度”，为算法形成与巩固提供必要的练习保证；四是算法形成不能依赖形式上的模仿，而要依靠算理的透彻理解，只有在真正理解算理的基础上掌握算法、形成计算技能，才能算是找到了算理与算法的平衡点；五是要防止算理与算法之间出现断痕或硬性对接，要充分利用例题或“试一试”中的“可以怎样算？”“在小组里说一说，计算时要注意什么？”等问题，指导学生提炼算法，为算理与算法的有效衔接服务。
9. 数据结构与算法分析荣政和严蔚敏版区别
严书我有系统地学习过，Mark Allen的书也粗略地读过一些。
这两本书虽然都是数据结构的教科书，但面向的读者类型并不一样。严书通常面向的读者是低年级的本科生，而Mark Allen的书面向的是高年级本科生和研究生。Mark Allen在前言部分也明确地说了这是一本进阶的数据结构教材。
严书基本上是国内使用最为广泛的数据结构教材，也是考研408的官方指定用书。严书全篇的逻辑体系非常清楚，国内出版的其他数据结构的书也都或多或少有严书的影子。它的内容组织是从数据结构的视角开展的。从逻辑结构的角度来看，全书是按从线性结构到非线性结构的思路来进行介绍的。在每一章的具体数据结构的实例里，又按物理结构从数组实现到链表实现来展开，从中穿插少量的算法复杂度分析等理论分析内容。严书把具有明显算法色彩的搜索主题和排序主题单独成章，放在了书的末尾几章，把读者从数据结构角度的视角引领到算法角度的视角，为后续进阶的算法课程做铺垫，这在内容编排上是很科学的。
数据结构和算法二者实际上是密不可分的。算法可以看作是定义在特定数据结构上的操作的序列，许多算法实际上是依托于数据结构的设计才能得以实现的。有不少教材不将二者分开，是将数据结构与算法同时讲述，Mark Allen的这本书就是非常经典的一本。
Mark Allen这本书在数据结构和算法两个角度上同时进行讲述。数据结构的部分不如严书讲得细致，但关键的要点都勾画出来了，代码部分也需要读者进行自行补充。对于高年级本科生和研究生来说，具体的实现不是什么困难的事情，Mark的这种处理方式容易使重点突出，这也是全书内容详实但篇幅不大的原因。Mark Allen这本书在算法部分涉及较为深入，有详细的理论推导和复杂度证明，课后习题里也有一定难度的算法题和算法分析题。除此之外，Mark Allen这本书还涉及到复杂的数据结构，例如左式堆、二项队列、红黑树、斐波那契堆等，这些内容在严书这种面向低年级本科生的教材里基本上是不提及的
10. 如何提高算法
计算的准确性不但在“应试教育”中占主要地位,在“素质教育”的今天同样重要。因为式子题的计算是学生解决实际问题的基础,是每个小学生必须掌握的数学基础知识和基本技能。只有计算过硬,才能进一步学好应用题和其他学科知识。式子题计算是各年级的重要内容,根据学生的考试和作业看,造成成绩不理想的原因是计算能力差,准确率不高。造成这种现象的原因是多方面的:首先是低年级忽略了口算训练,其次是在各年级中轻视了式子题的教学,误认为计算式子题只要弄清计算顺序,便能算出来,这种想法造成学生计算不细心,准确率低,从而缺乏攻克复杂式子题的兴趣和信心。
计算准确,要从低年级抓起,不仅要教学生算法,更要重视口算的训练。口算是笔算、估算的基础,只有让学生在理解的基础上掌握了口算的方法,坚持练习,逐步达到熟练的程度,才会在中、高年级中熟练、准确地计算。同样,中高年级也不能忽视口算的练习。
式子题的训练,还要从读题做起,读题要求学生正确规范,这样有助于弄清运算顺序。有括号题,如(a+b)c,可读作a与b的和乘以c,不能把括号读出来,严格要求学生读准,从中悟出运算顺序,确定自己的算法。弄清计算顺序是计算的前期。不这样训练,学生容易忽略和弄错顺序,对“准确”没有把握,长期这样,学生会对数学失去信心,失去积极性,教师也会对学生的计算失去信心。
文字题是式子题的读题与列式计算的训练,在读题的基础上,让学生列出算式,正反结合训练,会对学生的计算进行强化。文字题既然是计算题的叙述,那么解决文字题就是列出综合算式,它与应用题的解答有别,不能用分步计算,但可以用分步式分析。分析后列出综合计算是解决文字题的正确做法。
加强运算定律和运算性质的教学,多用于实际计算,让学生充分理解算理,掌握法则,鼓励学生运用简便算法。除题目要求简算外,教师要有意识地要求学生能简算的奥运用简算,提高学生的简算兴趣,使简算贯穿于一切计算之中,逐步摸索计算的技巧,做到计算合理,灵活,准确,迅速,有力的提高学生的计算能力。
计算准确性的训练要常抓不懈,养成检查、验算的习惯。对于一般的学生,式子题做完了不愿意检查、验算,造成准确率低的现象。针对这种现象,要有意识的训练,培养学生验算,长此以往,“准确”就有保证了。
在式子题的计算中,采用适当的计算方法也要给与指导和练习。如高年级的分数、小数、百分数的混合运算,要根据题和自己的特长确定具体算法。让学生针对题型动脑思考,自做练习,在和他人比较,找到巧妙的算法,也是准确性的训练。
对学生经过长期多方面的计算训练,培养学生严格、认真、对计算结果负责的良好习惯以及有毅力、肯动脑、克服困难的意志,学生的计算能力就会明显提高,为下一步学习打下坚实基础