欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)大整數(shù)乘法

 更新時(shí)間:2019年09月18日 08:32:44   作者:heyAmos  
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)大整數(shù)乘法,使用笛卡爾相乘,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

算法競賽入門經(jīng)典 這本書并沒有對大數(shù)乘法實(shí)現(xiàn),所以自己補(bǔ)充了一下,乘法的實(shí)現(xiàn)很簡單,就是再其數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上把每寬為8位的十進(jìn)制數(shù)看成多項(xiàng)式的系數(shù),vector的下標(biāo)看成多項(xiàng)式的指數(shù),然后再對應(yīng)相乘相加就可以了,注意系數(shù)超過8位 將超八位的補(bǔ)分進(jìn)位。

我這里是笛卡爾相乘。一般來說是夠用的。

但其實(shí)多項(xiàng)式乘法算法還有很多更高效的。

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
struct BigInteger{
  static const int BASE = 100000000;
  static const int WIDTH = 8;
  vector<int> s;
 
  BigInteger operator = (const string& str){
    s.clear();
    int x, len=(str.length()-1)/WIDTH+1;
    for(int i=0;i<len;i++){
      int r=str.length()-i*WIDTH;
      int l=max(0,r-WIDTH);
      sscanf(str.substr(l,r-l).c_str(),"%d",&x);
      s.push_back(x);
    }
    return *this;
  }
 
  BigInteger operator * (const BigInteger& b){
    BigInteger c;
    int lena=this->s.size(),lenb=b.s.size(),lenc=lena+lenb-1;
    LL *buf =new LL[lenc+1];
    for(int i=0;i<lenc+1;i++)buf[i]=0;
    for(int i=0;i<lena;i++)
      for(int j=0;j<lenb;j++){
        buf[i+j]+=(this->s[i])*((LL)b.s[j]);
        buf[i+j+1]+=buf[i+j]/BASE;
        buf[i+j]=buf[i+j]%BASE;
      }
    for(int i=0;i<lenc;i++)c.s.push_back(buf[i]);
    if(buf[lenc])c.s.push_back(buf[lenc]);
    return c;
  }
 
  BigInteger operator * (const int& x){
    char c[128];
    sprintf(c,"%d",x);
    string str(c);
    BigInteger res;
    res=str;
    return *this*res;
  }
};
 
ostream& operator<<(ostream& out,const BigInteger& b){
  int len=b.s.size();
  out<<b.s[len-1];
  for(int i=len-2;i>=0;i--){
    int buf=b.s[i],h=8;
    while(buf>0){buf/=10;h--;}
    for(int j=0;j<h;j++)out<<0;
    if(b.s[i])out<<b.s[i];
  }
  return out;
}
 
int main()
{
  int n;BigInteger b;
  b="1000000000000";
  cout<< b<<endl;
  cout<< (b*b)*4*b*b <<endl;
}

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • C語言結(jié)構(gòu)體中內(nèi)存對齊的問題理解

    C語言結(jié)構(gòu)體中內(nèi)存對齊的問題理解

    內(nèi)存對齊”應(yīng)該是編譯器的“管轄范圍”。編譯器為程序中的每個(gè)“數(shù)據(jù)單元”安排在適當(dāng)?shù)奈恢蒙?。但是C語言的一個(gè)特點(diǎn)就是太靈活,太強(qiáng)大,它允許你干預(yù)“內(nèi)存對齊”。如果你想了解更加底層的秘密,“內(nèi)存對齊”對你就不應(yīng)該再模糊了
    2022-02-02
  • C語言字符串的模式匹配之BF與KMP

    C語言字符串的模式匹配之BF與KMP

    這篇文章記錄一下串里面的模式匹配,模式匹配,顧名思義就是給定一個(gè)被匹配的字符串,然后用一個(gè)字符串模式(模型)去匹配上面說的字符串,看后者是否在前者里面出現(xiàn)。常用的有2種算法可以實(shí)現(xiàn),下面我們來具體探討下
    2021-09-09
  • C++采用TLS線程局部存儲的用法實(shí)例

    C++采用TLS線程局部存儲的用法實(shí)例

    這篇文章主要介紹了C++采用TLS線程局部存儲的用法實(shí)例,詳細(xì)講述了TLS索引及線程的操作,非常具有實(shí)用價(jià)值,需要的朋友可以參考下
    2014-10-10
  • C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像)

    C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C語言棧與隊(duì)列相互實(shí)現(xiàn)詳解

    C語言棧與隊(duì)列相互實(shí)現(xiàn)詳解

    棧和隊(duì)列,嚴(yán)格意義上來說,也屬于線性表,因?yàn)樗鼈円捕加糜诖鎯壿嬯P(guān)系為 "一對一" 的數(shù)據(jù),但由于它們比較特殊,本章講解分別用隊(duì)列實(shí)現(xiàn)棧與用棧實(shí)現(xiàn)隊(duì)列
    2022-04-04
  • C++通過boost.date_time進(jìn)行時(shí)間運(yùn)算

    C++通過boost.date_time進(jìn)行時(shí)間運(yùn)算

    這篇文章介紹了C++通過boost.date_time進(jìn)行時(shí)間運(yùn)算的方法,文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2022-06-06
  • NSString與C字符串之間的相互轉(zhuǎn)換

    NSString與C字符串之間的相互轉(zhuǎn)換

    本文將詳細(xì)介紹NSString與C字符串之間的相互轉(zhuǎn)換,需要的朋友可以參考下
    2012-11-11
  • C++雙向鏈表的增刪查改操作方法講解

    C++雙向鏈表的增刪查改操作方法講解

    相較單鏈表,雙向鏈表除了data與next域,還多了一個(gè)pre域用于表示每個(gè)節(jié)點(diǎn)的前一個(gè)元素。這樣做給雙向鏈表帶來了很多優(yōu)勢。本文主要介紹了雙向鏈表的實(shí)現(xiàn),需要的可以參考一下
    2023-03-03
  • C語言深入分析遞歸函數(shù)的實(shí)現(xiàn)

    C語言深入分析遞歸函數(shù)的實(shí)現(xiàn)

    遞歸(recursive)函數(shù)是“自己調(diào)用自己”的函數(shù),無論是采用直接或間接調(diào)用方式。間接遞歸意味著函數(shù)調(diào)用另一個(gè)函數(shù)(然后可能又調(diào)用第三個(gè)函數(shù)等),最后又調(diào)用第一個(gè)函數(shù)。因?yàn)楹瘮?shù)不可以一直不停地調(diào)用自己,所以遞歸函數(shù)一定具備結(jié)束條件
    2022-04-04
  • c++ 調(diào)用python傳輸圖片實(shí)例

    c++ 調(diào)用python傳輸圖片實(shí)例

    今天小編就為大家分享一篇c++ 調(diào)用python傳輸圖片實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12

最新評論