Решение на Polynomial от Георги Ангелов

Обратно към всички решения

Към профила на Георги Ангелов

Код

use std::ops::{Add, Mul, Div};

/// Структура която представя полином от `n`та степен на една променлива

///

/// Пример за такъв полином e `x^2 + 2*x + 1`.

#[derive(Debug, Clone)]

pub struct Polynomial {

coefficients: Vec<f64>,

}

fn float_eq(a: f64, b: f64) -> bool {

(a - b).abs() < 1e-10

}

impl Polynomial {

/// Проверява дали една точка удовлетворява полинома

///

/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.

pub fn has(&self, point: &(f64, f64)) -> bool {

let (x, y) = *point;

float_eq(self.apply(x), y)

}

pub fn apply(&self, x: f64) -> f64 {

self.coefficients.iter()

.enumerate()

.map( |(exponent, coefficient)| coefficient * x.powi(exponent as i32) )

.sum()

}

fn map_coefficients<F>(self, map: F) -> Polynomial

where F: Fn(f64) -> f64

{

let coefficients: Vec<f64> = self.coefficients.into_iter()

.rev()

.map( |coefficient| map(coefficient) )

.collect();

Polynomial::from(coefficients)

}

/// Намира полином, който минава през подадените точки, по метода на Лагранж.

///

/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)

/// е `x^2 + 2*x + 1`.

///

/// Връща `None`, ако две точки имат равни X координати.

pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {

let k = points.len();

let mut result = Polynomial::default();

for j in 0..k {

let mut product_result = Polynomial::from(vec![1.0]);

for m in 0..k {

if m == j {

continue;

}

let numerator = Polynomial::from(vec![1.0, -points[m].0]);

let denominator = points[j].0 - points[m].0;

if float_eq(denominator, 0.0) {

return None;

}

product_result = product_result * (numerator / denominator);

}

result = result + product_result * points[j].1;

}

Some(result)

}

}

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 coefficients: Vec<f64>) -> Self {

coefficients = coefficients.into_iter()

.skip_while( |&x| float_eq(x, 0.0) )

.collect();

coefficients.reverse();

Polynomial { coefficients }

}

}

/// Създава полином отговарящ на константата `0.0`

impl Default for Polynomial {

fn default() -> Self {

Polynomial::from(vec![])

}

}

/// Проверява дали два полинома са равни.

///

/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента

/// са равни ако разликата между тях е по-малка от 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 {

if self.coefficients.len() != rhs.coefficients.len() {

return false;

}

self.coefficients.iter()

.zip(rhs.coefficients.iter())

.all( |(&a, &b)| float_eq(a, b) )

}

}

/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.

///

/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв

/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако

/// мислите за ownership-а на стойността.

///

impl Mul<f64> for Polynomial {

type Output = Polynomial;

fn mul(self, rhs: f64) -> Self::Output {

self.map_coefficients( |a| a * rhs )

}

}

/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.

impl Div<f64> for Polynomial {

type Output = Polynomial;

fn div(self, rhs: f64) -> Self::Output {

self.map_coefficients( |a| a / rhs )

}

}

/// Умножава полином с полином -- всички компоненти на полинома биват умножени с всички

/// компоненти на десния полином.

///

/// Пример:

///

/// 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 {

let mut result = Polynomial::from(vec![]);

for (i, a) in self.coefficients.iter().enumerate() {

let mut poly: Vec<f64> = vec![];

for _ in 0..i {

poly.push(0.0);

}

for &b in rhs.coefficients.iter() {

poly.push(a * b);

}

poly.reverse();

result = result + Polynomial::from(poly);

}

result

}

}

/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това

/// докара най-високите степени до 0.

///

impl Add for Polynomial {

type Output = Polynomial;

fn add(self, rhs: Polynomial) -> Self::Output {

let maximum_powa = std::cmp::max(self.coefficients.len(), rhs.coefficients.len());

let mut coefficients = Vec::<f64>::with_capacity(maximum_powa);

for i in 0..maximum_powa {

let a = self.coefficients.get(i).unwrap_or(&0.0);

let b = rhs.coefficients.get(i).unwrap_or(&0.0);

coefficients.push(a + b);

}

coefficients.reverse();

Polynomial::from(coefficients)

}

}

Лог от изпълнението

Compiling solution v0.1.0 (file:///tmp/d20171121-6053-mcd3k9/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 5.29 secs
     Running target/debug/deps/solution-200db9172ea1f728

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

     Running target/debug/deps/solution_test-e3c9eb714e09105e

running 15 tests
test solution_test::test_add_poly ... ok
test solution_test::test_add_poly_zero_one ... ok
test solution_test::test_arithmetic_properties ... ok
test solution_test::test_create_poly ... ok
test solution_test::test_div_poly_f64 ... ok
test solution_test::test_div_poly_f64_zero ... ok
test solution_test::test_fp_comparison ... ok
test solution_test::test_has_point ... ok
test solution_test::test_lagrange_poly_1 ... ok
test solution_test::test_lagrange_poly_2 ... ok
test solution_test::test_lagrange_poly_err_eq_x ... ok
test solution_test::test_mul_poly ... ok
test solution_test::test_mul_poly_f64 ... ok
test solution_test::test_mul_poly_f64_zero ... ok
test solution_test::test_mul_poly_zero_one ... ok

test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

   Doc-tests solution

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

История (1 версия и 3 коментара)