Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Bigint от Велин Клисуров

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

Към профила на Велин Клисуров

Резултати

  • 15 точки от тестове
  • 0 бонус точки
  • 15 точки общо
  • 15 успешни тест(а)
  • 0 неуспешни тест(а)

Код

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
let mut num = Vec::new();
num.push(0);
let res = Bigint{ sign: 1, digits: num };
return res;
}
pub fn is_positive(&self) -> bool {
return if self.sign == -1 || (self.digits.len() == 1 && self.digits[0] == 0) {
false
} else {
true
}
}
pub fn is_negative(&self) -> bool {
return if self.sign == 1 || (self.digits.len() == 1 && self.digits[0] == 0) {
false
} else {
true
}
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut chars: Vec<char> = Vec::new();
let mut res = Bigint{ sign: 1, digits: Vec::new()};
if s.is_empty() || s == "+" || s == "-" {
return Ok(Bigint::new());
}
let mut is_relevant = false;
for c in s.chars() {
if c == '+' || c == '-' {
chars.push(c);
}
if c =='0' && is_relevant {
chars.push(c);
}
else if c != '0' && c != '+' && c != '-' {
chars.push(c);
is_relevant = true;
}
}
if chars.is_empty(){
return Ok(Bigint::new())
}
if chars[0] != '+' && chars[0] != '-' && !chars[0].is_digit(10) {
return Err(ParseError);
}
let mut cnt: u64 = 0;
for tmp in chars{
if cnt!=0 && !tmp.is_digit(10){
return Err(ParseError);
}
else if tmp == '+' {
res.sign = 1
}
else if tmp == '-' {
res.sign = -1
}
else {
res.digits.push(tmp.to_digit(10).unwrap() as u8);
}
cnt = cnt+1;
}
return if res.digits.is_empty() {
Ok(Bigint::new())
} else {
Ok(res)
}
}
}
use std::cmp::Ordering;
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
if self.sign < other.sign {
return Ordering::Less;
} else if self.sign > other.sign {
return Ordering::Greater;
} else if self.sign < 0 {
if self.digits.len() < other.digits.len(){
return Ordering::Greater;
}
else if self.digits.len() > other.digits.len(){
return Ordering::Less;
}
else {
for i in 0..self.digits.len(){
if self.digits[i] > other.digits[i] {
return Ordering::Less;
} else if self.digits[i] < other.digits[i] {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
} else {
if self.digits.len() < other.digits.len(){
return Ordering::Less;
}
else if self.digits.len() > other.digits.len(){
return Ordering::Greater;
}
else {
for i in 0..self.digits.len(){
if self.digits[i] > other.digits[i] {
return Ordering::Greater;
} else if self.digits[i] < other.digits[i] {
return Ordering::Less;
}
}
return Ordering::Equal;
}
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut res = Bigint{ sign: 1, digits: Vec::new() };
let mut self_reversed = self.digits.clone();
self_reversed.reverse();
let mut other_reversed= other.digits.clone();
other_reversed.reverse();
let mut res_reversed = Vec::new();
while self_reversed.len() < other_reversed.len() {
self_reversed.push(0);
}
while self_reversed.len() > other_reversed.len() {
other_reversed.push(0);
}
self_reversed.push(0);
other_reversed.push(0);
let mut one_over: u8 = 0;
if self.sign == other.sign{
res.sign = self.sign;
for i in 0..self_reversed.len()
{
if self_reversed[i] + other_reversed[i] + one_over >= 10 {
res_reversed.push(self_reversed[i] + other_reversed[i] + one_over - 10);
one_over = 1;
}
else {
res_reversed.push(self_reversed[i] + other_reversed[i] + one_over);
one_over = 0;
}
}
} else {
let tmp = Bigint{sign: 1, digits: self.digits}.cmp(&Bigint{sign: 1, digits: other.digits});
if tmp == Ordering::Greater {
res.sign = self.sign;
for i in 0..self_reversed.len()
{
if (self_reversed[i] as i8 - other_reversed[i] as i8 - one_over as i8) < 0 {
res_reversed.push((self_reversed[i] as i8 - other_reversed[i] as i8 - one_over as i8 + 10) as u8);
one_over = 1;
}
else {
res_reversed.push((self_reversed[i] as i8 - other_reversed[i] as i8 - one_over as i8 ) as u8 );
one_over = 0;
}
}
} else if tmp == Ordering::Less {
res.sign = other.sign;
for i in 0..self_reversed.len()
{
if (other_reversed[i] as i8 - self_reversed[i] as i8 - one_over as i8) < 0 {
res_reversed.push((other_reversed[i] as i8 - self_reversed[i] as i8 - one_over as i8 + 10) as u8);
one_over = 1;
}
else {
res_reversed.push((other_reversed[i] as i8 - self_reversed[i] as i8 - one_over as i8 ) as u8 );
one_over = 0;
}
}
} else {
res_reversed.push(0);
}
}
while !res_reversed.is_empty() && res_reversed[res_reversed.len()-1] == 0 {
res_reversed.pop();
}
if res_reversed.is_empty() {
res.sign = 1;
res_reversed.push(0);
}
res_reversed.reverse();
res.digits = res_reversed;
return res;
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let res = self.add(Bigint { sign: other.sign * (-1), digits: other.digits});
return res;
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-92sb3f/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.68s
     Running target/debug/deps/solution_test-589a43f0f4b10ca3

running 15 tests
test solution_test::test_bigint_construction ... ok
test solution_test::test_bigint_nonzero_sign ... ok
test solution_test::test_bigint_zero_sign ... ok
test solution_test::test_comparison ... ok
test solution_test::test_invalid_string ... ok
test solution_test::test_neutralization ... ok
test solution_test::test_parsing_with_and_without_sign ... ok
test solution_test::test_parsing_with_leading_zeroes ... ok
test solution_test::test_sub_1_basic ... ok
test solution_test::test_sub_2_diferent_lengths ... ok
test solution_test::test_sub_3_carry ... ok
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... ok
test solution_test::test_sum_3_overflow ... ok
test solution_test::test_sum_4_negative ... ok

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

История (2 версии и 0 коментара)

Велин качи първо решение на 27.11.2020 12:58 (преди почти 5 години)

Велин качи решение на 27.11.2020 13:00 (преди почти 5 години)

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
- /// Конструира нов Bigint със стойност "0" и положителен знак.
- /// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
- ///
pub fn new() -> Self {
let mut num = Vec::new();
num.push(0);
let res = Bigint{ sign: 1, digits: num };
return res;
}
- /// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
return if self.sign == -1 || (self.digits.len() == 1 && self.digits[0] == 0) {
false
} else {
true
}
}
- /// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
return if self.sign == 1 || (self.digits.len() == 1 && self.digits[0] == 0) {
false
} else {
true
}
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
- /// Очакваме низа да е във формат десетично цяло число с опционален знак, тоест всички тези
- /// неща би трябвало да върнат `Ok` резултат с конструиран Bigint:
- ///
- /// Bigint::from_str("123") // => положителен знак по подразбиране
- /// Bigint::from_str("+123")
- /// Bigint::from_str("-123")
- ///
- /// Това включва нулата, като имате предвид че, както казахме, +0 и -0 трябва да са
- /// еквивалентни.
- ///
- /// Ако подадения низ е празен, това връща същото като да сме подали "0". Ако подадения низ е
- /// само "+" или "-", ваше решение е дали да е нула или да е грешка, няма да го тестваме.
- ///
- /// Ако подадения низ започва с нули, това няма значение -- игнорират се. Тоест, конструиране с
- /// "00123" ще е същото като конструиране с "123".
- ///
- /// Ако сме подали низ, който включва каквито и да е други символи освен цифрите 0-9 (и
- /// опционален начален знак), очакваме да върнете `ParseError`.
- ///
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut chars: Vec<char> = Vec::new();
let mut res = Bigint{ sign: 1, digits: Vec::new()};
if s.is_empty() || s == "+" || s == "-" {
return Ok(Bigint::new());
}
let mut is_relevant = false;
for c in s.chars() {
if c == '+' || c == '-' {
chars.push(c);
}
if c =='0' && is_relevant {
chars.push(c);
}
else if c != '0' && c != '+' && c != '-' {
chars.push(c);
is_relevant = true;
}
}
if chars.is_empty(){
return Ok(Bigint::new())
}
if chars[0] != '+' && chars[0] != '-' && !chars[0].is_digit(10) {
return Err(ParseError);
}
let mut cnt: u64 = 0;
for tmp in chars{
if cnt!=0 && !tmp.is_digit(10){
return Err(ParseError);
}
else if tmp == '+' {
res.sign = 1
}
else if tmp == '-' {
res.sign = -1
}
else {
res.digits.push(tmp.to_digit(10).unwrap() as u8);
}
cnt = cnt+1;
}
return if res.digits.is_empty() {
Ok(Bigint::new())
} else {
Ok(res)
}
}
}
use std::cmp::Ordering;
impl PartialOrd for Bigint {
- /// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
- /// пълното.
- ///
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
- /// Ако едното от числата е положително, а другото -- отрицателно, положителното е по-голямо.
- ///
- /// Ако едното от числата има по-голям брой цифри, то ще бъде по-голямото. (Стига да не са нули
- /// -- вероятно е добра идея да се погрижите да няма започващи нули при конструкция.)
- ///
- /// Ако двете числа имат еднакъв брой цифри, лексикографско сравнение на числата ще ви даде
- /// правилен резултат -- от по-значимите цифри към по-малко значимите. Внимавайте в какъв ред
- /// си държите цифритe и дали не трябва да ги обърнете.
- ///
- /// Ако двете числа са отрицателни, сравнението по абсолютна стойност ще е обърнато (-1 е
- /// по-голямо от -2) -- погледнете документацията на `Ordering` за това как лесно можете да
- /// обърнете резултата.
- ///
fn cmp(&self, other: &Bigint) -> Ordering {
if self.sign < other.sign {
return Ordering::Less;
} else if self.sign > other.sign {
return Ordering::Greater;
} else if self.sign < 0 {
if self.digits.len() < other.digits.len(){
return Ordering::Greater;
}
else if self.digits.len() > other.digits.len(){
return Ordering::Less;
}
else {
for i in 0..self.digits.len(){
if self.digits[i] > other.digits[i] {
return Ordering::Less;
} else if self.digits[i] < other.digits[i] {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
} else {
if self.digits.len() < other.digits.len(){
return Ordering::Less;
}
else if self.digits.len() > other.digits.len(){
return Ordering::Greater;
}
else {
for i in 0..self.digits.len(){
if self.digits[i] > other.digits[i] {
return Ordering::Greater;
} else if self.digits[i] < other.digits[i] {
return Ordering::Less;
}
}
return Ordering::Equal;
}
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
- /// За да съберете две числа, първия въпрос е: какви са им знаците?
- ///
- /// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
- /// знак.
- /// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
- /// отрицателен знак на крайния резултат.
- /// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
- /// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
- /// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
- /// положителна).
- ///
- /// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
- /// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
- /// запълните с нули, да внимавате с индексите, или нещо по средата.
- ///
fn add(self, other: Self) -> Self {
let mut res = Bigint{ sign: 1, digits: Vec::new() };
let mut self_reversed = self.digits.clone();
self_reversed.reverse();
let mut other_reversed= other.digits.clone();
other_reversed.reverse();
let mut res_reversed = Vec::new();
while self_reversed.len() < other_reversed.len() {
self_reversed.push(0);
}
while self_reversed.len() > other_reversed.len() {
other_reversed.push(0);
}
self_reversed.push(0);
other_reversed.push(0);
let mut one_over: u8 = 0;
if self.sign == other.sign{
res.sign = self.sign;
for i in 0..self_reversed.len()
{
if self_reversed[i] + other_reversed[i] + one_over >= 10 {
res_reversed.push(self_reversed[i] + other_reversed[i] + one_over - 10);
one_over = 1;
}
else {
res_reversed.push(self_reversed[i] + other_reversed[i] + one_over);
one_over = 0;
}
}
} else {
let tmp = Bigint{sign: 1, digits: self.digits}.cmp(&Bigint{sign: 1, digits: other.digits});
if tmp == Ordering::Greater {
res.sign = self.sign;
for i in 0..self_reversed.len()
{
if (self_reversed[i] as i8 - other_reversed[i] as i8 - one_over as i8) < 0 {
res_reversed.push((self_reversed[i] as i8 - other_reversed[i] as i8 - one_over as i8 + 10) as u8);
one_over = 1;
}
else {
res_reversed.push((self_reversed[i] as i8 - other_reversed[i] as i8 - one_over as i8 ) as u8 );
one_over = 0;
}
}
} else if tmp == Ordering::Less {
res.sign = other.sign;
for i in 0..self_reversed.len()
{
if (other_reversed[i] as i8 - self_reversed[i] as i8 - one_over as i8) < 0 {
res_reversed.push((other_reversed[i] as i8 - self_reversed[i] as i8 - one_over as i8 + 10) as u8);
one_over = 1;
}
else {
res_reversed.push((other_reversed[i] as i8 - self_reversed[i] as i8 - one_over as i8 ) as u8 );
one_over = 0;
}
}
} else {
res_reversed.push(0);
}
}
while !res_reversed.is_empty() && res_reversed[res_reversed.len()-1] == 0 {
res_reversed.pop();
}
if res_reversed.is_empty() {
res.sign = 1;
res_reversed.push(0);
}
res_reversed.reverse();
res.digits = res_reversed;
return res;
}
}
impl Sub for Bigint {
type Output = Bigint;
- /// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
- /// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
- /// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
- /// събиране и по изваждане между `add` и `sub`.
- ///
- /// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
- /// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
- /// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
- ///
- /// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
- ///
fn sub(self, other: Self) -> Self {
let res = self.add(Bigint { sign: other.sign * (-1), digits: other.digits});
return res;
}
}