Advertisement
daskalot

Untitled

May 5th, 2019
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.83 KB | None | 0 0
  1. import java.util.*;
  2. import java.lang.Math;
  3.  
  4. class Complex{
  5. double re;
  6. double im;
  7.  
  8. public Complex(double real, double imag) {
  9. re = real;
  10. im = imag;
  11. }
  12.  
  13. public String toString() {
  14. double tRe = (double)Math.round(re * 100000) / 100000;
  15. double tIm = (double)Math.round(im * 100000) / 100000;
  16. if (tIm == 0) return tRe + "";
  17. if (tRe == 0) return tIm + "i";
  18. if (tIm < 0) return tRe + "-" + (-tIm) + "i";
  19. return tRe + "+" + tIm + "i";
  20. }
  21.  
  22. public Complex conj() {
  23. return new Complex(re, -im);
  24. }
  25.  
  26. // sestevanje
  27. public Complex plus(Complex b) {
  28. Complex a = this;
  29. double real = a.re + b.re;
  30. double imag = a.im + b.im;
  31. return new Complex(real, imag);
  32. }
  33.  
  34. // odstevanje
  35. public Complex minus(Complex b) {
  36. Complex a = this;
  37. double real = a.re - b.re;
  38. double imag = a.im - b.im;
  39. return new Complex(real, imag);
  40. }
  41.  
  42. // mnozenje z drugim kompleksnim stevilo
  43. public Complex times(Complex b) {
  44. Complex a = this;
  45. double real = a.re * b.re - a.im * b.im;
  46. double imag = a.re * b.im + a.im * b.re;
  47. return new Complex(real, imag);
  48. }
  49.  
  50. // mnozenje z realnim stevilom
  51. public Complex times(double alpha) {
  52. return new Complex(alpha * re, alpha * im);
  53. }
  54.  
  55. // reciprocna vrednost kompleksnega stevila
  56. public Complex reciprocal() {
  57. double scale = re*re + im*im;
  58. return new Complex(re / scale, -im / scale);
  59. }
  60.  
  61. // deljenje
  62. public Complex divides(Complex b) {
  63. Complex a = this;
  64. return a.times(b.reciprocal());
  65. }
  66.  
  67. // e^this
  68. public Complex exp() {
  69. return new Complex(Math.exp(re) * Math.cos(im), Math.exp(re) * Math.sin(im));
  70. }
  71.  
  72.  
  73. //potenca komplesnega stevila
  74. public Complex pow(int k) {
  75.  
  76. Complex c = new Complex(1,0);
  77. for (int i = 0; i <k ; i++) {
  78. c = c.times(this);
  79. }
  80. return c;
  81. }
  82.  
  83. }
  84.  
  85. public class i8{
  86. public static void printArray( double[] array ){
  87. int len = array.length;
  88. System.out.print( array[0] );
  89. for (int i = 1; i < len; i++ ){
  90. System.out.print( " " + array[i] );
  91. }
  92. System.out.println();
  93. return;
  94. }
  95. public static void printComplexArray( Complex[] array ){
  96. int len = array.length;
  97. System.out.print( array[0].toString() );
  98. for (int i = 1; i < len; i++ ){
  99. System.out.print( " " + array[i].toString() );
  100. }
  101. System.out.println();
  102. return;
  103. }
  104. public static Complex[] recursiveFFT(double[] vhod ){
  105. int len = vhod.length;
  106. if (len==1){
  107. Complex res = new Complex( 1.0*vhod[0] , 0.0 );
  108. Complex[] resitev = new Complex[1];
  109. resitev[0] = res;
  110. return resitev;
  111. }
  112. double[] novSod = new double[len/2];
  113. double[] novLih = new double[len/2];
  114. for ( int i = 0; i < len/2; i++){
  115. novSod[i] = vhod[2*i];
  116. novLih[i] = vhod[2*i+1];
  117. }
  118. Complex[] sodC = new Complex[len/2];
  119. Complex[] lihC = new Complex[len/2];
  120. sodC = recursiveFFT(novSod);
  121. lihC = recursiveFFT(novLih);
  122. Complex compI = new Complex(0.0,1.0);
  123. Complex exponent = compI.times(Math.PI*2.0/len);
  124. Complex w = exponent.exp();
  125. Complex wk = new Complex(1.0,0.0);
  126. Complex[] y = new Complex[len];
  127. for ( int k = 0; k < len/2; k++ ){
  128. y[k] = sodC[k].plus( wk.times(lihC[k]));
  129. y[k + len/2 ] = sodC[k].minus(wk.times(lihC[k]));
  130. wk = wk.times(w);
  131. }
  132. printComplexArray(y);
  133. return y;
  134. }
  135.  
  136. public static Complex[] recursiveFFTInverse(Complex[] vhod ){
  137. int len = vhod.length;
  138. if (len==1) return vhod;
  139. Complex[] novSod = new Complex[len/2];
  140. Complex[] novLih = new Complex[len/2];
  141. for (int i = 0; i < len/2; i++){
  142. novSod[i] = vhod[2*i];
  143. novLih[i] = vhod[2*i+1];
  144. }
  145. Complex[] vmesSodo = recursiveFFTInverse(novSod);
  146. Complex[] vmesLiho = recursiveFFTInverse(novLih);
  147. Complex compI = new Complex(0.0,1.0); // to je i.
  148. Complex exponent = compI.times(Math.PI*2.0/len);
  149. Complex w = exponent.exp();
  150. w=w.reciprocal();
  151. Complex wk = new Complex(1.0,0.0);
  152. Complex[] resitev = new Complex[len];
  153. for ( int k = 0; k < len/2; k++ ){
  154. resitev[k] = vmesSodo[k].plus( wk.times(vmesLiho[k]));
  155. resitev[k+len/2] = vmesSodo[k].minus(wk.times(vmesLiho[k]));
  156. wk = wk.times(w);
  157. }
  158. printComplexArray(resitev);
  159. return resitev;
  160. }
  161.  
  162. public static void main( String[] args ){
  163. Scanner sc = new Scanner( System.in );
  164. int n = sc.nextInt();
  165. int stTock = (int)(Math.pow(2,(int)Math.ceil(Math.log(2*n - 1)/Math.log(2))));
  166. double[] koefPrviPolinom = new double[stTock];
  167. double[] koefDrugiPolinom = new double[stTock];
  168. for ( int i = 0; i < n; i++ ) koefPrviPolinom[i] = 1.0*sc.nextInt();
  169. for ( int i = 0; i < n; i++ ) koefDrugiPolinom[i] = 1.0*sc.nextInt();
  170. Complex[] vrednostiPrvi = recursiveFFT(koefPrviPolinom);
  171. Complex[] vrednostiDrugi = recursiveFFT(koefDrugiPolinom);
  172. Complex[] arrayZmnozkov = new Complex[stTock];
  173.  
  174. for ( int i = 0; i < stTock; i++ ){
  175. arrayZmnozkov[i] = vrednostiPrvi[i].times( vrednostiDrugi[i] );
  176. }
  177. Complex[] y = recursiveFFTInverse(arrayZmnozkov);
  178. Complex _n = new Complex(stTock,0);
  179. for(int i=0;i<stTock;i++) y[i] = y[i].divides(_n);
  180. printComplexArray(y);
  181. }
  182.  
  183. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement