Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define INF 0x3f3f3f3f
  7. #define LINF 0x3f3f3f3f3f3f3f3fLL
  8. #define MAXN 101
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef vector<int> vi;
  14. typedef pair<int,int> ii;
  15. typedef vector<ii> vii;
  16.  
  17. int n;
  18. double xi[MAXN];
  19. double pdd[MAXN][MAXN]; //começa em 0 ou 1 e termina em i
  20. bool memo[MAXN][MAXN];
  21.  
  22. double f(int i, int j){
  23. if(i == j)
  24. return pdd[i][j] = xi[i];
  25.  
  26. if(memo[i][j]) return pdd[i][j];
  27.  
  28. memo[i][j] = true;
  29. return pdd[i][j] = (f(i+1,j) - f(i,j-1))/(j-i);
  30. }
  31.  
  32.  
  33. vector<double> g(int j)
  34. {
  35. deque<vector<double> > polinomio;
  36. for(int i = 0; i < j; i++) {
  37. vector<double> a;
  38. a.pb(-xi[i]);
  39. a.pb(1);
  40. polinomio.pb(a);
  41. }
  42. while(polinomio.size() > 1){
  43. vector<double> a(polinomio[0].size()+1,0);
  44.  
  45. for(int i = 0; i < polinomio[0].size(); i++){
  46. for(int j = 0; j < polinomio[1].size(); j++){
  47. a[i+j] += polinomio[0][i] * polinomio[1][j];
  48. }
  49. }
  50. polinomio.pop_front();
  51. polinomio.pop_front();
  52. polinomio.push_front(a);
  53. }
  54. return polinomio[0];
  55. }
  56.  
  57. void printPoli(vector<double> g)
  58. {
  59. for(int i = g.size()-1; i >= 0; i--)
  60. {
  61. if(i!=0)
  62. printf("%c %gx^%d ",g[i]>=0?'+':'-', fabs(g[i]), i);
  63. else
  64. printf("%c %g",g[i]>=0?'+':'-', fabs(g[i]));
  65. }
  66. return;
  67. }
  68.  
  69. int main(){
  70. scanf("%d",&n);
  71.  
  72. for(int i = 0; i < n; i++)
  73. scanf("%lf",&xi[i]);
  74.  
  75. printPoli(g(n));
  76.  
  77. printf("\n");
  78. return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement