Polynomial

Предадени решения

Краен срок:
21.11.2017 17:00
Точки:
15

Срокът за предаване на решения е отминал

extern crate solution as polynomial;
use self::polynomial::Polynomial;
fn valid_lp(poly: &Polynomial, points: &Vec<(f64, f64)>) -> bool {
points.iter().all(|point| poly.has(point))
}
#[test]
fn test_create_poly() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p = Polynomial::from(Vec::new());
assert_eq!(p, Polynomial::from(vec![0.0]));
assert_eq!(p, Polynomial::default());
let p = Polynomial::from(vec![1.0]);
assert_eq!(p, Polynomial::from(vec![1.0]));
let p = Polynomial::from(vec![0.0, 0.0, 1.0, 2.0, 5.0, 0.0]);
assert_eq!(p, Polynomial::from(vec![1.0, 2.0, 5.0, 0.0]));
}
#[test]
fn test_fp_comparison() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p = Polynomial::from(vec![1.0, 1e-25]);
assert_eq!(p.clone() * 3.0, Polynomial::from(vec![3.0, 3e-25]));
assert_eq!(p.clone() / 0.5, Polynomial::from(vec![2.0, 2e-25]));
assert_eq!(p.clone() + p.clone(), Polynomial::from(vec![2.0, 2e-25]));
}
#[test]
fn test_mul_poly_f64_zero() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p0 = Polynomial::from(Vec::new());
let p1 = p0.clone() * 2.0;
assert_eq!(p0, Polynomial::from(vec![0.0]));
assert_eq!(p1, Polynomial::from(vec![0.0]));
}
#[test]
fn test_mul_poly_f64() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p0 = Polynomial::from(vec![1.0, -2.0, 5.0]);
let p1 = p0.clone() * 5.0;
assert_eq!(p1, Polynomial::from(vec![5.0, -10.0, 25.0]));
}
#[test]
fn test_div_poly_f64_zero() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p0 = Polynomial::from(Vec::new());
let p1 = p0.clone() / 2.0;
assert_eq!(p0, Polynomial::from(vec![0.0]));
assert_eq!(p1, Polynomial::from(vec![0.0]));
}
#[test]
fn test_div_poly_f64() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p0 = Polynomial::from(vec![1.0, -2.0, 5.0]);
let p1 = p0.clone() / -6.0;
assert_eq!(p1, Polynomial::from(vec![1.0 / -6.0, -2.0 / -6.0, 5.0 / -6.0]));
}
#[test]
fn test_add_poly_zero_one() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let a = Polynomial::from(vec![]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a + b, Polynomial::from(vec![2.0, 0.0, 3.0]));
let a = Polynomial::from(vec![1.0]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a + b, Polynomial::from(vec![2.0, 0.0, 4.0]));
}
#[test]
fn test_add_poly() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let a = Polynomial::from(vec![1.0, -1.0]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a + b, Polynomial::from(vec![2.0, 1.0, 2.0]));
let a = Polynomial::from(vec![1.0, -1.0, 0.0]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a + b, Polynomial::from(vec![3.0, -1.0, 3.0]));
let a = Polynomial::from(vec![1.0, 2.0]);
let b = Polynomial::from(vec![-1.0, 3.0]);
assert_eq!(a + b, Polynomial::from(vec![5.0]));
}
#[test]
fn test_arithmetic_properties() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
// a + (-a) == 0
let a = Polynomial::from(vec![2.0, 0.0, 3.0]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]) * -1.0;
assert_eq!(a + b, Polynomial::default());
// a + b == b + a
let a = Polynomial::from(vec![0.0, 1.0, 2.0, 3.0, 0.0]);
let b = Polynomial::from(vec![4.0, 7.3, 13.37, 188.0]);
assert_eq!(a.clone() * b.clone(), b.clone() * a.clone());
assert_eq!(a.clone() + b.clone(), b.clone() + a.clone());
assert!(a.clone() + b.clone() == b.clone() + a.clone());
// (a + b) + c == a + (b + c)
let a = Polynomial::from(vec![0.0, 1.0, 2.0, 3.0, 0.0]);
let b = Polynomial::from(vec![4.0, 7.3, 13.37, 188.0]);
let c = Polynomial::from(vec![1.0 / 3.0]);
assert_eq! {
(a.clone() + b.clone()) + c.clone(),
a.clone() + (b.clone() + c.clone())
};
// (a + b) + c == a * c + b * c
assert_eq! {
(a.clone() + b.clone()) * c.clone(),
a.clone() * c.clone() + b.clone() * c.clone()
};
}
#[test]
fn test_mul_poly_zero_one() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let a = Polynomial::from(vec![]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a * b, Polynomial::from(vec![0.0, 0.0, 0.0]));
let a = Polynomial::from(vec![1.0]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a * b, Polynomial::from(vec![2.0, 0.0, 3.0]));
}
#[test]
fn test_mul_poly() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let a = Polynomial::from(vec![1.0, -5.0]);
let b = Polynomial::from(vec![1.0, 5.0]);
// (x+c)*(x-c) = x^2 - c^2
assert_eq!(a * b, Polynomial::from(vec![1.0, 0.0, -25.0]));
let a = Polynomial::from(vec![1.0, -1.0]);
let b = Polynomial::from(vec![2.0, 0.0, 3.0]);
assert_eq!(a * b, Polynomial::from(vec![2.0, -2.0, 3.0, -3.0]));
}
#[test]
fn test_has_point() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let p = Polynomial::from(vec![1.0, 2.0, 1.0]);
assert!(p.has(&(-1.0, 0.0)));
assert!(p.has(&(5.0, 36.0)));
let p = Polynomial::from(vec![1.0, 1e-25]);
assert!(p.has(&(-1e-25, 0.0)));
assert!(p.has(&(-3e-25, -2e-25)));
}
#[test]
fn test_lagrange_poly_1() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
// x^2 + 2*x + 1
let points = vec![
(-1.0, 0.0),
( 0.0, 1.0),
( 1.0, 4.0)
];
let poly = Polynomial::interpolate(points.clone());
let poly = poly.unwrap();
assert_eq!(poly, Polynomial::from(vec![1.0, 2.0, 1.0]));
assert!(valid_lp(&poly, &points));
}
#[test]
fn test_lagrange_poly_2() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let points = vec![
(-2.0, 0.0),
( 1.3, -10.0),
( 5.9, 4.0),
( 7.2, 4.0),
( 10.0, 4.0)
];
let poly = Polynomial::interpolate(points.clone());
assert!(poly.is_some());
assert!(valid_lp(&poly.unwrap(), &points));
}
#[test]
fn test_lagrange_poly_err_eq_x() {
// just in case, guard against dummy from implementations
assert_ne!(Polynomial::from(vec![2.0]), Polynomial::from(vec![1.0]));
let points = vec![
(-1.0, 0.0),
( 1.0, 1.0),
( 1.0, 4.0)
];
let poly = Polynomial::interpolate(points.clone());
assert!(poly.is_none());
}

