Push(s, r); n: =top(s, P) Div 4: Goto 0 2: pop (s): f:=Top(s, u1)&f: pop(s) 3: if not empty(s) then Goto Top(s, rd) end;{最后结果存在f中} 在黑板上举n=12为例进行演示! 另一个更简单方法由95级陈强和96级彭磊给出 int f(int n) lint f1 栈s置空;n进栈;f1:=1 while(s) pop(s, n): if(n==1)f1=f1+fl f(n>1)(push(s, n/2): push(s, n/4): 1 return fl int ff(int n) lint l, f[nl f[0]=1;f[1]=2; for(i=2;i<=n;i++)f[i]=f[i/2]*f[i/4] return f[n]: I 这是纯递推办法,虽效率低,但直观易编程! 以 FeiboNacc i数列第n项的求法引入这个算法 ①根据通项公式计算第n项之值 ②直接递推求解 由此看来,函数的非递归化因为是求值,比过程的非递归化更简单 n=0 ③递归方程:fn={2 n=1的解法见补充材料(学报待发) n>1 关于P与NP理论简介,可根据时间或学生实际略讲或不讲。 一、问题分类 1.无法写出算法的问题—一难题 2.有以多项式为界的算法存在的问题一P类问题 3.介于前两类之间的问题——存在指数阶算法,但不知道是否存在多项式算法(NP问 题) 二、概述 1.问题 2.问题实例 解决某问题的算法 4.问题实例的大小 5.将问题实例转化(映射)成字符串进行研究 6.两种难的问题Push(s,r);n:=top(s,Pn) Div 4;Goto 0; 2:pop(s);f:=Top(s,u1)&f;pop(s); 3:if not empty(s) then Goto Top(s,rd) end;{最后结果存在 f 中} 在黑板上举 n=12 为例进行演示！ 另一个更简单方法由 95 级陈强和 96 级彭磊给出： int f(int n) {int f1; 栈 s 置空；n 进栈;f1:=1; while(s) {pop(s,n);if(n==1)f1=f1+f1; if(n>1){push(s,n/2);push(s,n/4);} } return f1; } 或： int ff(int n) {int I,f[n]; f[0]=1;f[1]=2; for(i=2;i<=n;i++)f[i]=f[i/2]*f[i/4]; return f[n];} 这是纯递推办法，虽效率低，但直观易编程！ 以 FeiboNacci 数列第 n 项的求法引入这个算法： ①根据通项公式计算第 n 项之值； ②直接递推求解 由此看来，函数的非递归化因为是求值，比过程的非递归化更简单。 ③递归方程： ï ï î ï ï í ì > = = = * 1 2 1 1 0 2 4 f f n n n f n n n 的解法见补充材料（学报待发）。 关于 P 与 NP 理论简介，可根据时间或学生实际略讲或不讲。 一、问题分类 1．无法写出算法的问题——难题 2．有以多项式为界的算法存在的问题——P 类问题 3．介于前两类之间的问题——存在指数阶算法，但不知道是否存在多项式算法（NP 问 题） 二、概述 1．问题 2．问题实例 3．解决某问题的算法 4．问题实例的大小 5．将问题实例转化（映射）成字符串进行研究 6．两种难的问题