【DataStructure】Another usage of List: Polynomial

2024-03-02 20:32

本文主要是介绍【DataStructure】Another usage of List: Polynomial,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Statements: This blog was written by me, but most of content  is quoted from book【Data Structure with Java Hubbard】 


【Description】

Apolynomialis a mathematical function of the form:

p(x) = a0xn+ a1xn–1+a2xn–2+ ˜˜˜+an–1x + an The greatest exponent, n, is called the degreeof the polynomial. For example, p(x) = 7x4– 2 is abpolynomial of degree 4. The simplest polynomials are constant polynomialssuch as p(x) = 6 (degree 0) and linear polynomialssuch as p(x) = 9x+ 6 (degree 1). The unique zero polynomial p(x) = 0 is defined to have degree –1. In this section we present a Polynomialclass whose instances represent mathematical polynomials and which supports the usual algebraic operations on polynomials.A polynomial can be regarded as a sum of distinct terms. A termis a mathematical function of the form t(x) = cxe, where cis any real number and eis any nonnegative integer. The number ciscalled the coefficient, and the number eis called the exponent.To define a class whose objects represent polynomials, we use a linked list of Termobjects.For example, the polynomial p(x) = 3x2–2x+ 5 could be represented as a list of three elements,where the first element represents the term 3x2, the second element represents the term – 2x, andthe third element represents the (constant) term 5.

【Implement】

package com.albertshao.ds.polynomial;//  Data Structures with Java, Second Edition
//  by John R. Hubbard
//  Copyright 2007 by McGraw-Hillimport java.util.*;public class Polynomial {private List<Term> list = new LinkedList<Term>();public static final Polynomial ZERO = new Polynomial();private Polynomial() {}public Polynomial(double coef, int exp) {if (coef != 0.0) {list.add(new Term(coef, exp));}}public Polynomial(double... a) {for (int i=0; i<a.length; i++) {if (a[i] != 0.0) {list.add(new Term(a[i], i));}}}public Polynomial(Polynomial p) {  // copy constructorfor (Term term : p.list) {this.list.add(new Term(term));}}public int degree() {if (list.isEmpty()) {return -1;} else {return list.get(list.size()-1).exp;}}public boolean isZero() {return list.isEmpty();}public Polynomial plus(Polynomial p) {if (this.isZero()) {return new Polynomial(p);}if (p.isZero()) {return new Polynomial(this);}Polynomial q = new Polynomial();ListIterator<Term> it = list.listIterator();ListIterator<Term> itp = p.list.listIterator();while (it.hasNext() && itp.hasNext()) {Term term = it.next();Term pTerm = itp.next();if (term.exp < pTerm.exp) {q.list.add(new Term(term));itp.previous();} else if (term.exp == pTerm.exp) {q.list.add(new Term(term.coef + pTerm.coef, term.exp));} else {  // (term.exp > pTerm.exp) q.list.add(new Term(pTerm));it.previous();}}while (it.hasNext()) {q.list.add(new Term(it.next()));}while (itp.hasNext()) {q.list.add(new Term(itp.next()));}return q;}public String toString() {if (this.isZero()) {return "0";}Iterator<Term> it = list.iterator();StringBuilder buf = new StringBuilder();boolean isFirstTerm = true;while (it.hasNext()) {Term term = it.next();double c = term.coef;int e = term.exp;if (isFirstTerm) {buf.append(String.format("%.2f", c));isFirstTerm = false;} else {if (term.coef < 0) {buf.append(String.format(" - %.2f", -c));} else {buf.append(String.format(" + %.2f", c));}}if (e == 1) {buf.append("x");} else if (e > 1) {buf.append("x^" + e);}}return buf.toString();}private class Term {private double coef;private int exp;public Term(double coef, int exp) {if (coef == 0.0 || exp < 0) {throw new IllegalArgumentException();}this.coef = coef;this.exp = exp;}public Term(Term that) {  // copy constructorthis(that.coef, that.exp);}}
}

//  Data Structures with Java, Second Edition
//  by John R. Hubbard
//  Copyright 2007 by McGraw-Hillpackage com.albertshao.ds.polynomial;public class TestPolynomial {public static void main(String[] args) {Polynomial p = new Polynomial(3, -8, 0, 0, 2, 1);Polynomial q = new Polynomial(0, 5, 6, 9);System.out.println("p: " + p);System.out.println("p.degree(): " + p.degree());System.out.println("q: " + q);System.out.println("q.degree(): " + q.degree());System.out.println("p.plus(q): " + p.plus(q));System.out.println("q.plus(p): " + q.plus(p));System.out.println("p.plus(q).degree(): " + p.plus(q).degree());Polynomial z = new Polynomial(0);System.out.println("z: " + z);System.out.println("z.degree(): " + z.degree());System.out.println("p.plus(z): " + p.plus(z));System.out.println("z.plus(p): " + z.plus(p));System.out.println("p: " + p);Polynomial t = new Polynomial(8.88, 44);System.out.println("t: " + t);System.out.println("t.degree(): " + t.degree());}
}

【Result】

p: 3.00 - 8.00x + 2.00x^4 + 1.00x^5
p.degree(): 5
q: 5.00x + 6.00x^2 + 9.00x^3
q.degree(): 3
p.plus(q): 3.00 - 3.00x + 6.00x^2 + 9.00x^3 + 2.00x^4 + 1.00x^5
q.plus(p): 3.00 - 3.00x + 6.00x^2 + 9.00x^3 + 2.00x^4 + 1.00x^5
p.plus(q).degree(): 5
z: 0
z.degree(): -1
p.plus(z): 3.00 - 8.00x + 2.00x^4 + 1.00x^5
z.plus(p): 3.00 - 8.00x + 2.00x^4 + 1.00x^5
p: 3.00 - 8.00x + 2.00x^4 + 1.00x^5
t: 8.88x^44
t.degree(): 44



这篇关于【DataStructure】Another usage of List: Polynomial的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/767335

相关文章

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

Java使用Stream流的Lambda语法进行List转Map的操作方式

《Java使用Stream流的Lambda语法进行List转Map的操作方式》:本文主要介绍Java使用Stream流的Lambda语法进行List转Map的操作方式,具有很好的参考价值,希望对大... 目录背景Stream流的Lambda语法应用实例1、定义要操作的UserDto2、ListChina编程转成M

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

java streamfilter list 过滤的实现

《javastreamfilterlist过滤的实现》JavaStreamAPI中的filter方法是过滤List集合中元素的一个强大工具,可以轻松地根据自定义条件筛选出符合要求的元素,本文就来... 目录1. 创建一个示例List2. 使用Stream的filter方法进行过滤3. 自定义过滤条件1. 定

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

python中列表list切分的实现

《python中列表list切分的实现》列表是Python中最常用的数据结构之一,经常需要对列表进行切分操作,本文主要介绍了python中列表list切分的实现,文中通过示例代码介绍的非常详细,对大家... 目录一、列表切片的基本用法1.1 基本切片操作1.2 切片的负索引1.3 切片的省略二、列表切分的高