Number

Number

「數」或「數量」或「數值」或「數字」。例如1 2 3 4 5。

Large Number(Big Number)

「大數」。很大的數量。例如12345431848949513953123。

Number運算

     operation (noun)        operation (verb)      result (noun)
---  ----------------------  --------------------  ------------------
+    addition        加法    add           加      sum         和
−    subtraction     減法    subtract      減      difference  差
×    multiplication  乘法    multiply      乘      product     積
÷    division        除法    divide        除      quotient    商
mod  modulo          模      ---           模      remainder   餘
^    exponentiation  乘方    exponentiate  乘方    power       冪
√‾   ---             開方    ---           開方    root        根
log  ---             取對數  ---           取對數  logarithm   對數
∑    summation       連加    ---           連加    sum         總和
∏    ---             連乘    ---           連乘    product     連乘積

Number資料結構

要存放這麼大的數量,有個好方法——使用陣列。

陣列有很多格子,一個格子存一個數字。1000格的int陣列,可以存1000個位數!

我們習慣將低位數放在索引值較小的位置,高位數放在索引值較大的位置。比如存放680468975231245:

 ₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉ ...
 _____________________________________
|5|4|2|1|3|2|5|7|9|8|6|4|0|8|6| | | | ...
 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

每個人對陣列的思考模式不一樣,像這裡就是由左至右的,另外也有人覺得陣列是由右至左、由上至下、彎彎曲曲的、……。要怎麼思考都是可以的,一以貫之就好囉。

陣列右端的空格,通常設成0,運算的時候比較方便。

scan

從字串中讀取大數。

簡單起見,此處假設大數絕對不是負數。

print

在螢幕上印出大數。

如果這個大數有可能是零,就得加個幾行程式碼。

comparsion <

兩個大數比較大小。

addition +

大數加法的粗略程式碼。

大數的運算有個有趣的地方,就是運算時不用立即進位,可以後來再一口氣進位。

UVa 10035

subtraction −

大數減法的粗略程式碼。

multiplication ×

大數乘法的粗略程式碼。我一定要強調它是粗略的。

大數乘以int變數,比較容易一些。

UVa 338 10106

division ÷

大數除法可以直接使用長除法。

商數範圍是0到9,所以必須一一嘗試。可以利用高位數相除來估計商數的範圍,便不必一一嘗試。

大數除以int變數,比較容易一些。

square root √‾

大數平方根可以直接使用直式開方法。

http://mypaper.pchome.com.tw/zerojudge/post/1324177221

UVa 10023 10606

改進資料結構

 ₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉ ...
 _____________________________________
|5|4|2|1|3|2|5|7|9|8|6|4|0|8|6| | | | ...
 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

一格只存一個數字,有點浪費。

int的數值範圍約為10位數,一格能夠存入9位數。1000格的int陣列,從原來的1000位數,搖身一變成為9000位數。如果想要存入1000位數,僅僅需要112格。這個新想法,大幅降低空間用量,也大幅降低運算次數。

 ₀         ₁         ₂         ₃
 _________________________________
|975231245|   680468|         |   ...
 ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾

不過,如果一格存了很多位數,會對運算造成什麼影響呢?

一、進位:如果一格存了9個位數,那麼每到10⁹才能進位。

二、進位溢位:進位讓鄰格的數字增加。如果鄰格原本就有一個很大的數字,就可能產生溢位。

三、乘法溢位:乘法是兩格相乘,添加到另一格。如果兩格都存了9個位數,相乘之後至少17個位數,遠遠超過int的上限。

除此之外還要考慮除法、平方根。雖然問題重重,但是並不代表一格還是只能存一個數字。稍微存個幾位數,應該不成問題吧?這些問題就留給大家思考。

UVa 288 10220 10814 10925 748

Number Base

記載數量

想要記載一個數量,最直觀的方式是:一個符號、重複數次。

♥
♦♦
☁☁☁
★★★★★★★★★★★★★★★★★★

第一個技術:分堆

