大數相乘(暴力法)程式範例

主要是直式乘法的概念,僅僅只是分享這學期作業的程式碼…
 

/*
 * 程式名稱:大數乘法(暴力法)
 * function multiple()有Bug,需做修改
 */
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
using namespace std;

typedef struct NUM_ARRAY
{
    int *number;
    int length;
}NumArray;

string read_from_File(string);
int *convert_to_intArray(string);
NumArray makeUpZero(NumArray,int);
NumArray multiple(NumArray,NumArray);
void print(NumArray);
void write_into_File(int*,const int);

int main(void)
{
    string fn1,fn2;
    cout << "請輸入檔名:";
    cin >> fn1;
    string a = read_from_File(fn1.c_str());
    cout << "請輸入檔名:";
    cin >> fn2;
    string b = read_from_File(fn2.c_str());
    cout << "======================================================" << endl;
    /*string a,b;
    a = "1000";
    b = "90";*/
   
    NumArray n1,n2;   
    n1.number = convert_to_intArray(a);
    n1.length = a.length();
    n2.number = convert_to_intArray(b);
    n2.length = b.length();
     
    print(n1);
    cout << " * ";
    print(n2);
    cout << " = ";
    print( multiple(n1,n2) );
    cout << endl;
    cout << "======================================================" << endl;
    return 0;
}

string read_from_File(string str1)
{
    ifstream input( str1.c_str() );
    if(!input)
    {
        cerr << "ERROR..........!!" << endl;
        exit(1);
    }
    string snum;
    input >> snum;
    input.close();
    return snum;
}

int *convert_to_intArray(string str2)
{
    int *num = new int[str2.length()];
    for(int i=0;i    return num;
}

//補上0(參數帶入 (輸入的數字陣列, 要擴大到幾位)
NumArray makeUpZero(NumArray num,int toLength)
{
    if(toLength > num.length)
    {
        NumArray toNum;
        toNum.number = new int[toLength];
       
        for(int i=num.length-1; i>=0; i--) toNum.number[i+ (toLength-num.length)] = num.number[i];
        for(int i=0; i        toNum.length = toLength;

        return toNum;
    }
    else return num;  //否則直接回傳
}

NumArray multiple(NumArray num1, NumArray num2)
{
    int forwardIndex;
    //補上0
    if(num1.length > num2.length){
        forwardIndex = num1.length - num2.length;
        num2 = makeUpZero(num2,num1.length);
    }
    else if(num1.length < num2.length){
        forwardIndex = num2.length - num1.length;
        num1 = makeUpZero(num1,num2.length);
    }
    else forwardIndex = 0;
   
    //宣告sum回傳陣列
    NumArray sum;
    sum.length = num1.length + num2.length -forwardIndex;
    sum.number = new int[sum.length -forwardIndex];
    for(int k=0; k   
    //直式相乘
    int tmpResult, tmpCarry = 0;    //暫存: 相乘的基, 過程暫存, 進位值
    for(int i=num1.length-1; i>=0; i--)
    {
        for(int j=num2.length-1; j>=0; j--)
        {
            tmpResult = num2.number[i] * num1.number[j];
            sum.number[i+j+1 -forwardIndex] += (tmpResult%10) + tmpCarry;    //sum[(i+1)+(j+1)-1 -forwardIndex]
            tmpCarry = (sum.number[i+j+1 -forwardIndex]/10) + (tmpResult/10);
            sum.number[i+j+1 -forwardIndex] = sum.number[i+j+1 -forwardIndex]%10;          
        }
        sum.number[i -forwardIndex] += tmpCarry;
        tmpCarry = 0;
    }
   
    //如果相乘後的數字的頭是0的話,平移
    if(sum.number[0] == 0){
        for(int i=0; i            sum.number[i] = sum.number[i+1];
        sum.length--;
    }
    //print(sum,LEN1+LEN2);
    return sum;
}

void print(NumArray num)
{   
    for(int i=0;i   // cout << endl;
}

void write_into_File(int *arr,const int LEN)
{
    string str3;
    cout << "請輸入輸出檔的檔名:";
    cin >> str3;
    ofstream output(str3.c_str());
    for(int i=0;i    output << endl;
    cout << "已輸出至檔案中.........." << endl;
}

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

*