Решение на Polynomial от Радослав Георгиев
Към профила на Радослав Георгиев
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-yydpmf/solution)
Finished dev [unoptimized + debuginfo] target(s) in 5.21 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
История (7 версии и 1 коментар)
Радослав качи решение на 20.11.2017 13:09 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
use std::iter::FromIterator;
const EPSILON: f64 = 1e-10;
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs_rev: Vec<f64>,
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let value = self.coefs_rev
.iter()
.enumerate()
.fold(0.0, |sum, (index, coef)| sum + coef * x.powi(index as i32));
let diff = value - y;
diff.abs() < EPSILON
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut l = Polynomial::default();
for (j, &(x_j, y_j)) in points.iter().enumerate() {
- let mut l_j = Polynomial {
- coefs_rev: vec![1.0],
- };
+ let mut l_j = Polynomial::from(vec![1.0]);
for (m, &(x_m, _)) in points.iter().enumerate() {
if m == j {
continue;
}
if x_m == x_j {
return None;
}
let denom = x_j - x_m;
- let l_j_m = Polynomial {
- coefs_rev: vec![-x_m / denom, 1.0 / denom],
- };
+ let l_j_m = Polynomial::from(vec![1.0 / denom, -x_m / denom]);
l_j = l_j * l_j_m;
}
l = l + l_j * y_j;
}
Some(l)
}
+
+ fn canonicalize(&mut self) {
+ let coefs = &mut self.coefs_rev;
+ while coefs.last() == Some(&0.0) {
+ coefs.pop();
+ }
+ if coefs.is_empty() {
+ coefs.push(0.0);
+ }
+ }
}
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 {
- if coefs.len() == 0 {
+ coefs = Vec::from_iter(coefs.into_iter().skip_while(|&coef| coef == 0.0));
+ coefs.reverse();
+ if coefs.is_empty() {
coefs.push(0.0);
- } else {
- coefs = Vec::from_iter(coefs.into_iter().rev().skip_while(|&coef| coef == 0.0));
}
Self { coefs_rev: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self {
coefs_rev: vec![0.0],
}
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 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 {
- for (a, b) in self.coefs_rev.iter().zip(rhs.coefs_rev.iter()) {
+ let lhs_coefs = &self.coefs_rev;
+ let rhs_coefs = &rhs.coefs_rev;
+ if lhs_coefs.len() != rhs_coefs.len() {
+ return false;
+ }
+ for (a, b) in lhs_coefs.iter().zip(rhs_coefs.iter()) {
let diff = a - b;
if diff.abs() >= EPSILON {
return false;
}
}
true
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
- Self::Output {
- coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
+ if rhs == 0.0 {
+ Polynomial::default()
+ } else {
+ Self::Output {
+ coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
+ }
}
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef / 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 lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; lhs_coefs.len() + rhs_coefs.len() - 1];
for (ia, a) in lhs_coefs.iter().enumerate() {
for (ib, b) in rhs_coefs.iter().enumerate() {
result_coefs[ia + ib] += a * b;
}
}
Self::Output {
coefs_rev: result_coefs,
}
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
- Self::Output {
- coefs_rev: Vec::from_iter(
- self.coefs_rev
- .into_iter()
- .zip(rhs.coefs_rev.into_iter())
- .map(|(a, b)| a + b),
- ),
+ let lhs_coefs = self.coefs_rev;
+ let rhs_coefs = rhs.coefs_rev;
+ let mut result_coefs = vec![0.0; std::cmp::max(lhs_coefs.len(), rhs_coefs.len())];
+ let mut lhs_coefs_iter = lhs_coefs.iter();
+ let mut rhs_coefs_iter = rhs_coefs.iter();
+ let mut i = 0;
+ loop {
+ match (lhs_coefs_iter.next(), rhs_coefs_iter.next()) {
+ (None, None) => break,
+ (Some(&a), None) => result_coefs[i] = a,
+ (None, Some(&b)) => result_coefs[i] = b,
+ (Some(&a), Some(&b)) => result_coefs[i] = a + b,
+ }
+ i += 1;
}
+ let mut polynomial = Self::Output {
+ coefs_rev: result_coefs,
+ };
+ polynomial.canonicalize();
+ polynomial
}
}
Радослав качи решение на 20.11.2017 17:01 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
use std::iter::FromIterator;
const EPSILON: f64 = 1e-10;
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs_rev: Vec<f64>,
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let value = self.coefs_rev
.iter()
.enumerate()
.fold(0.0, |sum, (index, coef)| sum + coef * x.powi(index as i32));
let diff = value - y;
diff.abs() < EPSILON
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut l = Polynomial::default();
for (j, &(x_j, y_j)) in points.iter().enumerate() {
let mut l_j = Polynomial::from(vec![1.0]);
for (m, &(x_m, _)) in points.iter().enumerate() {
if m == j {
continue;
}
if x_m == x_j {
return None;
}
let denom = x_j - x_m;
let l_j_m = Polynomial::from(vec![1.0 / denom, -x_m / denom]);
l_j = l_j * l_j_m;
}
l = l + l_j * y_j;
}
Some(l)
}
fn canonicalize(&mut self) {
let coefs = &mut self.coefs_rev;
while coefs.last() == Some(&0.0) {
coefs.pop();
}
if coefs.is_empty() {
coefs.push(0.0);
}
}
}
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 {
coefs = Vec::from_iter(coefs.into_iter().skip_while(|&coef| coef == 0.0));
coefs.reverse();
if coefs.is_empty() {
coefs.push(0.0);
}
Self { coefs_rev: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self {
coefs_rev: vec![0.0],
}
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 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 {
let lhs_coefs = &self.coefs_rev;
let rhs_coefs = &rhs.coefs_rev;
if lhs_coefs.len() != rhs_coefs.len() {
return false;
}
for (a, b) in lhs_coefs.iter().zip(rhs_coefs.iter()) {
let diff = a - b;
if diff.abs() >= EPSILON {
return false;
}
}
true
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
if rhs == 0.0 {
Polynomial::default()
} else {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
}
}
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef / 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 lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; lhs_coefs.len() + rhs_coefs.len() - 1];
for (ia, a) in lhs_coefs.iter().enumerate() {
for (ib, b) in rhs_coefs.iter().enumerate() {
result_coefs[ia + ib] += a * b;
}
}
- Self::Output {
+ let mut polynomial = Self::Output {
coefs_rev: result_coefs,
- }
+ };
+ polynomial.canonicalize();
+ polynomial
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; std::cmp::max(lhs_coefs.len(), rhs_coefs.len())];
let mut lhs_coefs_iter = lhs_coefs.iter();
let mut rhs_coefs_iter = rhs_coefs.iter();
let mut i = 0;
loop {
match (lhs_coefs_iter.next(), rhs_coefs_iter.next()) {
(None, None) => break,
(Some(&a), None) => result_coefs[i] = a,
(None, Some(&b)) => result_coefs[i] = b,
(Some(&a), Some(&b)) => result_coefs[i] = a + b,
}
i += 1;
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
Радослав качи решение на 20.11.2017 17:35 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
+use std::cmp::max;
use std::iter::FromIterator;
const EPSILON: f64 = 1e-10;
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs_rev: Vec<f64>,
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let value = self.coefs_rev
.iter()
.enumerate()
.fold(0.0, |sum, (index, coef)| sum + coef * x.powi(index as i32));
let diff = value - y;
diff.abs() < EPSILON
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut l = Polynomial::default();
for (j, &(x_j, y_j)) in points.iter().enumerate() {
let mut l_j = Polynomial::from(vec![1.0]);
for (m, &(x_m, _)) in points.iter().enumerate() {
if m == j {
continue;
}
if x_m == x_j {
return None;
}
let denom = x_j - x_m;
let l_j_m = Polynomial::from(vec![1.0 / denom, -x_m / denom]);
l_j = l_j * l_j_m;
}
l = l + l_j * y_j;
}
Some(l)
}
fn canonicalize(&mut self) {
let coefs = &mut self.coefs_rev;
while coefs.last() == Some(&0.0) {
coefs.pop();
}
if coefs.is_empty() {
coefs.push(0.0);
}
}
}
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 {
coefs = Vec::from_iter(coefs.into_iter().skip_while(|&coef| coef == 0.0));
coefs.reverse();
if coefs.is_empty() {
coefs.push(0.0);
}
Self { coefs_rev: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self {
coefs_rev: vec![0.0],
}
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 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 {
let lhs_coefs = &self.coefs_rev;
let rhs_coefs = &rhs.coefs_rev;
if lhs_coefs.len() != rhs_coefs.len() {
return false;
}
for (a, b) in lhs_coefs.iter().zip(rhs_coefs.iter()) {
let diff = a - b;
if diff.abs() >= EPSILON {
return false;
}
}
true
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
if rhs == 0.0 {
Polynomial::default()
} else {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
}
}
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef / 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 lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; lhs_coefs.len() + rhs_coefs.len() - 1];
for (ia, a) in lhs_coefs.iter().enumerate() {
for (ib, b) in rhs_coefs.iter().enumerate() {
result_coefs[ia + ib] += a * b;
}
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
- let mut result_coefs = vec![0.0; std::cmp::max(lhs_coefs.len(), rhs_coefs.len())];
+ let mut result_coefs = vec![0.0; max(lhs_coefs.len(), rhs_coefs.len())];
let mut lhs_coefs_iter = lhs_coefs.iter();
let mut rhs_coefs_iter = rhs_coefs.iter();
let mut i = 0;
loop {
match (lhs_coefs_iter.next(), rhs_coefs_iter.next()) {
(None, None) => break,
(Some(&a), None) => result_coefs[i] = a,
(None, Some(&b)) => result_coefs[i] = b,
(Some(&a), Some(&b)) => result_coefs[i] = a + b,
}
i += 1;
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
Радослав качи решение на 21.11.2017 09:12 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
use std::cmp::max;
use std::iter::FromIterator;
const EPSILON: f64 = 1e-10;
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs_rev: Vec<f64>,
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let value = self.coefs_rev
.iter()
.enumerate()
.fold(0.0, |sum, (index, coef)| sum + coef * x.powi(index as i32));
let diff = value - y;
diff.abs() < EPSILON
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
- let mut l = Polynomial::default();
+ let mut l = Self::default();
for (j, &(x_j, y_j)) in points.iter().enumerate() {
- let mut l_j = Polynomial::from(vec![1.0]);
+ let mut l_j = Self::from(vec![1.0]);
for (m, &(x_m, _)) in points.iter().enumerate() {
if m == j {
continue;
}
if x_m == x_j {
return None;
}
let denom = x_j - x_m;
let l_j_m = Polynomial::from(vec![1.0 / denom, -x_m / denom]);
l_j = l_j * l_j_m;
}
l = l + l_j * y_j;
}
Some(l)
}
fn canonicalize(&mut self) {
let coefs = &mut self.coefs_rev;
while coefs.last() == Some(&0.0) {
coefs.pop();
}
if coefs.is_empty() {
coefs.push(0.0);
}
}
}
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 {
coefs = Vec::from_iter(coefs.into_iter().skip_while(|&coef| coef == 0.0));
coefs.reverse();
if coefs.is_empty() {
coefs.push(0.0);
}
Self { coefs_rev: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self {
coefs_rev: vec![0.0],
}
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 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 {
let lhs_coefs = &self.coefs_rev;
let rhs_coefs = &rhs.coefs_rev;
if lhs_coefs.len() != rhs_coefs.len() {
- return false;
+ false
+ } else {
+ lhs_coefs
+ .iter()
+ .zip(rhs_coefs.iter())
+ .all(|(a, b)| (a - b).abs() < EPSILON)
}
- for (a, b) in lhs_coefs.iter().zip(rhs_coefs.iter()) {
- let diff = a - b;
- if diff.abs() >= EPSILON {
- return false;
- }
- }
- true
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
if rhs == 0.0 {
- Polynomial::default()
+ Self::Output::default()
} else {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
}
}
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef / 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 lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; lhs_coefs.len() + rhs_coefs.len() - 1];
- for (ia, a) in lhs_coefs.iter().enumerate() {
+ for (ia, a) in lhs_coefs.into_iter().enumerate() {
for (ib, b) in rhs_coefs.iter().enumerate() {
result_coefs[ia + ib] += a * b;
}
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; max(lhs_coefs.len(), rhs_coefs.len())];
- let mut lhs_coefs_iter = lhs_coefs.iter();
- let mut rhs_coefs_iter = rhs_coefs.iter();
+ let mut lhs_coefs_iter = lhs_coefs.into_iter();
+ let mut rhs_coefs_iter = rhs_coefs.into_iter();
let mut i = 0;
loop {
match (lhs_coefs_iter.next(), rhs_coefs_iter.next()) {
(None, None) => break,
- (Some(&a), None) => result_coefs[i] = a,
- (None, Some(&b)) => result_coefs[i] = b,
- (Some(&a), Some(&b)) => result_coefs[i] = a + b,
+ (Some(a), None) => result_coefs[i] = a,
+ (None, Some(b)) => result_coefs[i] = b,
+ (Some(a), Some(b)) => result_coefs[i] = a + b,
}
i += 1;
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
Радослав качи решение на 21.11.2017 09:14 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
use std::cmp::max;
use std::iter::FromIterator;
const EPSILON: f64 = 1e-10;
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs_rev: Vec<f64>,
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let value = self.coefs_rev
.iter()
.enumerate()
.fold(0.0, |sum, (index, coef)| sum + coef * x.powi(index as i32));
let diff = value - y;
diff.abs() < EPSILON
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut l = Self::default();
for (j, &(x_j, y_j)) in points.iter().enumerate() {
let mut l_j = Self::from(vec![1.0]);
for (m, &(x_m, _)) in points.iter().enumerate() {
if m == j {
continue;
}
if x_m == x_j {
return None;
}
let denom = x_j - x_m;
- let l_j_m = Polynomial::from(vec![1.0 / denom, -x_m / denom]);
+ let l_j_m = Self::from(vec![1.0 / denom, -x_m / denom]);
l_j = l_j * l_j_m;
}
l = l + l_j * y_j;
}
Some(l)
}
fn canonicalize(&mut self) {
let coefs = &mut self.coefs_rev;
while coefs.last() == Some(&0.0) {
coefs.pop();
}
if coefs.is_empty() {
coefs.push(0.0);
}
}
}
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 {
coefs = Vec::from_iter(coefs.into_iter().skip_while(|&coef| coef == 0.0));
coefs.reverse();
if coefs.is_empty() {
coefs.push(0.0);
}
Self { coefs_rev: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self {
coefs_rev: vec![0.0],
}
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 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 {
let lhs_coefs = &self.coefs_rev;
let rhs_coefs = &rhs.coefs_rev;
if lhs_coefs.len() != rhs_coefs.len() {
false
} else {
lhs_coefs
.iter()
.zip(rhs_coefs.iter())
.all(|(a, b)| (a - b).abs() < EPSILON)
}
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
if rhs == 0.0 {
Self::Output::default()
} else {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
}
}
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef / 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 lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; lhs_coefs.len() + rhs_coefs.len() - 1];
for (ia, a) in lhs_coefs.into_iter().enumerate() {
for (ib, b) in rhs_coefs.iter().enumerate() {
result_coefs[ia + ib] += a * b;
}
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; max(lhs_coefs.len(), rhs_coefs.len())];
let mut lhs_coefs_iter = lhs_coefs.into_iter();
let mut rhs_coefs_iter = rhs_coefs.into_iter();
let mut i = 0;
loop {
match (lhs_coefs_iter.next(), rhs_coefs_iter.next()) {
(None, None) => break,
(Some(a), None) => result_coefs[i] = a,
(None, Some(b)) => result_coefs[i] = b,
(Some(a), Some(b)) => result_coefs[i] = a + b,
}
i += 1;
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
Радослав качи решение на 21.11.2017 09:20 (преди почти 8 години)
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
-use std::cmp::max;
use std::iter::FromIterator;
+
+use std::cmp::max;
const EPSILON: f64 = 1e-10;
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefs_rev: Vec<f64>,
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let value = self.coefs_rev
.iter()
.enumerate()
.fold(0.0, |sum, (index, coef)| sum + coef * x.powi(index as i32));
let diff = value - y;
diff.abs() < EPSILON
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut l = Self::default();
for (j, &(x_j, y_j)) in points.iter().enumerate() {
let mut l_j = Self::from(vec![1.0]);
for (m, &(x_m, _)) in points.iter().enumerate() {
if m == j {
continue;
}
if x_m == x_j {
return None;
}
let denom = x_j - x_m;
let l_j_m = Self::from(vec![1.0 / denom, -x_m / denom]);
l_j = l_j * l_j_m;
}
l = l + l_j * y_j;
}
Some(l)
}
fn canonicalize(&mut self) {
let coefs = &mut self.coefs_rev;
while coefs.last() == Some(&0.0) {
coefs.pop();
}
if coefs.is_empty() {
coefs.push(0.0);
}
}
}
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 {
coefs = Vec::from_iter(coefs.into_iter().skip_while(|&coef| coef == 0.0));
coefs.reverse();
if coefs.is_empty() {
coefs.push(0.0);
}
Self { coefs_rev: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self {
coefs_rev: vec![0.0],
}
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 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 {
let lhs_coefs = &self.coefs_rev;
let rhs_coefs = &rhs.coefs_rev;
if lhs_coefs.len() != rhs_coefs.len() {
false
} else {
lhs_coefs
.iter()
.zip(rhs_coefs.iter())
.all(|(a, b)| (a - b).abs() < EPSILON)
}
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
if rhs == 0.0 {
Self::Output::default()
} else {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef * rhs)),
Аз май ти казах да пробваш да викнеш map директно върху вектора, но така като гледам, няма да го бъде -- май няма такава опция за вектори, само за итератори.
Може да направиш това, макар че ще е добре наистина да benchmark-неш, за да видиш дали има осезаема разлика:
fn mul(mut self, rhs: f64) -> Self::Output {
if rhs == 0.0 {
Self::Output::default()
} else {
self.coefs_rev.iter_mut().for_each(|coef| *coef = *coef * rhs);
Self::Output { coefs_rev: self.coefs_rev }
}
}
Това би трябвало да мутира коефициентите in-place, и после ги move-ва в новия полином.
}
}
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
Self::Output {
coefs_rev: Vec::from_iter(self.coefs_rev.into_iter().map(|coef| coef / 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 lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; lhs_coefs.len() + rhs_coefs.len() - 1];
for (ia, a) in lhs_coefs.into_iter().enumerate() {
for (ib, b) in rhs_coefs.iter().enumerate() {
result_coefs[ia + ib] += a * b;
}
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let lhs_coefs = self.coefs_rev;
let rhs_coefs = rhs.coefs_rev;
let mut result_coefs = vec![0.0; max(lhs_coefs.len(), rhs_coefs.len())];
let mut lhs_coefs_iter = lhs_coefs.into_iter();
let mut rhs_coefs_iter = rhs_coefs.into_iter();
let mut i = 0;
loop {
match (lhs_coefs_iter.next(), rhs_coefs_iter.next()) {
(None, None) => break,
(Some(a), None) => result_coefs[i] = a,
(None, Some(b)) => result_coefs[i] = b,
(Some(a), Some(b)) => result_coefs[i] = a + b,
}
i += 1;
}
let mut polynomial = Self::Output {
coefs_rev: result_coefs,
};
polynomial.canonicalize();
polynomial
}
}
Аз май ти казах да пробваш да викнеш
mapдиректно върху вектора, но така като гледам, няма да го бъде -- май няма такава опция за вектори, само за итератори.Може да направиш това, макар че ще е добре наистина да benchmark-неш, за да видиш дали има осезаема разлика:
Това би трябвало да мутира коефициентите in-place, и после ги move-ва в новия полином.