一個個數,太花時間。為了節省時間,可以嘗試分堆。最常見的分堆方式,是十個一堆。如果有很多堆,那麼十堆再合成一大堆;如果有很多大堆,那麼十大堆再合成一大大堆;以此類推。

hard way:
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

easy way:
★★★★★★★★★★  ★★★★★★★★★★  ★ ★
★★★★★★★★★★
★★★★★★★★★★  ★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★  ★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★
★★★★★★★★★★

以此類推的過程,我們習慣採用固定數量,這個數量稱作「底數Base」或「基數Radix」。例如上例的底數就是十。

然而也有例外。例如時間:六十秒一分、六十分一時、二十四時一日,底數不是固定數量。

第二個技術:命名

一個個數,太花時間。為了節省時間,可以替每種數量取不一樣的名字;換句話說,用不一樣的符號代替每種數量。

長長一串數量,變成短短一個符號,人生充滿歡樂!

這些符號稱作「數字Digit」。

同時使用第一個技術和第二個技術:位數

越多符號,越難背誦。你能想像背誦一百種符號代替一百種數量嗎?符號還是少點好。

解法是同時使用第一個技術和第二個技術,令符號數量等於底數。例如底數是十,可以使用0123456789等十個符號。當數量大於等於十,十個形成一堆,記載在左邊一點的位置,變成10。當數量累積十堆,十堆形成一大堆,記載在更左邊一點的位置,變成100。這是地球上最流行的記載方式。

除了替每一種數量取名字,有些語言還會替每一種數量級取名字,讓數字之間穿插數量級符號。這是題外話。

132
英文:one hundred thirty-two      (hundred是數量級的符號)
中文:一百三十二                  (百、十是數量級的符號)

選擇底數

我們可以選擇自己喜歡的底數。底數不能是零、不能是一。底數是二,稱作「二進位」,使用01兩個符號。底數是三,稱作「三進位」,使用012三個符號。底數是十六,稱作「十六進位」,使用0123456789ABCDEF十六個符號。底數超過三十六,那麼必須額外引入一些符號,才夠用。

底數寫於數字的右下角,用括號包住。

101₍₂₎   二進位,數字是101
73F₍₁₆₎  十六進位,數字是73F

同樣的數量,使用不同的底數,往往得到不同的數字。

★★★★★★★★★★★★★★★★★★  10010₍₂₎
★★★★★★★★★★★★★★★★★★  18₍₁₀₎
★★★★★★★★★★★★★★★★★★  12₍₁₆₎

同樣的數字,使用不同的底數,往往得到不同的數量。

11₍₂₎   ★★★
11₍₁₀₎  ★★★★★★★★★★★
11₍₁₆₎  ★★★★★★★★★★★★★★★★★

選定底數,數字變數量(scan)

C語言當中的atoi()字串轉整數函式,其實就是「選定底數10,把數字變成數量」。

選定底數,數量變數字(print)

更換底數(進制轉換)

10010₍₂₎ = ?₍₁₆₎

令數量維持相等,給定原數字、原底數、新底數,求新數字。

演算法和程式碼交給讀者思考!

UVa 343 344 355 377 389 446 448 575 594 619 636 10019 10469 10473 11005 11121

Polynomial

Polynomial

「多項式」。變數的各種次方、乘上倍率、通通相加。

2x³ + 0x² - 4x¹ + 8x⁰

