c指针的问题

超长整数

dcy posted @ 2009年5月30日 23:30 in c with tags 算法 , 1934 阅读

在C中处理一些使用到很大的数的算法

http://202.193.64.35/dept7/acm/web/AlgorithmGossip/BigNumber.htm

說明

基於記憶體的有效運用,程式語言中規定了各種不同的資料型態,也因此變數所可以表達的最大整數受到限制,例如 123456789123456789這樣的整數就不可能儲存在long變數中(例如C/C++等),我們稱這為long數,這邊翻為超長整數(避免與資 料型態的長整數翻譯混淆),或俗稱大數運算。

 

解法

一個變數無法表示超長整數,則就使用多個變數,當然這使用陣列最為方便,假設程式語言的最大資料型態可以儲存至65535的數好了,為了計算方便及符合使用十進位制的習慣,讓每一個陣列元素可以儲存四個位數,也就是0到9999的數,例如:
大數運算

很多人問到如何計算像50!這樣的問題,解法就是使用程式中的乘法函式,至於要算到多大,就看需求了。

如果您使用的是Java,那麼在java.lang下有BigInteger與BigDecimal可以直接進行大數運算。

由於使用陣列來儲存數值,關於數值在運算時的加減乘除等各種運算、位數的進位或借位就必須自行定義,加、減、乘都是由低位數開始運算,而除法則是由高位數開始運算,這邊直接提供加減乘除運算的函式供作參考,以下的N為陣列長度。

實作

  • C
void add(int *a, int *b, int *c) { 
    int i, carry = 0; 

    for(i = N - 1; i >= 0; i--) { 
        c[i] = a[i] + b[i] + carry; 
        if(c[i] < 10000) 
            carry = 0; 
        else { // 進位 
            c[i] = c[i] - 10000; 
            carry = 1; 
        } 
    } 
} 

void sub(int *a, int *b, int *c) { 
    int i, borrow = 0; 

    for(i = N - 1; i >= 0; i--) { 
        c[i] = a[i] - b[i] - borrow; 
        if(c[i] >= 0) 
            borrow = 0; 
        else { // 借位 
            c[i] = c[i] + 10000; 
            borrow = 1; 
        } 
    } 
} 

void mul(int *a, int b, int *c) { // b 為乘數 
    int i, tmp, carry = 0; 

    for(i = N - 1; i >=0; i--) { 
        tmp = a[i] * b + carry; 
        c[i] = tmp % 10000;    
        carry = tmp / 10000; 
    } 
} 

void div(int *a, int b, int *c) {  // b 為除數 
    int i, tmp, remain = 0; 

    for(i = 0; i < N; i++) { 
        tmp = a[i] + remain; 
        c[i] = tmp / b; 
        remain = (tmp % b) * 10000; 
    } 
} 

 

  • Java
public class BigNumber {
    public static int[] add(int[] a, int[] b) { 
        int carry = 0;
        int[] c = new int[a.length];

        for(int i = a.length - 1; i >= 0; i--) { 
            c[i] = a[i] + b[i] + carry; 
            if(c[i] < 10000) 
                carry = 0; 
            else { // 進位 
                c[i] = c[i] - 10000; 
                carry = 1; 
            } 
        }
        
        return c;
    } 

    public static int[] sub(int[] a, int[] b) { 
        int borrow = 0; 
        int[] c = new int[a.length];
        
        for(int i = a.length - 1; i >= 0; i--) { 
            c[i] = a[i] - b[i] - borrow; 
            if(c[i] >= 0) 
                borrow = 0; 
            else { // 借位 
                c[i] = c[i] + 10000; 
                borrow = 1; 
            } 
        }
        
        return c;
    } 

    public static int[] mul(int[] a, int b) { // b 為乘數 
        int carry = 0; 
        int[] c = new int[a.length];
        
        for(int i = a.length - 1; i >=0; i--) { 
            int tmp = a[i] * b + carry; 
            c[i] = tmp % 10000;    
            carry = tmp / 10000; 
        } 
        
        return c;
    } 

    public static int[] div(int[] a, int b) {  // b 為除數 
        int remain = 0; 
        int[] c = new int[a.length];

        for(int i = 0; i < a.length; i++) { 
            int tmp = a[i] + remain; 
            c[i] = tmp / b; 
            remain = (tmp % b) * 10000; 
        } 
        
        return c;
    }
    
    public static void main(String[] args) {
        int[] a = {1234, 5678, 9910, 1923, 1124};
        int[] b = {1234, 5678, 9910, 1923, 1124};
        int[] c = BigNumber.add(a, b);
        
        for(int i = 0; i < c.length; i++) {
            System.out.print(c[i]);
        }
        System.out.println();
    }
}
Avatar_small
dcy 说:
2009年5月31日 08:20

有了这个算法,用C也可以处理很大的数了

coolzgx 说:
2009年7月31日 01:22

不错,比以前用的字符串来搞相对比较简单


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter