▶ 书中第六章部分程序,加上自己补充的代码,包括快速傅里叶变换,多项式表示

● 快速傅里叶变换,需要递归

 package package01;

 import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Complex; public class class01
{
private static final Complex ZERO = new Complex(0, 0);
private static final double EPSILON = 1e-8;
private class01() { } public static Complex[] fft(Complex[] x)// 正向傅里叶变换
{
int n = x.length;
if (n == 1)
return new Complex[] {x[0]};
if (n % 2 != 0)
throw new IllegalArgumentException("n != 2^k"); Complex[] temp = new Complex[n/2], result = new Complex[n];
for (int k = 0; k < n/2; k++) // 偶数项和奇数分别递归
temp[k] = x[2*k];
Complex[] q = fft(temp);
for (int k = 0; k < n/2; k++)
temp[k] = x[2*k + 1];
Complex[] r = fft(temp);
for (int k = 0; k < n/2; k++) // 合并
{
double kth = -2 * k * Math.PI / n;
Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
result[k] = q[k].plus(wk.times(r[k]));
result[k + n/2] = q[k].minus(wk.times(r[k]));
}
return result;
} public static Complex[] ifft(Complex[] x)// 傅里叶反变换,共轭、正变换、再共轭,最后除以项数
{
int n = x.length;
Complex[] result = new Complex[n], temp;
for (int i = 0; i < n; i++)
result[i] = x[i].conjugate();
result = fft(result);
for (int i = 0; i < n; i++)
result[i] = result[i].conjugate();
for (int i = 0; i < n; i++)
result[i] = result[i].scale(1.0 / n);
return result;
} public static Complex[] cconvolve(Complex[] x, Complex[] y)// 环形卷积
{
if (x.length != y.length)
throw new IllegalArgumentException("x.length != y.length");
int n = x.length;
Complex[] a = fft(x), b = fft(y), c = new Complex[n];
for (int i = 0; i < n; i++)
c[i] = a[i].times(b[i]);
return ifft(c);
} public static Complex[] convolve(Complex[] x, Complex[] y)// 线性卷积,后一半垫 0
{
if (x.length != y.length)
throw new IllegalArgumentException("x.length != y.length");
Complex[] a = new Complex[2 * x.length], b = new Complex[2 * y.length];
for (int i = 0; i < x.length; i++)
a[i] = x[i];
for (int i = x.length; i < 2*x.length; i++)
a[i] = ZERO;
for (int i = 0; i < y.length; i++)
b[i] = y[i];
for (int i = y.length; i < 2*y.length; i++)
b[i] = ZERO;
return cconvolve(a, b);
} private static void show(Complex[] x, String title)
{
StdOut.printf("%s\n-------------------\n",title);
for (int i = 0; i < x.length; i++)
StdOut.println(x[i]);
StdOut.println();
} public static void main(String[] args)
{
int n = 16;
Complex[] x = new Complex[n];
for (int i = 0; i < n; i++)
x[i] = new Complex(StdRandom.uniform(-1.0, 1.0), 0); show(x, "x");
Complex[] y = fft(x);
show(y, "y = fft(x)");
Complex[] z = ifft(y);
show(z, "z = ifft(y)");
Complex[] c = cconvolve(x, x);
show(c, "c = cconvolve(x, x)");
Complex[] d = convolve(x, x);
show(d, "d = convolve(x, x)");
}
}

● 多项式表示

 package package01;

 import edu.princeton.cs.algs4.StdOut;

 public class class01
{
private int[] coef; // 系数列表
private int degree; // 次数 public class01(int a, int b) // 建立单项式 a*x^b
{
coef = new int[b + 1];
coef[b] = a;
reduce();
} private void reduce() // 记录多项式的次数
{
degree = -1;
for (int i = coef.length - 1; i >= 0; i--)
{
if (coef[i] != 0)
{
degree = i;
return;
}
}
} public int degree()
{
return degree;
} public class01 plus(class01 that) // p(x) + q(x),把系数从低次项向高次项各加一遍
{
class01 poly = new class01(0, Math.max(degree, that.degree));
for (int i = 0; i <= degree; i++)
poly.coef[i] = coef[i];
for (int i = 0; i <= that.degree; i++)
poly.coef[i] += that.coef[i];
poly.reduce();
return poly;
} public class01 minus(class01 that)
{
class01 poly = new class01(0, Math.max(degree, that.degree));
for (int i = 0; i <= degree; i++)
poly.coef[i] = coef[i];
for (int i = 0; i <= that.degree; i++)
poly.coef[i] -= that.coef[i];
poly.reduce();
return poly;
} public class01 times(class01 that)
{
class01 poly = new class01(0, degree + that.degree);
for (int i = 0; i <= degree; i++)
{
for (int j = 0; j <= that.degree; j++)
poly.coef[i + j] += (coef[i] * that.coef[j]);
}
poly.reduce();
return poly;
} public class01 compose(class01 that)// p(q(x)),用了秦九韶
{
class01 poly = new class01(0, 0);
for (int i = degree; i >= 0; i--)
{
class01 term = new class01(coef[i], 0);
poly = term.plus(that.times(poly));
}
return poly;
} public class01 differentiate() // p'(x)
{
if (degree == 0)
return new class01(0, 0);
class01 poly = new class01(0, degree - 1);
poly.degree = degree - 1;
for (int i = 0; i < degree; i++)
poly.coef[i] = (i + 1) * coef[i + 1];
return poly;
} public int evaluate(int x) // p(x) /. {x->a}
{
int p = 0;
for (int i = degree; i >= 0; i--)
p = coef[i] + (x * p);
return p;
} public int compareTo(class01 that)
{
if (degree < that.degree)
return -1;
if (degree > that.degree)
return +1;
for (int i = degree; i >= 0; i--)
{
if (coef[i] < that.coef[i])
return -1;
if (coef[i] > that.coef[i])
return +1;
}
return 0;
} @Override
public String toString()
{
if (degree == -1)
return "0";
if (degree == 0)
return "" + coef[0];
if (degree == 1)
return coef[1] + "x + " + coef[0];
String s = coef[degree] + "x^" + degree;
for (int i = degree - 1; i >= 0; i--)
{
if (coef[i] == 0)
continue;
if (coef[i] > 0)
s += " + " + (coef[i]);
if (coef[i] < 0)
s += " - " + (-coef[i]);
s += (i == 1) ? "x" : ("x^" + i);
}
return s;
} public static void main(String[] args)
{
class01 zero = new class01(0, 0);
class01 p1 = new class01(4, 3);
class01 p2 = new class01(3, 2);
class01 p3 = new class01(1, 0);
class01 p4 = new class01(2, 1);
class01 p = p1.plus(p2).plus(p3).plus(p4); // 4x^3 + 3x^2 + 1 class01 q1 = new class01(3, 2);
class01 q2 = new class01(5, 0);
class01 q = q1.plus(q2); // 3x^2 + 5 StdOut.println("zero(x) = " + zero);
StdOut.println("p(x) = " + p);
StdOut.println("q(x) = " + q);
StdOut.println("p(x) + q(x) = " + p.plus(q));
StdOut.println("p(x) * q(x) = " + p.times(q));
StdOut.println("p(q(x)) = " + p.compose(q));
StdOut.println("p(x) - p(x) = " + p.minus(p));
StdOut.println("0 - p(x) = " + zero.minus(p));
StdOut.println("p(3) = " + p.evaluate(3));
StdOut.println("p'(x) = " + p.differentiate());
StdOut.println("p''(x) = " + p.differentiate().differentiate());
}
}

最新文章

  1. 【jQuery UI 1.8 The User Interface Library for jQuery】.学习笔记.10.Button 和 Autocomplete控件
  2. 怎么使用Docker搭建PHP开发环境呢?
  3. mac下U盘装机系统的制作(命令行)
  4. pthread的线程安全性
  5. java jfinal + ajaxfileupload.js 上传
  6. 10:Hello, World!的大小
  7. Microsoft Project 2010 简体中文专业版 + 永久激活密钥
  8. aliyun 主机Nginx 上配置Drupal 伪静态
  9. 通过this获取当前点击选项相关数据
  10. WebDriver获取table的内容(通过动态获取Table单元格的TagName对其innerHTML值进行获取)
  11. 百度导航试用 vs 高德导航
  12. 用ildasm和ilasm对.net下的exe程序进行破解初探
  13. ABP Zero 导航菜单之角色权限
  14. URL传递中文参数乱码问题
  15. 服务器与本地的控制工具unison
  16. Redis入门篇(安装与启动)
  17. [HAOI2007] 修筑绿化带
  18. 【Java编程思想笔记】-集合1
  19. android studio build.gradle 中的dependencies 的 compile jar文件
  20. c# 除掉前三个字符,剩下的4个字符全为数字方为特殊车辆

热门文章

  1. Lua手动编译姿势
  2. 深入了解view以及自定义控件
  3. Procdure for wanfo business report
  4. Android二手交易平台,dagger2+mvp+Bmob后台云搭建
  5. System.Windows.Forms.Timer反编译学习
  6. [转]十年前的老文:以 Linux 的名义
  7. ZOJ-3725 Painting Storages DP
  8. POJ 3356 AGTC(最长公共子)
  9. java.lang.NoClassDefFoundError: com/mchange/v2/ser/Indirector
  10. linux(3)磁盘与文件系统管理/查看硬盘、内存空间/文件系统的操作/ 文件的压缩和打包
  11. 容器化时代我们应当选择Kubernetes
  12. JavaScript match()方法和正则表达式match()
  13. Linux时间日期类指令
  14. windows系统上搭建redis集群哨兵及主从复制
  15. bootstrap 中这段代码 使bundles 失败
  16. spring cloud学习(五)断路器 Hystrix
  17. $2018/8/15 = Day \ \ 1$杂题整理
  18. [原]时间格式化hh:mm:ss和HH:mm:ss区别
  19. 编写高质量代码改善C#程序的157个建议——建议141:不知道该不该用大括号时,就用
  20. Mac OS terminal终端常用命令