Re: [閒聊] 程設作業

[game0416 (鳳狼)]

兩個禮拜前的printf大概推這個對岸連結
http://blog.pfan.cn/wentao/10152.html
其他說明就略，有問題再說


然後我不熟悉能怎樣用的繼承相關也都略
不然寫起來就是長課本那樣而已(死)
記得繼承等級我覺得就差不多啦...啦



所以這篇著重在這次作業的大數(BigInteger)這樣。


--


我不懂為什麼要從乘法開始講大數...
雖然說是大數乘小數，不要特意寫成串列不會太難
特意寫成串列的話...腦袋要夠活，然後我沒這個愛對於一千位的大數寫串列
等有需要的時候再看看....不然就不要用C或換編譯器啦(被毆)



因為提到大數，所以我想先從簡單的加法開始慢慢談
然後這段對於大數的說明，全都建立在"大數對大數"為討論前提
講是講大數，不過拿出來當例子的其實只是 66 跟 125 這樣的三位數字簡單說明
: 作業以外的部份不詳加code....不然寫完都不知道幾點了(遠目)


從數學基本的加法來當作開始

首先，對於大數的概念很單純，就是去模擬我們手算直式的行為而已
不管加減乘除取餘數開根號什麼的都是這樣，保持這個觀念去解大數會好很多


--

以66+125來說，我們會這樣做...


                      6 6               1.先把個位對個位，數字排好
                 +  1 2 5
               ----------
                      1 1               2.從個位對個位開始加總
                      6
                    1 2
               ----------
                      9 1               3.將十位加總、計入從個位進位來的數
                    1
               ----------
                    1 9 1               4.將十位加總、計入從十位進位來的數


用這樣的處理順序來得到66+125=191，將這樣的過程轉換成陣列/串列排列
用每個陣列/串列上的一個元素表示一位來運作，然後藉由語言讓電腦實作
就是大數的概念，剩下大概都只是優化的部份而已

--


減法一樣...這次改成125-66

                    1 2 5               1.一樣先把個位對個位，數字排好
                 -    6 6
               ----------
                     -1 9               2.從個位對個位開始相減
                 +  1 2                   然後將結果與被減數相加
               ----------
                    1 1 9
                 -    6                 3.將十位相減
               ----------                 然後將結果與被減數相加
                   -1 5
                 +  1 0 9
               ----------
                      5 9

像這樣逐步去做完減法，即大數減法...判斷正負號就看第一位就好


--

乘法亦同...只是大數對大數需要三條陣列來做處理會比較好
這次求125*66

                    1 2 5               1.一樣先把個位對個位，數字排好
                 *    6 6
               ----------
                    7 5 0               2.乘數每位先分別對被乘數每位相積
                  7 5 0
               ----------
                  8 2 5 0               3.將其各位數排好相加

如此得 125*66=8250
這裡要注意是...第二步最好另外設一條陣列與被乘數、程數分別出來
避免蓋掉其他位數，讓結果數值有問題
前面加減法比較不用管這個這樣


針對除法則先略..沒寫好過(攤)
內容是用"連減"去處理數值，然後紀錄減了幾次就可以了QQ
: 乘法也能用連加啦...建構式數學有它的好
--


上面大概說明了一下，再來回到這次的作業..

因為是大數乘小數、1000位以內，在某些地方可以比大數乘大數偷懶
: 遇到int範圍邊緣的階層會出問題...不過因為題目不會發生就跳一點無所謂
舉例一樣是125*66，這裡125是大數，66是用int宣告的數值
先想像有個int bignum[4]={0,1,2,5};
: 這部分只是我喜歡這樣...彥廷寫成{5,2,1,0}對陣列處理會比較方便
: 我只是覺得125比較符合我腦袋模擬的感覺，小作業不要求執行時間(逃跑

這裡我們先把剛才直式改寫成這樣的感覺
                    1 2 5
                 *     66             1.同樣把個位對個位...
               ----------               可是把小數整體視為個位
                      330
                    132               2.逐個相乘
                 + 66
               ----------


--

此時，
bignum[3] (我們用來裝個位數的那一個元素) 裡面裝330
顯然與我們一開始打算只裝一位不合
所以就讓它做進位處理
bignum[2] = bignum[2] + bignum[3]/10;
: int / int，餘數會變小數而被主動刪去...至少對g++是這樣啦
: 要避免不同編譯器有問題的話可能注意一下比較好
然後讓
bignum[3] = bignum[3]%10;
用以留下個位數字，這樣就算對個位的進位結束
再往上做十位...
現在bignum[2] == 165
同樣對其進位
bignum[1] = bignum[1] + bignum[2]/10
bignum[2] = bignum[2]%10;
類推
bignum[0] = bignum[0] + bignum[1]/10
bignum[1] = bignum[1]%10;


--



最後，再依項輸出

for (int i=0;i<4;i++)
  cout <<bignum[i];
就會得到 8250 這樣的輸出


回到題目本身要求n!

就直接讓人輸入n，以for迴圈來跑1到n的乘數
預設的被乘數個位設為1，配合上面這個思考作法就能直接做出來這個作業了




下頁起一樣附個沒優化的code，亂寫一氣的就不要在意了
寫法上我腦袋直觀把個位排最後有浪費執行時間跟行數就是了
執行上有問題一樣還是請通知一下Orz
--
#include<iostream>
#define max 1000
using namespace std;
int main()
{
  int input;
  while (cin >>input){
    int arr[max];
    for (int i=0;i<1000;i++)
      arr[i]=0;

    arr[max-1]=1;
    if (input>1){
      for (int i=2;i<=input;i++){
        for (int j=0;j<max;j++)
          arr[j]*=i;
        for (int j=max-1;j>0;j--){
          arr[j-1]+=arr[j]/10;
          arr[j]%=10;
        }
      }
    }

    int start=0;
    for (int i=0;i<max;i++)
      if (arr[i]!=0){
        start=i;
        break;
      }
    for (start;start<max;start++)
      cout <<arr[start];
    cout <<endl;
  }
}

--
  所恐懼的，不是沒有知識的大眾　          所憎恨的，不是深沉幽暗的人心
      而是自以為是的思考之聲                    而是自恃甚高的執法者

  所毀滅的，不是溫馨和諧的世界       這是我最後的期許，沒有憤怒、沒有悔恨
      而是自欺欺人的夢境                      只剩下，渾沌的死亡呼吸
                            　　　　　　　　　　　　　　 節自　新月神話－弒王者

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.114.65.42
推 gcobc12632:鳳狼必推
推 Arashinoon:未看先推
推 garfield112:先END再推
→ j2612280:"不要用C或換編譯器啦"......
→ game0416:我錯了嗎QQ
→ j2612280:沒啦..只是突然無言而已..
→ game0416:QQ
→ game0416:換語言有內建大數，換編譯器把陣列開更大嘛...
※ 編輯: game0416        來自: 220.130.128.171      (05/14 17:41)