java算法:基于应用ADT例子
例1:多项式ADT接口
- classPoly{
-
Poly(int,int)
-
doubleeval(double)
-
voidadd(Poly)
-
voidmult(Poly)
-
publicStringtoString()
- }
class Poly{
Poly(int,int)
double eval(double)
void add(Poly)
void mult(Poly)
public String toString()
}
例2:多项式客户程序
- publicclassBinomial{
-
publicstaticvoidmain(Stringargs[]){
-
intN=100;
-
doublep=1.1;
-
Polyy=newPoly(1,0);
-
Polyt=newPoly(1,0);
-
t.add(newPoly(1,1));
-
for(inti=0;i<N;i++){
- y.mult(t);
-
System.out.println(y+"");
- }
-
System.out.println("value:"+y.eval(p));
- }
- }
public class Binomial{
public static void main(String args[]){
int N = 100;
double p = 1.1;
Poly y = new Poly(1,0);
Poly t = new Poly(1,0);
t.add(new Poly(1,1));
for(int i = 0; i < N; i++){
y.mult(t);
System.out.println(y + " ");
}
System.out.println("value: " + y.eval(p));
}
}
例3:多项式ADT的数组实现
- classPoly{
-
privateintn;
-
privateint[]a;
-
Poly(intc,intN){
-
a=newint[N+1];
-
n=N+1;
- a[N]=c;
-
for(inti=0;i<N;i++){
-
a[i]=0;
- }
- }
-
doubleeval(doubled){
-
doublet=0.0;
-
for(inti=n-1;i>=0;i--){
-
t=t*d+(double)a[i];
- }
-
returnt;
- }
-
voidadd(Polyp){
-
int[]t=newint[(p.n>n)?p.n:n];
-
for(inti=0;i<p.n;i++){
- t[i]=p.a[i];
- }
-
for(intj=0;j<n;j++){
- t[j]+=a[j];
- }
- a=t;
- n=t.length;
- }
-
voidmult(Polyp){
-
int[]t=newint[p.n+n-1];
-
for(inti=0;i<p.n;i++){
-
for(intij=0;j<n;j++){
- t[i+j]+=p.a[i]*a[j];
- }
- }
- a=t;
- n=t.length;
- }
-
publicStringtoString(){
-
Strings="";
-
for(inti=0;i<n;i++){
-
s+=a[i]+"";
- }
-
returns;
- }
- }
class Poly{
private int n;
private int[] a;
Poly(int c,int N){
a = new int[N+1];
n = N + 1;
a[N] = c;
for(int i = 0; i < N; i++){
a[i] = 0;
}
}
double eval(double d){
double t = 0.0;
for(int i = n - 1; i >= 0; i--){
t = t * d + (double)a[i];
}
return t;
}
void add(Poly p){
int[] t = new int[(p.n > n) ? p.n : n];
for(int i = 0; i < p.n; i++){
t[i] = p.a[i];
}
for(int j = 0; j < n; j++){
t[j] += a[j];
}
a = t;
n = t.length;
}
void mult(Poly p){
int[] t = new int[p.n + n -1];
for(int i = 0; i < p.n; i++){
for(inti j = 0; j < n; j++){
t[i+j] += p.a[i] * a[j];
}
}
a = t;
n = t.length;
}
public String toString(){
String s = "";
for(int i = 0; i < n; i++){
s += a[i] + " ";
}
return s;
}
}
注意:Horner算法:a4x4 + a3x3 + a2x2 + a1x + a0 = (((a4x + a3)x + a2)x + a1)x + a0
分享到:
相关推荐
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
4.2.2 例子:表达式树 4.3 查找树ADT——二叉查找树 4.3.1 contains方法 4.3.2 findMin方法和findMax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 AVL树 4.4.1 单旋转 4.4.2 双旋转 4.5 伸展树...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
3.3.3 应用 3.4 队列ADT 3.4.1 队列模型 3.4.2 队列的数组实现 3.4.3 队列的应用 小结 练习 第4章 树 4.1 预备知识 4.1.1 树的实现 4.1.2 树的遍历及应用 4.2 二叉树 4.2.1 实现 4.2.2 一个例子:...
3.6.3 应用 3.7 队列adt 3.7.1 队列模型 3.7.2 队列的数组实现 3.7.3 队列的应用 小结 练习第4章 树 4.1 预备知识 4.1.1 树的实现 4.1.2 树的遍历及应用 4.2 二叉树 4.2.1 实现 4.2.2 例子:...
3.6.3 应用 3.7 队列adt 3.7.1 队列模型 3.7.2 队列的数组实现 3.7.3 队列的应用 小结 练习第4章 树 4.1 预备知识 4.1.1 树的实现 4.1.2 树的遍历及应用 4.2 二叉树 4.2.1 实现 4.2.2 例子:...
◆ 诠释了ADT的主要应用,如查找航班图、事件驱动的模拟和八皇后问题 ◆ 大部分章节中的例子都使用了标准模板库(STL) ◆ 介绍了递归 ◆ 附录中提供了基本的C++语法,以帮助学生从其他语言转换为C++ 第1章 数据...
例子: ./build/scripts/cs2-lab10-wordcount-java asdf oiu qwer asdf oiu oiu qwer qwer oiu asdf asdf xzc EOF (ctrl-D or ctrl-Z) asdf=4 oiu=4 qwer=3 xzc=1 具体来说: 完成各种来源中的TODO...
第四部分 一个例子:游戏引擎和实现 206 第12章 设计(需求分析) 207 12.1 第一天:接到一个案子 207 12.2 第二天:需求分析 208 第13章 设计(领域分析与抽象) 210 13.1 原语设计 210 13.2 了解Yake 216 13.3 ...