大
大
数运算与组合数学
数运算与组合数学
－－
－－
ACM
ACM
国际大学生程序设计竞赛
国际大学生程序设计竞赛
主讲：王树林
主讲：王树林
問題
問題
當有一個很大的整數要運算時
當有一個很大的整數要運算時
,
,
如何算
如何算
?
?
例如
例如
:
:
一個一佰位數的數字
一個一佰位數的數字
.
.
int
int
最大只能到
最大只能到
2
2
32
32
約十個位數的十進位數字
約十個位數的十進位數字
.
.
最簡單的方法
最簡單的方法
先看大數加法
先看大數加法
.
.
就是改成手動去算加法
就是改成手動去算加法
,
,
而不是由電腦算
而不是由電腦算
.
.
123456789123
123456789123
+ 234123467890
+ 234123467890
------------------------------------
------------------------------------
寫成電腦程式
寫成電腦程式
方法一
方法一
:
:
使用陣列
使用陣列
(array)
(array)
例如
例如
: int a[100], b[100], sum[100];
: int a[100], b[100], sum[100];
然後
然後
sum[i]=a[i]+b[i]+c
sum[i]=a[i]+b[i]+c
記住
記住
, c
, c
是進位
是進位
(carry),
(carry),
這邊我們要自行
這邊我們要自行
處理
處理
.
.
那輸入呢
那輸入呢
?
?
輸入成字串
輸入成字串
再把字串分解成陣列中各個元素
再把字串分解成陣列中各個元素
.
.
需要一個
需要一個
parse
parse
字串的副程式
字串的副程式
.
.