求值(Horner's Rule)

已知x、已知係數c₀ c₁ c₂ ...,求c₀x⁰ + c₁x¹ + c₂x² + ...。

一乘一加,得到答案。不需要次方運算。時間複雜度O(N)。

2x³ + 0x² - 4x¹ + 8 = (((((2 ⋅ x) + 0) ⋅ x) - 4) ⋅ x) + 8

求係數【尚無正式名稱】

已知x、已知c₀x⁰ + c₁x¹ + c₂x² + ...,求係數c₀ c₁ c₂ ...。

答案無限多種。其中一種答案是求值演算法顛倒做。

一模一除,得到答案。不需要次方運算。時間複雜度O(N)。

一個數字可以改寫成一個多項式

10010₍₂₎ ---> 1x⁴ + 0x³ + 0x² + 1x¹ + 0x⁰ (x = 2)
18₍₁₀₎   ---> 1x¹ + 8x⁰ (x = 10)
73F₍₁₆₎ ---> 7x² + 3x¹ + 15x⁰ (x = 16)

在數學家眼中,底數可以藉由多項式一以貫之。

「選定底數,數字變數量」就是「求值」。

「選定底數,數量變數字」就是「求係數」。

大數就是多項式,x代入10。大數運算就是多項式運算。

十進位、二進位、八進位、十六進位,進位制就是多項式,x代入各種底數。

luogu P5248

延伸閱讀:益智問題

以身試毒:

https://www.zhihu.com/question/60227816

兩步猜出多項式的係數:

http://www.matrix67.com/blog/archives/4064

Numeral System

春雨驚春清穀天,夏滿芒夏暑相連,        

秋處露秋寒霜降,冬雪雪冬小大寒。《二十四節氣歌》

Arabic Numerals

https://en.wikipedia.org/wiki/Arabic_numerals

Roman Numerals

http://en.wikipedia.org/wiki/Roman_numerals

UVa 759 11616 12397 11787

Clock

https://en.wikipedia.org/wiki/Clock

UVa 579 11677

Calendar

http://en.wikipedia.org/wiki/Calendar

1752年9月曾經調整過日曆。

UVa 300 602 10070 11356

Number Type

數量種類

   	operation (noun)                 	example
---	---------------------------------	-----------
ℕ  	natural numbers    自然數        	0 1 2 3 4
ℤ  	integers           整數          	-2 -1 0 1 2
ℚ  	rational numbers   有理數(分數)	1/3 0.123
𝔸  	algebraic numbers  代數數        	√22
---	---------------------------------	-----------
ℝ  	real numbers       實數          	π e
ℂ  	complex numbers    複數          	√-1 1+2𝑖

數量與運算

1 + 2 = ☐。自然數加法運算。數一數手指就行了。

☐ + 2 = 3。自然數加法反運算。等量公理(移項)就行了。

那麼☐ + 2 = 1呢?答案不是自然數。旅途就此開始。

數量種類(基於運算)

正運算補滿數域,反運算拓展數域。

數量的基礎是自然數。自然數裝備加法得到所有自然數。整數裝備乘法得到所有整數。分數裝備自然數乘方得到所有分數。

數量的基礎是自然數。自然數裝備減法得到整數。整數裝備除法得到分數。分數裝備自然數開方得到代數數。

數量種類(基於幾何)

實數是分數之間相鄰相連的數。用來簡化分數的計算。

複數是代數數之間相鄰相連的數。用來簡化代數數的計算。

數量變幾何之後,數量獲得長度、角度,方便理解數量的計算。

實數數線Real Line:直角座標系。

實數   ⇨ 點
實數長度 ⇨ 點到原點的距離
實數加法 ⇨ 點的座標相加(位移)
實數乘法 ⇨ 點的長度相乘(縮放)、點的方位負負得正(鏡射)

複數平面Complex Plane:直角座標系、極座標系兩者合體。

複數   ⇨ 點
複數長度 ⇨ 從原點出發的直線距離
複數角度 ⇨ 從實軸出發的逆時針夾角
複數加法 ⇨ 點的座標相加(位移)
複數乘法 ⇨ 點的長度相乘(縮放)、點的角度相加(旋轉)

複數總是可以化作a+b𝑖的形式。實數a b、虛數𝑖 = √-1

複數乘法變點的長度相乘、角度相加,使之循環繞圈,這是古人一致推薦的方式。由於很好用,從此沒有採用其他方式。

UVa 10378

程式語法

自然數:unsigned char、unsigned short、unsigned int、unsigned long long。記憶體使用量、數值範圍有所差異。

整數:char、short、int、long long。

分數、代數數:C/C++程式語言沒有對應的語法。

實數:float、double、long double。

複數:complex,需要引入標頭檔

函式庫

實數和複數也有專門的函式庫。GMP:任意精度運算函式庫。MPFR:實數高精度運算函式庫。MPC:複數高精度運算函式庫。