С тази задача, ще ви накараме да упражните уменията си с итератори, цикли, вектори и аритметични операции. За целта трябва да дефинирате структура Polynomial, която да има следния публичен интерфейс:

/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
    // ...
}

impl Polynomial {
    /// Проверява дали една точка удовлетворява полинома
    ///
    /// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
    fn has(&self, point: &(f64, f64)) -> bool {
        // ...
    }

    /// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
    /// по-долу.
    ///
    /// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
    /// е `x^2 + 2*x + 1`.
    ///
    /// Ако две точки имат равни X координати, върнете `None`.
    ///
    /// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
    /// стойности. Можете да го направите, разбира се, ако решите.
    ///
    fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
        // ...
    }
}

impl From<Vec<f64>> for Polynomial {
    /// Създава нов полином от подадените коефициенти
    ///
    /// Редът на коефициентите е от най-високата степен на променливата към най-малката.
    ///
    /// Ако е подаден празен вектор се създава полином отговарящ на константата `0.0`. Ако на
    /// най-високите степени на полинома има нули, премахнете ги. (Това е причината аргумента
    /// `coefs` да се предава като `mut coefs`. Тоест:
    ///
    /// - Polynomial::from(vec![]) == Polynomial::from(vec![0.0]);
    /// - Polynomial::from(vec![0.0, 1.0]) == Polynomial::from(vec![1.0]);
    ///
    /// Полином който отговаря на Polynomial::from(vec![1.0, 2.0, 0.0, 3.0])
    /// е `x^3 + 2.0*x^2 + 3.0`.
    ///
    fn from(mut coefs: Vec<f64>) -> Self {
        // ...
    }
}

/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial { /* ... */ }

/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 1e-10, т.е. |Ai - Bi| < 1e-10.
///
/// Ако полиномите имат водещи нули те трябва да се игнорират. Например следните два полинома
/// са равни:
///
/// -                     x^3 + 2.0*x^2 + 3.0
/// - 0.0*x^5 + 0.0*x^4 + x^3 + 2.0*x^2 + 3.0
///
impl PartialEq for Polynomial {
    fn eq(&self, rhs: &Self) -> bool {
        // ...
    }
}

/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
    type Output = Polynomial;
    fn mul(self, rhs: f64) -> Self::Output;
}

/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
    type Output = Polynomial;
    fn div(self, rhs: f64) -> Self::Output;
}

/// Умножава полином с полином -- всички компоненти на полинома биват умножени с всички
/// компоненти на десния полином.
///
/// Пример:
///
/// Polynomial::from(vec![1.0, 2.0]) * Polynomial::from(vec![2.0, 1.0])
/// // => Polynomial::from(vec![2.0, 5.0, 2.0])
///
impl Mul for Polynomial {
    type Output = Polynomial;
    fn mul(self, rhs: Polynomial) -> Self::Output;
}

/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
    type Output = Polynomial;
    fn add(self, rhs: Polynomial) -> Self::Output;
}

За интерполацията може да използвате метода на Лагранж: Интерполационният полином на Лагранж L(x) за дадено множество от точки

Точки

се намира по формулата:

Интерполационен полином

където

Базов полином

Ограничения

Материали

Внимавайте всички типове и методи, които ни трябват, да бъдат маркирани като pub, за да могат тестовете ни да ги викат. Задължително се погрижете базовия тест да минава: базов тест

Прочетете и общия guide за писане на домашни.

Задължително прочетете (или си припомнете): Указания за предаване на домашни